Finding Frequent Items in Time Decayed Data Streams

摘要：

　　Identifying frequently occurring items is a basic building block in many data stream applications.A great deal of work for efficiently identifying frequent items has been studied on the landmark and sliding window models.In this work,we revisit this problem on a new streaming model based on time decay,where the importance of every arrival item is decreased over the time.To address the importance changes over the time,we propose a new heap structure,named Quasiheap,which maintains the item order using a lazy update mechanism.Two approximation algorithms,Space Saving with Quasi-heap (SSQ) and Filtered Space Saving with Quasi-heap (FSSQ),are proposed to find the frequently occurring items based on the Quasi-heap structure.Extensive experiments demonstrate the superiority of proposed algorithms in terms of both efficiency (i.e.,response time) and effectiveness (i.e.,accuracy).

作者: Shanshan Wu Huaizhong Lin Leong Hou U Yunjun Gao Dongming Lu

作者单位: College of Computer Science and Technology,Zhejiang University,Hangzhou,China Department of Computer and Information Science,University of Macau,Macau,China

会议类型: 国际会议

会议名称: International Asia-Pacific Web Conference(第18届国际亚太互联网大会)

会议地点: 苏州

会议语种:英文

页码: 17-29

在线出版日期: 2016-09-23（万方平台首次上网日期，不代表论文的发表时间）