Con la investigación "Faster Compact Top-k Document Retrieval", que presenta una solución práctica al problema de obtener los mejores documentos de una colección a partir de una frase o secuencia de caracteres, el alumno del Doctorado en Ciencias de la Computación del DCC Roberto Konow, recibió el Capocelli Prize (Premio Capocelli) que se otorga en el marco de la Data Compression Conference 2013. El trabajo es de autoría de Konow con el académico del DCC Gonzalo Navarro.
El Capocelli Prize es un reconocimiento anual concedido por el Comité de Programa de la Data Compression Conference, una de las más importantes en el área de Compresión de Datos, que este año se realizó en marzo en Salt Lake City, Estados Unidos. Se otorga a un estudiante que sea autor de la investigación y lo haya presentado en la Conferencia, siendo el ganador notificado en forma posterior a la realización del evento. Esta distinción se otorga desde 1994 y ésta es la primera vez que lo recibe un representante de una universidad latinoamericana; anteriormente lo habían obtenido investigadores de prestigiosas universidades como el MIT, Carnegie Mellon y la Universidad de California, San Diego, entre otras.
Para escoger al ganador, el Comité de Programa seleccionó nueve de los papers presentados durante la Conferencia, entre los cuales se escogieron los tres mejores por medio de votación de los mismos integrantes del Comité, donde el trabajo de los investigadores del DCC obtuvo más del 50% de los votos.
Diseño e implementación de una nueva solución
"Faster Compact Top-k Document Retrieval" tiene su origen en un trabajo previo del profesor Gonzalo Navarro, realizado en conjunto con el investigador Yakov Nekrich, titulado "Top-k Document Retrieval in Optimal Time and Linear Space", y que fue publicado en SODA 2012, una de las tres mejores conferencias de Computación Teórica. Este trabajo, presenta una solución óptima para el problema de top-k document retrieval que consiste en, dada una colección de documentos, encontrar los k más relevantes a una consulta.
"La idea es que dada una colección de documentos de, por ejemplo, 1 millón se pueda encontrar rápidamente en cuáles de estos ocurre con mayor frecuencia una secuencia de caracteres. Por ejemplo, cuando uno busca en Google, no te va a retornar los millones y millones de documentos que contiene con la palabra que estás buscando, sino que te va a enviar los k mejores y por eso se llama top k, porque son los mejores k que contienen esa palabra", explica Roberto Konow.
El profesor Navarro agrega que "el problema inicial es fundamental en recuperación de información textual y en este caso se trabaja en una variante más general que se puede aplicar a otras áreas como bioinformática, colecciones multimediales, manejo de repositorios de software, etc.". El académico destaca que si bien el primer trabajo cerraba el problema desde un punto de vista teórico, desde una perspectiva práctica tenía el problema de que el espacio era demasiado alto: "Era proporcional al largo de la colección, pero una implementación directa podía requerir hasta 80 bytes por cada carácter de la colección. Es decir, para indexar una modesta colección de 1GB se requerirían 80GB de almacenamiento. La nueva solución requiere sólo 2-3 veces el tamaño del texto y responde las consultas en unos pocos microsegundos".
Por su parte, Roberto Konow explica que "si bien en colecciones de lenguaje natural el problema ya está bien resuelto (y los buscadores de Internet lo resuelven a cada segundo), esas soluciones no se pueden aplicar en el caso más general. "Las soluciones previas a la que se desarrolló, o bien usan menos espacio que la nuestra pero son mil veces más lentas, o bien requieren bastante más espacio. Eso hace que nuestra solución ocupe un nicho muy relevante en el mapa de espacio/tiempo".
Finalmente, el profesor Navarro destacó que el Capocelli Prize representa un importante reconocimiento al trabajo que Roberto realizó en esta investigación, no sólo porque se otorga en una de las conferencias más importantes en el área de Compresión de Datos, sino también porque el estudiante pudo participar activamente en el diseño e implementación de una nueva solución para un problema complejo, donde propuso "nuevas mejoras, algunas de las cuales fueron cruciales para obtener los resultados que se consiguieron. Para Roberto este premio es un hito muy importante en su Doctorado, que le da visibilidad y una carta de presentación para el futuro. Para el DCC, similarmente, es un reconocimiento importante a la calidad de su Programa de Doctorado", concluyó el académico.
