Duplikaterkennung - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 28

Die benötigten Ressourcen für die Durchführung der Duplikaterkennung kön-
nen mit der Zeit eines Durchlaufs quantifiziert werden 67 . Die benötigte Zeit hängt
im wesentlichen von zwei Faktoren ab:
1. Anzahl der Tupelvergleiche
Ein vollständiger Vergleich aller Tupel ist sehr kostenintensiv. Zur Steige-
rung der Effizienz sollten unnötige Vergleiche nach Möglichkeit vermieden
werden, ohne die Effektivität signifikant zu beeinträchtigen 68 .
2. Komplexität der Ähnlichkeitsfunktion
Bei Tupeln mit vielen Attributen ist der Aufwand für den Vergleich der ein-
zelnen Attribute relativ hoch. Zur Steigerung der Effizienz kann eine Reduk-
tion auf eine Teilmenge der Attribute vorgenommen werden 69 . Weiterhin
kann der Attribut-Vergleich abgebrochen werden, wenn die Klassifikation
als Duplikat/Nicht-Duplikat feststeht und die noch nicht verglichenen Attri-
bute die Klassifikation nicht mehr ändern. Ist der Einfluss der Attribute auf
das Gesamtergebnis unterschiedlich gewichtet, so sind zunächst Attribute
mit einer hohen Gewichtung zu vergleichen.
Betrachtet man Precision, Recall und Effizienz, so wird ein Zielkonflikt deut-
lich. Ein komplexes Ähnlichkeitsmaß steigert zwar die Precision, verringert dabei
jedoch die Effizienz. Das gleiche gilt für den Recall, der durch die Partitionsgrö-
ße und damit der Anzahl der Vergleiche beeinflusst wird. Ein hoher Recall geht
ebenfalls zu Lasten der Effizienz. Der verwendete Schwellwert für das Ähnlich-
keitsmaß wiederum beeinflusst Precision und Recall. Dieser Zusammenhang ist
noch einmal in Abbildung 2.6 dargestellt.
2.6 Zusammenfassung
Duplikaterkennung beschäftigt sich mit der Identifizierung gleicher Realwelt-Ob-
jekte in einem Datenbestand. Anwendungsgebiete für die Duplikaterkennung sind
beispielsweise die Bereinigung von Datenbeständen, die Kombination von Daten-
sätzen aus mehreren Quellen oder die Gewinnung von Informationen über Zu-
sammenhänge zwischen Daten verschiedener Quellen. Duplikate repräsentieren
67 Unter Ressourcen fällt auch die verwendete Hardware. Um jedoch die Vergleichbarkeit von Algo-
rithmen zu gewährleisten, ist jeweils die gleiche Hardware zu verwenden. Daher wird im Folgenden
auf eine Betrachtung von Hardware-Aspekten verzichtet.
68 vgl. auch Kapitel 2.3
69 vgl. hierzu und zum Folgenden [13], S. 12 und [34], S. 92