Una excelente noticia para nuestro Departamento y para el Profesor Gonzalo Navarro fue la distinción que le otorgó Editorial Elsevier, con motivo de tener tres artículos científicos entre los cinco más citados de las revistas correspondientes.  Se trata de los trabajos: “On compressing and indexing repetitive sequences”, “Colored range queries and document retrieval” –ambos publicados en publicados en la revista Theoretical Computer Science– y “DACs: Bringing direct access to variable-length codes”, publicado en la revista “Information Processing and Management”. Todos ellos fueron publicados en 2013 y  según informó la editorial estuvieron dentro de los más citados durante 2014, 2015 y al menos hasta junio de 2016.

El Profesor Navarro explica que las citas son una buena medida del impacto del trabajo que realizan los investigadores de nuestro Departamento. “Que dos de los cinco artículos más citados en una de las revistas importantes de computación teórica sean nuestros habla muy bien del alcance internacional de lo que hacemos. En el DCC tenemos varias otras medidas que confirman lo mismo, empezando por el número de Best Paper Awards que obtenemos en las mejores conferencias”, comentó el académico.

A continuación, el Profesor Navarro nos explicó un poco más sobre cada uno de los artículos reconocidos:

"On compressing and indexing repetitive sequences"

Publicado en la revista Theoretical Computer Science, es un artículo escrito junto al egresado del DCC Sebastián Kreft, siendo el resultado de su tesis de Magíster en Ciencias mención Computación, de la cual el académico fue su profesor guía. Este es el primer trabajo en que se mostró cómo se podía crear un índice para buscar eficientemente en colecciones de texto muy repetitivas usando espacio proporcional al de la compresión Lempel-Ziv. “Las colecciones muy repetitivas aparecen por ejemplo cuando indexamos versiones de software, o colecciones versionadas como Wikipedia, o colecciones de genomas. Suelen ser colecciones gigantescas pero con pocas diferencias entre distintos documentos. Lempel-Ziv es por lejos la técnica de compresión más exitosa para este tipo de colecciones, que las puede almacenar en hasta 1/100 de su espacio original. Pero es un formato muy difícil de manipular, por ejemplo extraer un documento de la colección sin descomprimir todo es difícil. Nosotros fuimos más allá y mostramos cómo buscar eficientemente sin descomprimir, usando un índice basado en esa forma de compresión. Hasta hoy en día, este índice es imbatible en su combinación de poco espacio y tiempo razonable de búsqueda”, explicó el Profesor.

Este artículo también fue seleccionado para el “Virtual Special Issue” de los 40 años de la misma Revista Theoretical Computer Science, que incluye el paper más citado de cada año desde 1975 hasta 2015.

“Colored Range Queries and Document Retrieval"

También publicado en Theoretical Computer Science, este artículo fue  realizado en conjunto con investigadores de la Universidad de Helsinki, y muestra cómo se pueden extender las técnicas típicas de recuperación de información a contextos más generales que lenguaje natural, donde los documentos son secuencias arbitrarias, como secuencias de ADN, de música, de código fuente, etc. “Para lenguaje natural, existe una estructura muy simple llamada índice invertido que, con distintas variantes, responde preguntas como "¿en qué documentos aparece esta palabra?" o "¿cuáles son los documentos donde esta palabra es más relevante?". Responder lo mismo para secuencias generales es más desafiante y requiere de nuevos algoritmos. En este artículo encontramos soluciones eficientes a algunas preguntas más fundamentales, como "¿qué colores distintos aparecen en este rango de esta secuencia de colores?" o "¿cuáles son los colores más frecuentes en este rango?" y mostramos cómo aplicarlas a problemas de recuperación de información”, señaló Gonzalo Navarro.

"DACs: Bringing Direct Access to Variable-Length Codes"

Este artículo fue publicado en la revista Information Processing and Management y fue escrito en conjunto con investigadores de la Universidade da Coruña. Fue parte de la tesis de Doctorado de Susana Ladra, la cual el profesor del DCC codirigió con Nieves Brisaboa. Este trabajo trata cómo representar secuencias de números en forma compacta pero aun permitiendo extraer eficientemente cualquiera de ellos. “Muchos métodos de compresión reducen el problema a representar una secuencia de números donde la mayoría son pequeños, y existen muchas técnicas para representarlos, pero la mayoría exige descomprimir una buena parte de la secuencia para acceder a alguno de ellos individualmente. La técnica DAC conserva buena compresión y da acceso directo a cualquier valor. Esto es clave para implementar estructuras de datos comprimidas, donde no sólo tenemos que comprimir los datos, sino accederlos eficientemente sin tener que descomprimirlos”, concluyó el Profesor Navarro.

--

Comunicaciones DCC