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

Yusuke TAKAHASHI; Taisuke IZUMI; Hirotsugu KAKUGAWA; Toshimitsu MASUZAWA

doi:10.1093/ietisy/e91-d.7.1971

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

Yusuke TAKAHASHI, Taisuke IZUMI, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E91-D No.7 pp.1971-1981

Publication Date: 2008/07/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e91-d.7.1971

Type of Manuscript: PAPER

Category: Algorithm Theory

Cite this

Copy

Yusuke TAKAHASHI, Taisuke IZUMI, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA, "An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks" in IEICE TRANSACTIONS on Information, vol. E91-D, no. 7, pp. 1971-1981, July 2008, doi: 10.1093/ietisy/e91-d.7.1971.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.7.1971/_p

Copy

@ARTICLE{e91-d_7_1971,
author={Yusuke TAKAHASHI, Taisuke IZUMI, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks},
year={2008},
volume={E91-D},
number={7},
pages={1971-1981},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e91-d.7.1971},
ISSN={1745-1361},
month={July},}

Copy

TY - JOUR
TI - An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks
T2 - IEICE TRANSACTIONS on Information
SP - 1971
EP - 1981
AU - Yusuke TAKAHASHI
AU - Taisuke IZUMI
AU - Hirotsugu KAKUGAWA
AU - Toshimitsu MASUZAWA
PY - 2008
DO - 10.1093/ietisy/e91-d.7.1971
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2008
AB - 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.
ER -