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