Análisis e indexación de datos no convencionales

Abstract

La constante aparición de datos en forma digital de diferentes tipos, tamaños y en gran cantidad, concuerda con un crecimiento de las capacidades de almacenamiento a precios más moderados. Por otro lado, dos fenómenos se han manifestado últimamente: mientras la velocidad de procesamiento de la CPU se ha duplicado casi anualmente, la de los almacenamientos masivos ha progresado poco; (b) han aparecido memorias caché con mayor capacidad, más rápidas y más pequeñas, aunque más costosas, que las memorias RAM. Estos fenómenos han cambiado los modelos de costos utilizados para diseñar algoritmos y estructuras de datos eficientes. Por tal motivo los costos que se pagaban al almacenar datos en forma comprimida, en términos de velocidad de procesamiento por la descompresión, hoy en día se tornan despreciables debido a que la diferencia entre los tiempos de CPU y acceso a disco es tan significativa que el esfuerzo de descompresión se paga a cambio de una pequeña disminución en el tiempo de I/O. Además, la transferencia de los datos sobre una red local cuesta casi lo mismo que la transferencia a disco, por lo cual ésta se ve favorecida con la compresión. Este escenario ha originado líneas de investigación que tienen en cuenta estas diferencias de costos de operaciones, así nos dedicamos a las estructuras de datos: compactas y/o con I/O eficiente. Nuestro objetivo es contribuir a estas líneas de investigación, diseñando estructuras de datos más eficientes para memorias jerárquicas, haciendo uso de la compacticidad o la I/O eficiente. Particularmente nos centraremos en las estructuras de datos capaces de manipular los siguientes tipos de datos: secuencias, textos, grafos, y espacios métricos, entre otros, y en estudiar los problemas desde ambos puntos de vista teórico y empírico. Además de diseñar estructuras de datos, planeamos investigar otros aspectos tales como la construcción eficiente (en espacio o en I/O u otras medidas de eficiencia), el dinamismo (es decir actualizaciones eficientes) y operaciones de búsqueda complejas (más allá de las básicas soportadas por las estructuras de datos clásicas).