addthis/hydra — pull request #76 by mspiegel (2014-04-21 15:20:19+00:00)
Title: New implementation of KeyTopper.

This PR is a reimplementation of the KeyTopper as a replacement of the ConcurrentKeyTopper. There are two purposes of this change: the new implementation uses the correct algorithm for estimating the top-K items. Specifically when a new item is encountered, then a minimum element is evicted and the new item is inserted with value (min + 1). Failure to increment the value breaks all the assumptions used in the theorems of the top-K algorithm. Second the lock-free properties of the data structure are removed. All data structures are currently protected by a write lock. The overhead of the concurrency control is unnecessary at the present time.