Bau effizienter und effektiver Metasuchmaschinen
von Daniel Weichert
FU-BerlinWS 03/04
Daniel Weichert FU-Berlin 2
Definition„Eine Meta-Suchmaschine ist eine Suchmaschine, deren wesentliches Merkmal darin besteht, dass sie eine Suchanfrage an mehrere andere Suchmaschinen weiterleitet, die Ergebnisse sammelt und aufbereitet…“ (www.net-lexikon.de)
Global Interface
Search Engine Search EngineSearch Engine
Daniel Weichert FU-Berlin 3
Übersicht (1)
Vorteile von Metasuchmaschinen Generelle Probleme durch unterschiedliche
Suchmaschinen Architektur und Aufbau von MSMs Funktionsweise einzelner MSM-
Komponenten Weitere Herausforderungen
Daniel Weichert FU-Berlin 4
Vorteile von Metasuchmaschinen Erreichung höherer Internet-Abdeckung Vorteile der Skalierbarkeit durch Nutzung
kleinerer (Spezial-)Suchmaschinen Einfachere Benutzung bei „verstreuten
Daten“ Effizienteres Aussortieren nicht relevanter
Dokumente
Daniel Weichert FU-Berlin 5
Übersicht (2)
Vorteile von Metasuchmaschinen Generelle Probleme durch
unterschiedliche Suchmaschinen Architektur und Aufbau von MSMs Funktionsweise einzelner MSM-
Komponenten Weitere Herausforderungen
Daniel Weichert FU-Berlin 6
Generelle Probleme durch unterschiedliche Suchmaschinen Indexierungsmethode Dokument-Term-Gewichtung Anfrage-Term-Gewichtung Vergleichs-Funktion Dokument-Datenbank Dokument-Version Unvergleichbarkeit untereinander und
proprietäres Unwissen
Daniel Weichert FU-Berlin 7
Übersicht (3)
Vorteile von Metasuchmaschinen Generelle Probleme durch unterschiedliche
Suchmaschinen Architektur und Aufbau von MSMs Funktionsweise einzelner MSM-
Komponenten Weitere Herausforderungen
Daniel Weichert FU-Berlin 8
Aufbau einer Metasuchmaschine„Architektur“ (1)
User Interface
Database Selector
1
2
User
Search Engine Search Engine
Daniel Weichert FU-Berlin 9
Aufbau einer Metasuchmaschine„Database Selector“ Auswahl nur sinnvoller Suchmaschinen
bei großer Suchmaschinenzahl bei geringer Anzahl auszugebender Ergebnisse
Ressourceneinsparung bei Anfrage-Weiterleitung in MSM-Umgebung bei Anfrage-Auswertung in Komponenten-
Suchmaschine durch weniger Netz-Verkehr bei Rückgabe-Auswertung in MSM-Umgebung
Daniel Weichert FU-Berlin 10
Aufbau einer Metasuchmaschine„Architektur“ (2)
User Interface
Database Selector
Document Selector
1
2
3
User
3
Search Engine Search Engine
Daniel Weichert FU-Berlin 11
Aufbau einer Metasuchmaschine„Document Selector“ Auswahl zurückzugebender Dokumente
Direkte Beeinflussung der Rückgabe-Anzahl Vergleich gegen einen „Ähnlichkeits-Grenzwert“
Maximale Anzahl sinnvoller Dokumente Minimale Anzahl unnützer Dokumente
Durchführung für jede ausgewählte Suchmaschine
Daniel Weichert FU-Berlin 12
Aufbau einer Metasuchmaschine„Architektur“ (3)
User Interface
Database Selector
Document Selector
Query Dispatcher
Search Engine Search Engine
1
2
3
4
5
User
3
5
Daniel Weichert FU-Berlin 13
Aufbau einer Metasuchmaschine„Query Dispatcher “ Verbindungsaufbau zu Komponenten-
Suchmaschinen HTTP-Anfrage-Methode (GET/POST) Suchanfrage-Format
Verändern der Suchanfrage (Relative) Gewichtung der Anfrage-Terme Anzahl der zurückzugebenden Dokumente
Daniel Weichert FU-Berlin 14
Aufbau einer Metasuchmaschine„Architektur“ (4)
User Interface
Database Selector
Document Selector
Query Dispatcher
Search Engine Search Engine
Result Merger
1
2
3
4
55
6
7
8
User
3
Daniel Weichert FU-Berlin 15
Aufbau einer Metasuchmaschine„Result Merger “ Verschmelzung der Rückgabe-Ergebnisse in
sinnvoller Weise EINE Liste mit Ergebnissen Beachtung der Dokument-Rückgabezahl der
MSM Bewertung (ranking) auf Basis einer globalen
Vergleichsfunktion (gegeben durch MSM)
Daniel Weichert FU-Berlin 16
Aufbau einer Metasuchmaschine„Architektur“ (5)
User Interface
Database Selector
Document Selector
Query Dispatcher
Search Engine Search Engine
Result Merger
1
2
3
4
55
6
7
8
User
3
Daniel Weichert FU-Berlin 17
Übersicht (4)
Vorteile von Metasuchmaschinen Generelle Probleme durch unterschiedliche
Suchmaschinen Architektur und Aufbau von MSMs Funktionsweise einzelner MSM-
Komponenten Weitere Herausforderungen
Daniel Weichert FU-Berlin 18
Einzelne MSM-Komponenten„Übersicht“ (1) Suchmaschinen-Auswahl (database
selection) Dokument-Auswahl (document selection) Ergebnis-Verschmelzung (result merging)
Daniel Weichert FU-Berlin 19
Einzelne MSM-Komponenten„Database Selection“ (1) Auswahl nur nützlicher Datenbanken mit Hilfe
von einfachen Repräsentanten statistischen Repräsentanten lern-basierten Methoden
Daniel Weichert FU-Berlin 20
Database Selection„Einfache Repräsentanten“ (1) Text-Beschreibung des Datenbank-Inhalts Oftmals manuell erstellt Vergleich Anfrage – Beschreibung Verschiedene Techniken
Beschreibung des DB-Inhalts Fachgebiets-Angabe plus Anfrage Restrukturierung der Anfrage Automatisch erstellte Repräsentanten (Bsp.:
Termvektoren als Repräsentanten)
Daniel Weichert FU-Berlin 21
Database Selection„Einfache Repräsentanten“ (2)
ALIWEB
Template-Type: DOCUMENTTitle: PerlURI: /public/perl/perl.htmlDescription: Information on the Perl
Programming Language. Includes a local Hypertext Perl Manual, and the latest FAQ in Hypertext.
Keywords: perl, perl-faq, languageAuthor-Handle: [email protected]
NetSerf
topic: countrysynset: [nation,
nationality, land, country, a_people]
synset: [state, nation,country, land,common-wealth, res_publica,body_politic]
synset: [country, state, land, nation]
info-type: facts
Beispiele:
Daniel Weichert FU-Berlin 22
Database Selection„Einfache Repräsentanten“ (3) Vorteile
Einfache Handhabung Ressourcenschonend Einsetzbar bei hoch spezialisierten Datenbanken
Nachteile Datenbank-Beschreibung unzureichend Eventuell Eingriff des Nutzers nötig bei DB-
Auswahl Nicht gut einsetzbar bei umfassenden DB
Daniel Weichert FU-Berlin 23
Einzelne MSM-Komponenten„Database Selection“ (2) Auswahl nur nützlicher Datenbanken mit Hilfe
von einfachen Repräsentanten statistischen Repräsentanten lern-basierten Methoden
Daniel Weichert FU-Berlin 24
Database Selection„Statistische Repräsentanten“ (1) Nutzung detaillierter Informationen einer KSM
über Dokument-Frequenz jedes Terms über Durchschnitts-Gewicht eines Terms über alle
Dokumente … Vorteil
Hohe Genauigkeit in Bestimmung der Ähnlichkeiten von Dokumenten zu einer Anfrage in einer KSM
Nachteil Skalierbarkeit nicht immer optimal
Daniel Weichert FU-Berlin 25
Database Selection„Statistische Repräsentanten“ (2) Methoden
Relative KSM-Bewertung Relativer KSM-Ranking-Wert
Absolute KSM-Bewertung Unabhängiger Ranking-Wert
Schätzung der Anzahl nützlicher Dokumente Schätzung der globalen Ähnlichkeit des der
Anfrage am ähnlichsten Dokumentes
Daniel Weichert FU-Berlin 26
Statistische Repräsentanten „Ähnlichstes Dokument“ (1) Definition:
Eine Menge von M Datenbanken ist optimal gewichtet [D1, D2, …, DM], wenn es ein k gibt, sodass D1, D2, …, Dk die m ähnlichsten Dokumente beinhalten und jede Di (1<= i <= k) mindestens eines der m Dokumente enthält.
Bedingung: msim(q, D1) > msim(q, D2) > …msim(q, Di) = Globaler Vergleichswert des der
Anfrage ähnlichsten Dokumentes Auswahl der ersten k KSMs
Daniel Weichert FU-Berlin 27
Statistische Repräsentanten„Ähnlichstes Dokument“ (2) Bestimmung von msim(q, D):
Zwei Repräsentanten Global: Globales inverses Dokument-Frequenz-Gewicht
gidfi für jeden Term ti
Lokal: Wertepaar (mnwi, anwi) mit
mnwi = Maximales normalisiertes Gewicht von t i
anwi = Durchschnittliches normalisiertes Gewicht von t i
Normalisiertes Gewicht = di / |d|
di = Gewicht von Term ti in Dokument d
|d| = Länge von Dokument d
Daniel Weichert FU-Berlin 28
Statistische Repräsentanten„Ähnlichstes Dokument“ (3) Anfrage-Vektor q = (q1, q2, …, qk)
msim(q, D) =
Links: Anfrage-ähnlichstes Dokument hat Maximumgewicht des i-ten Anfrage-Terms
/ |q|: Normalisierung von msim Sortierung der KSMs nach msim(q, D)
Daniel Weichert FU-Berlin 29
Statistische Repräsentanten„Ähnlichstes Dokument“ (4) Einfache Anpassung bei Wort-
zusammenhängen Maximales normalisiertes Gewicht dominiert
üblicherweise um 2 oder mehr Ordnungen wegen Einberechnungen der Null-Werte im
durchschnittlichen Gewicht Einschränkung der Formel für msim(q, D) auf
msim(q, D) = max1<=i<=k {qi * ami} mit
ami = gidfi * mnwi [Angepasstes normalisiertes Gewicht]
Daniel Weichert FU-Berlin 30
Einzelne MSM-Komponenten„Database Selection“ (3) Auswahl nur nützlicher Datenbanken mit Hilfe
von einfachen Repräsentanten statistischen Repräsentanten lern-basierten Methoden
Daniel Weichert FU-Berlin 31
Database Selection„Lern-basierte Methoden“ Nutzenbestimmung einer Datenbank durch
Erfahrungswerte Verschiedene Techniken
Statisches Lernen MRDD (modeling relevant document distribution)
Dynamisches Lernen Ranking-Wert-Bestimmung u.a. durch „Maus-Klicks“
Kombination aus statischem und dynamischem Lernen
Daniel Weichert FU-Berlin 32
Statisches Lernen„MRDD“ (1) Bilden einer Menge von Trainings-Anfragen Weiterleitung der T-Anfragen an alle KSM Bilden eines Verteilungs-Vektors aus
relevanten Dokumenten pro T-Anfrage und KSM Identifikation der relevanten Dokumente aus
Rückgabeliste Aufbau: Pro VV-Dimension Anzahl zu holender
Dokumente für nächstes relevantes Dokument
Daniel Weichert FU-Berlin 33
Statisches Lernen„MRDD“ (2) Vergleich Benutzer-Anfrage/Trainings-
Anfragen Bestimmung der k ähnlichsten T-Anfragen Pro KSM Errechnung eines Durchschnitts-
Verteilungs-Vektors der k T-Anfragen Nutzung dieser Durchschnittsvektoren zur
KSM-Auswahl mit Blick auf Precision-Maximierung
Daniel Weichert FU-Berlin 34
Statisches Lernen„MRDD“ (3) Beispiel (Aufbau eines Verteilungsvektors):
Für T-Anfrage wurden 100 Dokumente in KSM gefunden
(d1, d2, …, d100) [in dieser Reihenfolge]
Relevante Dokumente: d1, d6, d20, d88
Verteilungsvektor: {1, 6, 20, 88}
Daniel Weichert FU-Berlin 35
Statisches Lernen„MRDD“ (4) Beispiel-Fortsetzung (KSM-Auswahl):
Durchschnitts-Vektoren:
D1: {1, 4, 6, 7, 10, 12, 17}
D2: {3, 5, 7, 9, 15, 20}
D3: {2, 3, 6, 9, 11, 16}
Anzahl auszugebender Dokumente:
m = 3
Dokumentzahl pro KSM:
m1 = 1; m3 = 3 => Precision = 0,75
KSM-Auswahl:
D1, D3
Daniel Weichert FU-Berlin 36
Suchmaschinen-Auswahl„Zusammenfassung“ Einfache Repräsentanten Statistische Repräsentanten
„Ähnlichstes Dokument“ Lern-basierte Methoden
MRDD
Daniel Weichert FU-Berlin 37
Einzelne MSM-Komponenten„Übersicht“ (2) Suchmaschinen-Auswahl (database
selection) Dokument-Auswahl (document selection) Ergebnis-Verschmelzung (result merging)
Daniel Weichert FU-Berlin 38
Einzelne MSM-Komponenten„Document Selection“ Einschränkung der Ergebnis-Dokumenten-
Anzahl Entscheidung durch Benutzer (Datenbank-)Gewichtete Auswahl Lern-basierte Methoden Garantierte Rückgabe (guaranteed retrieval)
Daniel Weichert FU-Berlin 39
Document Selection„Benutzer-Entscheidung“ Benutzer-Entscheidung über Maximalanzahl
der Rückgabe-Dokumente pro KSM
Vorteil Einfachst-Implementierung
Nachteile Nur bei kleiner KSM-Zahl und großem Wissen
über selbige günstig Uneffektiv, wenn Dokument-Anzahl pauschal
angegeben (pro KSM Dokumente)
Daniel Weichert FU-Berlin 40
Document Selection„Gewichtete Auswahl“ Mehr Dokumente von gewichtigeren (nach
‚database selection‘) KSM Basierend auf ‚ranking score‘ oder ‚db rank‘
Vorteile Einfache Implementierung Vernünftige Grundlage
Nachteil Möglicherweise zu wenig nützliche Dokumente
Daniel Weichert FU-Berlin 41
Document Selection„Lern-basierte Methoden“ Rückblick auf Retrieval-Erfahrungen
MRDD (modeling relevant document distribution) QC (query clustering)
Daniel Weichert FU-Berlin 42
Document Selection„Lern-basiertes Query Clustering“ (1) Trainingsphase mit „Übungs-Anfragen“ Clustering dieser Anfragen innerhalb jeder
KSM
T-Anfrage 1
T-Anfrage 2
T-Anfrage 4
T-Anfrage 3
T-Anfrage 5
Dokument A, Dokument C, Dokument D
Dokument B, Dokument C, Dokument D
Dokument E, Dokument F, Dokument G
Dokument E, Dokument H, Dokument I
Dokument E, Dokument F, Dokument I
T-Anfrage 1T-Anfrage 2
T-Anfrage 3T-Anfrage 5
Anfragen Rückgabe-Dokumente Cluster
T-Anfrage 4T-Anfrage 5
Daniel Weichert FU-Berlin 43
Document Selection„Lern-basiertes Query Clustering“ (2) Bilden des Durchschnittsvektors (centroid)
der Anfrage-Vektoren pro Cluster Gewichtung der Cluster auf Basis
der Durchschnitts-Anzahl der relevanten Dokumente
aus den besten T ausgegebenen Dokumenten
Clustergewicht ~ ‚Precision‘ der Anfragen innerhalb des Clusters
Daniel Weichert FU-Berlin 44
Document Selection„Lern-basiertes Query Clustering“ (3) Wahl des Clusters pro KSM nach Ähnlichkeit
mit Benutzer-Anfrage m.H. des ‚centroid‘ Nutzung aller ausgewählten Cluster-
Gewichtungen zur Dokument-Auswahl
Dokumentanzahl aus KSM Di =
m = Gesamtzahl zurückzugebender Dokumentewi = Gewicht des Anfrage-Clusters von Di
N = Anzahl der KSMs
Daniel Weichert FU-Berlin 45
Document Selection„Lern-basiertes Query Clustering“ (4) Vorteile
Gute Ergebnisse bei großer Ähnlichkeit von Trainings- und Benutzer-Anfragen
Nachteile Schlechte Anpassungsfähigkeit des Verfahrens Schwierige Auswahl der Trainings-Anfragen Großer Zeitaufwand beim Filtern der relevanten
Dokumente bei hoher Zahl von Trainings-Anfragen
Daniel Weichert FU-Berlin 46
Document Selection„Garantierte Rückgabe“ Mitbetrachtung der globalen Vergleichsfunktionen
Umgehung von KSM-Unterschiedlichkeits-Problemen Effektivitäts-Steigerung bei Filterung nützlicher und
unnützer Dokumente Ziel: Rückgabe aller nützlichen bei Minimierung von
nutzlosen Dokumenten Methoden
Anfrage-Modifikation Berechnung des kleinsten lokalen Grenzwertes
Daniel Weichert FU-Berlin 47
Garantierte Rückgabe„Anfrage-Modifikation“ Veränderung der Anfrage vor Weiterleitung
an KSM Ziel: Rückgabe der KSM-Dokumente in
Reihenfolge der globalen Ähnlichkeiten Nachteile
Nicht jede Kombination von lokalen und globalen Vergleichs-Funktionen möglich
Wissen über Vergleichs-Funktion und Term-Gewichtungs-Formel nötig
Daniel Weichert FU-Berlin 48
Garantierte Rückgabe„Kleinster lokaler Grenzwert“ Finden eines Ähnlichkeits-Grenzwertes pro
KSM, bei dem alle relevanten Dokumente ausgegeben werden keine unnützen Dokumente zurückgegeben
werden Nachteile
Lösungsfindung für jedes Globale-Lokale-Vergleichsfunktions-Paar einzeln
Lösung existiert nicht immer
Daniel Weichert FU-Berlin 49
Dokument-Auswahl„Zusammenfassung“ Benutzer-Entscheidung Gewichtete Auswahl Lern-basierte Methoden
Query Clustering Garantierte Rückgabe
Daniel Weichert FU-Berlin 50
Einzelne MSM-Komponenten„Übersicht“ (3) Suchmaschinen-Auswahl (database
selection) Dokumenten-Auswahl (document selection) Ergebnis-Verschmelzung (result merging)
Daniel Weichert FU-Berlin 51
Einzelne MSM-Komponenten„Result Merging“ (1) Verschmelzung der Such-Ergebnisse in
eine Liste mit Bewertungen nach globaler Ähnlichkeit
Schwierigkeiten KSM-Ranking mit eigener Vergleichsfunktion Ähnlichkeitswert nicht unbedingt öffentlich Mehrfache Rückgabe von Dokumenten
Daniel Weichert FU-Berlin 52
Einzelne MSM-Komponenten„Result Merging“ (2) Lokale Ähnlichkeits-Anpassung
Nutzung zusätzlicher Informationen (KSM-Bewertung o.ä.)
Umwandlung von Dokument-Rang in Vergleichswert
Globale Ähnlichkeits-Schätzung Berechnung oder Schätzung globaler Vergleichswerte von
Dokumenten
Daniel Weichert FU-Berlin 53
Result Merging„Local Similarity Adjustment“ (1) Überlappungs-Möglichkeiten
Keine Überlappungen -> KSMs paarweise disjunkt
Überlappungen, aber KSMs nicht identisch KSMs sind identisch
‚Data Fusion‘ – Nutzung verschiedener Ranking-Methoden für höhere Rückgabe-Effektivität
Ergebnis-Findung durch Anwendung einfacher Funktionen (max, Summe, …)
Tritt nicht in MSMs auf
Daniel Weichert FU-Berlin 54
Result Merging„Local Similarity Adjustment“ (2) Einfach bei gegebenen lokalen
Vergleichswerten Normalisierung der Vergleichswerte (0 < s <= 1) Bsp.:
sd = Lokaler Vergleichswert von Dokument d
wD = Ranking-Wert von KSM D
Daniel Weichert FU-Berlin 55
Result Merging„Local Similarity Adjustment“ (3) Nutzung des Dokument-Ranges ohne lokalen
Vergleichswert Direkte Nutzung des Dokument-Ranges Umwandlung von Dokument-Rängen in
Vergleichswerte
Daniel Weichert FU-Berlin 56
Result Merging„Local Similarity Adjustment“ (4) Direkte Nutzung des Dokument-Ranges
Reihum nächst bestes Dokument der nächst besten KSM in Liste einfügen
„Zufällige“ Auswahl (MRDD KSM-Auswahl) Umwandlung von Dokument-Rängen
r = Lokaler Dokument-Rang
ri = Ranking-Wert von KSM Di
rmin = Niedrigster KSM-Ranking-Wert
m = Anzahl aller auszugebender Dokumente
Daniel Weichert FU-Berlin 57
Result Merging„Local Similarity Adjustment“ (5) Problem: Vorhandensein eines Dokumentes
in mehreren KSMs Lösungen
Durchführung von LSA-Verfahren danach Ergebnis-Behandlung wie in Pro-Fusion
Nicht unbedingt sinnvoll bei MSM KSM sieht Dokument nicht als sinnvoll an Dokument eventuell in KSM nicht vorhanden
Forschungsgebiet
Daniel Weichert FU-Berlin 58
Result Merging„Global Similarity Estimation“ Berechnung oder Schätzung von globalen
Vergleichswerten Dokument-Download (document fetching) Nutzen von „gefundenem Wissen“
Herausfinden von Indizierungs-Methode und Vergleichs-Funktion möglich
Wissen über Vergleichbarkeit von Vergleichsfunktionen, Anpassungs-Möglichkeiten von Vergleichsfunktionen, Bewertung von lokalen Vergleichsfunktionen in Hinblick
auf die globalen
Daniel Weichert FU-Berlin 59
Global Similarity Estimation„Document Fetching“ (1) Dokument wird normalerweise nicht
„mitgeliefert“ URL höchstens eine Zusammenfassung
Download der KSM-Dokumente Errechnung sämtlicher globaler Vergleichs-
Funktionsparameter möglich (Kosinus-Funktion) Globale Dokument-Frequenz ist Summe aller
lokalen Dokument-Frequenzen (bei wenig Überlappung)
Daniel Weichert FU-Berlin 60
Global Similarity Estimation„Document Fetching“ (2) Vorteile
Herausfiltern von nicht erreichbaren URLs Ranking auf Basis aktueller Dokumente Markierung der Suchwörter möglich
Nachteile Zeit- und Ressourcenaufwendig
Viele Dokumente (aber paralleles Downloaden) Große Dokumente (aber nur Download des
Dokumentanfangs)
Daniel Weichert FU-Berlin 61
Ergebnis-Verschmelzung„Zusammenfassung“ Lokale Vergleichswert-Anpassung Globale Vergleichswert-Schätzung
Daniel Weichert FU-Berlin 62
Übersicht
Vorteile von Metasuchmaschinen Generelle Probleme durch unterschiedliche
Suchmaschinen Architektur und Aufbau von MSMs Funktionsweise einzelner MSM-
Komponenten Weitere Herausforderungen
Daniel Weichert FU-Berlin 63
Weitere Herausforderungen (1) Integration lokaler Systeme mit
verschiedenen Indexierungsmethoden Integration lokaler Systeme mit
verschiedenen Anfrage-Mustern Informationsfindung zu Komponenten-
Suchmaschinen Effektivere Ergebnis-Verschmelzung Zusammenarbeit von MSM und
Komponenten-Suchmaschinen
Daniel Weichert FU-Berlin 64
Weitere Herausforderungen (2) Neue Indexierungs- und
Gewichtungsmethoden Verbesserung der Effektivität der Metasuche Verteilung der MSM-Komponenten Standard-Fälle für Tests von „database
selection“, „document selection“ und „result merging“
Daniel Weichert FU-Berlin 65
Zusammenfassung
Aufbau einer Metasuchmaschine MSM-Bauteil-Funktionen
Database Selector Document Selector Result Merger
Daniel Weichert FU-Berlin 66
Quellenangaben
Weiyi Meng, Clement Yu, King-Lup Liu “Building efficient and effective metasearch engines” (ACM Computing Surveys, Volume 34 Issue 1. March 2002)
www.net-lexikon.de