Implementing error detection in fast counting Bloom filters

摘要

Bloom filters have found numerous applications in computing and networking systems. They are used to determine whether a given element is present in a set. Counting Bloom filters (CBFs) are an extension of Bloom filters that supports the removal of elements from the set. Traditional Bloom filters require several memory accesses to determine whether an element is present in the set. Recently, fast CBFs that can complete a search operation with only one memory access have been presented. Modern electronic systems are prone to soft errors. These errors can corrupt the contents of memories, causing system failures. In the case of Bloom filters, errors can cause failures where an element that is in the set is classified as not being in the set and the other way around. To avoid those failures, a per-word parity bit is commonly added to detect errors in memories. It is shown that error detection can be implemented in fast CBFs without adding any parity bit. This is achieved by exploiting the properties of the filters to implement error detection.