Zusammenfassung - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 77

7 Zusammenfassung
Daten liegen heutzutage nicht mehr an einem zentralen Ort vor, sondern sind welt-
weit verteilt. Für einen vollständigen Überblick über die Daten ist es notwendig
verschiedene Quellen zu integrieren. Neben strukturellen und semantischen Hete-
rogenitäten existieren auch Heterogenitäten auf Datenebene. Diese zu lösen und
somit eine Verbindung zwischen gleichen Realwelt-Objekten herzustellen ist Auf-
gabe der Duplikaterkennung.
Die Ursachen für Duplikate sind vielfältig. Häufig entstehen sie durch eine feh-
lerhafte Erfassung der Daten, beispielsweise durch Tipp- und Hörfehler. Duplika-
te verursachen einen unnötigen Verbrauch von Speicherplatz und Rechenleistung.
Zudem ist es nicht mehr möglich, durch einfaches Zählen die Anzahl der Realwelt-
Objekte zu bestimmen, und es besteht die Gefahr weiterer Inkonsistenzen, da bei
Änderungs- und Löschoperationen nicht alle Elemente erfasst werden. Duplikate
sind daher in einem Datenbestand zu vermeiden bzw. zu beseitigen.
Der Ablauf der Duplikaterkennung gliedert sich in fünf Schritte. Zunächst wer-
den in der Vorverarbeitung die Daten bzgl. Schreibweise, Einheit und Format ver-
einheitlicht sowie offensichtliche Fehler beseitigt. Anschließend erfolgt eine Re-
duzierung des Suchraums , da der Aufwand eines vollständigen paarweisen Tu-
pelvergleichs quadratisch und somit in der Praxis ungeeignet ist. Durch Auftei-
lung der Gesamtdatenmenge in Partitionen verringert sich der jeweilige Suchraum.
Die Auswahl einer Ähnlichkeitsfunktion , mit der die Ähnlichkeit zweier Tupel be-
stimmt wird, basiert auf attributspezifischen Abstandsmaßen. Durch die Anwen-
dung der Ähnlichkeitsfunktion auf Tupelpaare und einen Schwellwert erfolgt eine
Klassifizierung der Datensätze als Duplikat oder Nicht-Duplikat. Abschließend er-
folgt eine Verifizierung der Ergebnisse anhand von Kennzahlen.
Zur Beurteilung von Duplikaterkennungs-Verfahren kann die Effektivität und
Effizienz der Verfahren miteinander verglichen werden. Für die Effektivität stehen
mit Precision (Korrektheit), Recall (Vollständigkeit) und F-Measure diverse Kenn-
zahlen zur Verfügung. Die Effizienz berücksichtigt neben den erzielten Ergebnis-
sen auch die benötigte Zeit der Duplikaterkennung. Diese ist einerseits abhängig
von der Komplexität der Ähnlichkeitsfunktion, andererseits von der Anzahl der
Tupelvergleiche.
Zur Reduzierung des Suchraums wurden mit Blocking und der Sorted-Neigh-
borhood-Methode zwei Verfahren vorgestellt. Blocking teilt die Gesamtmenge der