Invertierte Indizes

Ein invertierter Index ordnet jeden Begriff in einer Sammlung einer Postings-Liste der Dokumente zu, die ihn enthalten, wodurch ein Suchsystem passende Dokumente finden kann, ohne jedes Dokument zu scannen.

Definition

Ein invertierter Index ist eine Datenstruktur, die aus einem Wörterbuch indizierter Begriffe besteht, wobei jeder auf eine Postings-Liste verweist, die die Dokumente aufzählt, die den Begriff enthalten, oft mit Häufigkeiten und Begriffspositionen versehen, sodass der Abruf durch Schnittmengenbildung oder Zusammenführung von Postings-Listen erfolgen kann.

Scope

Dieses Thema behandelt die Struktur und den Aufbau des invertierten Index: das Wörterbuch der Begriffe, die Postings-Listen, die Dokument-Identifikatoren, Termhäufigkeiten und Positionen aufzeichnen, sowie die Algorithmen, die Indizes über große Sammlungen aufbauen und aktualisieren, einschließlich blockbasiertem Sortier-Indexing und Single-Pass-In-Memory-Indexing. Es behandelt Positionsinformationen für Phrasenabfragen und die technische Umsetzung der Indexpflege, während Komprimierung und Abfrage-Evaluierungsstrategie angrenzenden Themen überlassen werden.

Core questions

• Was enthält ein Wörterbucheintrag und seine Postings-Liste?
• Wie werden Positionen gespeichert, um Phrasen- und Proximity-Abfragen zu unterstützen?
• Wie wird ein invertierter Index aufgebaut, wenn die Sammlung zu groß für den Speicher ist?
• Wie wird ein Index aktualisiert, wenn Dokumente hinzugefügt, geändert oder gelöscht werden?
• Wie unterstützen Postings-Listen eine effiziente Schnittmengenbildung für konjunktive Abfragen?

Key concepts

• Begriffswörterbuch
• Postings-Liste
• Dokument-Identifikatoren
• Positionsindex
• Speicherung der Termhäufigkeit
• blockbasiertes Sortier-Indexing (BSBI)
• Single-Pass-In-Memory-Indexing (SPIMI)
• Indexzusammenführung und -aktualisierungen

Key theories

Organisation von Wörterbuch und Postings

Die Trennung eines kompakten Begriffswörterbuchs von Postings-Listen variabler Länge ermöglicht es dem System, einen Begriff schnell nachzuschlagen und dann nur die relevanten Dokumente zu streamen, was die strukturelle Grundlage jedes Inverted-Index-Retrievals bildet.

Skalierbare Indexkonstruktion

Festplattenbasierte Methoden wie blockbasiertes Sortier-Indexing und Single-Pass-In-Memory-Indexing erstellen invertierte Dateien für Sammlungen, die weit größer als der Speicher sind, indem sie partielle Indizes akkumulieren und zusammenführen.

Clinical relevance

Der invertierte Index ist die zentrale Datenstruktur praktisch aller Textsuchsysteme, einschließlich Web-Suchmaschinen, Open-Source-Suchplattformen wie Lucene und deren Derivate sowie Datenbank-Volltextsuche. Sein Design bestimmt, welche Abfragetypen unterstützt werden und wie schnell und kostengünstig sie beantwortet werden können.

History

Invertierte Dateien wurden in frühen bibliographischen Retrievalsystemen verwendet und entwickelten sich zur Standardstruktur für die Volltextsuche, als die Sammlungen wuchsen. Die Forschung in den 1990er und 2000er Jahren, einschließlich skalierbarer Konstruktionsmethoden wie dem Single-Pass-In-Memory-Indexing, machte es praktikabel, Korpora im Web-Maßstab zu indizieren, und die Struktur bildet heute die Grundlage weit verbreiteter Open-Source-Suchbibliotheken.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Warum wird er als „invertierter“ Index bezeichnet?

Ein normaler (vorwärts gerichteter) Index listet für jedes Dokument die Begriffe auf, die es enthält. Der invertierte Index kehrt diese Zuordnung um, um für jeden Begriff die Dokumente aufzulisten, die ihn enthalten. Diese Inversion ist genau das, was die begriffsbasierte Suche schnell macht.

Wofür wird ein Positionsindex verwendet?

Ein Positionsindex speichert die Positionen, an denen jeder Begriff innerhalb jedes Dokuments vorkommt. Dies ermöglicht es dem System, Phrasenabfragen und Proximity-Abfragen zu beantworten, bei denen die Reihenfolge oder Nähe der Begriffe wichtig ist, anstatt nur zu prüfen, ob die Begriffe irgendwo im Dokument vorkommen.