The Tandem Counting Bloom Filter - It Takes Two Counters to Tango Articles uri icon

publication date

  • October 2019

start page

  • 2252

end page

  • 2265

issue

  • 6

volume

  • 27

International Standard Serial Number (ISSN)

  • 1063-6692

Electronic International Standard Serial Number (EISSN)

  • 1558-2566

abstract

  • Set representation is a crucial functionality in various areas such as networking and databases. In many applications, memory and time constraints allow only an approximate representation where errors can appear for some queried elements. The Variable-Increment Counting Bloom Filter (VI-CBF) is a popular data structure for the representation of dynamically-changing sets, achieving a good tradeoff between memory efficiency and queries accuracy. For some applications, the required accuracy is higher than that enabled by the VI-CBF. In this paper, we present the Tandem Counting Bloom Filter (T-CBF), a new data structure that relies on the interaction among counters to describe sets with higher accuracy. We analyze its performance and show that by a joint consideration of counters, the T-CBF always performs better than the VI-CBF and it can for some configurations reduce its false positive probability by an order of magnitude. The overhead of such an approach is expressed upon an element insertion or query as read or write operations to a pair of counters rather than a single counter in each hash location. The operations themselves also require considering a larger number of scenarios.

keywords

  • Filters
    Memory management
    Hash functions
    Routing
    Information filtering
    Bloom filters
    Approximate membership check