Realização Eficiente de Consultas em Bancos de Dados Espaço Temporais
Autores
|
2015 |
312,10,443
|
|
|
2016 |
312,10,443
|
|
|
2017 |
312,10,443
|
Informações:
Publicações do PESC
É um fato conhecido que as novas aplicações de Sistemas de Informações Geográficas (SIG) necessitam armazenar informações temporais. Entretanto, índice espacial mais utilizado, a R-Tree e suas variantes, não preserva a evolução dos objetos espaciais. Alguns métodos de acesso foram propostos na literatura e permitem a recuperação de estados presentes e passados dos dados. Nesta dissertação iremos avaliar o desempenho dos métodos de acesso mais populares para executar consultas espaçotemporais. Por consultas entende-se consultas de seleção bem como consultas de junção. Consultas espaçotemporais podem ser agrupadas em duas classes: consultas envolvendo instantes de tempo e consultas envolvendo intervalos de tempo. Nós propomos uma nova estrutura de indexação de dados espaçotemporais chamada TR-Tree (do inglês Temporal R-Tree) que combina características temporais da Multiversion B-Tree com as características espaciais da R*-Tree. Nós projetamos e implementamos os algoritmos de inserção, remoção, consultas de seleção e consultas de junção. Esta dissertação é, até onde sabemos, um estudo pioneiro em junções espaçotemporais. Foi feito um estudo comparativo com diversos conjuntos de dados para mostrar a escalabilidade dos algoritmos da TR-Tree. Nossos experimentos mostraram que seu desempenho e utilização de espaço são muito bons até mesmo nos casos extremos, mostrando que a TR-Tree é atualmente a melhor escolha para a indexação de dados espaçotemporais.
It's a well-known fact that new GIS applications need to keep track of temporal information. However, the most widely used spatial index, the R-Tree and its variants, do not preserve the evolution of bounding boxes. Some new indexing structures were proposed in the literature that allows the retrieving of present and past states of data. In this thesis we evaluate the most popular indexes structure to perform spatiotemporal queries. For queries we mean selection queries and join queries. Spatiotemporal queries can be grouped in two classes: queries involving time instants and queries involving time intervals. We propose a new index structure termed the Temporal R-Tree, which combines several features of Becker et al.
Multi-Version B-Tree with the spatial indexing characteristics of the R*-Tree. We have designed and implemented algorithms for insertion, deletion, selection queries and join queries. This thesis is, at the best of our knowledge, the first study on spatiotemporal join queries. A number of comparative queries on several data sets were performed to show lhe scalability of the Temporal R-Tree. Our experiments show that its performance and space utilization are very good even on worst cases, showing that the Temporal R-Tree is by now the best choice for indexing spatiotemporal data.