An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks

Yusuke TAKAHASHI  Taisuke IZUMI  Hirotsugu KAKUGAWA  Toshimitsu MASUZAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.7   pp.1971-1981
Publication Date: 2008/07/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.7.1971
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
Keyword: 
Bloom filter,  unstructured P2P networks,  lookup problem,  index dissemination,  query routing,  

Full Text: PDF(515.1KB)>>
Buy this Article




Summary: 
Using Bloom filters is one of the most popular and efficient lookup methods in P2P networks. A Bloom filter is a representation of data item indices, which achieves small memory requirement by allowing one-sided errors (false positive). In the lookup scheme besed on the Bloom filter, each peer disseminates a Bloom filter representing indices of the data items it owns in advance. Using the information of disseminated Bloom filters as a clue, each query can find a short path to its destination. In this paper, we propose an efficient extension of the Bloom filter, called a Deterministic Decay Bloom Filter (DDBF) and an index dissemination method based on it. While the index dissemination based on a standard Bloom filter suffers performance degradation by containing information of too many data items when its dissemination radius is large, the DDBF can circumvent such degradation by limiting information according to the distance between the filter holder and the items holders, i.e., a DDBF contains less information for faraway items and more information for nearby items. Interestingly, the construction of DDBFs requires no extra cost above that of standard filters. We also show by simulation that our method can achieve better lookup performance than existing ones.