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

6 Verallgemeinertes Verfahren

In diesem Abschnitt wird ein verallgemeinertes Verfahren entwickelt, welches die
Vorteile von Blocking und Sorted-Neighborhood-Methode vereint.

6.1 Untersuchung der optimalen
Partitionsüberschneidung

Die bisher vorgestellten Partitionierungsverfahren Blocking und Sorted-Neighbor-
hood-Methode verwenden bzgl. der Überlagerung der Partitionen zwei Extreme.
In Kapitel 5 wurde die Überlagerung zweier Partitionen P 1 und P 2 definiert als:

U P 1 , P 2 = P 1 ∩ P 2

mit | U P 1 , P 2 | = 0 für Blocking

und | U P 1 , P 2 | = w − 1 für die Sorted-Neighborhood-Methode

In Abbildung 6.1 sind zwei alternative Überlagerungsgrößen u dargestellt, wo-
bei u die Anzahl der Elemente ist, die mit Tupeln der angrenzenden Partition ver-
glichen werden. Hierbei kann u sowohl als absolute Zahl, als auch in Abhängigkeit
von der Partitionsgröße p 8 angegeben werden. Tupel, die in mehreren Partitio-

nen auftreten, sind schraffiert markiert. Je größer die Überlagerung, desto mehr
Partitionen werden bei einer festen Partitionsgröße benötigt und damit steigt auch
die Anzahl der Tupelvergleiche.
Die optimale Überlagerungsgröße ist so zu wählen, dass ein möglichst großer
Anteil der echten Duplikate innerhalb einer Sortierreihenfolge abgedeckt ist, auch
wenn sie nicht in der gleichen Partition enthalten sind. Hierdurch wird sicherge-
stellt, dass die Tupel einer Duplikatgruppe miteinander verglichen werden, un-
abhängig davon, ob der Partitionierungsschlüssel eine geeignete Abgrenzung zwi-
schen den Partitionen erreicht. Im Folgenden werden noch einmal die CD-Testdaten
aus Kapitel 5 betrachtet, für die sich verschiedene Sortierschlüssel definieren las-
sen. In Abbildung 6.2 ist dargestellt, wie groß der Abstand der echten Duplikate
bei verschiedenen Sortierschlüsseln ist, wobei zwei direkt nebeneinander liegen-
de Tupel einen Abstand von 1 haben. Analog zu Kapitel 5.2.2 wurden die Sor-
tierschlüssel aus jeweils den ersten drei Buchstaben der drei Attribute „artist1“,

=