CFP-tree: A compact disk-based structure for storing and querying frequent itemsets |
| |
Authors: | Guimei Liu Hongjun Lu Jeffrey Xu Yu |
| |
Affiliation: | 1. The Hong Kong University of Science and Technology, Hong Kong;2. The Chinese University of Hong Kong, Hong Kong |
| |
Abstract: | Frequent itemset mining is an important problem in the data mining area with a wide range of applications. Many decision support systems need to support online interactive frequent itemset mining, which is a challenging task because frequent itemset mining is a computation intensive repetitive process. One solution is to precompute frequent itemsets. In this paper, we propose a compact disk-based data structure—CFP-tree to store precomputed frequent itemsets on a disk to support online mining requests. The CFP-tree structure effectively utilizes the redundancy in frequent itemsets to save space. The compressing ratio of a CFP-tree can be as high as several thousands or even higher. Efficient algorithms for retrieving frequent itemsets from a CFP-tree, as well as efficient algorithms to construct and maintain a CFP-tree, are developed. Our performance study demonstrates that with a CFP-tree, frequent itemset mining requests can be responded to promptly. |
| |
Keywords: | Frequent itemset mining Online interactive mining |
本文献已被 ScienceDirect 等数据库收录! |