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-53564
URL: http://opus.kobv.de/ubp/volltexte/2011/5356/


Abedjan, Ziawasch ; Naumann, Felix

Advancing the discovery of unique column combinations

pdf-Format:
Dokument 1.pdf (695 KB) (SHA-1:1162518152095b5f5f220797f66c1ae0006948c8)


Kurzfassung in Englisch

Unique column combinations of a relational database table are sets of columns that contain only unique values. Discovering such combinations is a fundamental research problem and has many different data management and knowledge discovery applications. Existing discovery algorithms are either brute force or have a high memory load and can thus be applied only to small datasets or samples. In this paper, the wellknown GORDIAN algorithm and "Apriori-based" algorithms are compared and analyzed for further optimization. We greatly improve the Apriori algorithms through efficient candidate generation and statistics-based pruning methods. A hybrid solution HCAGORDIAN combines the advantages of GORDIAN and our new algorithm HCA, and it significantly outperforms all previous work in many situations.

Kurzfassung in Deutsch

Unique-Spaltenkombinationen sind Spaltenkombinationen einer Datenbanktabelle, die nur einzigartige Werte beinhalten. Das Finden von Unique-Spaltenkombinationen spielt sowohl eine wichtige Rolle im Bereich der Grundlagenforschung von Informationssystemen als auch in Anwendungsgebieten wie dem Datenmanagement und der Erkenntnisgewinnung aus Datenbeständen. Vorhandene Algorithmen, die dieses Problem angehen, sind entweder Brute-Force oder benötigen zu viel Hauptspeicher. Deshalb können diese Algorithmen nur auf kleine Datenmengen angewendet werden. In dieser Arbeit werden der bekannte GORDIAN-Algorithmus und Apriori-basierte Algorithmen zum Zwecke weiterer Optimierung analysiert. Wir verbessern die Apriori Algorithmen durch eine effiziente Kandidatengenerierung und Heuristikbasierten Kandidatenfilter. Eine Hybride Lösung, HCA-GORDIAN, kombiniert die Vorteile von GORDIAN und unserem neuen Algorithmus HCA, welche die bisherigen Algorithmen hinsichtlich der Effizienz in vielen Situationen übertrifft.

Freie Schlagwörter (Deutsch): Apriori , eindeutig , funktionale Abhängigkeit , Schlüsselentdeckung , Data Profiling
Freie Schlagwörter (Englisch): apriori , unique , functional dependency , key discovery , data profiling
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: 51
Sprache: Englisch
Erstellungsjahr: 2011
Publikationsdatum: 28.09.2011
Bemerkung:
In Printform erschienen im Universitätsverlag Potsdam:

Abedjan, Ziawasch:
Advancing the discovery of unique column combinations / Ziawasch Abedjan ; Felix Naumann. - Potsdam : Universitätsverlag Potsdam, 2011. - 25 S. : graph. Darst.
(Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam ; 51)
ISBN 978-3-86956-148-6
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