###
DOI:
Journal of Software:2008.19(10):2585-2596

挖掘数据流任意滑动时间窗口内频繁模式
李国徽,陈辉
(华中科技大学 计算机科学与技术学院,湖北 武汉 430074)
Mining the Frequent Patterns in an Arbitrary Sliding Window over Online Data Streams
LI Guo-Hui,CHEN Hui
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3513   Download 3676
Received:November 08, 2007    Revised:January 08, 2008
> 中文摘要: 由于数据流的流动性与连续性,数据流所蕴含的知识会随着时间的推移而发生变化.因此,在绝大多数数据流的应用中,用户往往对新产生的流数据所包含的知识要比对历史流数据所包含的知识感兴趣得多.提出了一种挖掘数据流任意大小滑动时间窗口内频繁模式的方法MSW(mining sliding window).当数据流流过时,该方法使用滑动窗口树SW-tree在单遍扫描流数据的条件下及时捕获数据流上最新的模式信息.同时,该方法还周期性地删除滑动窗口树上过期的及不频繁的模式分支,从而降低滑动窗口树的空间复杂度与维护代价.此外,该方法还应用时间衰减模型逐步降低历史事务模式支持数的权重,并由此来区分最近产生事务与历史事务的模式.大量仿真实验的结果表明,算法MSW具有较高的效率与优良的可扩展性,同时也优于其他同类算法.
Abstract:Because of the fluidity and continuity of data stream, the knowledge embedded in stream data is most likely to be changed as time goes by. Thus, in most data stream applications, people are more interested in the information of the recent transactions than that of the old. This paper proposes a method for mining the frequent patterns in an arbitrary sliding window of data streams. As data stream flows, the contents of the data stream are captured with a compact prefix-tree by scanning the stream only once. And the obsolete and infrequent items are deleted by periodically pruning the tree. To differentiate the patterns of recently generated transactions from those of historic transactions, a time decaying model is also applied. Extensive simulations are conducted and the experimental results show that the proposed method is efficient and scalable, and also superior to other analogous algorithms.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60873030 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z300 (国家高技术研究发展计划(863)) Supported by the National Natural Science Foundation of China under Grant No.60873030 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z300 (国家高技术研究发展计划(863))
Foundation items:
Reference text:

李国徽,陈 辉.挖掘数据流任意滑动时间窗口内频繁模式.软件学报,2008,19(10):2585-2596

LI Guo-Hui,CHEN Hui.Mining the Frequent Patterns in an Arbitrary Sliding Window over Online Data Streams.Journal of Software,2008,19(10):2585-2596