TopX [Elektronische Ressource] : efficient and versatile top-k query processing for text, structured, and semistructured data / Martin Theobald

Sujets

• Informatik

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2006
• Nombre de lectures: 42
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

TopX
Efficient and Versatile
Top-k Query Processing for
Text, Structured, and Semistructured Data
Martin Theobald
Max-Planck-Institut für Informatik
Saarbrücken
April 2006
Dissertation
zur Erlangung des Grades
Doktor der Ingenieurwissenschaften (Dr.-Ing.)
der Naturwissenschaftlich-Technischen Fakultät I
der Universität des SaarlandesDekan der Naturwissenschaftlich-Technischen Fakultät I Prof. Dr. Thorsten Herfet
Vorsitzender der Prüfungskommission Prof. Dr. Christoph Koch
Erstgutachter Prof. Dr. Gerhard Weikum
Zweitgutachter Prof. Dr. Norbert Fuhr
Zwhter Prof. Dr. Michalis Vazirgiannis
Wissenschaftlicher Begleiter Dr. Ralf Schenkel
Tag des Promotionskolloquiums 16. Mai 2006Kurzfassung
TopX ist eine Top-k Suchmaschine für Text und XML Daten. Im Gegensatz
zu Boole’ schen Suchmaschinen terminiert TopX die Anfragebearbeitung,
sobald die k besten Ergebnisobjekte im Hinblick auf eine mehrdimensionale
Anfrage gefunden wurden. Die Hauptbeiträge dieser Arbeit teilen sich in
vier Schwerpunkte basierend auf vorherigen Veröffentlichungen bei interna-
tionalen Konferenzen oder Workshops:
• Top-k Anfragebearbeitung mit probabilistischen Garantien.
• Zugriffsoptimierte Top-k Anfragebearbeitung.
• Dynamische und selbstoptimierende, inkrementelle Anfrageexpansion
für Top-k Anfragebearbeitung.
• Effiziente Unterstützung für XML-Anfragen und Volltextsuche.
Unsere Experimente bestätigen die Vielseitigkeit und gesteigerte Effizienz un-
serer Verfahren gegenüber existierenden, führenden Ansätzen für eine weite
Bandbreite von Anwendungen in der Informationssuche.Abstract
TopX is a top-k retrieval engine for text and XML data. Unlike Boolean
engines, it stops query processing as soon as it can safely determine the
k top-ranked result objects according to a monotonous score aggregation
function with respect to a multidimensional query. The main contributions
of the thesis unfold into four main points, confirmed by previous publications
at international conferences or workshops:
• Top-k query processing with probabilistic guarantees.
• Index-access optimized top-k query processing.
• Dynamic and self-tuning, incremental query expansion for top-k query
processing.
• Efficient support for ranked XML retrieval and full-text search.
Our experiments demonstrate the viability and improved efficiency of our
approach compared to existing related work for a broad variety of retrieval
scenarios.Zusammenfassung
Top-k Anfragen basierend auf dem Erstellen von nach Relevanz sortierten
Ergebnislisten für mehrdimensionale Datensätze sind ein fundamentaler Bau-
stein für viele Arten der Informationssuche, wobei die Anwendungen von Text
und Datenintegration bis zur verteilten Aggregation von Netzwerkprotokollen
und Sensordaten reichen. The Top-k-Anfrageszenarien, die in dieser Arbeit
untersucht werden, arbeiten auf vorausberechneten, invertierten Indexlis-
ten für die elementaren Bedingungen einer Anfrage und aggregieren die ele-
mentaren Relevanzwerte der Ergebniskandidaten zu einem Gesamtrelevanz-
wert. Eine der effizientesten und vielseitigsten Implementierungsmethoden
in diesem Kontext ist Fagin’s Familie der Schwellwertalgorithmen, die darauf
zielen, die Indexzugriffe so früh wie möglich zu terminieren, basierend auf un-
teren und oberen Schranken für den schließlichen Gesamtwert eines Kandi-
daten. Im Gegensatz zu Boole’schen Auswertungsmodellen profitieren diese
fortgeschrittenen Verfahren von einer nicht-konjunktiven Auswertungsstrate-
gie, bei der ein Ergebniskandidat schwache Übereinstimmungen einiger An-
fragebedingungen (einschließlich keiner Übereinstimmung) durch starke Tref-
fer für andere Anfragebedingungen ausgleichen kann. Diese Arbeit präsen-
tiert eine neuartige Suchmaschine, genannt TopX, für die effiziente Anfrage-
evaluation von Text, strukturierten und semistrukturierten (XML) Daten.
Der Kern des TopX Anfragebearbeiters integriert und erweitert unterschied-
liche, existierende Verfahren auf signifikante Art zur kostenbewussten In-
dexzugriffssteuerung in einer flexiblen Mehrprozessarchitektur.
Da das Ziel eines Benutzers beim Stellen einer Top-k-Anfrage typischer-
weise darin liegt, eine oder mehrere neue Informationseinheiten zu entdecken,
besteht eine faszinierende Idee darin, approximative Top-k-Verfahren zu ent-
wickeln, um die Ausführungskosten einer solchen Anfrage weiter zu senken.
TopX stellt daher eine Reihe von approximativen Algorithmen basierend
auf probabilistischen Argumenten vor und ermöglicht dadurch großartige
Laufzeitgewinne mit einem geringen und kontrollierbaren Verlust an Ergeb-
nispräzision. Beim Einlesen der Indexlisten des zugrunde liegenden Daten-
raumes in absteigender Reihenfolge der lokalen Ränge werden verschiedene
Arten von Verteilungsfaltungen und daraus abgeleiteten Schranken unter-
sucht, um vorherzusagen, wann es mit hoher Wahrscheinlichkeit sicher ist,
2Ergebniskandidaten zu löschen und den Einlesevorgang frühzeitig abzubre-
chen. Unser Ansatz umfasst effizient berechenbare, geschlossene Formen
von Verteilungsfaltungen für parametrisierte Verteilungen wie Poission, viel-
seitige probabilistische Garantien mit momentgenerierenden Funktionen und
Chernoff-Hoeffding-Schranken, sowie flexible Histogramme, die dazu benutzt
werden können, beliebige Verteilungen zu approximieren.
Die grundlegende Anfrageauswertung führt effiziente sequentielle Indexzu-
griffe aus, hat aber auch die Option, gezielte randomisierte Zugriffe für aus-
gewählte Kandidatenobjekte auszulösen, um deren schließlichen Gesamtrele-
vanzwert direkt zu ermitteln. Diese Auswertungsstrategie beinhaltet also die
zielgesteuerte Planung von zwei Arten von Indexzugriffen, nämlich 1) die un-
terschiedliche Priorisierung der Indexlisten in den sequentiellen Zugriffen und
2) die Entscheidung, wann und für welche Kandidaten ein randomisierter Zu-
griff ausgelöst werden soll. In der bisher existierenden Literatur wurden diese
beiden Aspekte nur einzeln und für spezialisierte Umgebungen untersucht.
Diese Arbeit vermittelt eine integrierte Untersuchung dieser Zugriffsstrate-
gien und entwickelt neue Methoden, die die bisherigen Verfahren deutlich
verbessern. Unsere Hauptbeiträge in diesem Zusammenhang sind grundle-
gend neue Ansätze basierend auf einer dem Rucksack-Problem abgeleiteten
Optimierung von sequentiellen Zugriffen und ein probabilistisches Kosten-
modell für die Steuerung randomisierter Zugriffe. Unsere Verfahren können
durch die Einbeziehung unseres probabilistischen Schätzers, unterschiedlicher
Selektivitäten, sowie Korrelationen von Indexlisten weiter verfeinert werden.
Desweiteren präsentiert diese Arbeit ein neues Verfahren zur dynami-
schen und selbstoptimierenden Anfrageexpansion, das ebenfalls in unsere
Top-k-Auswertungsstrategie eingebettet ist. Traditionelle Expansionstech-
niken wählen Expansionsterme deren thematische Ähnlichkeit zu dem ur-
sprünglichen Term über einem bestimmten Schwellwert liegt und generie-
ren dadurch eine disjunktive Anfrage von deutlich höherer Dimensionalität.
Dies führt häufig zu den folgenden drei Problemen: 1) der Schwellwert muss
manuell eingestellt werden, 2) die Gefahr, dass das ursprüngliche Thema
der Anfrage durch zu aggressive Expansion zunehmend verwischt wird, und
3) die drastisch erhöhten Ausführungskosten einer hochdimensionalen An-
frage. Unsere Methoden adressieren diese drei Schwerpunkte, indem die
invertierten Indexlisten zu einer Menge von Expansionstermen dynamisch
und inkrementell Verschmolzen werden. Eine Prioritätsschlange wird zur
effizienten Verwaltung der Kandidaten verwendet, und das frühzeitige Eli-
minieren von schwachen Kandidaten basiert entweder auf dem konservativen
Schwellwertverfahren der ursprünglichen Top-k-Algorithmen oder wiederum
auf probabilistischen Argumenten. Die vorgestellten Algorithmen werden
eingebettet in zwei neuartige, spezialisierte Anfrageoperatoren.
3Für die effiziente Erstellung von Ergebnisranglisten von XML Dokumenten
über semistrukturierten aber nicht-schematischen Datensammlungen ist TopX
in der Lage, die effiziente Form der Indexzugriffssteuerung mit einem Großteil
an effizienten sequentiellen Zugriffen und nur einigen wenigen, kontrollierten
randomisierten Zugriffen beizubehalten und um ein XML-spezifisches Kosten-
modell zu erweitern, was eine einzigartige Charakteristik im Bereich der Top-
k-Anfragebearbeitung für XML Daten ist. Die Schwierigkeiten, die beste-
henden Top-k-Verfahren auf XML Daten zu übertragen bestehen darin, 1)
Relevanzwerte für einzelne XML Elemente zu betrachten, diese aber auf der
Dokumentebene zu aggregieren, 2) eine vage Interpretation der XML In-
halte mit strukturellen Bedingungen zu kombinieren, 3) einzelne Anfragebe-
dingungen dynamisch zu lockern, falls zu wenige Ergebnisse alle Bedingun-
gen erfüllen, sowie 4) die Anpassung der Selektivitätsschätzung sowohl für
textuelle als auch strukturelle Inhalte und deren Einfluss auf die Auswer-
tungsstrategien. TopX adressiert diese Anforderungen durch die gezielt