Module Hub Beta

countminsketch

An approximate items counter

This is trivial implementation of the Count Min Sketch (CMS) from Graham Cormode and S. Muthukrishnan as described in “Approximating Data with the Count-Min Data Structure”.

CMS is a probabilistic data structure that can be used to keep values associated with items, such as the counts of observations of samples in a stream (e.g. IP addresses, URLs, etc…). The counts are only approximated, i.e. there is a probability for error, but the data structure requires considerably less resources compared to storing all samples and their counts.

This implementation employs Redis’ Strings for storing the data structure using direct memory access and 16-bit registers.

© 2017 Redis Labs, Inc. All rights reserved.