Startseite Information Retrieval: Methoden zur Selektivitätsabschätzung Seminar S2D2, IPD Böhm, WS 2005/06 Matthias Bracht, 10.01.2006 (Betreuer: Guido

Startseite

Information Retrieval:Methoden zur

Selektivitätsabschätzung

Seminar „S2D2“, IPD Böhm, WS 2005/06

Matthias Bracht, 10.01.2006(Betreuer: Guido Sautter)

Seminar „S2D2“, IPD Böhm

2

Matthias Bracht, 10.01.2006

Wozu Selektivitätsabschätzung?

• Beispiel:- 100 Dokumente- 100 enthalten „das“, 50 „auto“, 1 „luxuskarosse“

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick

Information Retrieval: Methoden zur Selektivitätsabschätzung

- Anfrage: „das AND auto AND luxuskarosse“

1

50

11 1

100

0

20

40

60

80

100

120

das, auto, luxuskarosse luxuskarosse, auto, das

Grö

ße d

es Z

wis

chen

erge

bnis

ses


3


Selektivität

• klar: 0 <= Sel(Anfrage) <= 1• Beispiel von vorheriger Folie:

Sel(„das“) = 100% Sel(„luxuskarosse“) = 1%

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


Sel(Anfrage) =

#Dokumente, die für Anfrage relevant sind

#Dokumente insgesamt


4




5


Selektivitätsabschätzung sinnvoll für:

• Approximation der Anzahl von Termvorkommen Bestimmung der Signifikanz der Terme auf vorheriger Folie „of“ und „the“ gar nicht

berücksichtigt!• Reihenfolge der Anfrageabarbeitung

vgl. Einstiegsbeispiel• Berechnung der Relevanzfunktion

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



6


Verschiedene Methoden

• parametrische Methoden- bedingt sinnvoll, da bestimmte Art der Verteilung

angenommen wird

• Histogramme• Suffix Trees• Adaptive Sampling

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



7


Histogramme (1)

• Klassischer Einsatz: numerische Wertebereiche• Beispiel: Altersstruktur von 100 Maserati-Besitzern,

equi-length-Histogramm

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


15

60

2014

0

10

20

30

40

50

60

70

16-25 26-35 36-45 46-55 56-65

Sel(Alter < 42) = ?Antwort: irgendwo zw. 0,06 und 0,66!


8


Histogramme (2)

• Verbesserung: equi-depth-Histogramme• fülle jeden Bucket in etwa gleichmäßig• noch weitere Verbesserung: Varianz-Optimierung

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


20 20 20 20 20

0

5

10

15

20

25

18-36 37-40 41-43 44-52 53-65

Sel(Alter < 42) = ?Antwort: irgendwo zw. 0,4 und 0,6!

Intervall 3mal kleiner

füge 20 Leute im Alter von 41-43 hinzu, was passiert?


9


Histogramme (3)

• Problem: nicht trivial auf Textkollektionen anwendbar

• lexikographische Verteilung erschwert sinnvolle Wahl der Bucketgrenzen

• möglicher Ausweg: ein Eimer pro Wort• Counts:

– Termhäufigkeit– in wie vielen Dokumenten kommt Term vor

(1mal, 2mal, 4mal usw.)

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



10


Vor-/Nachteile

+ geringer Zugriffsaufwand+ geringer Speicheraufwand: nur Bucketgrenzen und

Counts

• equi-length: initialer und Update-Aufwand gering, dafür evtl. sehr ungenaue Abschätzungen

• equi-depth: genauere Abschätzungen möglich, aber schwieriger zu bauen (Wahl der Grenzen?) und zu pflegen (Buckets splitten, wenn zu voll?)

– Problem der sinnvollen Wahl der Bucketgrenzen– kaum Einsatzmöglichkeiten für Text Retrieval

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



11


Suffix Trees

• Datenstrukturen, die alle Suffixe von Strings beinhalten

• Suffixe werden in Baum einsortiert, gemeinsame Präfixe zusammengefasst

• Beispiel: Suffix Tree für „mautautomat“, Suffixe:

– mautautomat– mautautomat– autautomat– utautomat– tautomat

...

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


at

autautomat

automat

mat

mautautomat

...

Sortieren...


12


omat

Suffix Tree für „mautautomat“Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


omat

utautomat

ma

t

a ut tomat

omat

automat

omat

automat

tutautomat

Einfügen von „automat“?

automat

automat

ut


13


Count-Suffix Tree

• jeder Knoten enthält zusätzlich Count c• Beispiel:

– 100 Terme: 49x Mazda, 48x Manta, 2x Maserati, 1x Maybach

• Problem: Speicher

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


ma

100

... ...

zda49

nta48

serati2

ybach1


14


serati2

ybach1

Pruned Count-Suffix Tree

• Lösung: Knoten mit c < s (s Schwellwert) werden entfernt

• Beispiel: s = 10

• neues Problem: Abschätzung der nicht enthaltenen Terme

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


ma

100

... ...

serati2

ybach1

zda49

nta48

Sel(„maserati“) = ?

Sel(„matchbox“) = ?


15


Anwendung: Wildcard-Suche

• Beispiel:– Dokument mit Termen „lkwmaut“ (40x),

„pkwmaut“ (30x), „mautsystem“ (20x), „mautautomat“ (10x), „maut“ (100x)

– „maut“-Knoten enthält direkt Anzahl der für die Anfrage relevanten Terme!

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


maut

200

... ...

system20

automat10

Sel(„*maut*“) = ?


16


Vor-/Nachteile

+ gut geeignet für Texte, insbesondere Wildcard-Anfragen

+ geringer Zugriffsaufwand– hoher initialer Aufwand, zusätzlicher Speicheraufwand– Genauigkeit für seltenere Terme schlecht– keine Inkrementalität! Beispiel: s = 10, füge

„maserati“ hinzu

• periodisch neu bauen?

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


ma

99

... ...

serati9

nta90


17


Adaptive Sampling

• Idee: Random Sampling „weitergedacht“ (zufällig Dokumente auswählen)

• fortfahren, bis bestimmte Schwellwerte erreicht– Anzahl der betrachteten Dokumente– Anzahl der Treffer der jeweiligen Anfrage

• „adaptive“: bestimmte Strategie zur Auswahl der folgenden Samples anwenden– z.B. in der „Nähe“ von Treffern weitersuchen

• Blocksampling: komplette Speicherseiten samplen• zusätzliche Abhängigkeiten beachten!

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



18


Konfidenzbetrachtung

• Frage: Wieviel Sampling ist nötig, um akzeptablen Fehler zu erreichen?

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


Figure 5 aus [CRN98]


19


Vor-/Nachteile

+ kein initialer Aufwand, keine Speicherung von Statistiken nötig (vgl. Histogramme, Suffix Trees)

+ Genauigkeit: Konfidenzbereiche können für jede Anfrage neu angegeben werden (keine fixe Bucketanzahl/kein Pruning-Schwellwert)

+ Inkrementalität gegeben+ Methode für beliebige Daten verwendbar

– hoher Zugriffsaufwand

• ggf. sinnvoll: Sampling als Vorstufe zum Aufbau von Histogrammen/Suffix Trees

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick



20


ZusammenfassungMotivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


Histogramme Suffix Trees

Adapt. Sampling

Speicher-

aufwand

gering:nur

Bucketgrenzen und Counts

hoch: Werte, Zähler, Zeiger...

n/a

initialer Aufwand

linear, abh. von Genauigkeit

hoch n/a

Update-Aufwand

equi-length: gering, sonst ggf.

hoch

hoch (Pruning!)

n/a

Zugriffs-Aufwand

gering gering hoch

Genauig-keit

fix: abh. von Art, Bucketanzahl,

Varianz

fix: ungenau

für seltene Terme

variabel: abhängig von Sampling Rate

Daten v.a. numerisch v.a. textuell

beliebig


21


Abhängigkeiten/Korrelationen

• Beispiel:– Sel(„luxus“) = 1 / 10– Sel(„maybach“) = 1 / 100– bei Unabhängigkeit: Antwort 1 / 1000

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


Sel(„luxus“ AND „maybach“) = ?

• Dokumente mit „maybach“ enthalten aber vermutlich auch „luxus“

• Sel(„luxus“ AND „maybach“) also eher bei 1 / 100

Erweiterung der Methoden, um Abhängigkeiten zu erfassen


22


Synonyme

• insbesondere Nachrichtentexte verwenden aus Stilgründen Synonyme

• Beispiel:– Dokumente mit „Michael Schumacher“, „der

deutsche Rennfahrer“, „Schumi“, „der Rekord-Formel-1-Weltmeister“...

Motivation

Histogramme

Suffix Trees

Adaptive Sampling

Fazit

Ausblick


Anzahl der Vorkommen von „Schumacher“?

Erweiterung der Methoden, um Synonyme zu erfassen

nebenbei oben verwendet: Indizierung von Phrasen statt von einzelnen Termen


23


Schlussseite

Vielen Dankfür eure Aufmerksamkeit!


[CRN98]: Chaudhuri, S., Motwani, R., Narasayya, V.; Random Sampling for Histogram Construction: How much is enough? In Proc. of ACM SIGMOD, Seattle, 1998.

Documents

Startseite Information Retrieval: Methoden zur Selektivitätsabschätzung Seminar S2D2, IPD Böhm, WS 2005/06 Matthias Bracht, 10.01.2006 (Betreuer: Guido