Vergleich Blocking- und Sorted-Neighborhood-Methode - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 41

In Kapitel 3 wurden alternative Blocking-Methoden vorgestellt. Im Folgenden
wird zur Vereinfachung davon ausgegangen, dass das Blocking durch eine Sortie-
rung und nicht durch Hashing realisiert ist und jeder Block die gleiche Anzahl an
Elementen enthält. Der Blockingschlüssel erfüllt also die Anforderung, die Daten-
sätze möglichst gleichmäßig auf die Blöcke zu verteilen. In der Praxis wird dies
nicht immer möglich sein.
In Abbildung 5.1 sind die beiden Ansätze noch einmal dargestellt. Bei einer
Block- bzw. Fenstergröße von 3 werden 7 Fenster ( F 1 bis F 7 ) für die Sorted-
Neighborhood-Methode bzw. drei Blöcke ( B 1 bis B 3 ) für die Blocking-Methode
verwendet.

Fens ter

F 3 F 6

F 2 F 5

F 1 F 4 F 7

Datensatze 1 2 3 4 5 6 7 8 9

B 1 B 2 B 3

Blocke

Abbildung 5.1: Ansätze der Blocking- und Windowing-Verfahren

Die Duplikaterkennung findet bei beiden Verfahren paarweise für alle Tupel in-
nerhalb eines Blocks bzw. Fensters statt. Hierbei sind die Mengen der miteinander
verglichenen Tupelpaare beider Verfahren jedoch nicht identisch. Dies soll im Fol-
genden anhand eines Beispiels in Abbildung 5.2 dargestellt werden. Gegeben sei-
en 20 Tupel, die anhand eines Sortierschlüssels in eine Reihenfolge gebracht sind.
Bei beiden Verfahren werden Tupel nicht mit sich selber verglichen. Die Sorted-
Neighborhood-Methode ist durch grau gefärbte Kästchen für eine Fenstergröße
w 3 dargestellt. Das Blocking wird durch eine dicke Einrahmung der Blöcke mit

jeweils 5 Tupeln dargestellt.
Sei F i die Menge der Tupelvergleiche eines Fensters, dann ist die Gesamtmenge
der Tupelvergleiche in diesem Beispiel F

=

F 18 . Analog ist B i
die Menge der Tupelvergleiche eines Blocks und für die Gesamtmenge der Tupel-
vergleiche gilt B

= F 1 ∪ F 2 ∪ F 3 ∪ ... ∪

B 4 . In Tabelle 5.1 sind die Tupelvergleiche der
einzelnen Fenster bzw. Blöcke dargestellt. Dabei ist

= B 1 ∪ B 2 ∪ B 3 ∪

40.
Bildet man die Differenz der Mengen B und F , so ergeben sich die Tupelver-
gleiche, die nur durch ein Verfahren abgedeckt werden. Für das oben beschrie-

| F | = 37 und | B | =