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

=

w 6. D.h. die Sorted-Neighborhood-Methode deckt ab diesem Schnittpunkt den

gleichen maximalen Abstand zwischen den Tupeln ab, wie das verallgemeinerte
Verfahren bei seinem Anstieg des Recalls. Der Unterschied beider Verfahren liegt
jedoch in der Anzahl der Tupelvergleiche, die bei den jeweiligen Partitionsgrößen
erfolgen. Das verallgemeinerte Verfahren hat bei einer Partitionsgröße von m

6
die gleiche Anzahl an Tupelvergleichen, wie die Sorted-Neighborhood-Methode
schon bei einer Fenstergröße w

=

4 erreicht.
Im weiteren Verlauf des Graphen weist das verallgemeinerte Verfahren mehrere
lokale Maxima und Minima auf, im Gegensatz zum monoton steigenden Recall-
Wert der Sorted-Neighborhood-Methode. Der Verlauf des Graphen des verallge-
meinerten Verfahrens ähnelt hierbei dem Verlauf des Blockings, d.h. dort wo das
Blocking ein lokales Maximum hat, hat auch das verallgemeinerte Verfahren eins.
Das verallgemeinerte Verfahren bleibt jedoch stets deutlich über dem Graphen des
Blockings. Hier bestätigt sich die Beobachtung bei der Precision, dass das verall-
gemeinerte Verfahren bei kleinen Partitionsgrößen mehr der Sorted-Neighborhood-
Methode ähnelt und sich mit steigenden Partitionsgrößen dem Blocking annähert.
Zu berücksichtigen ist allerdings, dass feste Partitionsgrößen gewählt wurden, bei
denen die Partitionsgrenzen nicht an den Daten ausgerichtet sind. Bei Verwen-
dung eines Partitionierungsschlüssels, der die Tupel anhand ihrer Attribut-Werte
in Partitionen einteilt, sind auch bei steigenden Partitionsgrößen bessere Werte zu
erwarten.

=