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

bute dürfen nur eine geringe Wahrscheinlichkeit für fehlerhafte Werte aufweisen,
um eine falsche Zuordnung zu vermeiden 3 . Die hierdurch gebildeten Blöcke wei-
sen eine variable Blockgröße auf. Blöcke konstanter Größe werden erreicht, indem
die Datensätze wie beschrieben sortiert werden, die Blockzuweisung jedoch nicht
anhand des Blocking-Schlüssels erfolgt, sondern jeweils eine feste Anzahl an Da-
tensätzen den einzelnen Blöcken zugewiesen wird. Hierdurch entsteht jedoch das
Problem, dass Duplikate mit gleichem Blocking-Schlüssel trotzdem unterschied-
lichen Blöcken zugewiesen und somit nicht als Duplikat erkannt werden.
Für eine Betrachtung des Aufwands der Duplikaterkennung mit Blocking sei n
die Anzahl der Datensätze und b die Anzahl der Blöcke 4 . Wenn alle Blöcke die
gleiche Größe haben, so hat jeder Block b Datensätze. Der paarweise Vergleich
aller Datensätze pro Block verursacht für alle Blöcke einen Aufwand von O

b
2 ∗

(

n 2
2 b )

n
b )

n
b ))

2

(( ergibt. Zusätzlich müssen noch der Blocking-Schlüssel be-

rechnet und die Datensätze in Blöcke gruppiert werden, was einen Gesamtaufwand
von O

− was O (

n 2
2 b )

( h ( n )+ , mit h ( n )= n ∗ log n für die Sortierung bzw. h ( n )= n für das Ha-

shing ergibt.
Sind die Blöcke unterschiedlich groß, so gilt n

n i , wobei n i die
Anzahl der Datensätze des i-ten Block enthält. Für die Duplikaterkennung wer-
den somit

= n 1 + n 2 + ... +

i = 1 n i Vergleiche durchgeführt. Aufgrund des quadratischen Aufwands
der Duplikaterkennung pro Block, hängt der Aufwand bei variablen Blockgrößen
maßgeblich von der Anzahl Datensätzen im größten Block ab. Abbildung 3.1 zeigt
noch einmal den Unterschied zwischen variabler und fester Blocklänge.

b

∑

Sortierung

n
b

2 n

b

3 n

b

4 n

b

bn
b

0

Feste Blocklange

Block 1 Block 2 Block 3 Block 4 Block b

Variable Blocklange

Block 1 Block 2 Block 3 Block 4 Block b

Blocking-Schlussel andert Wert

Gesamt n Datensatze

Abbildung 3.1: Blocking-Verfahren

3 vgl. [17], S. 415
4 vgl. hierzu und zum Folgenden [5], S. 104