Fast Lossless Frequent Itemset Mining in Data Streams using Crucial Patterns
Ariyam Das, Carlo Zaniolo · 2016
We study the problem of mining exact frequent itemsets from data streams. Since the number of frequent patterns is often quite large, concise representations that save resources by avoiding redundancy are critical for an efficient lossless extraction of frequent patterns. In this paper, we introduce the novel concept of crucial patterns, and formally prove them to be an effective subset of closed frequent itemsets that assures lossless extraction. Extensive experiments confirm that crucial patterns provide a significantly better lossless compression for the frequent itemsets than other condensed representations. Lastly, we propose our new Crucial Pattern Mining (CPM) algorithm for data streams that includes the significant optimization strategies described in the paper. The performance study show that CPM consistently outperforms other state-of-the-art methods by orders of magnitude, on both synthetic and real-world data sets.