Database Reference
In-Depth Information
ständige Vergleich haben eine quadratische Komplexität, wohingegen diese für den
Tupelvergleich der Sorted-Neighborhood-Methode linear ist.
Blocking
Sorted
Vollständiger
Neighborhood
Vergleich
Anzahl Tupel-
w
2 )
n 2
n n
b
n
(
w
1
)(
n
vergleiche
Schlüssel-
2 b
2
O
(
n
)
O
(
n
)
entfällt
bildung
Sortierung
O
(
n log n
)
O
(
n log n
)
entfällt
Duplikat-
n 2
2 b )
n 2
2 )
O
(
wn
)
O
(
O
(
erkennung
Gesamt-
n
2 b +
n 2
2 )
(
(
))
O
n
log n
O
(
n
(
w
+
log n
))
O
(
Komplexität
Tabelle 5.2: Vergleich der Komplexitäten
In Abbildung 5.3 wird der unterschiedliche Aufwand für die Duplikaterkennung
deutlich. Für Blocking beträgt die Anzahl der Blöcke b
=
20 und für die Sorted-
Neighborhood-Methode beträgt die Fenstergröße w
20. Aus der Abbildung wird
ersichtlich, dass die Sorted-Neighborhood-Methode für große Mengen von Daten-
sätzen den geringsten Aufwand beim Tupelvergleich erzeugt. Der Aufwand für
das Blocking entspricht nur bei kleinen Block-Größen in etwa dem der Sorted-
Neighborhood-Methode.
Für das Blocking und die Sorted-Neighborhood-Methode stellt sich die Frage,
wie die Blockanzahl b bzw. die Fenstergröße w gewählt werden müssen, damit
beide Verfahren den gleichen Aufwand erfordern. Für diesen Fall gilt:
=
n 2
n
b
2 b )=(
w
2 )
n
(
w
1
)(
n
b
=
2 wn
n
w 2
+
w
Für das Beispiel aus Abbildung 5.2 mit n
=
20 und w
=
3 bedeutet dies:
20 2
400
94
b
=
3 =
4
,
26
2
3
20
20
3 2
+
D.h. für 4,26 Blöcke mit gleicher Blockgröße würde die gleiche Anzahl an Tupel-
vergleichen wie bei der Sorted-Neighborhood-Methode durchgeführt.
 
Search WWH ::




Custom Search