Evaluation of the Structured Bloom Filter
Fumiaki Sato · 2010
A Bloom filter offers a simple space-efficient randomized data structure for representing a set in order to support membership queries. The Bloom filter has become attractive as one of the methods of looking up data in the distributed system. Since two or more keywords can be used in the method based on the Bloom filter, it is more flexible than the distributed hash table (DHT). Especially, the key aspect of the structured Bloom filter is that the number of query forwarding is fixed. In the research of the past, the ring of the Bloom filter which is like the Chord structure is proposed. However, the node in the ring must maintain many filters corresponding to the number of nodes. In this paper, we propose the tree structured Bloom filter and evaluated the performance of the query forwarding. The size of filter information and the number of average hops of query forwarding in this research are compared to the existing research. The filter information managed in this research is reduced, and the number of hops is smaller than existing research.