Bitmap based algorithms for mining association rules.
Georges Gardarin, Philippe Pucheral, Fei Wu · 1998
: Discovery of association rules is an important problem in Data Mining. The classical approach is to generate all itemsets that have support (i.e., the fraction of transactions containing the itemset) above a user given threshold. Most existing algorithms aim at reducing the number of scans over the transaction database, i.e., the I/O overhead. We consider the problem of how to calculate efficiently the support, i.e., we try to optimize both I/O and CPU time. A straightforward way is to maintain, for each itemset, the relevant transaction identifiers directly into a list and use a sort-merge algorithm to do the intersection of two itemsets. Instead, we propose bitmap based algorithms. The basic idea is that every couple is represented by a bit in an index bitmap, and the logical operation AND is used in place of the sort-merge algorithm. We propose two variations of the bitmap based algorithm : the naïve bitmap algorithm (N-BM) and the hierarchical bitmap algorith...