Compression d'index
La compression d'index encode de manière compacte les listes de diffusion (postings lists) d'un index inversé, permettant ainsi à un système de recherche de stocker moins de données et de répondre plus rapidement aux requêtes.
Definition
La compression d'index est l'application de méthodes de codage d'entiers et de chaînes de caractères au dictionnaire et aux listes de diffusion (postings) d'un index inversé afin de réduire son empreinte de stockage tout en permettant un décodage rapide des listes de diffusion lors du traitement des requêtes.
Scope
Ce sujet couvre les techniques de compression des index inversés, en particulier l'encodage des écarts d'identifiants de documents et des fréquences de termes à l'aide de codes entiers à longueur variable et alignés sur des mots. Il aborde la compression de dictionnaire, l'encodage par écart (delta), les codes classiques tels que unaire, gamma et Golomb-Rice, les schémas alignés sur des octets et basés sur des blocs comme variable-byte et PForDelta, ainsi que le compromis entre le taux de compression et la vitesse de décodage. Il exclut la construction de l'index lui-même et la stratégie d'évaluation des requêtes qui l'utilise.
Core questions
- Pourquoi l'encodage des écarts entre les identifiants de documents compresse-t-il efficacement les listes de diffusion ?
- Quels codes entiers sont utilisés, et comment concilient-ils le taux de compression et la vitesse de décodage ?
- Comment le dictionnaire de termes lui-même est-il compressé ?
- Comment les listes de diffusion compressées peuvent-elles être décodées suffisamment rapidement pour maintenir une faible latence de requête ?
- Comment la compression interagit-elle avec le comportement du cache et le coût des entrées/sorties ?
Key concepts
- encodage par écart (delta)
- encodage variable-byte
- codes gamma et Golomb-Rice
- PForDelta et codes basés sur des blocs
- compression de dictionnaire
- taux de compression
- débit de décodage
- décodage SIMD / vectorisé
Key theories
- Encodage par écart des listes de diffusion
- Étant donné que les identifiants de documents dans une liste de diffusion sont croissants, le stockage des différences (écarts) entre les identifiants consécutifs produit de petits nombres qui se compressent bien, en particulier pour les termes fréquents avec des listes de diffusion denses.
- Compromis compression-vitesse
- Les codes alignés sur des bits, tels que gamma et Golomb, maximisent la compression mais se décodent lentement, tandis que les codes alignés sur des octets et basés sur des blocs, tels que variable-byte et PForDelta, sacrifient une partie du taux de compression pour un décodage beaucoup plus rapide et vectorisable, ce qui se traduit souvent par une meilleure performance globale des requêtes.
Clinical relevance
La compression est essentielle pour opérer la recherche à grande échelle : elle réduit la taille des index afin qu'ils tiennent en mémoire ou dans un espace de stockage plus petit, diminue les entrées/sorties et améliore la localité du cache, ce qui réduit à la fois la latence des requêtes et le coût matériel. Les moteurs de recherche en production et les bibliothèques de recherche open source s'appuient tous sur des listes de diffusion compressées.
History
Le codage compact des index textuels a été développé parallèlement aux fichiers inversés, avec des codes classiques alignés sur des bits (unaires, gamma, Golomb) systématisés dans l'ouvrage Managing Gigabytes des années 1990. À mesure que la recherche à l'échelle du web exigeait un décodage toujours plus rapide, les schémas alignés sur des octets et basés sur des blocs, tels que variable-byte et PForDelta, puis les décodeurs vectorisés capables de traiter des milliards d'entiers par seconde, ont déplacé l'accent vers la vitesse.
Key figures
- Alistair Moffat
- Ian H. Witten
- Daniel Lemire
- Justin Zobel
Related topics
Seminal works
- wittenmgb1999
- lemire2015
- manning2008
Frequently asked questions
- Comment un index compressé peut-il être plus rapide qu'un index non compressé ?
- La compression réduit la quantité de données lues depuis le disque ou la mémoire, ce qui constitue souvent le goulot d'étranglement. Les codes entiers modernes se décodent très rapidement, souvent à l'aide d'instructions vectorielles, de sorte que le temps économisé sur les entrées/sorties et le meilleur comportement du cache compensent largement le travail de décodage.
- Pourquoi stocker des écarts plutôt que des identifiants de documents bruts ?
- Les identifiants de documents dans une liste de diffusion sont triés et croissants, de sorte que les identifiants consécutifs ne diffèrent que de petites quantités. Le stockage de ces petits écarts au lieu de grands identifiants absolus produit des valeurs que les codes compacts peuvent représenter en très peu de bits.