Applications Of Bloom Filters In Peer-To-Peer Systems: Issues And Questions

Bloom filter is a widely-used data structure that concisely represents a large set of contents for approximate membership queries. Due to its good space efficiency, Bloom filter has been applied or customized in a variety of P2P system designs in the recent years. Although the basic idea of Bloom filter is explained each time it is used, elaborative details are ignored. However, we argue that it is not always a trivial task to make a good decision on specific design aspects when applying Bloom filters in P2P systems. If not well deployed, the overhead and side effects of Bloom filters may outweigh their benefits. In this paper we study Bloom filter in the context of P2P systems, and explore its design space on several important issues. Our goal is to provide an in-depth understanding on Bloom filter\u27s strength and weakness, and gain an insight into its usage in P2P systems. In addition, we raise some open questions that deserve further discussion among the P2P community. © 2008 IEEE