Windowing-Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 37

4.2 Multi-Pass Sorted-Neighborhood

Die Multi-Pass-Methode basiert auf der Annahme, dass ein einziger Durchlauf
durch die sortierte Liste nicht die besten Resultate liefert. Wie bereits erläutert
wurde, können bereits kleine Fehler in den Daten dazu führen, dass die Schlüs-
sel zweier Duplikate nicht mehr dicht beieinander liegen. Bei der Multi-Pass-
Methode erfolgen daher mehrere Durchläufe durch die sortierte Liste, wobei bei
jedem Durchlauf ein unterschiedlicher Sortierschlüssel verwendet wird. Mehrere
Durchläufe führen jedoch zu einer höheren Anzahl an Tupel-Vergleichen, was die
Effizienz des Algorithmus sinken lässt. Als Ausgleich wird daher vorgeschlagen,
die Größe des Fensters und damit auch die Anzahl der Tupel-Vergleiche zu verrin-
gern 11 .
Bei jedem einzelnen Durchlauf der Multi-Pass-Methode werden Duplikaten-
Paare identifiziert. Nachdem alle Durchläufe abgeschlossen sind, kann wieder die
transitive Hülle gebildet werden. Das Ergebnis sind dann die Duplikate der einzel-
nen Durchläufe und zusätzlich die aus der transitiven Hülle abgeleiteten Duplikate.
Abbildung 4.2 verdeutlicht den Ablauf der Multi-Pass-Methode. Im ersten Durch-
lauf werden zwei Duplikat-Paare gefunden (grau unterlegt). Im zweiten Durchlauf
wird aufgrund der neuen Sortierung (Attribut „Key“) ein weiteres Duplikat-Paar
gefunden. Nach Bildung der transitiven Hülle besteht das Ergebnis aus zwei Du-
plikatgruppen.

Element Key Element Key Duplikate:

x 1 x 2 1. Durchlauf: x 1 ,x 2 und x 4 ,x 5

gh 1a

x 2 hj x 6 2g 2. Durchlauf: x 4 ,x 3

x 3 x 4

iw 4f

x 4 pl x 3 5b Duplikate nach Bildung der transitiven Hülle:

x 5 xy x 1 8z x 1 , x 2

x 6 x 5 x 3 , x 4 , x 5

zt 9u

Durchlauf 1 Durchlauf 2

Abbildung 4.2: Multi-Pass Sorted-Neighborhood-Methode

11 vgl. [5], S. 115