Gegenstand der Arbeit - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 1

1 Gegenstand der Arbeit

1.1 Thematischer Überblick

Duplikaterkennung beschreibt Verfahren, um in einem Datenbestand mehrere Da-
tensätze zu identifizieren, die dasselbe Objekt der realen Welt beschreiben. In rela-
tionalen Daten wird dies durch den paarweisen Vergleich zweier Tupel mit einem
Ähnlichkeitsmaß erreicht. Der Abstand der Tupel und ein vorgegebener Schwell-
wert bestimmen dann, ob die Tupel als Duplikat oder Nicht-Duplikat klassifiziert
werden.
Der paarweise Vergleich aller Tupel führt bei n Datensätzen zu n 2

2 Ver-
gleichen (bei 10.000 Datensätzen ca. 50 Mio. Vergleiche). Da der Zeitaufwand
zu groß ist, wird die Relation in geeignete Partitionen unterteilt, und es werden
nur noch Paare innerhalb einer Partition verglichen, ohne dabei die Qualität der
Duplikaterkennung substantiell zu verschlechtern.
Ein Ansatz zur Partitionierung sind Blocking-Verfahren , die die Relation anhand
eines Schlüssels in disjunkte Partitionen unterteilen. Die Effizienz und Effektivi-
tät der Blocking-Methode hängen von der Anzahl der Elemente in jeder Partition
und dem Schlüssel ab. Bei zu vielen Elementen pro Partition werden viele unnöti-
ge Vergleiche durchgeführt. Sind zu wenig Elemente pro Partition vorhanden (im
Extremfall ein Element pro Partition), werden ggf. reale Duplikate nicht gefunden.
Den Blocking-Verfahren stehen Windowing-Verfahren wie die Sorted-Neigh-
borhood-Methode gegenüber, bei der die Datensätze zunächst anhand eines Schlüs-
sels sortiert und anschließend nur Tupel innerhalb der „Nachbarschaft“ verglichen
werden. Hierzu wird ein Fenster mit einer fixen Größe über die sortierten Elemen-
te gelegt und mit der Schrittweite 1 verschoben. Der paarweise Tupel-Vergleich
erfolgt ausschließlich innerhalb des jeweiligen Fensters. Die Effizienz und Effek-
tivität hängen sowohl von der Fenstergröße, als auch von dem Sortierschlüssel ab.
Die miteinander verglichenen Tupel unterscheiden sich bei den genannten Ver-
fahren, was zu abweichenden Ergebnissen bei der Effizienz und Effektivität der
Algorithmen führt. Sie lassen sich jedoch an das jeweilig andere Verfahren an-
gleichen. Bei Windowing-Verfahren geschieht dies durch eine Vergrößerung des
Fensters. Dementsprechend können bei den Blocking-Verfahren überlappende Par-
titionen gebildet werden. Die Vorgehensweise ist in Abbildung 1.1 dargestellt. Sie

( − n ) /