Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/2739
Title: Quadtrees eficientes en espacio para conjuntos de datos con clústers
Authors: Seco Naveiras, Diego , supervisora de grado
González Nova, Javier Ignacio
Keywords: Estructuras de Datos (Ciencia de la Computación);Sistemas de Almacenamiento y Recuperación de Información - Ingeniería - Metodología;Almacenamiento Virtual (Computación) - Problemas, Ejercicios, Etc;Sistemas de Información;Ciencias de la Computación
Issue Date: 2017
Publisher: Universidad de Concepción . Facultad de Ingeniería. Departamento de Ingeniería Informática y Ciencias de la Computación
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.
Description: Magister en Ciencias de la Computación Universidad de Concepción 2017
URI: http://repositorio.udec.cl/jspui/handle/11594/2739
Appears in Collections:Ingeniería Informática y Ciencias de la Computación - Tesis Magister

Files in This Item:
File Description SizeFormat 
Tesis_Quadtrees_eficientes_en_espacio_para_conjuntos.pdf1,36 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.