D*R-Tree: un método eficiente para responder consultas espacio-temporales

Abstract

Existen aplicaciones que requieren manejar objetos espacio-temporales, es decir, objetos cuya posición espacial o forma cambia en distintos instantes de tiempo. Para administrar la información referida a tales cambios se requieren de métodos de acceso espacio-temporal, que permitan además procesar en forma eficiente consultas de tipo espacio-temporal. En general, TimeSlice, Intervalo, Eventos y k son los tipos de consultas para las que podemos encontrar una variedad de métodos, los cuales intentan optimizar el desempeño de las consultas, pero por separado, apuntando a un subconjunto de las antes mencionadas. En este artículo presentamos un método de acceso espacio-temporal, llamado D*R-Tree, que resuelve eficientemente los cuatro tipos de consultas mencionados anteriormente, y mostramos su buen desempeño a través de las evaluaciones experimentales realizadas.

Spatio-temporal databases deal with objects that change their location and/or shape over time. Numerous researches have been done in developing spatio-temporal access methods as auxiliary structures to support spatiotemporal queries. The main interest of most applications is to efficiently store and query the positions of these objects. We can find a related rich literature on the subject about the methods for supporting a subset of the following TimeSlice, Events, Interval and Trajectory queries. In this paper we propose a new index structure, the D*R-Tree to efficiently store and retrieve spatio-temporal objects. The main objective of this work is to show a suitable method for supporting all mentioned queries types, with an optimal performance. We propose the index in terms of the basic algorithms for querying. We test our proposal in an extense experimental evaluation with generated data sets. In our tests, the D*R-Tree showed good scalability when increasing the number of objects and time units in the data sets, as well as in query processing, compared with a similar structure.