17/04/2009

Nuevo Doctor en Ciencias mención Computación

El pasado 30 de marzo Diego Arroyuelo obtuvo el grado de Doctor en Ciencias mención Computación con su tesis "Lempel-Ziv Compressed Full-Text Self-Indexes", trabajo de investigación guiado por el académico del DCC Gonzalo Navarro. En su tesis realizó un estudio de autoíndices comprimidos basados en el algoritmo de compresión Lempel-Ziv, contribuyendo así con nuevos desarrollos.

El pasado 30 de marzo Diego Arroyuelo obtuvo el grado de Doctor en Ciencias mención Computación con su tesis "Lempel-Ziv Compressed Full-Text Self-Indexes", trabajo de investigación guiado por el académico del DCC Gonzalo Navarro. En su tesis realizó un estudio de  autoíndices comprimidos basados en el algoritmo de compresión Lempel-Ziv, contribuyendo así con nuevos desarrollos.
 
La comisión evaluadora estuvo integrada por los profesores del Departamento de Ciencias de la Computación Jérémy Barbay y Benjamín Bustos; Mauricio Marín, investigador de Yahoo! Research Latin America, y como profesor invitado Juha Karkkainen de la Universidad de Helsinki, Finlandia.
 
En su tesis, Arroyuelo realiza un estudio profundo de índices comprimidos para texto, basados en el algoritmo de compresión de Lempel-Ziv, de 1978. Según explicó el nuevo Doctor, "con esto se contribuye a mostrar que existen otros tipos de índices comprimidos que también valen la pena por su eficiencia, no sólo los basados en arreglos de sufijos que eran los más conocidos y estudiados en la literatura. El aporte es una nueva familia de índices comprimidos para texto, con muchas características relevantes: eficiencia en operaciones de búsqueda (siendo los más competitivos en operaciones claves en la práctica); adaptables a un rango de espacio disponible (intercambiando espacio por tiempo); posibles de construir con muy poco espacio de memoria (aún menor que el espacio del índice mismo y con un algoritmo de indexación que es el más rápido entre los índices comprimidos), y pueden ser almacenados en memoria secundaria de memoria eficiente, siendo significativamente más pequeño que cualquier otro índice para texto sobre disco. Con la investigación además  se aportó en áreas de investigación relacionadas como las estructuras sucintas. Y en particular se destaca la representación sucinta de tries dinámicos que era un problema abierto hace varios años".
 
Diego Arroyuelo es Licenciado en Ciencias de la Computación de la Universidad Nacional de San Luis, Argentina. Sus líneas de investigación de interés son Algoritmos y Estructuras de Datos; Búsqueda en Texto Indexado; Índices Comprimidos para Texto y Estructuras de Datos Sucintas. Además participa en el Grupo de Algoritmos del DCC dirigido por el profesor Gonzalo Navarro.
 
Para la realización de su tesis, Arroyuelo obtuvo el apoyo de becas de doctorado otorgadas por CONICYT y Yahoo! Research Latin America. Durante el desarrollo de la investigación realizó estadías en las Universidades de: Kyushu (Japón), Pisa (Italia), Waterloo (Canadá), Melbourne (Australia) y en NICTA (Australia). "Es importante que el DCC dé estas oportunidades a sus alumnos. Tuve la suerte de poder contactarme con investigadores muy importantes en mi área de los cuales siempre se puede aprender mucho", dijo el nuevo doctorado.
Es el caso de su estadía en la Universidad de Waterloo, done Arroyuelo permaneció por nueve meses. En esa oportunidad trabajó con los investigadores Ian Munro y Álex López Ortiz. Respecto a sus proyectos futuros, cuenta: "Planeo continuar mi investigación en los laboratorios de Yahoo! Research Latin America y seguir trabajando en esta área de investigación, apuntando a índices para texto que puedan ser empleados en máquinas de búsqueda. También pretendo continuar con mi investigación en Estructuras de Datos Sucintas, sobre todo en representaciones de árbol".

 

 
(Colaboración Comunicaciones DCC).

Resumen tesis: "Lempel-Ziv Compressed Full-Text Self-Indexes", Diego Arroyuelo.
 
Debido a las grandes colecciones de texto disponibles hoy en día, el problema de búsqueda en texto es común en diversas aplicaciones, las que necesitan proveer acceso eficiente a esas colecciones. Los índices clásicos para texto requieren demasiado espacio (además de almacenar el texto), y entonces podrían no caber en memoria principal, aún para textos de tamaño moderado que sí caben. La tendencia actual en búsqueda en texto indexado es la de los autoíndices comprimidos, los cuales reemplazan el texto con una representación que requiere espacio proporcional al del texto comprimido y proveen acceso indexado al texto.
 
Los autoíndices comprimidos basados en arreglos de sufijos son los más conocidos en la literatura. Existen, sin embargo, otros tipos de autoíndices que han recibido menos atención a pesar de su eficiencia. En esta tesis se realizó un estudio de los autoíndices comprimidos basados en el algoritmo de compresión Lempel-Ziv (LZ-índices), contribuyendo con nuevos desarrollos. Basamos nuestros estudios en el LZ-índice de Navarro (o simplemente LZ-índice). Previo a nuestro trabajo, los LZ-índices eran una alternativa atractiva, aunque con algunas deficiencias: requerían usualmente más espacio que otros esquemas existentes, no permitían compromisos entre espacio y tiempo de búsqueda (para ajustarse a la memoria disponible), requerían demasiado espacio de construcción, y no funcionaban eficientemente en memoria secundaria (para textos muy grandes). Contribuimos a aliviar todas esas deficiencias.
 
Nuestra primera contribución es un enfoque práctico para reducir el espacio del LZ-índice, alcanzando hasta dos tercios de su espacio, y manteniendo sus buenas cualidades. Aunque nuestros índices sólo garantizan buen tiempo promedio de búsqueda, son las alternativas más eficientes para las operaciones claves de extraer subcadenas del texto y mostrar los contextos de las ocurrencias, suponiendo que disponemos del espacio que requieren nuestros índices.
 
Luego estudiamos maneras de reducir el espacio que requiere el LZ-índice, esta vez con garantías de peor caso en tiempo de búsqueda, obteniendo los LZ-índices más pequeños que existen, a la vez que mejoramos el costo de búsqueda original. Exploramos diversas maneras para lograr nuestro objetivo y obtenemos una familia completa de LZ-índices, con diferentes requerimientos de espacio y tiempos de búsqueda. De esta manera, somos capaces de competir en casos en los que no podíamos hacerlo con el LZ-índice original, debido a limitaciones de espacio.
 
Estudiamos luego la construcción con poco espacio de nuestra familia de LZ-índices. Concluimos que nuestros LZ-índices pueden ser construidos sin espacio extra sobre el del índice final, lo que mejora su aplicabilidad ya que si disponemos del espacio para almacenar el índice final seremos capaces de construirlo sin acceder a la memoria secundaria. En la práctica, nuestros LZ-índices son los autoíndices más rápidos en construirse con espacio proporcional al del texto comprimido.
 
Finalmente estudiamos cómo adaptar el LZ-índice en memoria secundaria. Obtenemos el índice para texto en memoria secundaria más pequeño que existe, siendo a la vez muy competitivos en cantidad de accesos a disco.