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

Partition während des paarweisen Vergleichs zwischenzeitlich auf die Festplatte
auszulagern und später für weitere Vergleiche wieder einzulesen. Dies verursacht
einen hohen Aufwand. Daher ist bei einem Vergleich von Partitionierungsverfah-
ren auch der benötigte Hauptspeicher zu berücksichtigen. Die Sorted-Neighbor-
hood-Methode hat hierbei aufgrund der konstanten Fenstergröße nur einen gerin-
gen Bedarf. Blocking erreicht einen niedrigen Speicherbedarf, wenn bei großen
Datenmengen die Anzahl der Blöcke entsprechend groß gewählt wird.

Angleichung der Verfahren
Wie bereits dargestellt, werden bei Blocking und Sorted-Neighborhood-Metho-
de unterschiedliche Tupelpaare miteinander verglichen, was zu unterschiedlichen
Ergebnissen führt. Beide Verfahren lassen sich jedoch aneinander angleichen, d.h.
ein Verfahren führt mindestens die gleichen Tupelvergleiche wie das andere Ver-
fahren aus. Für die Sorted-Neighborhood-Methode bedeutet dies, dass die Fenster-
größe w erhöht wird. Dies führt jedoch dazu, dass die Anzahl der Tupelvergleiche
ebenfalls steigt. Die Veränderung der Effizienz der Sorted-Neighborhood-Methode
hängt dann davon ab, wieviel echte Duplikate der Realwelt durch die Vergrößerung
des Fensters zusätzlich gefunden werden. Im Allgemeinen ist jedoch mit einer Re-
duktion der Effizienz zu rechnen, da der Abstand der zusätzlich in einem vergrö-
ßerten Fenster verglichenen Elemente sich innerhalb der sortierten Liste erhöht
und daher Duplikate unwahrscheinlicher werden.
Eine Angleichung des Blocking-Verfahrens an die Sorted-Neighborhood-Me-
thode kann dagegen nicht über eine Vergrößerung der Blöcke erfolgen. Wie bereits
angesprochen, sind die Übergänge zwischen den Blöcken kritisch, da hier benach-
barte Elemente im Gegensatz zur Sorted-Neighborhood-Methode nicht miteinan-
der verglichen werden. Dieses Problem bleibt jedoch, wenn die Blockgröße erhöht
wird. Daher erfolgt eine Angleichung durch eine Überlappung der Blöcke, wo-
durch die einzelnen Blöcke nicht mehr disjunkt sind. Die Größe der Überlappung
definiert dabei einerseits die zusätzlichen Tupel-Vergleiche, anderseits den Grad
der Angleichung an die Sorted-Neighborhood-Methode. Sei wie bisher n die An-
zahl der Tupel, b die Anzahl der Blöcke und b die Anzahl der Tupel pro Block.
Dann liegt die Überlappung der Blöcke zwischen 1 und b − 1, wobei eine Über-

lappung von b −

1 der Sorted-Neighborhood-Methode entspricht.
Die Anpassung der beiden Verfahren ist noch einmal in Abbildung 5.5 darge-
stellt.