Abfrageverarbeitung und -optimierung

Abfrageverarbeitung ist die Menge von Algorithmen, die einen invertierten Index durchlaufen, um eine Abfrage auszuwerten, und Optimierungstechniken beschleunigen dies, indem sie unnötige Arbeit vermeiden.

Definition

Abfrageverarbeitung und -optimierung ist der Entwurf von Algorithmen, die die übereinstimmenden oder am höchsten bewerteten Dokumente für eine Abfrage durch das Durchlaufen invertierter Postings berechnen, zusammen mit den Beschneidungs- und Ordnungsverfahren, die die Anzahl der bewerteten Dokumente und gelesenen Postings minimieren, ohne das Ergebnis zu verändern (oder während die Änderung des Ergebnisses begrenzt wird).

Scope

Dieses Thema behandelt, wie Abfragen effizient anhand eines invertierten Index ausgewertet werden: Postings-Listen-Schnittmenge und -Zusammenführung für Boolesche Abfragen, Dokument-für-Dokument- und Term-für-Term-Strategien für die Rangfolgen-basierte Suche sowie Top-k-Optimierung durch dynamische Beschneidungsalgorithmen wie MaxScore und WAND, die Dokumente überspringen, die nicht in die Top-Ergebnisse gelangen können. Es behandelt Sprungzeiger, Abfrage-Neuordnung und gestufte oder zweistufige Retrieval-Verfahren, wobei der Fokus auf der algorithmischen Effizienz der Ergebnisrückgabe liegt und nicht auf dem Ranking-Modell oder der Indexkodierung.

Core questions

• Wie werden Postings-Listen geschnitten oder zusammengeführt, um Boolesche und Rangfolgen-basierte Abfragen auszuwerten?
• Was ist der Unterschied zwischen der Dokument-für-Dokument- und der Term-für-Term-Auswertung?
• Wie können die Top-k-Ergebnisse gefunden werden, ohne jedes Kandidatendokument vollständig zu bewerten?
• Wie überspringen dynamische Beschneidungsverfahren wie MaxScore und WAND Dokumente sicher?
• Wie reduzieren Sprungzeiger und Abfrage-Neuordnung den Arbeitsaufwand?

Key concepts

• Postings-Schnittmenge und -Zusammenführung
• Dokument-für-Dokument-Auswertung
• Term-für-Term-Auswertung
• Top-k-Retrieval
• dynamische Beschneidung (MaxScore, WAND)
• Sprungzeiger
• Neuordnung von Abfragetermen
• zweistufiges / gestuftes Retrieval

Key theories

Dokument-für-Dokument- vs. Term-für-Term-Auswertung

Die Rangfolgen-basierte Suche kann die Postings aller Abfrageterme in Dokumentreihenfolge durchlaufen, wobei die Bewertung jedes Dokuments sofort akkumuliert wird, oder die Postings eines Terms vollständig verarbeiten, bevor der nächste Term bearbeitet wird; die Wahl beeinflusst den Speicherverbrauch, Beschneidungsmöglichkeiten und das Cache-Verhalten.

Dynamische Beschneidung für Top-k-Retrieval

Durch die Beibehaltung der Bewertung des aktuell k-besten Dokuments und die Verwendung von maximalen Bewertungsgrenzen pro Term überspringen Algorithmen wie MaxScore und WAND Dokumente, die nachweislich nicht in die Top-k gelangen können, und liefern die gleichen Rangfolgen-Ergebnisse wesentlich schneller.

Clinical relevance

Eine effiziente Abfrageverarbeitung ermöglicht interaktive Suchen mit geringer Latenz über Milliarden von Dokumenten. Dynamische Beschneidungstechniken wie WAND werden in weit verbreiteten Suchmaschinen und Open-Source-Suchbibliotheken implementiert und steuern direkt die Antwortzeit und die Betriebskosten im großen Maßstab.

History

Grundlegende Strategien und Optimierungen zur Abfrageauswertung wurden 1995 von Turtle und Flood systematisiert. Mit der Skalierung der Websuche wurde die Top-k-Optimierung entscheidend, und der WAND-Algorithmus von Broder und Kollegen im Jahr 2003 popularisierte die sichere dynamische Beschneidung. Nachfolgende blockbasierte Varianten beschleunigten die Auswertung weiter, und diese Methoden sind heute Standard in Retrieval-Engines in der Produktion.

Key figures

• Howard Turtle
• Andrei Z. Broder
• David Carmel
• W. Bruce Croft

Seminal works

• turtle1995
• broder2003
• manning2008

Frequently asked questions

Was ist Top-k-Retrieval?

Top-k-Retrieval bedeutet, nur die k am höchsten bewerteten Dokumente für eine Abfrage zurückzugeben, anstatt die gesamte Sammlung zu bewerten und zu ranken. Da Benutzer nur die ersten Ergebnisse sehen, nutzen Systeme dies aus, um Dokumente zu überspringen, die es nicht in die Top k schaffen können, was erheblichen Arbeitsaufwand spart.

Sind Beschneidungsmethoden wie WAND verlustfrei?

In ihrer grundlegenden sicheren Form ja: MaxScore und WAND überspringen nur Dokumente, die nachweislich nicht in die Top-k gelangen können, sodass sie genau die gleichen Rangfolgen-Ergebnisse wie eine erschöpfende Bewertung liefern, nur schneller. Approximative Varianten tauschen ein geringes Maß an Genauigkeit gegen zusätzliche Geschwindigkeit ein.