Approaches for Improving Bloom Filter-Based Set Membership Query


HyunYong Lee, Byung-Tak Lee, Journal of Information Processing Systems Vol. 15, No. 3, pp. 550-569, Jun. 2019  

10.3745/JIPS.04.0116
Keywords: Additional Filters, Bloom Filter, False Positive Probability, Hash table, Processing Time
Fulltext:

Abstract

We propose approaches for improving Bloom filter in terms of false positive probability and membership query speed. To reduce the false positive probability, we propose special type of additional Bloom filters that are used to handle false positives caused by the original Bloom filter. Implementing the proposed approach for a routing table lookup, we show that our approach reduces the routing table lookup time by up to 28% compared to the original Bloom filter by handling most false positives within the fast memory. We also introduce an approach for improving the membership query speed. Taking the hash table-like approach while storing only values, the proposed approach shows much faster membership query speed than the original Bloom filter (e.g., 34 times faster with 10 subsets). Even compared to a hash table, our approach reduces the routing table lookup time by up to 58%.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from November 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Lee, H. & Lee, B. (2019). Approaches for Improving Bloom Filter-Based Set Membership Query. Journal of Information Processing Systems, 15(3), 550-569. DOI: 10.3745/JIPS.04.0116.

[IEEE Style]
H. Lee and B. Lee, "Approaches for Improving Bloom Filter-Based Set Membership Query," Journal of Information Processing Systems, vol. 15, no. 3, pp. 550-569, 2019. DOI: 10.3745/JIPS.04.0116.

[ACM Style]
HyunYong Lee and Byung-Tak Lee. 2019. Approaches for Improving Bloom Filter-Based Set Membership Query. Journal of Information Processing Systems, 15, 3, (2019), 550-569. DOI: 10.3745/JIPS.04.0116.