Scalable algorithms for association mining
Mohammed Javeed Zaki · IEEE Transactions on Knowledge and Data Engineering · 2000
Association rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identifying the frequent itemsets, and then forming conditional implication rules among them. We present efficient algorithms for the discovery of frequent itemsets which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The items are organized into a subset lattice search space, which is decomposed into small independent chunks or sublattices, which can be solved in memory. Efficient lattice traversal techniques are presented which quickly identify all the long frequent itemsets and their subsets if required. We also present the effect of using different database layout schemes combined with the proposed decomposition and traversal techniques. We experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.
Cited by 1,751 works. doi:10.1109/69.846291
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Mining association rules between sets of items in large databases
- Fast Algorithms for Mining Association Rules in Large Databases
- Fast algorithms for mining association rules
- Fast discovery of association rules
- An effective hash-based algorithm for mining association rules
- An Efficient Algorithm for Mining Association Rules in Large Databases
- Introduction to Lattices and Order
- Dynamic itemset counting and implication rules for market basket data
- Sampling Large Databases for Association Rules