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

4 Windowing-Verfahren

Windowing-Verfahren reduzieren die Tupel-Vergleiche auf diejenigen Datensätze,
die innerhalb eines definierten Fensters liegen. Die Sorted-Neighborhood-Methode
wurde von Hernandez und Stolfo 1 entwickelt. Sorted-Neighborhood bedeutet über-
setzt „sortierte Nachbarschaft“ und basiert auf der Idee, dass die Datensätze zu-
nächst nach einem Schlüssel sortiert und anschließend nur noch Tupel miteinander
verglichen werden, die innerhalb einer definierten Nachbarschaft liegen.

4.1 Sorted-Neighborhood-Methode

Die Sorted-Neighborhood-Methode besteht aus drei Schritten:

1. Erzeugung eines Schlüssels
Zunächst wird ein Sortierschlüssel definiert. Hierfür werden relevante At-
tribute oder Bestandteile der Attribute konkateniert 2 (z.B. die ersten drei
Buchstaben des Nachnamens und die ersten beiden Buchstaben des Vorna-
mens).

2. Sortierung
Die Tupel werden anhand des in Schritt 1 gebildeten Schlüssels alphabe-
tisch sortiert. Wenn ein geeigneter Schlüssel verwendet wurde, liegen die
Duplikate nach der Sortierung dicht beieinander.

3. Duplikaterkennung
Es wird ein Fenster mit konstanter Länge w

3 über die sor-
tierte Liste geschoben. Der paarweise Vergleich wird nur für die Elemente
innerhalb des jeweiligen Fensters vorgenommen. Das Fenster definiert somit
die „Nachbarschaft“. Nachdem alle Elemente eines Fensters auf Duplikate

( 2 ≤ w ≤ n )

1 vgl. hierzu und zum Folgenden [15]
2 vgl. [8], S. 134
3 Im Falle von w = 2 werden nur direkt nebeneinander liegende Elemente miteinander verglichen. Bei
w n sind alle Elemente in einem einzigen Fenster enthalten. In diesem Fall macht die Verwendung

des Sorted-Neighborhood-Algorithmus keinen Sinn, da keine Partitionierung der Gesamt-Menge
der Elemente erfolgt.

=