Noticias
Agosto, 2023.- Gonzalo Navarro, académico del Departamento de Ciencias de la Computación de la Universidad de Chile e investigador del Instituto Milenio Fundamentos de los Datos, es nombrado hoy como «People of the ACM», distinción que destaca los logros científicos únicos y la historia personal de los miembros de la Association for Computing Machinery (ACM) que están a la vanguardia y marcan diferencias para el avance de la informática, tanto como ciencia y también como profesión.
Estos boletines presentan y destacan a personas miembros de ACM cuyas historias personales y profesionales son una fuente de inspiración para la comunidad de la computación en general. Gonzalo Navarro es el tercer investigador IMFD que recibe este reconocimiento, que en mayo de 2018 fue entregado a Ricardo Baeza-Yates y en enero de 2021 a Marcelo Arenas.
La ACM es la sociedad computacional educativa y científica más grande del mundo, que ofrece recursos que hacen avanzar la informática como ciencia y profesión. ACM proporciona la principal biblioteca digital del campo de la informática, y sirve a sus miembros y a las profesiones de la computación con publicaciones, conferencias y recursos profesionales de vanguardia.
En la entrevista, Gonzalo Navarro destaca la importancia del trabajo en equipos para el desarrollo de sus diversas investigaciones, como también la necesidad de elegir bien los problemas de investigación. A continuación, una traducción del artículo original en inglés.
People of the ACM
22 de agosto de 2023
¿Cómo se interesó inicialmente en los algoritmos y las estructuras de datos?
¡Ha sido un largo viaje! Soy argentino y comencé mi carrera de pregrado en la Universidad Nacional de La Plata. Eso fue en los años 80 -las carreras de Ciencias de la Computación apenas estaban despegando en América Latina y los recursos universitarios eran limitados (teníamos algunas computadoras para cientos de estudiantes). Aún así, el programa fue sólido y bien pensado, y estoy agradecido por lo que me dio. Sin embargo, como todavía sucede en muchos lugares de América Latina, el plan de estudios en algoritmos y estructuras de datos era muy básico. Después del tercer año me mudé a ESLAI, un proyecto educativo de vanguardia en Ciencias de la Computación de pregrado en Argentina que seleccionaba unas pocas docenas de estudiantes por año y les brindaba apoyo completo con becas, equipos, alojamiento y, lo más importante, profesores internacionales. Tuve mi primer curso de algoritmos serio con Giorgio Ausiello (todavía hoy trabajando en la Universidad de Roma La Sapienza), basado en el libro The Design and Analysis of Computer Algorithms de Aho, Hopcroft y Ullman, y fue como el primer amor: nunca lo olvidas. Un segundo curso estuvo a cargo de Jorge Olivos, un brillante profesor de la Universidad de Chile que estaba de año sabático en Argentina, y que finalmente definió dónde vivo y trabajo hoy.
Después de graduarme y entrar al mercado laboral, me di cuenta de lo aburrido que era cuando no estas aprendiendo todo el tiempo. Eran los años 90, y supongo que trabajar hoy en empresas como Google y similares debe ser mucho más emocionante. Entonces contacté a Jorge Olivos para que me asesorara y él me convenció de ir a Chile a hacer una maestría. Él ya estaba semi-retirado, así que me puso en contacto con Ricardo Baeza-Yates, quien regresaba de su trabajo de doctorado en la Universidad de Waterloo con un tema nuevo y hermoso que se convirtió en mi segundo amor: la búsqueda en texto. Todavía recuerdo mi fascinación por la elegancia y la belleza de la estructura de datos de arreglo de sufijos (suffix array data structure). Hice mi maestría y doctorado con Ricardo Baeza-Yates en recuperación de texto estructurado y coincidencia aproximada de cadenas (structured text retrieval and approximate string matching) La combinación de búsqueda de texto, con compresión de texto, mi otra área principal de interés desde entonces, surgió con Nivio Ziviani, un colega de Ricardo de la Universidad Federal de Minas Gerais, Brasil, y otro actor destacado en el desarrollo de motores de búsqueda web en América Latina. Mi interés actual generaliza esas experiencias y abarca toda el área de las estructuras de datos compactas, un cruce entre las estructuras de datos y la teoría de la información.
Su artículo “On Compressing and Indexing Repetitive Sequences,” (en coautoría con Sebastian Kreft) se incluyó en un compendio de los artículos más citados en ciencia de la computación teórica. ¿Qué desafío buscaba abordar con este documento y cómo lo resolvió la introducción de LZ-End?
Las versiones de este documento en la conferencia se remontan a 2010, cuando el término “avalancha de datos” se escuchaba en todas partes. Estaba empezando a darme cuenta de que gran parte de los datos de texto de más rápido crecimiento, tenían poco contenido de información, ya que las colecciones de texto eran muy repetitivas, y esto nos dio la oportunidad de frenar la avalancha de datos en esos casos. Piense en colecciones de genomas o lecturas de la misma especie en bioinformática, o colecciones de documentos versionados como Wikipedia, GitHub o el proyecto Software Heritage. Hoy, una década después, con los proyectos para secuenciar un millón de genomas humanos y la promesa de una medicina personalizada en el horizonte, el problema de indexar enormes colecciones repetitivas está recibiendo mucha atención, desde la práctica en los laboratorios de bioinformática hasta la teoría en el estudio de repetitividad y cómo aparece en las estructuras de datos de indexación de texto.
En ese momento, el concepto de autoíndices (self-indexes), que son representaciones comprimidas de textos a los que se puede acceder y buscar de manera eficiente sin siquiera descomprimirlos, existía desde hacía una década en forma de arreglos de sufijos comprimidos (compressed suffix arrays). Sin embargo, estos autoíndices se centraban en la compresión estadística, que es ciega a la repetitividad. Otros modelos de compresión, como los basados en diccionarios, capturaban la repetición, pero acceder al texto en forma comprimida era mucho más desafiante y mas aún, era buscarlas sin descomprimirlo. Ya habíamos obtenido buenos resultados con técnicas como la compresión basada en gramática (grammar-based compression) o arreglos de sufijos con compresión run-length, pero no con el gran premio: el parsing Ziv-Lempel original de 1976, la base de compresores como gzip y p7zip, proporcionaba la mejor compresión en secuencias repetitivas, y fue el modelo más difícil de usar.
Sebastian Kreft era un estudiante de maestría sobresaliente y asumió este desafío. Descubrimos cómo adaptar viejas ideas de Juha Kärkkäinen y Esko Ukkonen (a quienes conocí por mi posdoctorado en la Universidad de Helsinki en 1999) para reducir las búsquedas de texto a consultas geométricas y permutaciones, y para acceder de manera eficiente al texto comprimido, inventando el LZ-End variante de Lempel-Ziv. Nuestro índice de texto comprimido aún ofrece el mejor espacio en colecciones repetitivas, con tiempos de búsqueda competitivos.
Su paper “Colored Range Queries and Document Retrieval,»(en coautoría con Travis Gagie, Juha Kärkkäinen y Simon J. Puglisi) también es reconocido por hacer importantes contribuciones a la búsqueda de texto. ¿Qué son las consultas de rango de color y cuales fueron los conocimientos claves de este paper?
Colorear es solo un nombre «colorido» para categorizar objetos en clases. Tienes un conjunto de objetos, cada uno con un “color” (su clase) y realizas consultas (queries) que los agrupan por color. En las consultas de rango de colores, tiene una variedad de colores y deseas responder preguntas como «¿Qué colores aparecen en este rango?» “¿Cuáles son los más frecuentes?” etcétera. Los problemas abstractos de este tipo se estudian en computación teórica y sus soluciones se pueden aplicar a una amplia gama de situaciones.
En este documento, dimos nuevas soluciones a esos problemas y luego mostramos cómo podrían aplicarse a la recuperación de documentos. Esta área amplía, en cierto sentido, la disciplina clásica de recuperación de información que trabaja sobre textos en lenguaje natural, para aplicarla a colecciones de secuencias generales. Luego responde consultas como «¿Qué secuencias contienen este patrón corto?» “¿Cuáles son aquellos en los que aparece con mayor frecuencia?” y así sucesivamente, que tienen sentido en áreas como la bioinformática (por ejemplo, encontrar genes donde aparece a menudo algún marcador de ADN), minería de datos (por ejemplo, encontrar temas de actualidad en una red social durante un período de tiempo), etc.
¿Hay alguna investigación reciente que le gustaría destacar?
Me gustaría referirme al artículo “Worst-Case Optimal Graph Joins in Almost No Space”, que apareció en ACM SIGMOD 2021, porque pertenece al área de bases de datos de grafos donde comencé a trabajar recientemente en el contexto de mi trabajo con el IMFD en Chile. Para mí, significó el descubrimiento de una nueva área con un contenido algorítmico increíblemente rico donde la avalancha de datos ejerce presión sobre la cantidad de espacio utilizado por los índices eficientes. Los mejores índices requieren multiplicar el espacio de datos para ofrecer diferentes vistas de los mismos objetos y, por lo tanto, no son prácticos con los volúmenes de datos actuales.
Este es el escenario perfecto para aplicar estructuras de datos compactas. Las estructuras clásicas son altamente redundantes y las estructuras de datos compactas tienen como objetivo ofrecer la misma funcionalidad mientras usan un espacio cercano a la entropía de los datos -su verdadero contenido de información- eliminando así la redundancia. Logramos desarrollar nuevos índices que usan casi cero espacio además del tamaño de los datos simples, e incluso comprimen los datos, al tiempo que respaldan las operaciones de la base de datos de manera competitiva y, a veces, más rápida que los sistemas actuales, que usan un orden de magnitud más de espacio. Aprendí mucho en el proceso al ingresar a una nueva área de la informática, y mis colegas aprendieron mucho en términos de estructuras de datos sofisticadas. Como dijo un colega, “es como si hubieras traído una tecnología alienígena”. Ha sido una aventura inmensamente satisfactoria que recién comienza.
Ha sido prolífico en términos de autoría. ¿Qué consejo le daría a un colega más joven en términos de hábitos de trabajo para una carrera productiva?
El consejo más importante es: ¡trabaja con otras personas! Al menos para mí, la diferencia entre encontrar y desarrollar ideas solo, versus hacerlo mientras converso y me reúno con colegas es enorme. Incluso en los casos en que las ideas son originalmente mías, emergen y fluyen mucho mejor en conversaciones inspiradoras en lugar de estar enjauladas en mi cabeza. Una pregunta inocente, una relación con una idea de alguna otra área que tu compañero conoce mejor, una observación clave sobre algo que estaba frente a tus narices y que no habías visto, hace toda la diferencia. Y en otras ocasiones, al compartir una idea con otros cuando estás limitado en cómo abordar un problema, puedes comprenderlo mejor y proponer mejores soluciones, etc. Ve a conferencias y conoce gente, haz estadías prolongadas en otros lugares y aprende cómo trabajan otros equipos. Encontrarás esto mucho más gratificante que trabajar solo.
Mi segundo consejo es: elige bien tus problemas. A veces encuentras ideas interesantes perdidas en publicaciones mediocres porque los problemas no son tan relevantes. Un colega con más experiencia, a quien puedas juzgar por el impacto de sus publicaciones, puede guiarte hacia problemas en los que vale la pena invertir tu talento. Aun así, intenta trabajar en lo que realmente disfrutas, ya que es mucho más fácil ser bueno en las cosas que te emocionan. ¡Y tu vida será mucho más colorida!
