Partitionierung zur effizienten Duplikaterkennung in relationalen Daten

verfasst von: Uwe Draisbach

Verlag: Vieweg+Teubner Verlag

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Duplikate bzw. Dubletten sind mehrere Datensätze, die das gleiche Realweltobjekt beschreiben, etwa mehrfach erfasste Kunden in einem CRM-System oder unterschiedliche Repräsentationen eines Produkts. Das Auffinden dieser Duplikate ist auch für moderne Computer eine komplexe und zeitintensive Aufgabe. Uwe Draisbach vergleicht zwei der einschlägigen Partitionierungsstrategien, die eine intelligente Auswahl von zu vergleichenden Datensatzpaaren treffen. Daraus entwickelt er ein verallgemeinertes Verfahren und zeigt, dass eine intelligente Auswahl der Datensatzpaare den Aufwand signifikant reduzieren kann, ohne die Qualität der Duplikaterkennung wesentlich zu verringern.

Die Arbeit wurde mit dem „Information Quality Best Master Degree Award“ der Deutschen Gesellschaft für Informations- und Datenqualität ausgezeichnet.

Inhaltsverzeichnis

Frontmatter

1. Gegenstand der Arbeit

Zusammenfassung

Duplikaterkennung beschreibt Verfahren, um in einem Datenbestand mehrere Datensätze zu identifizieren, die dasselbe Objekt der realenWelt beschreiben. In relationalen Daten wird dies durch den paarweisen Vergleich zweier Tupel mit einem Ähnlichkeitsmaß erreicht. Der Abstand der Tupel und ein vorgegebener Schwellwert bestimmen dann, ob die Tupel als Duplikat oder Nicht-Duplikat klassifiziert werden.

Uwe Draisbach

2. Duplikaterkennung

Zusammenfassung

Daten liegen heutzutage zumeist nicht mehr zentral an einem physischen Ort vor, sondern sind weltweit an jeweils lokalen Orten verteilt. Für einen vollständigen Überblick über die Daten ist es notwendig, die verschiedenen Quellen zu integrieren und in einer einheitlichen Sicht darzustellen. Dies ist Aufgabe der Datenintegration, die jedoch dadurch erschwert wird, dass die Quellen verteilt, autonom und heterogen sind. Autonomie bedeutet, dass die Quellen unabhängig voneinander erstellt und gepflegt werden. Die Autonomie der Quellen ist daher auch die Ursache für die Heterogenität der Quellen. Bei struktureller Heterogenität ist ein bestimmter Sachverhalt der Realwelt in zwei Quellen unterschiedlich modelliert. Demgegenüber steht die semantische Heterogenität, bei der ein modellierter Sachverhalt in verschiedenen Systemen eine unterschiedliche Bedeutung hat. Die Lösung dieser Heterogenitäten ist Aufgabe des Schema-Matchings.

Uwe Draisbach

3. Blocking-Verfahren

Zusammenfassung

In Kapitel 2.3 wurde die Notwendigkeit der Reduzierung des Suchraums bei der Duplikaterkennung bereits angesprochen. Die Datensätze sind daher in Partitionen zu zerlegen und der Vergleich ist auf diese Partitionen beschränkt. Durch die Partitionierung sinkt der Recall, da Duplikate in unterschiedliche Partitionen fallen können und somit nicht mehr als Duplikate erkannt werden. Gleichzeitig steigt jedoch die Effizienz, da viele unnötige Vergleiche von Nicht-Duplikaten entfallen. Wie die Zerlegung in Partitionen erfolgt, ist abhängig von der Partitionierungsstrategie, die einen großen Einfluss auf das Ergebnis der Duplikaterkennung hat. In diesem Kapitel wird das Blocking vorgestellt. Kapitel 4 beschreibt anschließend die Sorted-Neighborhood-Methode.

Uwe Draisbach

4. Windowing-Verfahren

Zusammenfassung

Windowing-Verfahren reduzieren die Tupel-Vergleiche auf diejenigen Datensätze, die innerhalb eines definierten Fensters liegen. Die Sorted-Neighborhood-Methode wurde von Hernandez und Stolfo entwickelt. Sorted-Neighborhood bedeutet übersetzt „sortierte Nachbarschaft“ und basiert auf der Idee, dass die Datensätze zunächst nach einem Schlüssel sortiert und anschließend nur noch Tupel miteinander verglichen werden, die innerhalb einer definierten Nachbarschaft liegen.

Uwe Draisbach

5. Vergleich Blocking- und Sorted-Neighborhood-Methode

Zusammenfassung

In den vorherigen beiden Kapiteln wurden zwei Partitionierungsstrategien zur effizienten Duplikaterkennung beschrieben. In diesem Abschnitt erfolgt ein Vergleich dieser beiden Verfahren. Neben einer theoretischen Betrachtung wird mit Hilfe von Testdatensätzen ein praktischer Vergleich beider Verfahren durchgeführt.

Uwe Draisbach

6. Verallgemeinertes Verfahren

Zusammenfassung

In diesem Abschnitt wird ein verallgemeinertes Verfahren entwickelt, welches die Vorteile von Blocking und Sorted-Neighborhood-Methode vereint.

Uwe Draisbach

7. Zusammenfassung

Zusammenfassung

Daten liegen heutzutage nicht mehr an einem zentralen Ort vor, sondern sind weltweit verteilt. Für einen vollständigen Überblick über die Daten ist es notwendig verschiedene Quellen zu integrieren. Neben strukturellen und semantischen Heterogenitäten existieren auch Heterogenitäten auf Datenebene. Diese zu lösen und somit eine Verbindung zwischen gleichen Realwelt-Objekten herzustellen ist Aufgabe der Duplikaterkennung.

Uwe Draisbach

Backmatter

Titel: Partitionierung zur effizienten Duplikaterkennung in relationalen Daten
verfasst von: Uwe Draisbach
Verlag: Vieweg+Teubner Verlag
Electronic ISBN: 978-3-8348-8289-9
Print ISBN: 978-3-8348-1772-3
DOI: https://doi.org/10.1007/978-3-8348-8289-9