Compresión de índices
La compresión de índices codifica las listas de publicaciones de un índice invertido de forma compacta para que un sistema de búsqueda almacene menos datos y responda a las consultas más rápidamente.
Definition
La compresión de índices es la aplicación de métodos de codificación de enteros y cadenas al diccionario y a las publicaciones de un índice invertido para reducir su espacio de almacenamiento, manteniendo al mismo tiempo las publicaciones rápidamente decodificables durante el procesamiento de consultas.
Scope
Este tema abarca técnicas para comprimir índices invertidos, especialmente la codificación de las brechas de identificadores de documentos y las frecuencias de términos con códigos enteros de longitud variable y alineados por palabras. Trata la compresión de diccionarios, la codificación de brechas (delta), códigos clásicos como unario, gamma y Golomb-Rice, esquemas alineados por bytes y basados en bloques como variable-byte y PForDelta, y la relación entre la tasa de compresión y la velocidad de decodificación. Excluye la construcción del índice en sí y la estrategia de evaluación de consultas que lo consume.
Core questions
- ¿Por qué la codificación de las brechas entre identificadores de documentos comprime las publicaciones de forma efectiva?
- ¿Qué códigos enteros se utilizan y cómo equilibran la tasa de compresión con la velocidad de decodificación?
- ¿Cómo se comprime el propio diccionario de términos?
- ¿Cómo se pueden decodificar las publicaciones comprimidas lo suficientemente rápido como para mantener baja la latencia de las consultas?
- ¿Cómo interactúa la compresión con el comportamiento de la caché y el costo de entrada/salida?
Key concepts
- codificación de brechas (delta)
- codificación de bytes variables
- códigos gamma y Golomb-Rice
- PForDelta y códigos basados en bloques
- compresión de diccionario
- tasa de compresión
- rendimiento de decodificación
- decodificación SIMD / vectorizada
Key theories
- Codificación de brechas de publicaciones
- Dado que los identificadores de documentos en una lista de publicaciones son crecientes, almacenar las diferencias (brechas) entre identificadores consecutivos produce números pequeños que se comprimen bien, especialmente para términos frecuentes con publicaciones densas.
- Compromiso entre compresión y velocidad
- Los códigos alineados por bits, como gamma y Golomb, maximizan la compresión pero decodifican lentamente, mientras que los códigos alineados por bytes y basados en bloques, como variable-byte y PForDelta, sacrifican parte de la relación para una decodificación mucho más rápida y vectorizable, lo que a menudo mejora el rendimiento general de las consultas.
Clinical relevance
La compresión es esencial para operar búsquedas a escala: reduce los índices para que quepan en la memoria o en un almacenamiento más pequeño, disminuye la entrada/salida y mejora la localidad de la caché, lo que reduce tanto la latencia de las consultas como el costo del hardware. Los motores de búsqueda de producción y las bibliotecas de búsqueda de código abierto se basan en publicaciones comprimidas.
History
La codificación compacta de índices de texto se desarrolló junto con los archivos invertidos, con códigos clásicos alineados por bits (unario, gamma, Golomb) sistematizados en el trabajo de Managing Gigabytes de la década de 1990. A medida que la búsqueda a escala web exigía una decodificación cada vez más rápida, los esquemas alineados por bytes y basados en bloques, como variable-byte y PForDelta, y posteriormente los decodificadores vectorizados capaces de miles de millones de enteros por segundo, cambiaron el énfasis hacia la velocidad.
Key figures
- Alistair Moffat
- Ian H. Witten
- Daniel Lemire
- Justin Zobel
Related topics
Seminal works
- wittenmgb1999
- lemire2015
- manning2008
Frequently asked questions
- ¿Cómo puede un índice comprimido ser más rápido que uno sin comprimir?
- La compresión reduce la cantidad de datos leídos del disco o la memoria, lo que a menudo es el cuello de botella. Los códigos enteros modernos decodifican muy rápidamente, frecuentemente utilizando instrucciones vectoriales, por lo que el tiempo ahorrado en entrada/salida y el mejor comportamiento de la caché compensan con creces el trabajo de decodificación.
- ¿Por qué almacenar brechas en lugar de identificadores de documentos sin procesar?
- Los identificadores de documentos en una lista de publicaciones están ordenados y son crecientes, por lo que los consecutivos difieren en pequeñas cantidades. Almacenar esas pequeñas brechas en lugar de grandes identificadores absolutos produce valores que los códigos compactos pueden representar en muy pocos bits.