Title: Mining Frequent Patterns in an FP-tree Without Conditional FP-tree Generation
Abstract: FP-growth algorithm is one of the most efficient frequent pattern mining methods published recently. However, FP-growth algorithm must generate a huge number of conditional FP-trees recursively in process of mining, so the efficiency of FP-growth remains unsatisfactory. In this paper, the structure of a traditional FP-tree is improved and an efficient frequent pattern-mining algorithm based on constrained sub-tree is proposed. The new FP-tree is a one-way tree and there is no pointers to point its children in each node, so at least one third of memory is saved compared with the former structure in the same storage of frequent pattern information. By introducing constrained sub-tree (consisting of three small arrays), the proposed algorithm doesn't generate conditional FP-trees in mining process and therefore greatly improves the mining efficiency in both time and space. Experiments show that in comparison with FP-growth, this algorithm has accelerated the mining speed by at least two times and reduced the space consumption by half. Moreover, the algorithm has a very good time and space scalability with the number of transactions, and has an excellent performance in dense database mining as well.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 18
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot