Representaciones compactas de matrices con localidad espacial

Abstract

El objetivo de este trabajo de tesis es diseñar e implementar representaciones eficientes en espacio de matrices con localidad espacial, es decir, matrices cuyas celdas cercanas almacenan valores similares entre sí . Esto es de utilidad en muchas aplicaciones prácticas como por ejemplo, en el dominio de los sistemas de información geográfica, se necesitan almacenar y consultar mapas de temperatura, precipitaciones, elevación, etc. en donde los datos están relacionados y tienen localidad espacial. En este trabajo se explorar an las representaciones existentes para abordar dicho problema, las propiedades del dominio de datos abordado y, a partir de esto, se diseñarán nuevas estructuras, tomando como base varias técnicas conocidas en los dominios de bases de datos espaciales y estructuras de datos compactas, como son las curvas de llenado del espacio, arboles binarios de b usqueda en su versión comprimida, arboles sucintos, Wavelet Trees comprimidos y k2-trees. Las operaciones que nuestras soluciones soportan son: responder consultas por el valor de una celda en particular y consultas por una subregión (con y sin rango de valores posibles restringido). Un dominio donde este tipo de consultas resulta interesante, es en los mapas climáticos, en los cuales se quiere conocer la temperatura de una de una coordenada en particular (consulta de acceso), realizar zoom sobre un mapa (consulta por una subregión) o conocer la temperatura de una zona que excede un umbral (consulta por una subregión con rango).