Caching for Web Search

Caching for Web Search
1
AMIR KHEIRKHAHAN
SEMINAR EFFIZIENTE ARCHITEKTUREN UND METHODE FÜR
I N F O R M AT I O N S S Y S T E M E S S 1 0
BETREUER: DIPL.-INFORM. MARC LECHTENFELD
Universität Duisburg-Essen
Fakultät für Ingenieurwissenschaften
Abteilung für Informatik und Angewandte Kognitionswissenschaft
Prof. Dr. –Ing. Norbert Fuhr
Inhalt
2
• Motivation
• Einführung
• Caching-Methode
• Aktualisierungsproblem
• Fazit
• Literatur
Motivation
3
Viele tägliche Suchanfragen an Suchmaschinen in Internet
Erwartung von einer
kurzen Antwortzeit
Das Ziel ist Einsatz eines Speichers zur Beschleunigung der
Berechnung und Rückgabe der Ergebnisse
Einführung
4
Einführung
5
Suchmaschine :
IR(Information Retrieval) Systeme, als Eingabe eine Anfrage
und als Ergebnis eine Menge von relevanten Dokumente
(Internetseiten)
Caching :
Die Speicherung von Web-Dateien für eine spätere
Wiederverwendung zur Beschleunigen des Suchvorgangs
Einführung Caching-Arten
6
1) Caching von Ergebnisse :
- Speicherung der Ergebnisse zum späteren Anfragen
2) Caching von Anfrage-Terme:
- Speicherung der Invertierten Liste der beteiligten
Suchterme
- Speicherung aller invertierten Liste im Cache ist nicht
Effizient.
Einführung Caching-Arten
7
1) Caching von Ergebnisse :
Speicherung der Liste von Dokumenten
bezüglich der angegebenen Anfrage im Cache
zum wieder gestellten Anfragen
Beispiel: Für jeden Dokument wird
URL , Titel, und 250 Zeichen gespeichert
Einführung Caching-Arten
8
2) Caching von Anfrage Termen :
Speicherung der Liste von Webdokumente im Bezug auf
angegebene Anfrageterme
Die Größe von diesen Listen ist von zwei Faktoren abhängig :
Wie beliebt ist ein Term in der ganzen Sammlung
Die Anzahl der indexierten Dokumente
Problem: Für die großen Sammlungen könnte diese Liste sehr
riesig sein.
Lösungsvorschlag : filtered vector model processing
Einführung Caching von Anfrage-Termen
9
o Invertierte Liste haben variabel Länge
o Auswahl der besten Liste zur Speicherung anhand der
verschiedenen Algorithmen :
1) Statische Algorithmen
QTF ,QTFDF
2) Dynamische Algorithmen
LRU,LFU, dynamische QTFDF
Einführung Caching von Anfrage-Termen
Notation
10
Notationen:
Annahme zur Beschreibung dieser Algorithmen :
fq(t)
: die Anzahl der Anfragen im Anfrage-Log, die den Term
t enthalten
fd(t) : die Anzahl der Dokumente in der ganzen Sammlung, in
den Term t erscheinen
f q (t )
Das Verhältnis W=
ist eine Kriterium zur Auswahl der
f (t )
invertierten Liste d
Einführung Caching von Anfrage-Termen
Statische Algorithmen
11
1) Statischen Algorithmen :
i) QTF
Die Terme mit höhen fq(t) sollten im Cache bleiben
Die Terme mit höhen fd(t) sind wegen langer Liste nicht
geeignet für den Cache
ii) QTFDF
Anhand Rucksack Problem :
-Auswahl der Terme mit höchstem Wert von W
Einführung Caching von Anfrage-Termen
Dynamische Algorithmen
12
2) Dynamischen Algorithmen :
I.
LRU (Least Recent Usage)
Viele Liste sollen wegen der mangelnden Speicherplatz
weggelassen werden
II. LFU (Least Frequently Used).
Dyn- QTFDF
Die Terme, die das geringste W besitzen, werden
aus dem Cache hinausgeworfen.
III.
Einführung Caching von Anfrage-Termen
Vergleich
13
Vergleich :
Die statische QTFDF hat
bessere Trefferrate als die
andere Methode
Grund :
Keine
Änderung des Caches
keine Ersetzungsmethode
nötig, daher ist effizienter
(Ein Bruchteil von gesamte Speicher)
Caching-Methode
Caching(1.Teil)
14
Caching-Methode
Zuordnungsverfahren (admission policy)
15
Problem von Verwendung der Ersetzungsmethode(wie LRU) :
Aufnahme aller Anfragen im Cache, inklusiv diejenigen, die
selten auftreten werden und sind keine Cachetreffer
Lösung : Zuordnungsverfahren
Schätzen der Anfragehäufigkeit zum Speichern
Zuordnungserfahren :
Zur Verhinderung der Aufnahme der nicht-häufige oder
singelton Anfragen im Cache
Aufteilung des Caches in zwei dynamische Teile :
Controlled Cache(CC)
uncontrolled Cache(UC)
Caching-MethodeZuordnungsverfahren (admission policy)
Dynamische Teile von Cache
16
I ) Controlled Cache(CC) :
Akzeptanz nur die Anfragen, die dieses Verfahren als
Trefferrate klassifiziert hat.
II) Uncontrolled Cache(UC)
Die Anfrage, die selten oder nur einmal auftreten werden
o Vorgehensweise
− Gegeben Qs als Anfrageströmung.
− Zuordnungsfunktion :
f : Qs {0,1} und q∈ Qs eine Anfrage.
Caching-MethodeZuordnungsverfahren (admission policy)
Algorithmus
17
o Beispiel für eine Zuordnungsmethode :
- Wenn q schon in CC häufig vorgekommen ist, dann setze
f(q) =1 , sonst f(q)=0.
- Nachteil: CC ist hier statisch. Also ist hier nötig eine
effizientere und dynamische Methode
Caching-MethodeZuordnungsverfahren (admission policy)
Entwurf dynamischer Zuordnungsmethode
18
Features :
Die Eigenschaften von der Anfrage zum Entwurf einer guten
Methode
Zwei Arten von Features :
1) Die Methode mit Zustandsbehafteten Feature :
Bedarf des zusätzlichen Speicherplatz zum Behalten der
Statistik im Bezug auf die Häufigkeit der Anfragen
Statistik wird in reguläre Zeitintervall aktualisiert
Akzeptanz aller Anfragen, wenn deren Häufigkeit in
früheren Anfragen größer als ein beliebige Schwellenwert
ist.
Caching-MethodeZuordnungsverfahren (admission policy)
Bewertung
19
Bewertung der Zustandsbehafteten Methode
Caching-MethodeZuordnungsverfahren (admission policy)
Entwurf dynamischer Zuordnungsmethode
20
2) Die Methode mit Zustandslosem Feature :
Schnell aus dem Anfragestrom berechnet wird, ohne die
gesammelten Informationen zu brauchen
Abhängig von Zeichen oder Wörter, die eine Anfrage enthält oder
die Anzahl der nicht-alphanumerische Charakter in der Anfrage.
Vorteil : keinen zusätzlichen Speicherplatz
Nachteil: nicht effiziente Methode als ein Schätzer, der auf
Häufigkeit der Wörter basiert.
Caching-MethodeZuordnungsverfahren (admission policy)
Bewertung
21
Bewertung der Zustandslosen Methode
Caching-MethodeZuordnungsverfahren (admission policy)
Fazit
22
Fazit :
− Finden von einer guten Feature, die Zustandsbehaftete Methode
übertreffen kann, bleibt noch ein offenes Problem
− Vergleich von Optimale Methode mit LRU
2001
Caching-Methode
Caching(2.Teil)
23
Caching-Methode
ResIn * Methode und Architektur
24
Eine Kombination von Ergebnisse-Cache und Indexreduzierung
zum Erreichen der guten Leistung der Suchmaschine
* Result Caching and Index Pruning
Caching-Methode ResIn Methode und Architektur
Ergebnisse-Cache
25
(1) Ergebnisse-Cache(Results Cache)
Rückgabe der top gespeicherte Ergebnisse, wenn die Anfrage
ein Treffer, sonst berichtet ein Fehl
Verwendung von LRU als Ersetzungstaktik
Sein Trefferrate bleibt monoton bei der Zunahme von der
Dokumentsammlungsgröße
Nachteil : der häufig auftauchenden Singelton Anfrage nimmt
der Trefferrate ab.
Caching-Methode ResIn Methode und Architektur Indexreduzierungstechniken
26
(2) Indexreduzierung(Index pruning)
Definition:
o
kleinere Version von Haupt-Index, welche aus einer
Teilmenge von Dokumente besteht, die als TopErgebnisse zurückgegeben werden müssen.
Reduzierungstechnik:
Term Reduzierung(term pruning) : Entfernen von
invertierten Liste der bestimmten Terme
Caching-Methode ResIn Methode und Architektur Indexreduzierungstechniken
Term-Reduzierung
27
Term-Reduzierung
Auswahl der am meisten profitablen Terme mit ihren
invertierten Liste
Eine Anfrage kann bei der reduzierten Index Cache verarbeitet
werden, wenn alle Terme in der Anfrage sich drin befinden.
Annahme :
bei dieser Technik beinhaltet jede Dokument in der
Ergebnisliste alle Terme in der Anfrage.
Schätze das Profit eines Terms:
pop(t)
profit(t) =
df (t)
Caching-Methode ResIn Methode und Architektur Indexreduzierungstechniken
Term-Reduzierung
28
Term Reduzierung Algorithmus:
i)
Extraktion der Liste von Terms aus dem Anfrage-Log und
Berechnung ihrer Profite
ii) Sortieren der Terme absteigend nach ihrem Profit-Wert
iii) Speicherung der Top-Terms und deren invertierten Liste
Caching-Methode ResIn Methode und Architektur Indexreduzierungstechniken
Bewertung
29
Aktualisierungsproblem
30
Aktualisierungsproblem
31
Problemstellung
Ein Nachteil von der großen Ergebnis-Cache ist Frische
Häufige Aktualisierung der Suchmaschineindexen durch
neues Crawling von Dokumente führt dazu:
Der große Anteil von vorherige berechnete Ergebnisse im
Cache wird abgestanden
Lösung:
Entwertung der Einträge im Lauf der Zeit
(Entkoppelungsverfahren)
Aktualisierungsproblem
Entkoppelungsverfahren
32
Vorgehensweise :
Verwendung von TTL(Time To Live) Wert
Markiere die Einträge als abgelaufen, wenn die sich im Cache
länger als TTL befinden
Nachteil: Beeinträchtigung von Trefferrate durch die
abgelaufene Einträge
Optimierung
:
Auffrischung der Ergebnisse von abgelaufenen Einträge, der
täglich oder wöchentlich durchgeführt wird
Fazit
33
Caching ist eine effektive Technik in Suchmachine zur
Beschleunigung der Antwortzeit
Zuordnungsmethode verbessert der Trefferrate in Cache im
Vergleich zu bekannten Methode , wie LRU, SDC, ...
Reduzierung der Arbeitslast von Anfragen in Back-End Server
mit ResIn Architektur aus der Kombination von Caching von
Ergebnisse und Indexreduzierung
Bei optimierter TTL-Methode erhöht der Trefferrate durch
Reduzierung der Anzahl von Fehlerrate auf abgelaufene Einträge
Ende
34
Vielen Dank für Ihre Aufmerksamkeit
Literaturverzeichnis
35
[BaYat] Ricardo Baeza-Yates, Aristides Gionis, the impact of
caching on search engine, 2007
[ResIn] Gleb Skobeltsyny,Flavio P. Junqueiraz, A Combination
of Results Caching and Index Pruning for Highperformance Web Search Engines, 2008
[BaJun] Ricardo Baeza-Yates, Flavio Junqueira, Admission
Policies for Caches of Search Engine Results , 2007
[AlJun] Alexandros Ntoulas, Junghoo Cho, Pruning Policies for
Two-Tiered Inverted Index with Correctness Guarantee,
2007
[PaEd] Patricia Saraiva, Edleno de Moura, Rank-Preserving Two-Level
Caching for scalable Search Engine,2001
[BarJun] Barla Cambazoglu, P.Junqueira, a refreshing
perspektive of Search Engine Caching, 2010

Download Report