A simple algorithm for finding frequent elements in streams and bags Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou   View Paper (PDF)   Return to March 2003, Volume 28, Number 1 Abstract We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold µ . The algorithm requires two passes, linear time, and space 1=µ . The first pass is an on-line algorithm, generalizing a well-known algorithm for finding a majority element, for identifying a set of at most 1=µ items that includes, possibly among others, all items with frequency greater than µ . ©2004 Association for Computing Machinery