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

Betrachtung der Effizienz
In Kapitel 2.5 wurde Effizienz als Quotient von Ergebnis und benötigten Res-
sourcen definiert. Das Ergebnis der Duplikaterkennung wird mit Recall und F-
Measure und die benötigten Ressourcen mit der Anzahl Tupelvergleiche quantifi-
zierbar. Während der Recall ausschließlich die Vollständigkeit betrachtet, ist das
F-Measure auch abhängig von der Precision und somit von der Korrektheit der
Ergebnisse. In den vorherigen Abbildungen 6.7 und 6.8 sind das F-Measure und
die Anzahl der Tupelvergleiche enthalten. Die Effizienz der Verfahren kann also
direkt in diesen Abbildungen verglichen werden. Für eine gegebene Anzahl an Tu-
pelvergleichen ist das Verfahren am effizientesten, welches den höchsten Wert des
F-Mesure hat.
Abbildung 6.9 betrachtet zusätzlich die Effizienz in Abhängigkeit von der Par-
titionsgröße. Hierfür wurde für jede Partitionsgröße der Quotient aus F-Measure
und der jeweiligen Anzahl an Tupelvergleichen des Verfahrens gebildet und das
Ergebnis mit 100.000 multipliziert, um viele Nachkommastellen zu vermeiden 3 .
Das rechte Diagramm ist ein Ausschnitt des linken Diagramms. Es ist zu erken-
nen, dass die Sorted-Neighborhood-Methode bezogen auf die Partitionsgröße die
schlechteste Effizienz aufweist. Die Effizienz des Blockings liegt zunächst über
dem neuen Verfahren, fällt dann aber zwischen die Effizienz für die Überlage-
rungsgrößen u

= 2 und u = 6.

6.4 Bewertung des verallgemeinerten Verfahrens

Ziel dieser Arbeit ist die Entwicklung eines verallgemeinerten Verfahrens zur Du-
plikaterkennung, welches die Effizienz imVergleich zum Blocking und zur Sorted-
Neighborhood-Methode steigert. Hierbei kann die Effizienz als Quotient der An-
zahl der gefundenen echten Duplikate und der benötigten Tupelvergleiche be-
schrieben werden. Ausgangsbasis für das neue Verfahren ist das Blocking, da dies
bei gleicher Partitionsgröße weniger Tupelvergleiche als die Sorted-Neighborhood-
Methode benötigt und zusätzlich auch die Möglichkeit variabler Partitionsgrößen
bietet. Darauf aufbauend wurde eine geeignete Überlagerungsgröße zwischen den
Partitionen für die CD-Testdaten gewählt und später auch validiert. Durch diese
Überlagerung wird sichergestellt, dass echte Duplikate, die in der Sortierreihen-
folge dicht beieinander liegen, dem paarweisen Tupelvergleich unterzogen und so-
mit bei einer geeigneten Ähnlichkeitsfunktion als Duplikate erkannt werden. Dies
ist auch bei der Sorted-Neighborhood-Methode der Fall, bei der das Fenster je-

3 Da die Effizienz für den Vergleich verschiedener Verfahren verwendet wird und keine absolute Größe
darstellt, beeinflusst die Multiplikation mit 100.000 das Ergebnis nicht.