Efficient Top-k Frequent Itemset Mining on Massive Data
Data Science and Engineering · 2024-06 · 9 (2) · 177-203
DOI: 10.1007/s41019-024-00241-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Data Science and Engineering, online erschienen am 06.02.2024. Verfasst von Xiaolong Wan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 25-mal zitiert (Crossref) und nennt 58 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Taishan Scholars Program of Shandong Province.
Abstract (Originalsprache)
Top- k frequent itemset mining (top- k FIM) plays an important role in many practical applications. It reports the k itemsets with the highest supports. Rather than the subtle minimum support threshold specified in FIM, top- k FIM only needs the more understandable parameter of the result number. The existing algorithms require at least two passes of scan on the table, and incur high execution cost on massive data. This paper develops a prefix-partitioning-based PTF algorithm to mine top- k frequent itemsets efficiently, where each prefix-based partition keeps the transactions sharing the same prefix item. PTF can skip most of the partitions directly which cannot generate any top- k frequent itemsets. Vertical mining is developed to process the partitions of vertical representation with the high-support-first principle, and only a small fraction of the items are involved in the processing of the partitions. Two improvements are proposed to reduce execution cost further. Hybrid vertical storage mode maintains the prefix-based partitions adaptively and the candidate pruning reduces the number of the explored candidates. The extensive experimental results show that, on massive data, PTF can achieve up to 1348.53 times speedup ratio and involve up to 355.31 times less I/O cost compared with the state-of-the-art algorithms.
Förderung
- National Natural Science Foundation of China
- Taishan Scholars Program of Shandong Province
Zitieren
APA
Wan, X., & Han, X. (2024). Efficient Top-k Frequent Itemset Mining on Massive Data. Data Science and Engineering, 9(2), 177-203. https://doi.org/10.1007/s41019-024-00241-2
Vancouver
Wan X, Han X. Efficient Top-k Frequent Itemset Mining on Massive Data. Data Science and Engineering. 2024;9(2):177-203. doi:10.1007/s41019-024-00241-2
BibTeX
@article{Wan2024,
author = {Wan, Xiaolong and Han, Xixian},
title = {Efficient Top-k Frequent Itemset Mining on Massive Data},
journal = {Data Science and Engineering},
year = {2024},
volume = {9},
number = {2},
pages = {177--203},
doi = {10.1007/s41019-024-00241-2}
}
EUVIMED