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 θ.
No takes yet. Share an insight, caveat, or question.
Karp et al. (2003) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: