Eingang zum Volltext

Eingang zum Volltext in OPUS

Home | Suche | Browsen

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

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

Ihr Kontakt für Fragen und Anregungen:
Universitätsbibliothek Potsdam