New algorithms for fast discovery of association rules

TLDR

Association rule discovery is a key problem in database mining. The authors propose new single‑pass algorithms for fast association mining that aim to efficiently extract all rules in one database scan. The algorithms cluster itemsets using novel techniques—equivalence classes and maximal hypergraph cliques—to approximate potentially maximal frequent itemsets, then traverse the resulting lattice with bottom‑up or hybrid search while exploiting a vertical layout to group related transactions. Experiments demonstrate more than an order of magnitude speedup over previous algorithms.

Abstract

Discovery of association rules is an important problem in database mining. In this paper we present new algorithms for fast association mining, which scan the database only once, addressing the open question whether all the rules can be efficiently extracted in a single database pass. The algorithms use novel itemset clustering techniques to approximate the set of potentially maximal frequent itemsets. The algorithms then make use of efficient lattice traversal techniques to generate the frequent itemsets contained in each cluster. We propose two clustering schemes based on equivalence classes and maximal hypergraph cliques, and study two traversal techniques based on bottom-up and hybrid search. We also use a vertical database layout to cluster related transactions together. Experimental results show improvements of over an order of magnitude compared to previous algorithms.