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

5.3 Zusammenfassung für die Entwicklung eines
verallgemeinerten Verfahrens
Dieser Abschnitt soll noch einmal die Ergebnisse des Vergleichs zwischen Block-
ing und Sorted-Neighborhood-Methode im Hinblick auf die Entwicklung eines
verallgemeinerten Verfahrens zusammen fassen. Im ersten Teil des Kapitels wur-
den beide Partitionierungsstrategien theoretisch unter verschiedenen Aspekten mit-
einander verglichen. Relevante Ergebnisse sind:
1. Verglichene Tupelpaare
Die Stärke der Sorted-Neighborhood-Methode liegt in den Übergängen zwi-
schen einzelnen Partitionen. Durch die große Überlappung zwischen den
Partitionen ist eine scharfe Abgrenzung nicht von großer Bedeutung. Es wer-
den allerdings wenige Tupel gefunden, die in der Sortierreihenfolge weiter
voneinander entfernt sind, da die Fenstergröße sehr beschränkt ist.
Blocking demgegenüber erfasst auch weiter entfernte Tupel. Kritisch sind
jedoch die Übergänge zwischen den Blöcken, denn hier ist eine korrekte
Abgrenzung der Tupel durch den Blocking-Schlüssel notwendig.
2. Vergleich des Hauptspeicherbedarfs
Die Sorted-Neighborhood-Methode hat einen sehr geringen Hauptspeicher-
bedarf aufgrund des kleinen Fensters. Beim Blocking ist der Bedarf auf-
grund der höheren Anzahl an Tupeln pro Partition größer. Die Berücksich-
tigung des Hauptspeicherbedarfs ist notwendig, da Festplattenzugriffe die
dominierenden Kosten darstellen und daher möglichst zu vermeiden sind.
3. Angleichung der Verfahren
Eine Angleichung beider Verfahren erfolgt bei der Sorted-Neighborhood-
Methode durch Vergrößerung des Fensters. BeimBlocking erfolgt dies durch
eine Überlagerung der Blöcke.
Im zweiten Teil des Kapitels wurden Blocking und Sorted-Neighborhood-Me-
thode mit Hilfe von Testdaten verglichen. Hierbei bestätigte sich, dass insbeson-
dere die Übergänge zwischen den Partitionen kritisch sind. Die Sorted-Neighbor-
hood-Methode erreicht schon bei kleinen Fenstergrößen sehr gute Ergebnisse beim
Recall, die schon an den vollständigen Vergleich heranreichen.
Beim Blocking sind hierfür deutlich größere Partitionen und damit Tupelver-
gleiche notwendig. Bei kleinen Partitionsgrößen zeigt der Verlauf der Recall-Kurve
Ausschläge nach oben und unten, die mit zunehmender Partitionsgröße jedoch ab-
flachen. Der Grund für die Sprünge im Kurvenverlauf ist der Blockingschlüssel.
Da die Tupel in Blöcke gleicher Größe geschnitten wurden, hat der Blocking-
Schlüssel die Anforderung einer korrekten Abgrenzung zwischen den Blöcken