¹Department of Computer Science, Yangzhou University, Jiangsu, China State Key Lab of Novel Software Tech, Nanjing University, Nanjing, China
²Department of Computer Science, Washington University in St Louis, USA
³Department of Computer Science, Jiangyin Polytechnic College, Jiangyin 214405, China

---

Abstract—We investigate the problem of finding the frequent items in a continuous data stream. We present an algorithm called λ-Count for computing frequency counts over a user specified threshold on a data stream. To emphasize the importance of the more recent data items, a fading factor λ  is used. Our algorithm can detect ε- approximate frequent items of a data stream using O(log_λε) memory space and O(1) time to process each data record. The computation time for answering each query is O( log_λε ), and for answering a query about the frequentness of a given data item is O(1). Experimental study shows that λ-Count outperforms other methods in terms of accuracy, memory requirement, and processing speed.

Index Terms—Data mining, data stream, frequent items.

[PDF]

Cite: Ling Chen, Yixin Chen, Li Tu, "A Fast and Efficient Algorithm for Finding Frequent Items over Data Stream," Journal of Computers vol. 7, no. 7, pp. 1545-1554, 2012.