Representación eficiente de secuencias espaciales y espacio-temporales.
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
El volúmen actual de información espacial y espacio-temporal que se genera se ha visto incrementado por la masividad de dispositivos que permiten registros constantes, ya sea para determinar la ubicación de determinados objetos en movimiento, o para obtener mediciones sobre un espacio o punto de interés determinado. Estos pequeños dispositivos actualmente se encargan de recopilar la información, que luego debe ser pre-procesada, para limpiar sus datos, corregirla en ciertos casos, para finalmente almacenar y responder consultas sobre la información. Este trabajo de tesis se orienta en desarrollar propuestas novedosas para el registro de secuencias espaciales, y secuencias espacio-temporales que permitan almacenar de manera eficiente los datos, y responder consultas en tiempo competitivo.
Este compendio contiene el desarrollo de dos líneas de trabajo enfocadas en datos espacio-temporales. La primera propuesta es una estructura de datos compacta para la representación eficiente de trayectorias sobre una representación en red como caminos, con un fuerte enfoque en responder consultas de relaciones topológicas en los datos contenidos, permitiendo responder todas aquellas secuencias que cumplen una determinada relación. Esta estructura resulta en una representación eficiente en términos de espacio, y por sobre todo eficiente en los tiempos de respuesta para la mayoría de las operaciones implementadas. La segunda investigación corresponde a dos estructuras de datos compactas para la representación de series de tiempo relacionadas a una ubicación espacial. La formulación de la estructura estuvo guiada por índices de autocorrelación de los conjuntos de datos, estableciendo dos situaciones diferentes según las características de los datos. Esta representación resulta especialmente eficiente en grillas de datos espacio-temporales densas, y se puede identificar una diferencia entre los valores de autocorrelación entre los conjuntos utilizados que permiten decidir el uso de la estructura, o de su variante.
The current volume of spatial and spatio-temporal information being generated has increased significantly due to the widespread availability of devices that enable continuous recording—whether for determining the location of moving objects or for collecting measurements over a space or specific point of interest. These small devices are now responsible for gathering the data, which must then be preprocessed to clean and, in some cases, correct the information, before it can be stored and queried efficiently. This thesis focuses on developing novel proposals for the representation of spatial sequences and spatio-temporal sequences that enable efficient data storage and competitive query performance. This compendium presents the development of two research directions centered on spatio-temporal data. The first contribution is a compact data structure for the efficient representation of trajectories over a network-based model, such as roads, with a strong emphasis on answering topological relation queries. It supports retrieving all sequences that satisfy a given relation. This structure achieves an efficient space representation and, most notably, fast query times for most of the implemented operations. The second research contribution involves two compact data structures for the representation of time series associated with spatial locations. The formulation of these structures was guided by autocorrelation indices derived from the datasets, leading to two different approaches depending on the data characteristics. This representation proves particularly effective for dense spatio-temporal grids, and a clear distinction in autocorrelation values among the datasets enables a well-founded decision between the proposed structure and its variant.
The current volume of spatial and spatio-temporal information being generated has increased significantly due to the widespread availability of devices that enable continuous recording—whether for determining the location of moving objects or for collecting measurements over a space or specific point of interest. These small devices are now responsible for gathering the data, which must then be preprocessed to clean and, in some cases, correct the information, before it can be stored and queried efficiently. This thesis focuses on developing novel proposals for the representation of spatial sequences and spatio-temporal sequences that enable efficient data storage and competitive query performance. This compendium presents the development of two research directions centered on spatio-temporal data. The first contribution is a compact data structure for the efficient representation of trajectories over a network-based model, such as roads, with a strong emphasis on answering topological relation queries. It supports retrieving all sequences that satisfy a given relation. This structure achieves an efficient space representation and, most notably, fast query times for most of the implemented operations. The second research contribution involves two compact data structures for the representation of time series associated with spatial locations. The formulation of these structures was guided by autocorrelation indices derived from the datasets, leading to two different approaches depending on the data characteristics. This representation proves particularly effective for dense spatio-temporal grids, and a clear distinction in autocorrelation values among the datasets enables a well-founded decision between the proposed structure and its variant.
Description
Tesis presentada para optar al grado de Doctor/a en Ciencias de la Computación.
Keywords
Análisis de series de tiempo, Sistemas de información geográfica, Estructuras de datos (ciencia de la computación)