Verallgemeinertes Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 62

700

Sortierreihenfolge:

Track01 − Artist1 − Title1

69,02%

Title1 − Artist1 − Track01

Artist1 − Title1 − Track01

600

500

400

300

200

15,10%

100

9,28%

2,80%

1,23% 1,01% 0,56% 0,11% 0,22% 0,45% 0,22%

0

1 2 3 4 5 6 7 8 9 10 >10

Abstand

Abbildung 6.2: Abstand der echten Duplikate für verschiedene Sortierschlüssel

6.2 Beschreibung des Algorithmus

Die Vorgehensweise des verallgemeinerten Verfahrens ist in Abbildung 6.3 darge-
stellt. Analog zum Blocking werden die Tupel nach einem Partitionierungsschlüs-
sel sortiert und in disjunkte Partitionen unterteilt. Innerhalb der einzelnen Parti-
tionen erfolgt ein vollständiger Vergleich, wie in der Abbildung für die Partition
P 1 dargestellt. Die Partitionen sollten aufgrund des quadratischen Aufwands eines
vollständigen Tupelvergleichs jeweils die gleiche Anzahl von Elementen enthal-
ten, um die Gesamtzahl der Tupelvergleiche zu minimieren. Sie können jedoch
auch verschieden groß gewählt werden. Eine Überlappung der Partitionen wird
durch Fenster analog der Sorted-Neighborhood-Methode realisiert, wobei jedes
Fenster die Größe u 1 hat. Das Fenster wird mit der Schrittweite 1 über den

gesamten Überlagerungsbereich zweier benachbarter Partitionen geschoben. Der
Überlagerungsbereich besteht aus u Fenstern, hat die Größe 2 u und ist in beiden
Partitionen gleich groß. Innerhalb der Fenster werden nur Tupel verschiedener Par-
titionen miteinander verglichen, da Vergleiche von Tupeln der gleichen Partition

+