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

Methode bei gleicher Anzahl von Tupelvergleichen erst eine Fenstergröße von
w 4 erreicht.

Durch die Vergrößerung der Partitionen steigt die Anzahl der Tupelvergleiche
und dabei ist auch eine Vergrößerung der Abweichungen zwischen dem verallge-
meinerten Verfahren und der Sorted-Neighborhood-Methode zu beobachten, wo-
bei beide Verfahren abwechselnd die besseren Ergebnisse erzielen. Hierbei ist je-
doch zu bedenken, ob feste Partitionsgrößen

=

10 bei 9.763 CD-Datensätzen noch
sinnvoll sind, da echte Duplikate sich bei diesen Abständen nur noch im Promille-
Bereich befinden. Hier sollte vielmehr eine an den Attribut-Werten ausgerichtete
Partitionierung verwendet werden, was ggf. zu Partitionen verschiedener Größe
führt. Die Effizienz des verallgemeinerten Verfahrens ist bei einer niedrigen An-
zahl an Tupelvergleichen höher als bei der Sorted-Neighborhood-Methode, liegt
bei steigenden Tupelvergleichen jedoch teilweise darunter. Vergleicht man die Ef-
fizienz für gleiche Partitionsgrößen, so erzielt das neue Verfahren bessere Ergeb-
nisse als die Sorted-Neighborhood-Methode.
Im Vergleich zum Blocking erzielt das verallgemeinerte Verfahren bei gleicher
Anzahl an Tupelvergleichen stets bessere Recall-Ergebnisse. Durch die Überlage-
rung ist das verallgemeinerte Verfahren unabhängiger von der Wahl eines geeig-
neten Partitionierungsschlüssels als das Blocking. Die Überlagerung verursacht
zwar zusätzliche Tupelvergleiche, diese fallen bei steigender Partitionsgröße je-
doch immer weniger ins Gewicht. Einerseits verringert sich die Anzahl der Über-
lagerungen bei steigender Partitionsgröße. Andererseits ist der Aufwand für den
vollständigen Vergleich innerhalb der Partitionen deutlich größer als der Aufwand
für die Überlagerungen. Für die CD-Testdaten bedeutet jede Überlagerung u

>

2
nur einen Aufwand von 3 zusätzlichen Tupelvergleichen. Die Effizienz des verall-
gemeinerten Verfahrens ist bei gleicher Anzahl an Tupelvergleichen stets größer
als die des Blockings.

=