[en] Spatio-temporal databases were designed to manage very large datasets of spatial objects, whose location and/or shape evolves with time, and whose changes are relevant to the domain of application. Air traffic control systems, fleet management, migratory birds and other animals are just some examples of this type of systems. Much research on spatio-temporal databases has been devoted to spatial access methods and efficient indexes for secondary memory. However, just a few works tackle the efficient access in main memory. In the field of Information Retrieval, some strategies have arisen to develop new data structures and efficient algorithms in terms of space usage that also keep efficient access times. These have been called Compact Data Structures. These data structures are very space-efficient (getting good compression ratios), while supporting access queries to the data efficiently without decompressing them. Similarly, several data structures that use compression techniques have been developed in the context of spatial access methods. However, to the best of our knowledge, there do not exist previous works on the use of compact data structures for spatio-temporal databases. Therefore, this thesis proposes the use of compact data structures in the context of spatio-temporal databases and, in particular, to index moving objects (represented by spatial coordinates). As a result, a compact self-index is proposed to solve timeslice, time-interval, trajectory and 𝑘-nearest neighbor queries. An experimental evaluation shows that our proposal is efficient to support such queries, while using few space.

[es] Los sistemas de bases de datos espacio-temporales nacen con el objetivo de manipular grandes volúmenes de objetos espaciales cuya posición y/o forma cambia en el tiempo y donde dichos cambios son relevantes en el dominio de aplicación. Algunos ejemplos son los sistemas de control de tráfico aéreo, los sistemas de control de flotas de vehículos, de aves migratorias y de otros animales. Se ha investigado mucho en el campo de las bases de datos espacio-temporales en relación a los métodos de acceso e indexación eficientes para memoria secundaria, pero poco para memoria principal. En el ámbito de los sistemas de recuperación de información han surgido nuevas estrategias para desarrollar estructuras de datos y algoritmos eficientes en el uso de la memoria y que no penalizan los tiempos de acceso, las denominadas Estructuras de Datos Compactas. Estas estructuras de datos son muy eficientes en el uso de la memoria, incluso logrando altos ratios de compresión en algunos casos, a la vez que permiten un acceso eficiente a los datos contenidos sin la necesidad de descomprimir la estructura. En el campo de la indexación espacial se han desarrollado diversas estructuras de datos que utilizan técnicas de compactación. Sin embargo, no existen trabajos previos de estructuras de datos compactas en el campo de las bases de datos espaciotemporales. Por lo anterior en este tesis se abordó la temática de las estructuras de datos compactas en el contexto de las bases de datos espacio temporales y en particular, la indexación de objetos móviles, representados como un punto espacial. Como resultado, se ha definido un auto-índice compacto que permite responder a consultas de time slice, time interval, trayectoria de un objeto y los 𝑘 vecinos más cercanos. En los experimentos nuestra propuesta demuestra minimizar el espacio utilizado a la vez que es eficiente al responder las consultas dadas en algunos escenarios.