- AutorIn
- Dr.-Ing. Benjamin Schlegel Technische Universität Dresden, Fakultät Informatik, Institut für Systemarchitektur, Professur für Datenbanken
- Prof. Dr. rer. nat. Rainer GemullaTechnische Universität Dresden, Fakultät Informatik, Institut für Systemarchitektur, Professur für Datenbanken
- Prof. Dr.-Ing. Wolfgang LehnerTechnische Universität Dresden, Fakultät Informatik, Institut für Systemarchitektur, Professur für Datenbanken
- Titel
- Memory-Efficient Frequent-Itemset Mining
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-806316
- Konferenz
- EDBT/ICDT '11: EDBT/ICDT '11 joint conference. Uppsala, 21. - 24. März 2011
- Quellenangabe
- EDBT/ICDT '11: Proceedings of the 14th International Conference on Extending Database Technology
Herausgeber: Anastasia Ailamaki
Herausgeber: Sihem Amer-Yahia
Erscheinungsort: New York
Verlag: ACM
Erscheinungsjahr: 2011
Seiten: 461-472
ISBN: 978-1-4503-0528-0 - Erstveröffentlichung
- 2011
- Abstract (EN)
- Efficient discovery of frequent itemsets in large datasets is a key component of many data mining tasks. In-core algorithms---which operate entirely in main memory and avoid expensive disk accesses---and in particular the prefix tree-based algorithm FP-growth are generally among the most efficient of the available algorithms. Unfortunately, their excessive memory requirements render them inapplicable for large datasets with many distinct items and/or itemsets of high cardinality. To overcome this limitation, we propose two novel data structures---the CFP-tree and the CFP-array---, which reduce memory consumption by about an order of magnitude. This allows us to process significantly larger datasets in main memory than previously possible. Our data structures are based on structural modifications of the prefix tree that increase compressability, an optimized physical representation, lightweight compression techniques, and intelligent node ordering and indexing. Experiments with both real-world and synthetic datasets show the effectiveness of our approach.
- Andere Ausgabe
- Link zum Artikel, der zuerst in der ACM Digital Library erschienen ist.
DOI: 10.1145/1951365.1951420 - Freie Schlagwörter (DE)
- Algorithmen, Leistungsfähigkeit, Datenbankmanagement, Datenbankanwendungen, Data Mining, Datenstrukturen
- Freie Schlagwörter (EN)
- Algorithms, Performance, Database Management, Database Applications, Data mining, Data structures
- Klassifikation (DDC)
- 004
- Verlag
- ACM, New York
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-806316
- Veröffentlichungsdatum Qucosa
- 15.09.2022
- Dokumenttyp
- Konferenzbeitrag
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis