Implementing error detection in fast counting Bloom filters. Issue 22 (1st October 2014)

• Record Type: Journal Article
• Authors: Reviriego, P.; Maestro, J.A.
• Is Part Of: Electronics letters. Volume 50:Issue 22(2014)
• Page Start: 1602
• Page End: 1604
• Publication Date: 2014-10-01
• Subjects: data structures -- error detection -- storage management; system failures -- soft errors -- per‐word parity bit -- electronic systems -- memory access -- search operation -- CBF -- computing systems -- networking systems -- fast counting Bloom filters -- error detection; Electronics -- Periodicals; 621.381
• DOI: 10.1049/el.2014.3097
• Languages: English
• ISSNs: 0013-5194

Abstract

Abstract : 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.