Database Reference
In-Depth Information
4.3 Union-/Find-Methode
Bei der Union-/Find-Methode werden die Tupel nicht immer direkt miteinander
verglichen, sondern es wird für jede Duplikatgruppe eine Tupelmenge angelegt,
aus der jeweils ein Repräsentant ausgewählt wird. Weiterhin wird eine Vorrang-
warteschlange (Priority Queue) zur Verwaltung der Repräsentanten verwendet. Für
die Tupelmengen gibt es zwei Operationen
12
:
• Union(
x
,
y
)
Vereint die Tupelmengen, in denen
x
und
y
enthalten sind.
• Find(
x
)
Liefert den Repräsentanten der Tupelmenge, in der
x
enthalten ist.
Die Union-/Find-Methode verwendet ebenfalls mehrere Durchläufe von Sortie-
rung und Duplikaterkennung. Monge und Elkan schlagen zwei Durchläufe vor, in
denen die Attribute der Tupel jeweils zu einem String konkateniert werden. Im
ersten Durchlauf erfolgt eine Sortierung alphabetisch von links nach rechts und im
zweiten Durchlauf von rechts nach links.
Für ein neu eingelesenes Tupel
i
wird zunächst mit der Find-Operation geprüft,
ob der Repräsentant der Menge, in der
i
enthalten ist, mit einem Repräsentanten in
der Priority Queue identisch ist. Ist dies der Fall, so ist i schon in einer Tupelmenge
der Priority Queue enthalten und der nächste Datensatz kann gelesen werden. Die
Find-Methode ist dabei nur wenig kostenintensiv. Ergibt die Find-Methode jedoch
keinen Treffer, so wird das Tupel
i
mit Hilfe eines Ähnlichkeitsmaßes mit den Re-
präsentanten der Priority Queue verglichen. Wird eine ausreichende Ähnlichkeit
festgestellt, so wird die Union-Operation ausgeführt und die beiden Tupelmengen
werden vereint. Andernfalls wird das Tupel als Repräsentant einer neuen Menge
in der Priority Queue eingefügt und erhält die höchste Priorität. Durch die Sortie-
rung liegen ähnliche Tupel dicht beieinander. Die Anzahl der Tupelmengen in der
Priority Queue kann daher gering sein (z.B. 4). In Abbildung 4.3 wird noch einmal
der Ablauf der Union-/Find-Methode dargestellt.
12
vgl. hierzu und zum Folgenden [23], S. 24 ff.
Search WWH ::
Custom Search