数据流中频繁项近似挖掘算法  

Approximate Algorithm for Mining Frequent Items in Data Streams

作　　者：王述云 张成洪[3] 范颖捷[2] 徐和祥[2] 胡运发[2] 

机构地区：[1]福州大学八方物流学院,福建福州350002 [2]复旦大学计算机与信息技术系,上海200433 [3]复旦大学信息管理与信息系统系,上海200433

出　　处：《小型微型计算机系统》2009年第8期1535-1540,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60736016;70471011)资助;福州大学引进人才启动基金项目资助

摘　　要：提出新的数据结构ESBF(Extensible and Scalable Bloom Filter)-可扩展的Bloom Filter.并提出基于ESBF的数据流中频繁项近似挖掘算法,该算法在保证较高精度的同时,实现比同类算法具有更好的时间效率且在一般情况下具更好的空间效率,并证明只需ln((-M)/(lnρ))·e/ε·1/(ε·M)个计数器就能保证满足用户规定的误差ε及可信度ρ要求.A new data structure-ESBF（extensible and scalable Bloom Filter） is introduced here and a ESBF-based algorithm is also proposed for estimating the frequent items in data streams approximatly. The proposed algorithm can work with high precision and it is more efficient in terms of time and memory consuming than the other algorithms dealing with the frequent itemmining in data streams in most cases. It is also proved here that the number of counter needed is only ln（-M/lnρ）·e/ε·1/ε·M for required precision and probability.

关 键 词：数据流 频繁项 BLOOM FILTER 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]