A Scalable Association Rules Mining Algorithm Based on Sorting, Indexing and Triming

Apriori is an influential and well-known algorithm for mining association rules. However, the main drawback of Apriori algorithm is the large amount of candidate itemsets it generates. Several hash-based algorithms, such as DHP and MPIP, were proposed to deal with the problem. DHP employs hash functions to filter out potential-less candidate itemsets. MPIP further improves DHP by employing minimal perfect hashing functions to avoid generation of candidate itemsets. Though MPIP results in a very promising mining efficiency, the memory space required in MPIP increases rapidly as the number of items grows. To obtain even better mining efficiency while reducing the memory space required, a sorting-indexing-trimming (SIT) algorithm for mining association rules is proposed in this paper. SIT uses the sorting, indexing, and trimming techniques to reduce the amount of itemsets to be considered. Then, to utilize both the advantages of Ariori and MPIP, a revised MPIP algorithm is employed to deal with 2-itemsets, and a revised apriori algorithm to deal with Mtemsets for k>2. Though the memory space required in SIT is less than MPIP, from the experiment results, SIT outperforms both Apriori and MPIP.