Algorithms and compressed data structures for information retrieval

Abstract

[Abstract] In this thesis we address the problem of the efficiency in Information Retrieval by presenting new compressed data structures and algorithms that can be used in different application domains and achieve interesting space/time properties. We propose (i) a new variable-length encoding scheme for sequences of integers that enables fast direct access to the encoded sequence and outperforms other solutions used in practice, such as sampling methods that introduce an undesirable space and time penalty to the encoding; (ii) a new self-indexed representation of the compressed text obtained by any word-based, byte-oriented compression technique that allows for fast searches of words and phrases over the compressed text occupying the same space than the space achieved by the compressors of such type, and obtains better performance than classical inverted indexes when little space is used; and (iii) a new compact representation of Web graphs that supports efficient forward and reverse navigation over the graph using the smallest space reported in the literature, and in addition it also allows for extended functionality not usually considered in compressed graph representations. These data structures and algorithms can be used in several scenarios, and we experimentally show that they can successfully compete with other techniques commonly used in those domains.

[Resumen] En esta tesis abordamos el problema de la eficiencia en la Recuperación de Información presentando nuevas estructuras de datos compactas y algoritmos que pueden ser usados en diferentes dominios de aplicación y obtienen interesantes propiedades en espacio y tiempo. En ella proponemos (i) un nuevo esquema de codificación de longitud variable para secuencias de enteros que permite un rápido acceso directo a la secuencia codificada y supera a otras soluciones utilizadas en la práctica, como los métodos de muestreo que introducen una penalización indeseable en tiempo y espacio; (ii) una nueva representación autoindexada del texto comprimido obtenido por cualquier técnica de compresión orientada a byte y palabra que permite búsquedas eficientes de palabras y frases sobre el texto comprimido usando el mismo espacio que el obtenido por técnicas de compresión de dicho tipo, y que obtiene mejores resultados que índices invertidos clásicos cuando se usa poco espacio; y (iii) una nueva representación compacta de grafos Web que soporta una navegación directa y reversa eficiente usando el menor espacio de la literatura, y además permite una funcionalidad extendida no considerada usualmente por otras representaciones comprimidas de grafos. Estas estructuras de datos y algoritmos pueden utilizarse en diferentes escenarios, y probamos experimentalmente que compiten

[Resumo] Nesta tese abordamos o problema da eficiencia na Recuperación de Información presentando novas estruturas de datos compactas e algoritmos que poden ser usados en diferentes dominios de aplicación e obteñen interesantes propiedades en espazo e tempo. Nela propoñemos (i) un novo esquema de codificación de lonxitude variable para secuencias de enteiros que permite un rápido acceso directo á secuencia codificada e supera a outras solucións utilizadas na práctica, como os métodos de mostraxe que introducen unha penalización indesexable en tempo e espazo; (ii) unha nova representación autoindexada do texto comprimido obtido por calquera técnica de compresión orientada a byte e palabra que permite buscas eficientes de palabras e frases sobre o texto comprimido usando o mesmo espazo que as técnicas de compresión de dito tipo, e que obtén mellores resultados que índices invertidos clásicos cando se usa pouco espazo; e (iii) unha nova representación compacta de grafosWeb que soporta unha navegación directa e reversa eficiente usando o menor espazo da literatura, e que ademais permite unha funcionalidade estendida non considerada usualmente por outras representacións comprimidas de grafos. Estas estruturas de datos e algoritmos poden utilizarse en diferentes escenarios, e probamos experimentalmente que compiten exitosamente con outras técnicas comunmente usadas neses dominios.