Indexación Espacial de Puntos Empleando Wavelet Trees

Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.

El desarrollo de estructuras de indexación que permitan recuperar objetos espaciales de manera eficiente ha sido un tema de interés en las últimas décadas. La mayoría de estas estructuras han sido diseñadas pensando en las características específicas de la memoria secundaria. Sin embargo, en los últimos años el precio de la memoria principal se ha reducido considerablemente y, por tanto, hoy en día es posible almacenar índices espaciales completos sin necesidad de acceder a disco.

En este trabajo nos centramos en los métodos de acceso a puntos, una subcategoría de los índices espaciales caracterizada por la indexación de puntos. Presentamos una estructura de indexación diseñada para memoria principal que mantiene un buena relación entre el espacio necesario para almacenar el índice y la eficiencia de las búsquedas. Nuestra estructura se basa en el wavelet tree, un árbol diseñado originalmente para indexar los caracteres de un texto, pero que recientemente se ha empleado con éxito para la construcción de auto-índices en áreas tan diferentes como la recuperación de información o la compresión de imágenes.