Estructuras de datos sucintas para recuperación de documentos

Abstract

La recuperación de documentos consiste en, dada una colección de documentos y un patrón de consulta, obtener los documentos más relevantes para la consulta. Cuando los documentos están disponibles con anterioridad a las consultas, es posible construir un índice que permita, al momento de realizar las consultas, obtener documentos relevantes en tiempo razonable. Contar con índices que resuelvan un problema como éste es fundamental en áreas como recuperación de la información, minería de datos y bioinformática, entre otros. Cuando el texto que se indexa es lenguaje natural, la solución paradigmática corresponde al índice invertido. Sin embargo, los problemas de recuperación de documentos emergen también en escenarios en que el texto y los patrones de consulta pueden ser secuencias generales de caracteres, como lenguajes orientales, bases de datos multimedia, secuencias genómicas, etc. En estos escenarios los índices invertidos clásicos no se aplican con el mismo éxito. Si bien existen soluciones que requieren espacio lineal en este escenario de texto general, el espacio que utilizan es un problema importante: estas soluciones pueden utilizar más de 20 veces el espacio de la colección. Esta tesis presenta nuevos algoritmos y estructuras de datos para resolver algunos pro- blemas fundamentales para recuperación de documentos en colecciones de texto general, en espacio reducido. Más específicamente, se ofrecen nuevas soluciones al problema de document listing con frecuencias, y recuperación de los top-k documentos. Como subproducto, se de- sarrolló un nuevo esquema de compresión para bitmaps repetitivos que puede ser de interés por sí mismo. También se presentan implementaciones de las nuevas propuestas, y de trabajos relaciona- dos. Estudiamos nuestros algoritmos desde un punto de vista práctico y los comparamos con el estado del arte. Nuestros experimentos muestran que nuestras soluciones para document listing reducen el espacio de la mejor solución existente en un 40%, con un impacto mínimo en los tiempos de consulta. Para recuperación de los top-k documentos, también se redujo el espacio de la mejor solución existente en un 40% en la práctica, manteniendo los tiempos de consulta. Así mismo, mejoramos el tiempo de esta solución hasta en un factor de 100, a expensas de usar un bit extra por carácter. Nuestras soluciones son capaces de retornar los top-10 a top-100 documentos en el orden de milisegundos. Nuestras nuevas soluciones dominan la mayor parte del mapa espacio-tiempo, apuntando a ser el estándar contra el cual comparar la investigación futura.