The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O uso de filtros Bloom é um dos métodos de pesquisa mais populares e eficientes em redes P2P. Um filtro Bloom é uma representação de índices de itens de dados, que atinge pequenos requisitos de memória ao permitir erros unilaterais (falso positivo). No esquema de pesquisa baseado no filtro Bloom, cada peer dissemina um filtro Bloom representando índices dos itens de dados que possui antecipadamente. Usando as informações dos filtros Bloom divulgados como pista, cada consulta pode encontrar um caminho curto até seu destino. Neste artigo, propomos uma extensão eficiente do filtro Bloom, chamada de Deterministic Decay Bloom Filter (DDBF) e um método de disseminação de índice baseado nele. Enquanto a disseminação do índice baseado em um filtro Bloom padrão sofre degradação de desempenho por conter informações de muitos itens de dados quando seu raio de disseminação é grande, o DDBF pode contornar tal degradação limitando as informações de acordo com a distância entre o porta-filtro e os porta-itens, isto é, um DDBF contém menos informações para itens distantes e mais informações para itens próximos. Curiosamente, a construção de DDBFs não requer nenhum custo extra superior ao dos filtros padrão. Também mostramos por simulação que nosso método pode obter melhor desempenho de pesquisa do que os existentes.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
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
Copiar
@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},}
Copiar
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 -