extensions

The estimation procedure for Count-Min sketch is deliberately simple for efficiency.  Improved estimates can be obtained using more sophisticated estimation.  In this case, the data is formulated as an optimization problem: given the sketch summary, find the "best" input vector that explains the observation, via optimization (somewhat akin to compressed sensing).
"In this paper, we propose a novel approach called lsquare to significantly improve the reconstruction accuracy of the sketch data structure. Given a sketch and a set of keys, we estimate the values associated with these keys by constructing a linear system and finding the optimal solution for the system using linear least squares method. We use a large amount of real Internet traffic data to evaluate lsquare against countmin, the state-of-the-art sketch scheme. Our results suggest that given the same memory requirement, lsquare achieves much better reconstruction accuracy than countmin. Alternatively, given the same reconstruction accuracy, lsquare requires significantly less memory."
"We now present a modification to the Count-Min sketch introduced in [6] that uses fewer
hash functions in a manner similar to our improvement for Bloom filters, at the cost of a
small space increase."
Deterministic bounds for many of the applications of count-min, the cost of quadratic blow-up: size is proportional to epsilon^-2 (deterministic) instead of epsilon^-1 (randomized).
  • The Eternal Sunshine of the Sketch Data Structure.  Xenofontas Dimitropoulos,  Marc Stoecklin, Paul Hurley, Andreas Kind.  Computer NetworksVolume 52, Issue 17, December 2008.

    When summarizing long-running streams, sketches can "saturate".  This paper considers ways to remove old information in the sketch to keep it fresh, via marking and sliding-window techniques.
"Count-Min sketch is an efficient approximate query tool for data stream. In this paper, we address how to further improve its point query performance. Firstly, we modify the estimation method under cash register model, Our method will relieve error propagation. Secondly, we find better method under turnstile model and prove that our method is more efficient than that Count-Min sketch. These conclusions are well supported by experimental results."
Comments