| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2006-11-17 12:50 ［奨励講演］P2Pネットワークにおける決定性減衰型ブルームフィルタの提案と検索効率の評価 ○高橋佑典（阪大）・泉 泰介（名工大）・増澤利光（阪大）  NS2006-133 |
|
| 抄録 | （和） | ブルームフィルタは，データアイテム集合のインデックス情報を効果的に表現するための一つの手法である．ブルームフィルタは誤検出を生じる可能性があるが，一方で少ないメモリ領域で実現可能という利点がある．そのため，P2Pネットワークにおいて，各ノードが自分の所持するデータアイテム集合に対するブルームフィルタを近隣ノードに散布することで，検索効率を上げる手法が提案されている．我々は以前の報告において，従来のブルームフィルタを改良した，決定性減衰型ブルームフィルタ(DDBF)，および，それに基づく検索手法を提案した．従来のブルームフィルタでは，散布半径の増加に伴い，1フィルタが表すデータアイテム数が増えるため，誤検出確率が増加するという問題が存在するが，DDBFでは，ノードが散布するフィルタ構成のための情報量を距離に応じて減衰させることで，1ノードが収集する情報の量を削減し，誤検出確率の増加を抑えることができる．本稿では，従来のDDBFによる検索手法において，データアイテムの検索頻度に応じて散布半径を変更する手法を併せて用いることで，更なる検索効率の向上を達成することが可能であることをシミュレーションにより示す． |
| （英） | A bloom filter is a representation of data item indexes, which achives small memory requirement by allowing one-sided errors (false positive). Because of such a feature, it is often used for lookup in P2P networks; in advance, each peer disserminates a bloom filter representing indexes of the data items it owns. Using the information of disserminated bloom filters as clue, each query can find a short path to its destination. In our previous work, we proposed an extension of the bloom filter, called a Deterministic Decay Bloom Filter(DDBF), and a search method based on it. While the standard bloom filter suffers performance degradation by containing the information of too much data items when its dissermination range is large, the DDBF can circumvent such degradation by containing the information according to the distance between the filter holder and items holders, i.e., a DDBF contains less information for faraway items and more information for nearby items. Then, we can reduce the amount of information aggregated by one peer,and can avoid the increase of error rate. In this paper, we further extend the DDBF-based search method by introducing the tchnique that the protocol adjusts dissermination range of each filter according to the popularity of data items that the filter represents. We also show by simulation that this popularity-biased scheme drastically improves efficiency of the DDBF-based lookup. | |
| キーワード | （和） | ブルームフィルタ / P2Pネットワーク / 検索問題 / / / / / |
| （英） | Bloom filter / P2P network / lookup problem / / / / / | |
| 文献情報 | 信学技報, vol. 106, no. 355, NS2006-133, pp. 55-60, 2006年11月. | |
| 資料番号 | NS2006-133 | |
| 発行日 | 2006-11-09 (NS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2006-133 |
|
| 研究会情報 | |
| 研究会 | CQ NS ICM |
| 開催期間 | 2006-11-16 - 2006-11-17 |
| 開催地（和） | 鳥取環境大学 |
| 開催地（英） | Tottori Univ. of Environmental Studies |
| テーマ（和） | ネットワーク品質，トラヒック計測，一般 |
| テーマ（英） | Network Quality of Service, Traffic Measurement, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2006-11-CQ-NS-TM |
| 本文の言語 | 日本語 |
| タイトル（和） | P2Pネットワークにおける決定性減衰型ブルームフィルタの提案と検索効率の評価 |
| サブタイトル（和） | |
| タイトル（英） | A Proposal of Deterministic Decay Bloom Filter in P2P Network and its Evaluation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ブルームフィルタ / Bloom filter |
| キーワード(2)（和/英） | P2Pネットワーク / P2P network |
| キーワード(3)（和/英） | 検索問題 / lookup problem |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 高橋 佑典 / Yusuke Takahashi / タカハシ ユウスケ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 泉 泰介 / Taisuke Izumi / イズミ タイスケ |
| 第2著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） | 増澤 利光 / Toshimitsu Masuzawa / マスザワ トシミツ |
| 第3著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2006-11-17 12:50:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NS |
| 資料番号 | NS2006-133 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | no.355 |
| ページ範囲 | pp.55-60 |
| ページ数 | 6 |
| 発行日 | 2006-11-09 (NS) |
[研究会発表申込システムのトップページに戻る]