Efficient query processing in distributed spatial data management systems

Resumen

La Computación Espacial (Spatial Computing) engloba ideas, soluciones, herramientas, tecnologías y sistemas que transforman nuestras vidas y la sociedad al crear una nueva comprensión de los espacios, ubicaciones, lugares y propiedades. Desde que se acuñó el término Big Data por primera vez en 2005, éste ha desencadenado una revolución mundial en la investigación científica y en los negocios. Big Spatial Data (BSD), el Big Data asociado con información espacial, es ahora uno de los campos de investigación más activos en computación espacial, motivado principalmente por el rápido desarrollo de tecnologías inteligentes, de sensores y móviles. El uso actual del término Big Spatial Data tiende a referirse al proceso de capturar, almacenar, gestionar, analizar y visualizar grandes cantidades de datos espaciales, sin utilizar herramientas y sistemas tradicionales. El reciente desarrollo de sistemas que manipulen grandes volúmenes de datos espaciales ha motivado la aparición de nuevas tecnologías para el procesamiento distribuido de datos espaciales a gran escala en clústeres shared-nothing (clústeres en los que cada nodo es independiente y autosuficiente) de computadoras, surgiendo así los sistemas de gestión de datos espaciales distribuidos (Distributed Spatial Data Management Systems (DSDMSs)). Los sistemas de procesamiento distribuido basados en clústeres se pueden clasificar como sistemas basados en Hadoop o en Spark. Según esta clasificación, dos de los DSDMS más importantes son SpatialHadoop (DSDMS basado en disco) y LocationSpark (DSDMS basado en memoria). Estos sistemas distribuidos proporcionan varias características, como el particionado de datos espaciales, métodos de indexación y el procesamiento de consultas espaciales. Un aspecto importante de estos DSDMS es que adoptan una arquitectura en capas para la computación distribuida e inyectan la capacidad de manipular datos espaciales en cada una de ellas. Por ejemplo, las capas en SpatialHadoop son Language (Lenguaje), Storage (Almacenamiento), MapReduce y Operations (Operaciones). Dado que SpatialHadoop es una extensión integral del ecosistema Hadoop, se trata de un marco de computación en la nube escalable y eficiente que permite el procesamiento distribuido de conjuntos de datos espaciales a gran escala utilizando el modelo de programación MapReduce. En esta tesis, estudiamos y enriquecemos SpatialHadoop mediante la implementación de algoritmos MapReduce para consultas basadas en distancia en la capa Operations: εDistance Range Query (εDRQ), kNearest Neighbor Query (kNNQ), kClosest Pairs Query (kCPQ), kNearest Neighbor Join Query (kNNJQ), εDistance Join Query (εDJQ), εDistance Range Join Query (εDRJQ), Reverse kNearest Neighbor Query (RkNNQ), etc. Además, mejoramos la capa Storage con una nueva técnica de particionado espacial (particionado basado en diagramas de Voronoi), y una nueva estructura de indexación local (Quadtree) para optimizar el procesamiento de consultas espaciales distribuidas en clústeres shared-nothing. Este estudio, y el conocimiento adquirido sobre SpatialHadoop, nos ayuda a identificar nuevas oportunidades para, también, enriquecer LocationSpark (un sistema de procesamiento de datos espaciales construido sobre el ecosistema Spark), con consultas de join basados en distancias (DJQ) mediante el diseño e implementación de nuevos algoritmos distribuidos (kCPQ, εDJQ y εDRJQ), extensiones y mejoras sobre ellos. Además, proponemos otras mejoras y optimizaciones para el procesamiento de consultas espaciales distribuidas que aprovechan tanto los datos como las propiedades algorítmicas. Por último, comparamos estos dos DSDMS evaluando el rendimiento de varios algoritmos DJQ distribuidos según diferentes configuraciones con grandes conjuntos de datos espaciales reales procedentes de OpenStreetMap. Para desarrollar esta tesis, se revisan los DSDMS (prototipos de investigación) más relevantes, el estado del arte de las técnicas de particionado espacial en DSDMS, y las DBQ más representativas y comunes. Luego, se estudian la estructura y operaciones de los métodos de particionado de datos espaciales y estructuras de indexación en SpatialHadoop, proponiendo una técnica de particionado espacial basada en diagramas de Voronoi y la incorporación del Quadtree como índice local en dicho DSDMS. Dirigidos por un estudio exhaustivo sobre el procesamiento de consultas espaciales en SpatialHadoop, identificamos e implementamos nuevas consultas espaciales (εDRQ, kCPQ, εDJQ, εDRJQ, kNNJQ, R kNNQ, etc.) con diferentes extensiones (por ejemplo, para tipos de datos espaciales que no son puntos) y mejoras (por ejemplo, métodos de reparticionamiento, la técnica less data, nuevas reglas de poda, etc.) en este DSDMS. A continuación, se estudia el esquema general de procesamiento de consultas espaciales de LocationSpark para extenderlo con nuevos algoritmos DJQ distribuidos y diversas mejoras. Posteriormente, se realiza una extensa evaluación del rendimiento de las diferentes propuestas (algoritmos de consulta espacial, extensiones y mejoras) en SpatialHadoop y LocationSpark. Finalmente, también se lleva a cabo un estudio comparativo entre SpatialHadoop y LocationSpark mediante la ejecución de un conjunto exhaustivo de experimentos de varias DBQ para identificar qué DSDMS es el más adecuado para el procesamiento de consultas distribuidas sobre grandes volúmenes de datos espaciales.