Eingang zum Volltext in OPUS

Home | Suche | Browsen

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:517-opus-53007
URL: http://opus.kobv.de/ubp/volltexte/2012/5300/


Draisbach, Uwe ; Naumann, Felix ; Szott, Sascha ; Wonneberg, Oliver

Adaptive windows for duplicate detection

pdf-Format:
Dokument 1.pdf (714 KB) (SHA-1:27a7288f88c0be0b32c1bcc2d69f05b3235887cc)


Kurzfassung in Englisch

Duplicate detection is the task of identifying all groups of records within a data set that represent the same real-world entity, respectively. This task is difficult, because (i) representations might differ slightly, so some similarity measure must be defined to compare pairs of records and (ii) data sets might have a high volume making a pair-wise comparison of all records infeasible. To tackle the second problem, many algorithms have been suggested that partition the data set and compare all record pairs only within each partition. One well-known such approach is the Sorted Neighborhood Method (SNM), which sorts the data according to some key and then advances a window over the data comparing only records that appear within the same window.
We propose several variations of SNM that have in common a varying window size and advancement. The general intuition of such adaptive windows is that there might be regions of high similarity suggesting a larger window size and regions of lower similarity suggesting a smaller window size. We propose and thoroughly evaluate several adaption strategies, some of which are provably better than the original SNM in terms of efficiency (same results with fewer comparisons).

Kurzfassung in Deutsch

Duplikaterkennung beschreibt das Auffinden von mehreren Datensätzen, die das gleiche Realwelt-Objekt repräsentieren. Diese Aufgabe ist nicht trivial, da sich (i) die Datensätze geringfügig unterscheiden können, so dass Ähnlichkeitsmaße für einen paarweisen Vergleich benötigt werden, und (ii) aufgrund der Datenmenge ein vollständiger, paarweiser Vergleich nicht möglich ist. Zur Lösung des zweiten Problems existieren verschiedene Algorithmen, die die Datenmenge partitionieren und nur noch innerhalb der Partitionen Vergleiche durchführen. Einer dieser Algorithmen ist die Sorted-Neighborhood-Methode (SNM), welche Daten anhand eines Schlüssels sortiert und dann ein Fenster über die sortierten Daten schiebt. Vergleiche werden nur innerhalb dieses Fensters durchgeführt.
Wir beschreiben verschiedene Variationen der Sorted-Neighborhood-Methode, die auf variierenden Fenstergrößen basieren. Diese Ansätze basieren auf der Intuition, dass Bereiche mit größerer und geringerer Ähnlichkeiten innerhalb der sortierten Datensätze existieren, für die entsprechend größere bzw. kleinere Fenstergrößen sinnvoll sind. Wir beschreiben und evaluieren verschiedene Adaptierungs-Strategien, von denen nachweislich einige bezüglich Effizienz besser sind als die originale Sorted-Neighborhood-Methode (gleiches Ergebnis bei weniger Vergleichen).

Freie Schlagwörter (Deutsch): Informationssysteme , Datenqualität , Datenintegration , Duplikaterkennung
Freie Schlagwörter (Englisch): Duplicate Detection , Data Quality , Data Integration , Information Systems
RVK - Regensburger Verbundklassifikation: ST 230
Institut: Hasso-Plattner-Institut für Softwaresystemtechnik GMBH
DDC-Sachgruppe: Informatik
Dokumentart: b Monographie
Schriftenreihe: Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam, ISSN 2191-1665
Bandnummer: 49
Sprache: Englisch
Erstellungsjahr: 2012
Publikationsdatum: 06.02.2012
Bemerkung:
In Printform erschienen im Universitätsverlag Potsdam:

Adaptive windows for duplicate detection / Uwe Draisbach ; Felix Naumann ; Sascha Szott ; Oliver Wonneberg. - Potsdam : Universitätsverlag Potsdam, 2012. - 41 S. : graph. Darst.
(Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam ; 49)
ISBN 978-3-86956-143-1
ISSN (print) 1613-5652
ISSN (online) 2191-1665
--> bestellen
Lizenz: Diese Nutzungsbedingung gilt nicht, wenn in den Metadaten eine modifizierende Lizenz genannt ist. Keine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht


Home | Leitlinien | Impressum | Haftungsausschluss | Statistik | Universitätsverlag | Universitätsbibliothek
Ihr Kontakt für Fragen und Anregungen:
Universitätsbibliothek Potsdam
powered by OPUS  Hosted by KOBV  Open
Archives Initiative  DINI Zertifikat 2007  OA Netzwerk