Mining frequent closed itemsets over data stream based on Bitvector and digraph
Guanglu Zhang, Jingsheng Lei, Xinghui Wu · 2010
A data stream is a continuous, huge, fast changing, rapid, infinite sequence of data elements. The nature of streaming data makes it essential to use online algorithms which require only one scan over the data for knowledge discovery. Mining frequent patterns on streaming data is a new challenging problem. Recent research mainly focuses on mining frequent itemsets over data stream. However, when the threshold of support set is small, the number of frequent itemsets is staggering. moreover frequent closed itemsets is completely contains the information of frequent itemsets and the total number of frequent closed itemsets is still much smaller than that of frequent itemsets. Therefore, mining frequent closed itemsets is a better choice. In this paper, A new algorithm named MFCIDS_BD (Mining Frequent Closed Itemsets Over Data Stream Based On Bit-vector and Digraph) is proposed to mine frequent all closed itemset in the transaction sliding window over data stream. MFCIDS_BD uses a Bit-vector table based data structure, an an effective bit-sequence representation of items, to dynamically maintain all information over transactions slding window. A digraph based data structure is developed in the MFCIDS_BD to depth-first mine all CFs. The maximum number of nodes in digraph does not exceed the total number of items in data stream. in the mining process, MFCIDS_BD uses simple bit “AND” Operations to calculate the support of itemset. MFC-DS_BD Effectively save the save memory and improve speed. Experimental results show that MFCIDS_BD is effective and efficient.