Soft Error Tolerant Count Min Sketches

The estimation of the frequency of the elements on a set is needed in a wide range of computing applications. For example, to estimate the number of hits that a video gets or the number of packets in a network flow. In some cases, the number of elements in the set is very large and it is not practical to maintain a table with the exact count for each of them. Instead, simpler and more efficient data structures, commonly referred to as sketches, that provide an estimate are used. Among those structures the Count Min Sketch (CMS) is one of the most popular sketches. The CMS provides estimates that have one sided errors. In more detail, the CMS returns an estimate that is equal to or larger than the actual value. An update or check requires a small and constant number of memory accesses and the memory footprint is fixed and does not depend on the number of elements. The CMS relies on several arrays of counters that are stored in memory. Memories are prone to suffer soft errors that flip the contents of memory cells due for example to ionizing radiation. Therefore, it is of interest to study the impact that soft errors can have on the CMS estimates and to propose protection techniques that minimize their effect while requiring low overhead in terms of additional memory and circuitry. To the best of our knowledge this has not been done before. In this article, first the effect of soft errors on the CMS is evaluated by injecting errors. Then, in the second part a protection technique that does not require additional memory bits is presented and compared with the protection using a parity bit. In the last part of the article, the technique is extended to protect also against double adjacent bit errors.