Algorithms and compressed data structures for information retrieval
Use este enlace para citar
http://hdl.handle.net/2183/9350Coleccións
- Teses de doutoramento [2150]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Algorithms and compressed data structures for information retrievalAutor(es)
Director(es)
Brisaboa, Nieves R.Navarro Badino, Gonzalo
Data
2011Centro/Dpto/Entidade
Universidade da Coruña. Departamento de ComputaciónResumo
[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.
Palabras chave
Algoritmos
Datos
Compresión
Recuperación de la información
Datos
Compresión
Recuperación de la información
Dereitos
Os titulares dos dereitos de propiedade intelectual autorizan a visualización do contido desta tese a través de Internet, así como a súa reproducción, gravación en soporte informático ou impresión para o seu uso privado e/ou con fins de estudo e de investigación. En nengún caso se permite o uso lucrativo deste documento. Estos dereitos afectan tanto ó resumo da tese como o seu contido Los titulares de los derechos de propiedad intelectual autorizan la visualización del contenido de esta tesis a través de Internet, así como su repoducción, grabación en soporte informático o impresión para su uso privado o con fines de investigación. En ningún caso se permite el uso lucrativo de este documento. Estos derechos afectan tanto al resumen de la tesis como a su contenido