Algoritmos de indexación y carga masiva de datos geoespaciales

Resumo

La relevancia de los datos provenientes de los satélites orbitales de observación terrestre (geodatos), junto al requerimiento de recuperaciones rápidas para las aplicaciones de consulta voraces como son las de análisis, búsqueda de patrones y minado de datos, o las de los sistemas de control de emergencias, desastres y de alerta temprana, requieren de un almacenamiento indexado que acelere los accesos a estos datos. Se propone su almacenamiento mediante el uso de índices de particionamiento espacial de los datos. Específicamente se proponen los índices Q-tree y Q-full-tree, pertenecientes a la familia de índices basados en el árbol k-d, donde Q-full-tree es una aportación novedosa. La consideración que sustenta la elección de éstos índices es que el formato matricial y denso de los geodatos, además de su ubicación bien delimitada, permiten trocearlos en regiones estancas sin solapar. Los índices de basados en el árbol k-d, de particionamiento espacial, no conllevan solapamiento de regiones a la hora de almacenar los datos, disminuyéndose, por lo general, los caminos de búsqueda, y evitándose acceder a más páginas de datos de las necesarias. Por el contrario, las estructuras que solapan regiones pueden producir el acceso a más páginas de datos de las necesarias (tantas como solapamientos existan para una determinada región de consulta), siendo muchas de ellas infructuosas por no contener los datos buscados. La tesis también se centra en los algoritmos de carga masiva que de forma eficiente alimenten a estos índices de los datos geoespaciales, no sólo para mejorar la velocidad de carga de los datos en el índice, sino también para reducir el espacio de utilización y mejorar los tiempos de respuesta en las consultas en este tipo de indexación. En la tesis se propone la adaptación del índice multidimensional Q-tree en un índice espacio-temporal, denominado Q-full-tree, ideado principalmente para la carga masiva de estos geodatos. Para ello, se toma el tiempo no como una dimensión más, sino de manera diferenciada a las demás dimensiones, de manera que permitan realizar consultas espacio-temporales por intervalos de tiempo y por rodaja de tiempo con mayor rendimiento. Los datos seleccionados para ser cargados en el índice espacial Q-tree son los geodatos de elevación terrestre obtenidos por la misión espacial SRTM de la NASA, que en el año 2000 produjo el mayor conjunto de datos topográficos de calidad de un modelo digital de elevación (MDE) terrestre global. Se presenta un método para indexar por completo todos los datos disponibles, produciéndose dos hechos remarcables: por un lado, teniendo en cuenta el gran abasto de geodatos involucrados, la construcción del índice es particularmente competitiva si la comparamos con los métodos de carga existentes, debido al diseño extremadamente eficiente del algoritmo de carga masiva; por otro lado, el índice espacial resultante queda equilibrado en todas sus alturas y presenta un grado de ocupación alto (superior al 96%), lo que conlleva una mayor eficiencia en la respuestas a consultas. Un hecho también importante es que el algoritmo de carga masiva es aplicable a virtualmente cualquier estructura de particionamiento espacial en regiones independientes con solo adaptar mínimamente el método de inserción para que permita, además de la normal inserción de tuplas, la carga de páginas de datos completas. Los datos seleccionados para ser cargados en el índice espacio-temporal Q-full-tree son los geodatos sobre vientos y precipitaciones a nivel global de toda la superficie oceánica provenientes del satélite orbital QuikSCAT. El método de carga masiva se adapta a la espacio-temporalidad de la estructura del índice, siguiendo las mismas bases de la carga masiva diseñada para los datos espaciales cargados en el índice Q-tree. En definitiva, la idea fundamental que subyace en la realización de esta tesis es la de formar una base de geodatos global indexada. El almacenamiento de los geodatos se realiza con su modelado vector con el fin de que posteriores alimentaciones de otros datos provenientes de otras fuentes, mediante cargas masivas e inserciones ordinarias, queden completamente integrados en estos mismos índices. También para que la integración de los datos (geodatos o no) sea también posible con otras bases de datos vectoriales; es decir, para permitir la convivencia sencilla entre varias bases de datos de la misma naturaleza vectorial. El almacenamiento de los geodatos modelados vectorialmente evita las posteriores conversiones raster (la forma generalizada en la que los geodatos suelen almacenarse) a vector, acelerando sobremanera los tiempos de respuesta de las aplicaciones voraces que someten al índice a continuas operaciones de consulta, como son los sistemas de alerta, emergencia, y de control, o las aplicaciones de análisis y de minado de datos.