Mining association rules: anti-skew algorithms

TLDR

Mining association rules in large databases is a key data mining problem, yet all existing methods require scanning the database at least once or almost twice in the worst case. The authors propose techniques that address data skew in basket data. Their algorithms leverage prior knowledge collected during mining and sampling to reduce candidate itemsets and detect false candidates early, thereby cutting scan counts. These techniques lower the maximum number of scans to less than two and, in most cases, find all association rules in about one scan.

Abstract

Mining association rules among items in a large database has been recognized as one of the most important data mining problems. All proposed approaches for this problem require scanning the entire database at least or almost twice in the worst case. We propose several techniques which overcome the problem of data skew in the basket data. These techniques reduce the maximum number of scans to less than 2, and in most cases find all association rules in about 1 scan. Our algorithms employ prior knowledge collected during the mining process and/or via sampling, to further reduce the number of candidate itemsets and identify false candidate itemsets at an earlier stage.