Zusammenfassung - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 78

Tupel anhand eines Blocking-Schlüssels in disjunkte Blöcke. Innerhalb der Blö-
cke erfolgt dann ein vollständiger paarweiser Tupelvergleich. Die Sorted-Neigh-
borhood-Methode sortiert die Datensätze zunächst anhand eines Sortierschlüs-
sels und schiebt anschließend ein Fenster mit der Schrittweite 1 über die sor-
tierten Tupel. Der paarweise Tupelvergleich erfolgt dabei ausschließlich innerhalb
des jeweiligen Fensters. Wesentlicher Unterschied von Blocking und der Sorted-
Neighborhood-Methode ist die Überlappung der Partitionen. Während Blocking
keine Überlappung verwendet, ist die Überlappung bei der Sorted-Neighborhood-
Methode maximal, da sich zwei benachbarte Fenster nur durch ein einziges Ele-
ment unterscheiden.
In einem praktischen Vergleich sind beide Verfahren anhand von CD-Testdaten
miteinander verglichen worden. Hierfür sind die Basisalgorithmen beider Verfah-
ren implementiert worden und es erfolgten jeweils mehrere Durchläufe mit un-
terschiedlichen Partitionsgrößen. Während die Precision kaum Unterschiede auf-
weist, ist der Recall beider Verfahren signifikant unterschiedlich. Speziell bei klei-
nen Partitionsgrößen ist die Sorted-Neighborhood-Methode dem Blocking überle-
gen. Dies liegt an der Überlappung zwischen den Fenstern, wodurch eine korrekte
Abgrenzung der Partitionen weniger relevant ist als beim Blocking.
Die Ergebnisse des Vergleichs beider Verfahren sind dann in die Entwicklung
eines verallgemeinerten Verfahrens eingeflossen. Hierfür wurde zunächst unter-
sucht, wie weit sich die Partitionen überlagern müssen, um eine möglichst große
Abdeckung der echten Duplikate zu erreichen. Für die CD-Testdaten ergab dies
eine Überlagerung von zwei Elementen, wobei der Wert spezifisch für die CD-
Testdaten ist und bei anderen Datensätzen größer oder kleiner sein kann.
Das verallgemeinerte Verfahren teilt die Gesamtdatenmenge ähnlich demBlock-
ing in Partitionen, für die jeweils ein vollständiger paarweiser Tupelvergleich er-
folgt. Zusätzlich werden Elemente am Rand der Partitionen mit Rand-Elementen
der benachbarten Partition verglichen. Hierfür wird ein Fenster wie bei der Sorted-
Neighborhood-Methode der Größe u

1 über den gesamten Überlagerungsbereich
geschoben, wobei u die gewählte Überlagerung ist. Der Überlagerungsbereich hat
die Größe 2 u und beinhaltet die gleiche Anzahl Tupel beider benachbarter Parti-
tionen.
Eine Analyse des Algorithmus zeigt, dass das verallgemeinerte Verfahren bei
gleichen Partitionsgrößen zunächst eine identische Anzahl von Tupelvergleichen
hat wie die Sorted-Neighborhood-Methode, sich mit steigenden Partitionsgrößen
jedoch mehr dem Blocking annähert und deutlich unter den Tupelvergleichen der
Sorted-Neighborhood-Methode bleibt. Aufgrund der gewählten Überlagerung
bleibt das verallgemeinerte Verfahren jedoch stets geringfügig über der Anzahl

+