Approaches for Improving Bloom Filter-Based Set Membership Query
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
We propose approaches for improving Bloom filter in terms of false positive probability and membership queryspeed. To reduce the false positive probability, we propose special type of additional Bloom filters that are usedto handle false positives caused by the original Bloom filter. Implementing the proposed approach for a routingtable lookup, we show that our approach reduces the routing table lookup time by up to 28% compared to theoriginal Bloom filter by handling most false positives within the fast memory. We also introduce an approachfor improving the membership query speed. Taking the hash table-like approach while storing only values, theproposed approach shows much faster membership query speed than the original Bloom filter (e.g., 34 timesfaster with 10 subsets). Even compared to a hash table, our approach reduces the routing table lookup time byup to 58%.
Abstract
We propose approaches for improving Bloom filter in terms of false positive probability and membership queryspeed. To reduce the false positive probability, we propose special type of additional Bloom filters that are usedto handle false positives caused by the original Bloom filter. Implementing the proposed approach for a routingtable lookup, we show that our approach reduces the routing table lookup time by up to 28% compared to theoriginal Bloom filter by handling most false positives within the fast memory. We also introduce an approachfor improving the membership query speed. Taking the hash table-like approach while storing only values, theproposed approach shows much faster membership query speed than the original Bloom filter (e.g., 34 timesfaster with 10 subsets). Even compared to a hash table, our approach reduces the routing table lookup time byup to 58%.
참고문헌 (19)
- S. Dharmapurikar, "Longest prefix matching using bloom filters", IEEE, 2006, pp.14(2), 397~409
- M. Yu, "BUFFALO: bloom filter forwarding architecture for large organizations", Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies, pp.313~324 (2009)
- Hengkui Wu, "SybilBF: Defending against Sybil Attacks via Bloom Filters", ETRI Journal, 33(5), pp.826~829 (2011), 한국전자통신연구원
- J. Byers, "Informed content delivery across adaptive overlay networks", ACM SIGCOMM Computer Communication Review, 32(4), pp.47~60 (2002)
- L. Fan, "Summary cache : a scalable wide-area web cache sharing protocol", IEEE, 2000, pp.8(3), 281~293
- B. H. Bloom, "Space", time trade-offs in hash coding with allowable errors, 1970, pp.13(7), 422~426
- "Click modular router"[URL]
- B. Fan, "Cuckoo filter: Practically better than bloom", Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, pp.75~88 (2014)
- A. Crainiceanu, "Bloofi: a hierarchical Bloom filter index with applications to distributed data provenance", Proceedings of the 2nd International Workshop on Cloud Intelligence (2013)
- J. Lu, "One-hashing bloom filter", Proceedings of 2015 IEEE 23rd International Symposium on Quality of Service (IWQoS), pp.289~298 (2015)
- T. Yang, "A shifting bloom filter framework for set queries", Proceedings of the VLDB Endowment, 9(5), pp.408~419 (2016)
- Y. Liu, "Par-BF : a parallel partitioned Bloom filter for dynamic data sets", The International Journal of High Performance Computing Applications, 30(3), pp.259~275 (2016)
- S. Tarkoma, "Theory and practice of bloom filters for distributed systems", IEEE Communications Surveys & Tutorials, 14(1), pp.131~155 (2011)
- M. Zhong, "Optimizing data popularity conscious bloom filters", Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp.355~364 (2008)
- J. Bruck, "Weighted bloom filter", Proceedings of 2006 IEEE International Symposium on Information Theory, pp.2304~2308 (2006)
- B. Donnet, "Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives", Proceedings of the 2006 ACM CoNEXT Conference (2006)
- C. Kim, "Passive and Active Network Measurement", pp.3~12 (2009), Springer
- "COIN-OR Interior Point Optimizer (IPOPT)"[URL]
- D. Wagner, "Advances in Cryptology-CRYPTO 2002", pp.288~304 (2002), Springer