MAFIA: a maximal frequent itemset algorithm for transactional databases

TLDR

The paper introduces a new algorithm for mining maximal frequent itemsets from transactional databases and evaluates its components through experimental analysis. The algorithm employs a depth‑first traversal of the itemset lattice with pruning, using a vertical bitmap representation and relative bitmap compression to efficiently search for maximal frequent itemsets. The algorithm is particularly efficient on long itemsets and outperforms prior methods by three to five times.

Abstract

We present a new algorithm for mining maximal frequent itemsets from a transactional database. Our algorithm is especially efficient when the itemsets in the database are very long. The search strategy of our algorithm integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms. Our implementation of the search strategy combines a vertical bitmap representation of the database with an efficient relative bitmap compression schema. In a thorough experimental analysis of our algorithm on real data, we isolate the effect of the individual components of the algorithm. Our performance numbers show that our algorithm outperforms previous work by a factor of three to five.