A Fast and Efficient Algorithm for Finding Frequent Items over Data Stream
Ling Chen, Yixin Chen, Li Tu · Journal of Computers · 2012
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 l is used. Our algorithm can detect e -approximate frequent items of a data stream using O (log λ e) memory space and O (1) time to process each data record. The computation time for answering each query is O ( ), 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.