Verallgemeinertes Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 65

6.3 Analyse des Algorithmus

In diesem Abschnitt erfolgt eine Analyse des zuvor beschriebenen Algorithmus.
Es werden einerseits die Komplexität und der Hauptspeicherbedarf betrachtet, an-
dererseits wird der Algorithmus anhand der Kennzahlen Precision, Recall und
F-Measure für die CD-Testdaten bewertet.

Komplexität
Der Aufwand der Duplikaterkennung ist die Summe der Tupelvergleiche inner-
halb der Partionen und der Tupelvergleiche zwischen den Partitionen. Im Über-
lagerungsbereich werden u Elemente der Partition P i mit jeweils durchschnittlich
u + 1

2 Elementen der Partition P i + 1 verglichen. Sei p die Anzahl der Partitionen und
P i die Menge der Tupel in der i-ten Partition. Dann gibt es insgesamt p − 1 Über-

lagerungsbereiche und es gilt:

p
i = 1 | P i |

u 2

2

+ u

2 +

−| P i |

Anzahl Tupelvergleiche = ( p − 1 )

2

In der Gleichung ist der Sonderfall nicht berücksichtigt. Tritt dieser auf, so sinkt
die Anzahl der Tupelvergleiche, da identische Fenster nur einmal auf Duplikate
geprüft werden. Bei Partitionen gleicher Größe sei m die Partitionsgröße und n die
Gesamtzahl der Tupel mit m

n

=

p . Für diesen Fall gilt:

u 2

p m 2

+ u

2 +

− m

Anzahl Tupelvergleiche = ( p − 1 )

2
Da u eine Konstante ist, ist der zweite Term bei einer Komplexitätsbetrach-
tung dominierend. Die Komplexität der Duplikaterkennung ist damit O

pm 2
2 )=

(

nm
2

O . Die Komplexität der Schlüsselbildung ist wie bei Blocking und der Sorted-

Neighborhood-Methode O

( )

( )

n und ebenso beträgt die Komplexität der Sortierung

m
2 +

O .

Tabelle 6.1 enthält einen Vergleich der Anzahl der Tupelvergleiche für die Sor-
ted-Neighborhood-Methode, das Blocking sowie das verallgemeinerte Verfahren
mit verschiedenen Überlagerungsgrößen. Die Berechnung basiert auf festen Parti-
tionsgrößen mit n

( n log n ) . Die Gesamt-Komplexität beträgt daher O ( n ( log n ))

000.
Wie zu erwarten ist der Aufwand bei festen Partitionsgrößen für Blocking auf-
grund der fehlenden Partitionsüberlagerung geringer als bei der Sorted-Neigh-
borhood-Methode. Der Aufwand des verallgemeinerten Verfahrens entspricht für
m

= 10 .

1 dem Aufwand der Sorted-Neighborhood-Methode und nähert sich mit
steigender Partitionsgröße dem Blocking, bleibt jedoch stets darüber. In Abbildung
6.5 ist dies noch einmal graphisch dargestellt. Es wird ersichtlich, dass der Einfluss
der Überlagerungsgröße mit steigenden Partitionsgrößen abnimmt.

= u +