New data structures and algorithms for the efficient management of large spatial datasets
B Roca, Guillermo de · Dialnet (Universidad de la Rioja) · 2014
En esta tesis estudiamos la representacion eficiente de matrices multidimensionales, presentando nuevas estructuras de datos compactas para almacenar y procesar grids en distintos ambitos de aplicacion. Proponemos varias estructuras de datos estaticas y dinamicas para la representacion de matrices binarias o de enteros y estudiamos aplicaciones a la representacion de datos raster en Sistemas de Informacion Geografica, bases de datos RDF, etc. En primer lugar proponemos una coleccion de estructuras de datos estaticas para la representacion de matrices binarias y de enteros: 1) una nueva representacion de matrices binarias con grandes grupos de valores uniformes, con aplicaciones a la representacion de datos raster binarios; 2) una nueva estructura de datos para representar matrices multidimensionales; 3) una nueva estructura de datos para representar matrices de enteros con soporte para consultas top-k de rango. Tambien proponemos una nueva representacion dinamica de matrices binarias, una nueva estructura de datos que proporciona las mismas funcionalidades que nuestras propuestas estaticas pero tambien soporta cambios en la matriz. Nuestras estructuras de datos pueden utilizarse en distintos dominios. Proponemos variantes especificas y combinaciones de nuestras propuestas para representar grafos temporales, bases de datos RDF, datos raster binarios o generales y datos raster temporales. Tambien proponemos un nuevo algoritmo para consultar conjuntamente un conjuto de datos raster (almacenado usando nuestras propuestas) y un conjunto de datos vectorial almacenado en una estructura de datos clasica, mostrando que nuestra propuesta puede ser mas rapida y usar menos espacio que otras alternativas. Nuestras representaciones proporcionan interesantes trade-offs y son competitivas en espacio y tiempos de consulta con representaciones habituales en los diferentes dominios.