Database Reference
In-Depth Information
9
1.3
Blocking
Sorted Neighborhood
Neues Verfahren, u=2
Neues Verfahren, u=6
Blocking
Sorted Neighborhood
Neues Verfahren, u=2
Neues Verfahren, u=6
1.2
8
1.1
7
1
6
0.9
5
0.8
4
0.7
3
0.6
2
0.5
1
0.4
0
0.3
5
10
15
20
25
16
18
20
22
24
26
Partitionsgröße
Partitionsgröße
Abbildung 6.9: Effizienz der Partitionsgrößen
weils mit der Schrittweite 1 weitergeschoben wird. Bei der Sorted-Neighborhood-
Methode steigt die Anzahl der Tupelvergleiche mit zunehmender Fenstergröße je-
doch stark an, da jedes Tupel mit mindestens w
2
Tupeln verglichen wird 4 . Hierdurch wird zwar eine hohe Abdeckung an miteinan-
der verglichenen Tupeln erreicht, es sinkt jedoch die Effizienz, da immer mehr
Tupel miteinander verglichen werden, die keine Duplikate sind.
Das vorgestellte verallgemeinerte Verfahren wirkt dem entgegen, indem nur ei-
ne geringe, an die Datensätze angepasste, Überlagerung zwischen den Partitionen
gewählt wird. So können bei gleicher Anzahl von Tupelvergleichen größere Parti-
tionen verwendet werden als bei der Sorted-Neighborhood-Methode. Dies ist bei
den CD-Testdaten sehr gut für eine Partitionsgröße von m
1 Tupeln und maximal mit 2 w
6 sichtbar geworden,
bei der ein Anstieg des Recalls zu beobachten ist und die Sorted-Neighborhood-
=
4 Es sind w 1 Tupelvergleiche für die beiden Tupel am Rand der Sortierreihenfolge. Je weiter ein
Tupel vom Rand entfernt ist, gegen desto mehr Tupel wird es bis zum Maximalwert verglichen.
 
Search WWH ::




Custom Search