Blocking-Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 31

3 Blocking-Verfahren

In Kapitel 2.3 wurde die Notwendigkeit der Reduzierung des Suchraums bei der
Duplikaterkennung bereits angesprochen. Diese ist notwendig, da ein vollständi-
ger paarweiser Vergleich sämtlicher Tupel bei n Datensätzen zu n 2

n
2 Vergleichen
führt. 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.
Blocking teilt die Gesamtmenge der Datensätze in gleich oder verschieden große
Blöcke auf, die jeweils eine disjunkte Teilmenge der Datensätze enthalten. Sei N
die Menge der Datensätze, b die Anzahl der Blöcke mit b

−

≥ 2 und N i die Menge

der Datensätze im i -ten Block mit 1 ≤ i ≤ b . Dann gelte:

N = N 1 ∪ N 2 ∪ N i ... ∪ N b und

N 1 ∩ N 2 ∩ N i ... ∩ N b = 0

Blocking wird durch Sortierung der Datensätze anhand eines Blocking-Schlüs-
sels realisiert. Datensätze mit dem gleichen Blocking-Schlüssel werden in einem
Block gruppiert. Alternativ zur Sortierung kann auch eine Hash-Funktion verwen-
det werden, wodurch die Datensätze einzelnen Hash-Blöcken zugeordnet werden 1 .
Der Hash-Wert kann jedoch nicht direkt für den Duplikat-Vergleich zweier Tupel
herangezogen werden, da nicht sichergestellt ist, dass der Hash-Wert zweier „ähn-
licher“ Tupel der gleiche ist 2 .
Ein Blocking-Schlüssel besteht aus einem oder mehreren Attributen des Daten-
satzes bzw. aus Teilen der Attribute. Er sollte so gewählt werden, dass Tupel einer
Duplikatengruppe dem gleichen Block zugeordnet werden. Weiterhin sollen eine
große Anzahl an Schlüsseln existieren und die Datensätze möglichst gleichmäßig
auf die Schlüssel verteilt werden. Die für die Schlüsselbildung verwendeten Attri-

1 vgl. [12], S. 22
2 vgl. [13], S. 11