very interesting, thanks. I could like to simulate the problem in order to check how my simple algorithm performs compared to others described in the article.

very interesting, thanks. I could like to simulate the problem in order to check how my simple algorithm performs compared to others described in the article. EDIT: I analyzed a bit the differences between Yale University algorithm using M conters and my algorithm. It is interesting that while the Yale's algo gives you all the top elements with a given minimal frequency it is O(M) because you have to decrement M counters for every new element not matching any of elements in the M registers. My algorithm even if randomized (so you are not sure you track all the top M elements, but the output will be an approximation of that) can bring the M-probably-top-elements using O(1) time for element. The memory used is O(M) in both the algorithms. I wonder if the algorithm I proposed was described or not. Note how you can trade time for accuracy selecting more accurately what element to drop to add the next one. If you sample three elements dropping the minimum of the three the accuracy will be a given one, but if you sample ten elements it will be different. I wonder if somebody is able here to analyze this algorithm more in depth.