Indexando bases de datos no convencionales para memorias jerárquicas

Abstract

La alarmante velocidad de crecimiento de los datos disponibles en forma digital, se condice con un paralelo crecimiento de las capacidades de almacenamiento a precios más moderados. Por otro lado, mientras la velocidad de procesamiento de la CPU se ha duplicado cada 18 meses, la de los almacenamientos masivos ha progresado poco. Sin embargo han aparecido memorias caché con mayor capacidad, más rápidas y más peque nas, aunque m´as costosas, que las memorias RAM; algunas tienen incluso varias capas de memorias que poseen diferencias signi cativas de e ciencia de un nivel al siguiente. Antes almacenar datos en forma comprimida conllevaba un costo en términos de velocidad de procesamiento por la descompresión. Hoy en dí a, la diferencia entre los tiempos de la CPU y disco es tan signi cativa que el esfuerzo de descompresión se paga a cambio de una peque na disminución en el tiempo de I/O. Además, la transferencia de datos sobre una red local cuesta aproximadamente lo mismo que la transferencia al disco, por lo cual ésta se ve favorecida con la compresión. Este panorama ha promovido varias lí neas de investigación las cuales tienen en cuenta estas arquitecturas: las estructuras de datos compactas con distintas variantes (las sucintas y las comprimidas) y las estructuras de datos con I/O e ciente. Nuestro objetivo es contribuir a estas lí neas de investigación, dise nando estructuras de datos más e cientes para memorias jerárquicas, haciendo uso de la compacticidad o la I/O e ciente. Particularmente nos centraremos en las estructuras de datos capaces de manipular los siguientes tipos de datos: secuencias, textos, árboles, 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 nar estructuras de datos estáticas, planeamos investigar otros aspectos tales como la construcción e ciente (en espacio o en términos de la I/O), el dinamismo (es decir actualizaciones e cientes) y operaciones de búsqueda complejas (más allá de las básicas soportadas por las estructuras de datos).