Database Reference
In-Depth Information
geprüft wurden, wird das Fenster innerhalb der sortierten Liste um ein Ele-
ment weitergeschoben, wodurch das erste Element des vorherigen Fensters
aus der Menge der zu vergleichenden Tupel entfällt. Die übrigen
w
1 Ele-
mente des ursprünglichen Fensters sind jedoch auch im neuen Fenster ent-
halten. Um doppelte Duplikatsprüfungen zu vermeiden, müssen diese
w
−
1
Elemente nur mit dem neu hinzugekommenen Element verglichen werden.
Das Verschieben des Fensters endet, sobald das letzte Element der sortierten
Liste erreicht wurde.
−
Häufig wird in einem zusätzlichen vierten Schritt die transitive Hülle der Dupli-
kate gebildet. Abbildung 4.1 verdeutlicht den Ablauf der Sorted-Neighborhood-
Methode.
Element
Key
Element
Key
Element
Key
x
1
x
8
x
8
xy
ar
ar
aktuelles
Fenster
x
2
gh
x
7
bg
x
7
bg
x
3
iw
x
2
gh
x
2
gh
nächstes
Fenster
x
4
pl
x
10
hg
x
10
hg
hj
hj
hj
x5
x5
x5
x
6
x
3
x
3
zt
iw
iw
x
7
x
9
x
9
bg
lo
lo
x
8
ar
x
4
pl
x
4
pl
letztes
Fenster
x
9
lo
x
1
xy
x
1
xy
x
10
hg
x
6
zt
x
6
zt
Schlüsselbildung
Sortierte Liste
Duplikaterkennung
Abbildung 4.1: Ablauf der Sorted-Neighborhood-Methode
4
Der Aufwand für einen Durchlauf der Sorted-Neighborhood-Methode hängt von
zwei Faktoren ab:
1. Anzahl der Elemente:
n
2. Größe des Fensters:
w
Für eine Analyse des Aufwands
5
der Sorted-Neighborhood-Methode müssen
zunächst die Phasen einzeln betrachtet werden. Für die Schlüsselbildung muss je-
der Datensatz einmal gelesen werden. Die Komplexität ist daher
O
, wobei dies
noch nicht die Kosten für die Berechnung des Schlüsselwerts enthält. Die Sortie-
rung der Datensätze verursacht einen Aufwand von
O
(
n
)
(
n
log
n
)
. Die abschließende
4
Quelle: in Anlehnung an [5], S. 114
5
vgl. hierzu und zum Folgenden [16], S. 13
Search WWH ::
Custom Search