Evaluation of the Structured Bloom Filters Based on Similarity
Hiroshi Sakuma, Fumiaki Sato · 2011
The Bloom filter is a data structure which the characteristics of contents is expressed by a bit pattern. 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 previous research, the ring of the Bloom filter, which is like Chord ring, was 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. We also propose similarity-based tree management method which is effective to reduce the cost of reconstruction of the tree. To evaluate our method, the size of filter information and the number of average hops of query forwarding in this research are compared to the existing research. The tree reconstruction cost is also evaluated by simulation.