CFI-Stream: mining closed frequent itemsets in data streams

Nan Jiang, Le GruenwaldKDD 2006 · DOI

TL;DR

This paper introduces CFI-Stream, a novel algorithm for efficiently mining closed frequent itemsets from data streams. Unlike previous methods that require multiple passes or store extensive auxiliary information, CFI-Stream processes transactions online and incrementally, maintaining only the essential closed itemsets and their supports, leading to significant time and space efficiency.

What Problem Does This Paper Address?

Data streams, characterized by their continuous, unbounded, and high-speed nature, present unique challenges for traditional data mining techniques. Specifically, mining closed frequent itemsets (itemsets that are not subsets of any larger frequent itemset) from these streams is difficult. Traditional methods often require multiple scans of static databases, making them impractical for data streams where data is transient and arrives rapidly. Existing stream mining algorithms often focus on general frequent itemsets, not necessarily closed ones, or employ complex data structures and multiple scans, leading to high computational and memory costs, especially when dealing with concept drift (changes in data distribution over time). This paper aims to bridge this gap by providing an efficient, online, and incremental method for mining closed frequent itemsets directly from data streams.

Methods

The core of the proposed solution is the CFI-Stream algorithm and its associated in-memory data structure, the Direct Update (DIU) tree.

  • DIU Tree: This is a lexicographically ordered tree where each node represents a closed itemset. The tree is structured by levels, with level i storing closed i-itemsets. Each node stores the itemset itself, its current support count, and links to parent and child nodes. Crucially, it only stores closed itemsets, making it more compact than methods that store intermediate or boundary nodes.
  • Online and Incremental Processing: CFI-Stream processes transactions as they arrive (online) and updates its state based on previous results (incremental).
  • Closure Checking: The algorithm performs closure checking "on the fly" for both transaction additions and deletions. This involves verifying if an itemset remains closed or becomes closed/unclosed after a transaction enters or leaves the sliding window. The paper meticulously proves conditions under which closure checks are necessary, minimizing unnecessary computations.
  • Efficiency: The algorithm avoids rescanning data. When a transaction arrives, it updates the supports of relevant closed itemsets. When a transaction leaves, it performs similar updates. The key insight is that for most operations, only the supports of existing closed itemsets need updating, rather than recomputing entire sets of itemsets.

Datasets

The paper uses synthetic datasets for evaluation:

  • T10.16.D100K: Represents transactions with an average size of 10, average maximal potential frequent itemset size of 16, and 100,000 total transactions.
  • T5.14.D100K-AB: Represents transactions with an average size of 5, average maximal potential frequent itemset size of 14, and 100,000 total transactions.

These datasets are generated using a method described in reference [1], which is a standard approach for generating synthetic data for association rule mining.

Key Insights and Ideas

  • Focus on Closed Itemsets: By directly mining closed itemsets, the algorithm inherently provides a more condensed representation compared to mining all frequent itemsets, leading to more efficient downstream tasks like rule generation.
  • Minimal Data Structure: The DIU tree's design, storing only closed itemsets and their supports, is a significant departure from methods like "Moment" which store additional "boundary" nodes, leading to better space efficiency.
  • True Online Processing: The "on the fly" closure checking for both additions and deletions allows for real-time updates without the need for multiple passes or batch processing, which is critical for high-speed data streams.
  • Support Independence: The CFI-Stream algorithm's runtime is largely independent of the minimum support threshold. While other algorithms' performance degrades significantly at lower supports (due to more itemsets), CFI-Stream's efficiency stems from its incremental update mechanism, making it robust across different support levels.

Key Results

  • Runtime Performance: CFI-Stream significantly outperforms the state-of-the-art "Moment" algorithm in terms of runtime, especially at lower minimum support thresholds. For instance, Figure 2 shows CFI-Stream running much faster than Moment when the support threshold is low. At higher thresholds, their performance is comparable, with Moment being slightly faster.
  • Memory Usage: CFI-Stream demonstrates superior memory efficiency, particularly at low support thresholds. Figure 3 illustrates that CFI-Stream's memory usage remains relatively stable, whereas Moment's memory usage increases dramatically as the support threshold decreases. This is attributed to Moment's need to store additional boundary nodes.
  • Scalability and Adaptability: The paper claims CFI-Stream has good scalability as the number of processed transactions increases and adapts rapidly to changes in data streams (concept drift).

Limitations and Future Work

  • Limitations: While the paper highlights CFI-Stream's efficiency, it acknowledges that when the minimum support threshold is very high, Moment might run slightly faster. This is because at very high supports, the number of boundary nodes in Moment decreases, and its overhead becomes less significant.
  • Future Work: The authors plan to extend the proposed CFI-Stream algorithm to different data stream applications, suggesting its potential for broader use beyond closed frequent itemset mining.

Summary updated

BibTeX
@inproceedings{jiang2006cfi,
  author = {Nan Jiang and Le Gruenwald},
  title = {{CFI-Stream: mining closed frequent itemsets in data streams}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150473},
}
Figure