Code on the web
- High-throughput sketch update on a low-power stream processor, Yu-Kuen Lai, Gregory T. Byrd, ANCS 2006. Presentation.
Lai and Byrd report on an implementation of Count-Min sketches on a low-power stream processor, capable of processing 40byte packets at a throughput rate of up to 13Gbps. This is equivalent to about 44 million updates per second.
- On Efficient Query-Processing of Stream Counts on the Cell Processor, D. Thomas, R.
Bordawekar, C. Aggarwal, P. Yu. ICDE 2009.
Implementation from IBM shows that Count-min sketch can be adapt well to parallelism (in this case, IBM cell processor) and achieve almost full parallelism.
- Implementing On-line Sketch-Based Change Detection on a NetFPGA Platform, Yu-Kuen Lai, Nan-Cheng Wang, Tze-Yu Chou, Chun-Chieh Lee, Theophilus Wellem, Hargyo Tri Nugroho, NetFPGA 2010
Implementation of sketches for network anomaly detection, capable of processing 4Gbps.
Other Implementation Studies
- Holistic udafs at streaming speeds, G. Cormode, F. Korn, S. Muthukrishnan, T. Johnson, O. Spatscheck, and D. Srivastava. SIGMOD, 2004.
- Supratik Bhattacharyya,
How to scalably and accurately skip past streams.
ICDE Workshops 2007: 654-663
- Methods for finding frequent items in data streams, G. Cormode and M. Hadjieleftheriou. . The VLDB Journal, 19(1):3-20, 2010.