Finding Frequent Items in a Turnstile Data Stream

摘要：

Because of important applications such as denial-ofservice attack detection, finding frequent items in data streams under different models has been studied extensively. Finding frequent items in a turnstile data stream is the most challenging because both insertions and deletions of items are allowed in the stream. In this paper, we propose a deterministic algorithm that solves the problem. Furthermore, we propose a randomized algorithm for the problem. Empirical results show that our randomized algorithM provides better results than existing randomized algorithms for the problem and our algorithm uses much smaller space, and supports faster query time and similar update time.

作者: Regant Y.S. Hung Kwok Fai Lai Hing Fung Ting

作者单位: Department of Computer Science,The University of Hong Kong,Pokfulam, Hong Kong Department of Computer Science,The University of Hong Kong, Pokfulam, Hong Kong

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 498-509

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