P2PネットワークにおけるSkip GraphとBloom Filterを用いた効率的な複数キーワード検索手法の提案

提供: Research



岩本大記,安倍広多,石橋勇人,松浦敏雄,P2PネットワークにおけるSkip GraphとBloom Filterを用いた効率的な複数キーワード検索手法の提案,情報処理学会研究報告,Vol. 2011-DPS-146, No. 28, pp. 1--8 (2011-3)


構造化 P2P ネットワークとして多く用いられている分散ハッシュテーブルでは,1つの key に対して1つの value を対応づけ,非常に多数のノードに分散して格納する.このため,複数のキーワードを同時に含むデータを効率良く検索することは困難である.この問題を解決するため,本稿では,Bloom filter を利用した検索手法を提案する.Bloom filter を用いることによって,検索対象のデータが含むすべてのキーワードをコンパクトに記憶することが可能となる.各ノードが持つ Bloom filterの内容は集約 Skip graph に基づくアルゴリズムによって集約され,保持される.検索時にはそれを用いて対象となるノードの範囲を絞り込んでゆくため,複数キーワードによる検索を効率良く実行することが可能である.提案手法の有効性を確認するため,シミュレーションによる実験をおこなったので,その結果についても述べる.

DHT (Distributed Hash Table) is a popular data structure for structured P2P networks. A DHT is a distributed key-value store that manages mapping from keys to values by means that one key corresponds to one value. Due to this property, it is difficult to perform multiple keyword search efficiently. This paper proposes an efficient search method using Bloom filter, a space-efficient data structure storing multiple keys in one bit sequence. Bloom filters on a series of nodes are aggregated by an algorithm based on Aggregation Skip Graph so that narrowing search ranges can be efficient in time. Simulation results are also reported.


ここに掲載した著作物の利用に関する注意 本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。

Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof.