Vergleich Blocking- und Sorted-Neighborhood-Methode - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 49

5.2 Praktischer Vergleich

In diesem Abschnitt wird ein praktischer Vergleich zwischen Sorted-Neighbor-
hood-Methode und Blocking durchgeführt. Hierfür wurden die Basisalgorithmen,
d.h. ohne multi-pass oder sonstige Erweiterungen, beider Verfahren implementiert.
Für ausgewählte Testdaten kann so die Effektivität und Effizienz beider Verfahren
untersucht und miteinander verglichen werden.

5.2.1 Beschreibung Vergleichsdurchführung

Der Ablauf der Vergleichsdurchführung ist in Abbildung 5.6 dargestellt. In einer
Datenbank liegen die Testdatensätze, sowie eine Zuordnung, welche Tupel Dupli-
kate sind. Die Tupel werden anhand eines Schlüssels für die Sorted-Neighborhood-
Methode sortiert bzw. in Blöcke aufgeteilt. Anschließend erfolgt die Duplikater-
kennung innerhalb der einzelnen Partitionen und es wird die transitive Hülle ge-
bildet. Die so gefundenen Duplikate werden wiederum in einer Datenbank gespei-
chert. Abschließend erfolgt ein Vergleich zwischen echten und gefundenen Dupli-
katen. Jedes gefundene Duplikat wird als true-positive oder false-positive klassi-
fiziert 4 . Weiterhin erfolgt eine Berechnung der false-negative , der Precision , dem
Recall und des F-measure .

Test-
daten

Berechnung der
Ähnlichkeit, sowie
Klassifikation als
Duplikat/Nicht-Duplikat

Bilden der
transitiven
Hülle

Sortierung /
Blocking

Testdaten &
echte Duplikate

Gefundene
Duplikate

echte Duplikate gefundene Duplikate

Vergleich von echten und
gefundenen Duplikaten

Kennzahlen (Precision,
Recall, f-measure, Anzahl
Vergleiche, etc.)

Abbildung 5.6: Ablauf praktischer Vergleich Blocking und Sorted-Neighborhood

4 vgl. hierzu und zum Folgenden Abschnitt 2.5