Indexkomprimierung

Die Indexkomprimierung kodiert die Postings-Listen eines invertierten Indexes kompakt, sodass ein Suchsystem weniger Daten speichert und Anfragen schneller beantwortet.

Definition

Indexkomprimierung ist die Anwendung von Ganzzahl- und String-Kodierungsmethoden auf das Wörterbuch und die Postings eines invertierten Indexes, um dessen Speicherbedarf zu reduzieren, während die Postings während der Abfrageverarbeitung schnell dekodierbar bleiben.

Scope

Dieses Thema behandelt Techniken zur Komprimierung invertierter Indizes, insbesondere die Kodierung von Lücken in Dokumenten-Identifikatoren und Termfrequenzen mit variabler Länge und wortausgerichteten Ganzzahlcodes. Es behandelt die Wörterbuchkomprimierung, die Lücken-(Delta-)Kodierung, klassische Codes wie Unär-, Gamma- und Golomb-Rice-Codes, byte-ausgerichtete und blockbasierte Schemata wie Variable-Byte und PForDelta sowie den Kompromiss zwischen Komprimierungsverhältnis und Dekodierungsgeschwindigkeit. Ausgeschlossen sind der Aufbau des Indexes selbst und die Abfrage-Evaluierungsstrategie, die ihn nutzt.

Core questions

• Warum komprimiert die Kodierung von Lücken zwischen Dokumenten-Identifikatoren Postings effektiv?
• Welche Ganzzahlcodes werden verwendet und wie tauschen sie Komprimierungsverhältnis gegen Dekodierungsgeschwindigkeit ein?
• Wie wird das Termwörterbuch selbst komprimiert?
• Wie können komprimierte Postings schnell genug dekodiert werden, um die Abfragelatenz niedrig zu halten?
• Wie interagiert Komprimierung mit dem Cache-Verhalten und den Ein-/Ausgabe-Kosten?

Key concepts

• Lücken-(Delta-)Kodierung
• Variable-Byte-Kodierung
• Gamma- und Golomb-Rice-Codes
• PForDelta und blockbasierte Codes
• Wörterbuchkomprimierung
• Komprimierungsverhältnis
• Dekodierungsdurchsatz
• SIMD / vektorisierte Dekodierung

Key theories

Lückenkodierung von Postings

Da Dokumenten-Identifikatoren in einer Postings-Liste aufsteigend sind, führt das Speichern der Differenzen (Lücken) zwischen aufeinanderfolgenden Identifikatoren zu kleinen Zahlen, die sich gut komprimieren lassen, insbesondere für häufige Begriffe mit dichten Postings.

Kompromiss zwischen Komprimierung und Geschwindigkeit

Bit-ausgerichtete Codes wie Gamma und Golomb maximieren die Komprimierung, dekodieren aber langsam, während byte-ausgerichtete und blockbasierte Codes wie Variable-Byte und PForDelta einen Teil des Verhältnisses für eine viel schnellere, vektorisierbare Dekodierung opfern, was oft die Gesamtleistung der Abfrage verbessert.

Clinical relevance

Komprimierung ist für den Betrieb von Suchsystemen im großen Maßstab unerlässlich: Sie verkleinert Indizes, sodass sie in den Speicher oder kleinere Speichermedien passen, reduziert Ein-/Ausgabe und verbessert die Cache-Lokalität, wodurch sowohl die Abfragelatenz als auch die Hardwarekosten gesenkt werden. Produktionssuchmaschinen und Open-Source-Suchbibliotheken verlassen sich alle auf komprimierte Postings.

History

Die kompakte Kodierung von Textindizes wurde parallel zu invertierten Dateien entwickelt, wobei klassische bit-ausgerichtete Codes (Unär, Gamma, Golomb) in der Arbeit „Managing Gigabytes“ der 1990er Jahre systematisiert wurden. Da die Websuche immer schnellere Dekodierung erforderte, verlagerten byte-ausgerichtete und blockbasierte Schemata wie Variable-Byte und PForDelta sowie später vektorisierte Dekodierer, die Milliarden von Ganzzahlen pro Sekunde verarbeiten können, den Schwerpunkt auf die Geschwindigkeit.

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

Wie kann ein komprimierter Index schneller sein als ein unkomprimierter?

Komprimierung reduziert die Menge der von der Festplatte oder dem Speicher gelesenen Daten, was oft der Engpass ist. Moderne Ganzzahlcodes dekodieren sehr schnell, häufig unter Verwendung von Vektorbefehlen, sodass die eingesparte Zeit bei der Ein-/Ausgabe und das bessere Cache-Verhalten die Dekodierungsarbeit mehr als ausgleichen.

Warum speichert man Lücken anstelle von rohen Dokumenten-Identifikatoren?

Dokumenten-Identifikatoren in einer Postings-Liste sind sortiert und aufsteigend, sodass aufeinanderfolgende sich nur geringfügig unterscheiden. Das Speichern dieser kleinen Lücken anstelle großer absoluter Identifikatoren erzeugt Werte, die kompakte Codes mit sehr wenigen Bits darstellen können.