Windowing-Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 36

w
2

Tupel-Vergleiche 6 , die Komplexität

( − )( − )

Duplikaterkennung benötigt w 1 n

ist daher O . Werden die Phasen seriell ausgeführt, ergibt sich insgesamt ei-

ne Komplexität von O

( wn )

( n ( w + log n )) . Vergleicht man w und log n , so gilt in der

Regel w > log n . Für diesen Fall ist die Gesamt-Komplexität O ( wn ) , ansonsten

O . In Experimenten hat sich eine Fenstergröße von w =20 als ausreichend

erwiesen 7 .
Für sehr große Datenbanken sind die dominierenden Kosten voraussichtlich die
Festplatten-Zugriffe, da nicht alle Daten im Hauptspeicher gehalten werden kön-
nen 8 . Insgesamt müssen die Daten mindestens dreimal gelesen werden, je einmal
pro Phase. Für die Sortierphase sind jedoch mehrere Zugriffs-Durchläufe wahr-
scheinlich.
Die Effektivität der Sorted-Neighborhood-Methode hängt stark vom verwen-
deten Sortierschlüssel ab 9 . Dabei haben Attribute, die am Anfang des Schlüssels
auftreten, einen größeren Einfluss auf das Ergebnis als solche, die erst später auf-
treten. Enthält ein Datensatz in einem Attribut mit großem Einfluss einen Fehler,
so ist es unwahrscheinlich, dass dieser Datensatz in die Nähe ähnlicher Datensätze
sortiert wird. Werden Datensätze beispielsweise anhand der Postleitzahl sortiert,
so ist es unwahrscheinlich, dass die Datensätze mit den Postleitzahlen „19432“
und „91432“ in dasselbe Fenster fallen, obwohl nur die ersten beiden Ziffern ver-
tauscht sind. Der Sortierschlüssel sollte daher invariant sein für typische Fehler
in den Daten, d.h. zwei Tupel mit unterschiedlichen, verfälschten Daten erhalten
trotzdem den identischen Sortierschlüssel 10 . Beispielsweise sollten „Müller“ und
„Mueller“ nicht zu einem unterschiedlichen Sortierschlüssel führen, wenn die rest-
lichen Attribute gleiche Werte haben. Weiterhin ist zu beachten, dass die Anzahl
der Tupel mit identischem Sortierschlüssel nicht größer als das Fenster w ist. An-
dernfalls würden Elemente mit gleichem Sortierschlüssel ggf. nicht in das gleiche
Fenster fallen und könnten somit nicht als Duplikat erkannt werden.
Bisher wurde die Basis-Version der Sorted-Neighborhood-Methode beschrie-
ben, die einen einzigen Durchlauf durch die sortierte Liste beinhaltet. In den fol-
genden Unterkapiteln werden Erweiterungen des Algorithmus vorgestellt, die als
Ziel die Erhöhung der Effektivität bzw. der Effizienz der Sorted-Neighborhood-
Methode haben.

( n log n )

6 vgl. [12], S. 22
7 vgl. [19], S. 342
8 vgl. hierzu und zum Folgenden [16], S.13
9 vgl. hierzu und zum Folgenden [15], S. 131
10 vgl. [26], S. 95 f.