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

Für die Vergleichbarkeit der Ergebnisse werden folgende Annahmen getroffen:

• Es erfolgen mehrere Durchläufe beider Verfahren mit unterschiedlichen
Block- bzw. Fenstergrößen. Die Block- bzw. Fenstergröße wird so gewählt,
dass beide Verfahren in einem Durchlauf ungefähr die gleiche Anzahl an
Tupelvergleichen ausführen.

• Für den Vergleich zweier Tupel verwenden beide Verfahren dieselbe Ähn-
lichkeitsfunktion und denselben Schwellwert.

• Die Schlüssel für beide Verfahren müssen die gleichen Attribute in der glei-
chen Reihenfolge enthalten. Hierdurch wird verhindert, dass ein Verfahren
nur aufgrund des geeigneteren Schlüssels die besseren Ergebnisse liefert.
Für den Vergleich bedeutet dies, dass der Blocking-Schlüssel ein Präfix des
Sortierschlüssels der Sorted-Neighborhood-Methode ist.

• Beim Blocking sollen die Partitionen in etwa gleich groß sein, d.h. der
Blocking-Schlüssel soll eine annähernde Gleichverteilung erreichen. Auf-
grund der geringen Anzahl an Datensätzen ließ sich kein geeigneter Schlüs-
sel finden. Daher werden die Tupel anhand des Sortierschlüssels der Sorted-
Neighborhood-Methode sortiert und anschließend in Blöcke gleicher Größe
geschnitten. Die Anzahl der Blöcke und damit auch die Anzahl der Elemen-
te pro Block werden in Abhängigkeit der jeweiligen Fenstergröße berechnet.
In Tabelle 5.3 sind Block- und Fenstergrößen dargestellt, die zu einer unge-
fähr gleichen Anzahl von Tupelvergleichen führen.

Fenstergröße 2 3 4 5 6 7 8 9 10 11

Blockanzahl 3255 1953 1395 1085 888 751 651 575 514 465

Elemente/Block 3 5 7 9 11 13 15 17 19 21

Fenstergröße 12 13 14 15 16 17 18 19 20

Blockanzahl 425 391 362 337 315 296 279 264 251

Elemente/Block 23 25 27 29 31 33 35 37 39

Tabelle 5.3: Übersicht der Fenster- und Blockgrößen 5

Neben den Durchläufen für Blocking und die Sorted-Neighborhood-Methode
wird auch ein vollständiger Vergleich der Tupel durchgeführt. Hierdurch können
die Auswirkungen der Partitionierung untersucht werden.

5 Die berechnete Anzahl der Blöcke bezieht sich auf 9763 Testdatensätze.