Quadtrees eficientes en espacio para conjuntos de datos con clústers

Abstract

Poder almacenar en memoria principal conjuntos de puntos de dos dimensiones para realizar consultas sobre ellos (por ejemplo, saber si un punto est a en el conjunto o qu e puntos est an en un cierto rango. Un rango son todos los puntos tales que x 2 [x1; x2] y y 2 [y1; y2], con x e y coordenadas y x1 < x2; y1 < y2.) es útil en varias áreas de la computación, tales como geometría computacional, sistemas de información geográfica, gráficos, etc. En esta tesis se explorarán estructuras sucintas (estructuras que no necesitan ser descomprimidas para realizar consultas sobre ellas) porque tener la estructura en niveles superiores de la jerarquía de memoria supone un incremento en la velocidad de procesamiento (que puede llegar a ser ordenes de magnitud en el caso de pasar de disco a RAM), a un cuando realizar operaciones sobre este tipo de estructuras suele ser más costoso que en las estructuras clásicas, asumiendo que ambas estructuras pudiesen estar contenidas en memoria principal. En base a esto, se propondrá una estructura alternativa que mejore las actuales. La estructura propuesta es una representación comprimida de quadtrees que aprovecha los clústers que forman los elementos. Esta estructura intenta mejorar el problema que presenta el k2 􀀀 tree, el cual ocupa mucho espacio para almacenar matrices esparsas. Se espera también mejorar el tiempo de las consultas (buscar puntos en el espacio) con respecto al k2 - tree.