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

terscheiden. Ziel der Arbeit ist ein Vergleich zwischen Blocking- und Windowing-
Verfahren und die Entwicklung eines neuen, verallgemeinerten Verfahrens. Hierzu
ist zu charakterisieren, wie stark sich die Partitionen im optimalen Fall überlappen
sollen. Zunächst sollen die Basisalgorithmen beider Verfahren implementiert und
anhand von Testdatensätzen quantitativ und qualitativ miteinander verglichen wer-
den. Die gewonnenen Erkenntnisse fließen dann in die Entwicklung eines neuen,
verallgemeinerten Verfahrens. Dieses soll im Vergleich zu den Windowing- und
Blocking-Verfahren die Effizienz der Duplikaterkennung steigern.
1.2 Aufbau der Arbeit
Schwerpunkt der Arbeit ist ein Vergleich vonWindowing- und Blocking-Verfahren
zur Partitionierung von relationalen Daten bei der Duplikaterkennung. In Kapi-
tel 2 wird zunächst ein Überblick über Duplikaterkennung gegeben. Neben ei-
ner Betrachtung, wie Duplikate entstehen und welche Auswirkungen sie haben,
wird auch der Duplikaterkennungs-Prozess beschrieben. Kapitel 2.4 beschäftigt
sich mit der Ähnlichkeitsmessung und stellt verschiedene Maße vor, mit denen die
Ähnlichkeit zweier Tupel bestimmt werden kann. Den Abschluss bildet Kapitel
2.5, in dem die Messung der Qualität der Duplikaterkennung beschrieben wird.
Es werden Kennzahlen vorgestellt, mit denen die Effektivität und Effizienz der
Duplikaterkennung quantifizierbar gemacht werden können.
Kapitel 3 und Kapitel 4 beschreiben zwei Partitionierungsstrategien, mit de-
nen die Effizienz der Duplikaterkennung gesteigert werden kann. Kapitel 3 erläu-
tert zunächst das Blocking, bei dem die Gesamtmenge der Datensätze in disjunk-
te Teilmengen aufgeteilt wird. Kapitel 4 stellt ein Windowing-Verfahren, genau-
er gesagt die Sorted-Neighborhood-Methode vor. Zu dem ursprünglichen Basis-
Algorithmus der Sorted-Neigborhood-Methode von Hernandez und Stolfo 1 wer-
den auch noch Erweiterungen wie das Multipass-Verfahren und die inkrementelle
Sorted-Neighborhood-Methode vorgestellt.
Kapitel 5 vergleicht dann die beiden Partitionierungsstrategien Blocking und
Sorted-Neighborhood. Neben einer theoretischen Betrachtung der beiden Verfah-
ren erfolgt auch ein praktischer Vergleich anhand von Testdatensätzen. Für den
Vergleich wird auf die theoretischen Grundlagen aus Kapitel 2 zurückgegriffen,
insbesondere auf die Kennzahlen zur Güte der Duplikaterkennung (siehe Kapitel
2.5).
In Kapitel 6 wird ein neues Partitionierungsverfahren entwickelt, basierend auf
dem Vergleich aus Kapitel 5. Dieses Verfahren hat das Ziel, die Effizienz der Du-
1 vgl. [15]