Vergleich Blocking- und Sorted-Neighborhood-Methode - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 45

10000

Anzahl > Wertebereich

8000

Vollständiger Vergleich
Blocking
Sorted Neighborhood

6000

4000

2000

0

0 2000 4000 6000 8000 10000

Anzahl Elemente

Abbildung 5.3: Vergleich des Aufwands der Duplikaterkennung

Abbildung 5.4 zeigt die Entwicklung der Blockanzahl bei steigender Fenster-
größe und gleicher Anzahl an Tupelvergleichen für Blocking und Sorted-Neigh-
borhood-Methode. Die Graphen basieren auf verschiedenen Größen der Gesamt-
datenmenge. Im rechten Teil der Abbildung ist ein Ausschnitt der linken Gesamt-
ansicht dargestellt, um den Kurvenverlauf im Bereich der größeren Fenster besser
zu erkennen. Bei einer Fenstergröße von 1 entspricht die Anzahl der Blöcke der
Gesamtanzahl der Tupel. Mit steigender Fenstergröße nimmt die Blockanzahl zu-
nächst stark ab, anschließend flacht die Kurve jedoch ab. Bei einem Fenster in
Größe der Gesamtdatenmenge ist die Blockanzahl 1.
Bei der bisherigen Betrachtung des Aufwands für die Tupelvergleiche wurde nur
die Anzahl der Vergleiche herangezogen. Die Kosten für die Berechnung der Ähn-
lichkeitsfunktion sind nicht relevant, da sie bei allen drei Verfahren gleich sind.
In Kapitel 4.1 wurde bereits erwähnt, dass die Kosten für die Festplattenzugriffe
vermutlich die dominierenden sein werden. Für den Schritt des Tupelvergleichs
wurde bisher davon ausgegangen, dass sich alle Tupel im Hauptspeicher befinden.
Bei einer großen Anzahl von Tupeln wird dies jedoch nicht immer möglich sein.