Un índice espacio temporal para puntos móviles basado en estructuras de datos compactas
![Thumbnail](/dspace/bitstream/handle/2183/19303/RomeroVasquez_MigueEsteban_TD_2017.pdf.jpg?sequence=4&isAllowed=y)
Use this link to cite
http://hdl.handle.net/2183/19303Collections
- Teses de doutoramento [2128]
Metadata
Show full item recordTitle
Un índice espacio temporal para puntos móviles basado en estructuras de datos compactasAuthor(s)
Directors
Seco Naveiras, DiegoRodríguez Luaces, Miguel
Date
2017Abstract
[Abstract]
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. [Resumen]
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. [Resumo]
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.
Keywords
Bases de datos espacio-temporales
Sistemas de información geográfica
Estructuras de datos (Informática)
Sistemas de información geográfica
Estructuras de datos (Informática)
Description
Programa Oficial de Doutoramento en Computación . 5009V01
Rights
Os titulares dos dereitos de propiedade intelectual autorizan a visualización do contido desta tese a través de Internet, así como a súa reproducción, gravación en soporte informático ou impresión para o seu uso privado e/ou con fins de estudo e de investigación. En nengún caso se permite o uso lucrativo deste documento. Estos dereitos afectan tanto ó resumo da tese como o seu contido Los titulares de los derechos de propiedad intelectual autorizan la visualización del contenido de esta tesis a través de Internet, así como su repoducción, grabación en soporte informático o impresión para su uso privado o con fines de investigación. En ningún caso se permite el uso lucrativo de este documento. Estos derechos afectan tanto al resumen de la tesis como a su contenido