EFFICIENT SUBSET-LATTICE ALGORITHMS FOR MINING CLOSED FREQUENT ITEMSETS AND MAXIMAL FREQUENT ITEMSETS IN DATA STREAMS

摘要

There are multiple applications for using association rules in data streams, such as market analysis, sensor networks and web tracking. Because data streams are continuous, high speed, unbounded and in real time, we can only scan once for data streams. Mining closed frequent itemsets is a further work of mining association rules, where a closed frequent itemset is a frequent itemset which has no superset with the same support. One well-known algorithm for mining closed frequent itemsets based on the sliding window model is the NewMoment algorithm. However, the NewMoment algorithm could not efficiently mine closed frequent itemsets in data streams, since they will generate closed frequent itemsets and many unclosed frequent itemsets. Moreover, when data in the sliding window is incrementally updated, the NewMoment algorithm needs to reconstruct the whole tree structure. On the other hand, a frequent itemset is called maximal, if it is not a subset of any other frequent itemset. One well-known algorithm for mining maximal frequent itemsets based on the sliding window model is called the MFIoSSW algorithm. The MFIoSSW algorithm uses a compact structure to mine the maximal frequent itemsets. However, when the new transaction comes, the number of comparisons between the new transaction and the old transactions is too much. Therefore, in this paper, we propose the Subset-Lattice algorithm, which embed the property of subsets into the lattice structure to efficiently mine closed frequent itemsets and maximal frequent itemsets over a data stream sliding window. Moreover, when data in the sliding window is incrementally updated, our Subset-Lattice algorithms will not reconstruct the whole lattice structure. From our simulation results, we show that our algorithm for mining closed frequent itemsets outperforms the NewMoment algorithm, and our algorithm for mining maximal frequent itemsets also outperforms the MFIoSSW algorithm.