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

Hauptspeicherbedarf
Der Hauptspeicherbedarf des neuen Verfahrens richtet sich wie bei der Sorted-
Neighborhood-Methode nach der Partitionsgröße. Für den vollständigen Vergleich
innerhalb einer Partition müssen alle Elemente im Hauptspeicher enthalten sein,
um Festplattenzugriffe zu vermeiden. Da m u gilt 2 , ist der Hauptspeicherbedarf

in den Überlagerungsbereichen geringer. Dies gilt auch für Partitionen verschie-
dener Größe, bei denen sich der maximale Hauptspeicherbedarf nach der größten
Partition richtet.
Für die Beispielwerte aus Kapitel 5.1 mit einer Tupelgröße von 300 Byte und
einer Partitionsgröße m

>

= 20 beträgt der Hauptspeicherbedarf wie bei der Sorted-

Neighborhood-Methode ≈ 5,86 KB.

Precision, Recall & F-Measure
In diesem Abschnitt wird das verallgemeinerte Verfahren anhand der Kennzah-
len Precision, Recall und F-Measure auf Effektivität und Effizienz anhand der CD-
Testdaten geprüft. Hierfür sind 25 Durchläufe des verallgemeinerten Verfahrens
erfolgt, jeweils mit einer festen Partitionsgröße von 3-27 Elementen. Die Ergeb-
nisse der Durchläufe sind in Tabelle 6.2 dargestellt. Für eine Vergleichbarkeit der
Ergebnisse mit denen des Blockings und der Sorted-Neighborhood-Methode in
Kapitel 5.2 sind der gleiche Sortierschlüssel und die gleiche Ähnlichkeitsfunktion
mit einem Schwellwert von 0,78 verwendet worden. Als Überlagerungsgröße wird
zunächst u

2 gewählt.
Precision und Recall sind in Abbildung 6.6 graphisch dargestellt. Die Abbil-
dung enthält auch für das Blocking, die Sorted-Neighborhood-Methode und den
vollständigen Vergleich die Vergleichswerte aus Kapitel 5.2. Da diese Graphen
bereits beschrieben wurden, konzentrieren sich die folgenden Absätze auf die Be-
schreibung des verallgemeinerten Verfahrens.
Die Precision des verallgemeinerten Verfahrens entspricht in etwa dem Block-
ing und der Sorted-Neighborhood-Methode. Die Ausschläge des Graphen sind
hierbei weniger stark als beim Blocking, dafür etwas stärker als bei der Sorted-
Neighborhood-Methode. Hierbei ist zu beobachten, dass die Ausschläge des ver-
allgemeinerten Verfahrens mit zunehmender Partitionsgröße steigen. Der Einfluss
der Überlagerung auf die Precision scheint daher mit zunehmender Partitions-
größe immer weiter abzunehmen, denn der Precision-Wert nähert sich dem des
Blockings ohne Überlagerung, während zu Beginn des Graphen der Precision-
Wert näher an dem der Sorted-Neighborhood-Methode mit maximaler Überlage-
rung liegt.

=

2 Ein Wert u ≥ m führt effektiv zu einer Vergrößerung der Partitionen.