BAMBOO: Accelerating closed itemset mining by deeply pushing the length-decreasing support constraint

Mining valid closed itemsets with the length-decreasing support constraint is a particularly challenging problem due to the fact that the downward-closure property cannot be used to prune the search space. In this paper, we have newly proposed several pruning methods and optimization techniques which can push deeply the length-decreasing support constraint into the closed itemset mining, and developed an efficient algorithm, BAMBOO. Our performance study based on various length-decreasing support constraints and datasets with different characteristics has shown that BAMBOO not only generates more concise result set, but also runs orders of magnitude faster than several efficient pattern discovery algorithms. In addition, BAMBOO also shows very good scalability in terms of the database size.