Fast Mining of Closed Frequent Itemsets in Data Streams

Abstract:

With the emergence of large-volume and high-speed streaming data, traditional techniques for mining closed frequent itemsets has become inefficient. Online mining of closed frequent itemsets over streaming data is one of the most important issues in mining data streams. In this paper, a combinative data structure is designed by using an effective bit-victor to represent items and an extended dictionary frequent item list to record the current closed frequent information in streams. For tremendous reduction of search space, some new search strategies are proposed to avoid a large number of intermediate itemsets generated. Meanwhile, some new pruning strategies are also proposed for the purpose of efficiently and dynamically maintaining of all the closure check operations. Experimental results show that the method proposed is efficient in time, with sound scalability as the number of transactions processed increases and adapts rapidly to the changes in data streams.

• Periodical: Applied Mechanics and Materials (Volumes 263-266)
• Pages: 231-240
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.263-266.231
• Online since: December 2012
• Authors: Yi Min Mao, Zhi Gang Chen, Li Xin Liu
• Keywords: Closed Frequent Item, Data Mining (DM), Data Streams, Frequent Item Set

References

[1] L.Golab, M.T. Ozsu. Issues in Data Stream Management.ACM SIGMOD RECORD.Journal Vol.32(2)(2003),P.5-14.

DOI: 10.1145/776985.776986

[2] Chi, Y, Wang H, Yu P. MOMENT: maintaining closed frequent itemsets over a data stream sliding window,in:Proceedings of the 2004 IEEE International Conference on Data Mining. LosAlamitos, USA: TCCI press, 2004. 59-66.

DOI: 10.1109/icdm.2004.10084

[3] JiangNan, Gruenwald. CFI-stream：Mining closed frequent itemsets in data streams. In：Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, USA:ACM press, 2006. 592-597.

DOI: 10.1145/1150402.1150473

[4] Ranganath, B.N, Murty, M.N. Stream-Close：Fast Mining of Closed Frequent Itemsets in High Speed Data Streams. In：Proceeding of 2008 IEEE International Conference on Data Mining Workshops, Pisa, Italy, 2008.516-525.

DOI: 10.1109/icdmw.2008.51

[5] Hua-Fu Li, Suh-Yin Lee. Mining Frequent Itemsets over Data Streams Using Efficient Window Sliding Techniques. Journal Vol 36(2)(2009),Expert Systems with Applications. P.1466-1477.

DOI: 10.1016/j.eswa.2007.11.061

[6] Yen Show-Jane, Lee Yue-Shi. An efficient algorithm for maintaining frequent closed itemsets over data stream. in：Proceedings of 22nd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, Tainan, Taiwan: IEA/AIE press 2009. 767-776.

DOI: 10.1007/978-3-642-02568-6_78

[7] Cheng James, Ke Yiping, Nq Wilfred. Maintaining frequent closed itemsets over a sliding window[J]. Journal of Intelligent Information Systems. Kluwer Academic Publishers，2008, 31(1): 191-215

DOI: 10.1007/s10844-007-0042-3

[8] Song Wei, Yang Bingru, Xu Zhangyan, et al. An Improved Algorithm for Mining Frequent Closed Itemsets[J]. Computer Research and Development, 2007, 45(2): 278-286 (in Chinese)

[9] C Lucchesc, S Orlando, R Perego. Fast and memory efficient mining of frequent closed itemsets [J]. IEEE Trans on Knowledge and Data Engineering, 2006, 18(1)：21-36.

DOI: 10.1109/tkde.2006.10

[10] Information on http://www.almaden.ibm.com