A sliding window based algorithm for frequent closed itemset mining over data streams

摘要

Frequent pattern mining over data streams is an important problem in the context of data mining and knowledge discovery. Mining frequent closed itemsets within sliding window instead of complete set of frequent itemset is very interesting since it needs a limited amount of memory and processing power. Moreover, handling concept change within a compact set of closed patterns is faster. However, it requires flexible and efficient data structures as well as intuitive algorithms. In this paper, we have introduced an effective and efficient algorithm for closed frequent itemset mining over data streams operating in the sliding window model. This algorithm uses a novel data structure for storing transactions of the window and corresponding frequent closed itemsets. Moreover, the support of a new frequent closed itemset is efficiently computed and an old pattern is removed from the monitoring set when it is no longer frequent closed itemset. Extensive experiments on both real and synthetic data streams show that the proposed algorithm is superior to previously devised algorithms in terms of runtime and memory usage.