Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window

TLDR

Time and memory limits prevent monitoring all itemsets, and restricting to frequent ones hinders detection of newly frequent itemsets. The study aims to mine closed frequent itemsets over a sliding window with limited memory by designing a compact synopsis data structure. The authors introduce the closed enumeration tree (CET), a synopsis that maintains a boundary between closed frequent and other itemsets, allowing boundary movements to reflect concept drifts and enabling efficient updates. Because the boundary is stable, mining costs drop to those of transactions that may trigger boundary changes, and experiments show the algorithm outperforms prior methods.

Abstract

This paper considers the problem of mining closed frequent itemsets over a sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of item-sets over a sliding-window. The selected itemsets consist of a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent item-sets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than previous approaches.