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

Schritt 2: Reduzierung des Suchraums
Ein einfacher Algorithmus zur Duplikaterkennung vergleicht mit Hilfe von zwei
geschachtelten Schleifen alle Tupel einer Relation 19 . Da zwei Tupel nur einmal
miteinander verglichen werden müssen und ein Tupel nicht mit sich selbst vergli-
chen werden muss, führt der paarweise Vergleich sämtlicher Tupel bei n Daten-
sätzen zu n 2

− n

2 Vergleichen. Für 10.000 Datensätze sind dies bereits ca. 50 Mio.
Vergleiche. Der Zeitaufwand ist bei großen Datenbanken zu hoch, deshalb ist ei-
ne Reduzierung des Suchraums erforderlich. Die Relation wird daher in geeignete
Partitionen unterteilt, so dass nur noch Paare innerhalb einer Partition verglichen
werden, ohne dabei die Qualität der Duplikaterkennung substantiell zu verschlech-
tern.
Durch die Reduktion des Suchraums kann es jedoch passieren, dass Realwelt-
Duplikate verschiedenen Partitionen zugeordnet werden. Dadurch werden sie nicht
miteinander verglichen und fälschlicherweise als Nicht-Duplikat klassifiziert. Der
Auswahl geeigneter Partitionen kommt also eine besondere Bedeutung zu. Zur
Reduzierung des Suchraums stehen drei verschiedene Methoden zur Verfügung:

• Pruning
Pruning hat das Ziel, Datensätze aus dem Suchraum zu entfernen, die kei-
ne Duplikate sind, ohne jedoch diese Datensätze einem Vergleich zu unter-
ziehen. Sind beispielsweise zwei Datenquellen mit Personendaten gegeben,
wovon die eine Quelle Männer und Frauen und die andere Quelle nur Frauen
enthält, so können die Datensätze der Männer aus der ersten Quelle entfernt
werden. Pruning setzt schon vor dem eigentlichen Vergleich der Tupel an
und kann mit Blocking oder der Sorted-Neighborhood-Methode kombiniert
werden.

• Blocking
Beim Blocking werden die Datensätze in disjunkte Mengen aufgeteilt. Eine
Beschreibung der Blocking-Methode findet sich in Kapitel 3.

• Sorted-Neighborhood-Methode
Die Sorted-Neighborhood-Methode sortiert die Datensätze nach einem Sor-
tierschlüssel und bewegt dann ein Fenster konstanter Länge über die Daten-
sätze. Der Datensatzvergleich reduziert sich dabei um die jeweils im Fens-
ter enthaltenen Datensätze. Eine Beschreibung der Sorted-Neighborhood-
Methode findet sich in Kapitel 4.

19 vgl. hierzu und zum Folgenden [13], S. 11