Access-Efficient Balanced Bloom Filters

Free registration required

Executive Summary

The implementation of Bloom Filters in network devices ideally has low memory access-rate and low false positive rate. However, since Bloom Filters hash elements to arbitrary memory blocks, they need high memory access rates. On the other hand, Blocked Bloom Filters first hash elements to a single memory block, where they maintain a local Bloom Filter. Therefore, they access only one memory block per element, resulting in better memory-access efficiency. Unfortunately, they have poor performance, with poor load-balancing and high false positive rates. In this paper, the authors propose to implement load-balancing schemes for the choice of the memory block, along with an optional overflow list, resulting in improved false positive rates while keeping a high memory-access efficiency.

  • Format: PDF
  • Size: 220.56 KB