BISC
Authors:
Open Access
- 22 October 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 4 (3) , 1-37
Abstract
The performance of a depth-first frequent itemset (FI) miming algorithm is closely related to the total number of recursions. In previous approaches this is mainly decided by the total number of FIs, which results in poor performance when a large number of FIs are involved. To solve this problem, a three-strategy adaptive algorithm, bitmap itemset support counting (BISC), is presented. The core strategy, BISC1, is used in the innermost steps of the recursion. For a database D with only s frequent items, a depth-first approach need up to s levels of recursions to detect all the FIs (up to 2 s ). BISC1 completely replaces these recursions with a special summation that directly calculates the supports of all the possible 2 s candidate itemsets. With BISC1 the run-time is entirely independent of the database after one database scan, and the per-candidate cost is only s . To offset the exponential growth of cost (both time and space) with BISC1 as s increases, a second strategy, BISC2, is introduced to effectively double the acceptable range of s . BISC2 divides an itemset into prefix and suffix and improves the performance by pruning all the itemsets with infrequent prefixes. If the total number of frequent items in D is high, the classic database projection strategy is used. In this case for the first s items a single run of BISC (1 or 2) is applied. For each of the remaining items, a projected database is created and the mining process proceeds recursively. To achieve optimal performance, BISC adaptively decides which strategy to use based on the dataset and minimum support. Experiments show that BISC outperforms previous approaches in all the datasets tested. Even though this does not guarantee that BISC will always perform the best, the result is impressive given the fact that most existing algorithms are only efficient in some types of datasets. The memory usage of BISC is also comparable to those of other algorithms.Keywords
Funding Information
- Research Foundation of The City University of New York (62274-40)
This publication has 9 references indexed in Scilit:
- Association miningACM Computing Surveys, 2006
- Fast algorithms for frequent itemset mining using FP-treesIEEE Transactions on Knowledge and Data Engineering, 2005
- LCM ver.32005
- On benchmarking frequent itemset mining algorithms2005
- Fast vertical mining using diffsets2003
- Mining frequent patterns without candidate generation2000
- Dynamic itemset counting and implication rules for market basket dataACM SIGMOD Record, 1997
- Using a hash-based method with transaction trimming for mining association rulesIEEE Transactions on Knowledge and Data Engineering, 1997
- Mining association rules between sets of items in large databases1993