Computer Sciences Dept.

Cristian Estan

Thumbnail portrait
Comparison between multistage filters and sketches for finding heavy hitters
Cristian Estan
UCSD technical report CS2004-0784, April 2004

The purpose of this write-up is to compare multistage filters and sketches with respect to their ability to identify heavy hitters. In a nutshell, the conclusion is that multistage filters as I use them identify heavy hitters with less memory than sketches, but some sketches support important other operations, more specifically they can be added and subtracted without any need to re-read the data stream(s).

Paper in PDF and Postscript.

Computer Sciences | UW Home