[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.

[gl] Os sistemas de bases de datos espazo-temporais naceron co obxectivo de manipular grandes volumes de obxectos espaciais cuxa posición e/ou forma cambia co tempo e onde ditos cambios son relevantes no dominio da aplicación. Algúns exemplos son os sistemas de control de tráfico aéreo, os sistemas de control de flotas de vehículos, de aves migratorias e doutros animais. Existe moita investigación no campo das bases de datos espazo-temporais en relación cos métodos de acceso e indexación eficientes para memoria secundaria, pero moi pouca para memoria principal. No ámbito dos sistemas de recuperación da información xurdiron novas estratexias para propor estruturas de datos e algoritmos eficientes no uso de memoria e que non perxudican os tempos de acceso, as denominadas estruturas de datos compactas. Estas estruturas de datos son moi eficientes no uso de memoria, obtendo boas razóns de compresión nalgúns casos, á vez que permiten un acceso eficiente aos datos contidos sen necesidade de descomprimir a estrutura. No campo da indexación espacial existen diversas estruturas de datos que utilizan técnicas de compactación. A pesar diso, non existen traballos previos de estruturas de datos compactas no campo das bases de datos espazo-temporais. Debido a todo o exposto, nesta tese abordouse a temática das estruturas de datos compactas no contexto das bases de datos espazo-temporais e, en particular, a indexación de obxectos móbiles, representados como un punto no espazo. Como resultado, definiuse un auto-índice compacto que permite responder consultas de tipo time-slice, time-interval, traxectoria dun obxecto e os 𝑘 veciños más próximos. A avaliación experimental amosa que é posible minimizar o espazo empregado á vez que se poden responder as consultas descritas de xeito eficiente.