Indizierung und Abfrageverarbeitung

Indizierung und Abfrageverarbeitung umfassen die Datenstrukturen und Algorithmen, die es einem Suchsystem ermöglichen, Abfragen über große Textsammlungen schnell zu beantworten, hauptsächlich durch den invertierten Index.

Definition

Indizierung ist der Aufbau von Datenstrukturen, hauptsächlich des invertierten Index, der Terme den Dokumenten zuordnet, die sie enthalten, um eine effiziente Suche zu unterstützen, während Abfrageverarbeitung die Menge von Algorithmen ist, die diese Strukturen durchlaufen, um die Dokumente zu berechnen, die einer Abfrage entsprechen oder am besten für sie eingestuft sind.

Scope

Dieser Bereich behandelt, wie Textsammlungen in durchsuchbare Strukturen umgewandelt und wie Abfragen gegen diese ausgewertet werden: den Aufbau des invertierten Index, die Tokenisierungs- und Termvokabular-Entscheidungen, die dahinter stehen, das Komprimieren von Postings zur Platzersparnis und Beschleunigung des Zugriffs, die effiziente Verarbeitung von Abfragen einschließlich Rangfolge-Retrieval und frühzeitiger Beendigung sowie tolerante Retrieval-Techniken wie Wildcard-, Rechtschreibkorrektur- und phonetische Übereinstimmung. Er befasst sich mit dem System-Engineering des schnellen Retrievals, unterschieden von den Retrieval-Modellen, die die Rangfolge definieren, und den Evaluierungsmethoden, die die Qualität messen.

Sub-topics

• Indexkomprimierung
• Invertierte Indizes
• Abfrageverarbeitung und -optimierung
• Tolerante und Wildcard-Retrieval

Core questions

• Wie wird ein invertierter Index für eine große, sich ändernde Sammlung aufgebaut und aktualisiert?
• Wie können Postings-Listen komprimiert werden, ohne die Abfrageauswertung zu verlangsamen?
• Wie werden Abfragen effizient ausgewertet, insbesondere Rangfolge-Abfragen über Millionen von Dokumenten?
• Wie kann ein System gute Ergebnisse abrufen, ohne jedes Dokument zu bewerten?
• Wie geht ein System mit Rechtschreibfehlern, Wildcards und ungefähren Übereinstimmungen um?

Key concepts

• invertierter Index
• Postings-Liste
• Tokenisierung und Termvokabular
• Indexkonstruktion (BSBI, SPIMI)
• Indexkomprimierung
• Dokument-für-Dokument- und Term-für-Term-Auswertung
• dynamisches Pruning und frühzeitige Beendigung
• tolerantes Retrieval

Key theories

Invertierter Index als zentrale Datenstruktur

Die Zuordnung jedes Terms zu einer Postings-Liste der Dokumente (und Positionen), in denen er vorkommt, ermöglicht es dem Retrieval, nur Dokumente zu berücksichtigen, die Abfrageterme enthalten, was sie zur grundlegenden Struktur für skalierbare Textsuche macht.

Komprimierungs-Effizienz-Kompromiss

Das Kodieren von Dokument-ID-Lücken und Termfrequenzen mit kompakten Integer-Codes verkleinert den Index dramatisch und kann durch die Reduzierung von Input/Output und die Verbesserung des Cache-Verhaltens auch die Abfrageverarbeitung beschleunigen.

Effiziente Rangfolge-Abfrageauswertung

Dokument-für-Dokument- und Term-für-Term-Strategien, kombiniert mit dynamischem Pruning und frühzeitigen Beendigungstechniken, ermöglichen es Systemen, die am besten bewerteten Ergebnisse zurückzugeben, ohne die gesamte Sammlung vollständig zu bewerten.

Clinical relevance

Invertierte Indizes und effiziente Abfrageverarbeitung sind die „Maschinenräume“ jedes produktiven Suchsystems, von Web-Suchmaschinen und Open-Source-Suchplattformen bis hin zu Unternehmens- und Datenbank-Volltextsuche. Ihre Effizienz bestimmt direkt die Abfragelatenz, die Hardwarekosten und den Umfang der Sammlungen, die interaktiv durchsucht werden können.

History

Invertierte Dateien werden seit den frühesten Informationssystemen für die Textsuche verwendet, aber die moderne Theorie der Indexkonstruktion, Komprimierung und effizienten Auswertung wurde in den 1990er Jahren konsolidiert, insbesondere durch die Arbeit „Managing Gigabytes“ von Witten, Moffat und Bell. Die Übersicht von Zobel und Moffat aus dem Jahr 2006 fasste zwei Jahrzehnte der Forschung zu invertierten Indizes zusammen, als die Suche im Web-Maßstab die Effizienz von größter Bedeutung machte.

Key figures

• Justin Zobel
• Alistair Moffat
• Ian H. Witten
• W. Bruce Croft

Seminal works

• zobel2006
• wittenmgb1999
• manning2008

Frequently asked questions

Warum wird der invertierte Index dem Scannen von Dokumenten vorgezogen?

Das Scannen jedes Dokuments für jede Abfrage ist in großem Maßstab viel zu langsam. Der invertierte Index ermöglicht es dem System, direkt zu der kleinen Menge von Dokumenten zu springen, die die Abfrageterme enthalten, sodass die Abfragezeit von den beteiligten Postings-Listen und nicht von der Größe der gesamten Sammlung abhängt.

Verlangsamt das Komprimieren des Index die Suche?

In der Regel das Gegenteil. Ein kleinerer Index reduziert den Festplatten- und Speicherverkehr, und moderne Integer-Codes dekomprimieren sehr schnell, sodass die durch Input/Output und verbessertes Cache-Verhalten eingesparte Zeit die Dekodierungskosten typischerweise überwiegt, wodurch komprimierte Indizes sowohl kleiner als auch schneller werden.