title: Please identify this algorithm: probabilistic top-k elements in a data stream
body: <p>I remember hearing about the following algorithm some years back, but can't find any reference to it online. It identifies the top <i>k</i> elements (or heavy hitters) in a data stream of <i>n</i> elements using only <i>m</i> counters. This is particularly useful for finding top search terms, network abusers, etc. while using minimal memory.</p>
  
  <p>The algorithm: for each element,</p>
  
  <ol>
  <li>If the element does not already have a counter and counters &lt; <i>m</i>, create a counter for the element and initialize to 1.
  <li>Else if the element does have a counter, increment it.
  <li>Else if the element does not have a counter and counters &gt; <i>m</i>, decrement an existing counter <i>c</i>. If <i>c</i> reaches 0, replace its corresponding element, with the current element. (<i>c</i> is an index into the list of existing counters, where <i>c</i> increases in round robin fashion for each element that reaches this step.)
  </ol>
  
  <p>I have found many other similar algorithms (many of which are listed, though not described, in this wikipedia article about <a href="http://en.wikipedia.org/wiki/Streaming_algorithm#Heavy_hitters" rel="noreferrer">streaming algorithms</a>), but not this one.
  I particularly like it because it is as simple to implement as it is to describe.</p>
  
  <p>But I'd like to learn more about its probabilistic characteristics- if I'm only interested in the top 100 items, what effect does using 1,000 counters instead of 100 counters have?</p>