Bloom tree: A search tree based on Bloom filters for multiple-set membership testing
Authors:
- 1 April 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1429-1437
Abstract
A Bloom filter is a compact and randomized data structure popularly used for networking applications. A standard Bloom filter only answers yes/no questions about membership, but recent studies have improved it so that the value of a queried item can be returned, supporting multiple-set membership testing. In this paper, we design a new data structure for multiple-set membership testing, Bloom tree, which not only achieves space compactness, but also operates more efficiently than existing ones. For example, when existing work requires 107 bits per item and 11 memory accesses for a search operation, a Bloom tree requires only 47 bits and 8 memory accesses. The advantages come from a new data structure that consists of multiple Bloom filters in a tree structure. We study a theoretical analysis model to find optimal parameters for Bloom trees, and its effectiveness is verified through experiments.Keywords
This publication has 14 references indexed in Scilit:
- The Bloom paradox: When not to use a Bloom filter?2012
- The Variable-Increment Counting Bloom Filter2012
- Fast Dynamic Multiple-Set Membership Testing Using Combinatorial Bloom FiltersIEEE/ACM Transactions on Networking, 2011
- Exact Pattern Matching with Feed-Forward Bloom Filters2011
- BUFFALO2009
- Designing Packet Buffers for Router LinecardsIEEE/ACM Transactions on Networking, 2008
- Beyond bloom filters2006
- Approximate caches for packet classification2005
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000