cBiK: A Space-Efficient Data Structure for Spatial Keyword Queries

Abstract

La universalización en el uso de dispositivos móviles y otros sensores ha traído consigo la creación de cantidades ingentes de datos georreferenciados, lo que lo que incrementa la relevancia de los análisis espacio-textuales sobre este tipo de información. Debido a este elevado volumen de datos, resulta imprescindible el uso de índices para acelerar consultas que posibilitan dichos análisis. En el estado del arte existen numerosas propuestas de índices basados en disco, su eficiencia se ve perjudicada por sus elevados costes de E/S, aspecto aún más determinante en colecciones de gran tamaño. En este trabajo, proponemos cBiK, el primer índice espacio-textual que emplea estructuras de datos compactas para construir soluciones eficientes en memoria principal. Nuestra evaluación experimental muestra que este enfoque requiere la mitad de espacio y es más de un orden de magnitud más rápido que un índice de última generación residente en disco. Asimismo, demostramos que nuestra propuesta sigue siendo competitiva incluso en un escenario en el que la estructura de datos residente en disco ha sido precargada en memoria principal.

A vast amount of geo-referenced data is being generated by mobile devices and other sensors increasing the importance of spatio-textual analyses on such data. Due to the large volume of data, the use of indexes to speed up the queries that facilitate such analyses is imperative. Many disk resident indexes have been proposed for different types of spatial keyword queries, but their efficiency is harmed by their high I/O costs. In this work, we propose cBiK, the first spatio-textual index that uses compact data structures to reduce the size of the structure, hence facilitating its usage in main memory. Our experimental evaluation, shows that this approach needs half the space and is more than one order of magnitude faster than a disk resident state-of-the-art index. Also, we show that our approach is competitive even in a scenario where the disk resident data structure is warmed-up to fit in main memory.