P2PネットワークにおけるBloom Filterを用いた移動履歴に基づくユーザ探索手法の提案

情報処理学会

書誌事項

タイトル別名
  • Proposal of a User Search Method Based on Movement Records Utilizing Bloom Filter for P2P Network
公開日
2010-09-15
資源種別
journal article

この論文をさがす

説明

本稿では，ユーザの移動履歴がP2Pネットワークにおいて分散管理されている状況のもと，指定した移動履歴を持つユーザを効率的に探索するための手法を提案する．提案手法では，移動履歴を，訪問場所を示すspot IDと訪問時刻を示すtimeの組を1つの要素とした系列とし，各要素にBloom Filterを適用したビット論理和をユーザ（ピア）ごとに算出する．この算出されたBloom FilterをBloom FilterのP2Pネットワークでの探索手法であるBloom Finger Table（BFT）に適用し，移動履歴のAND/OR検索を実現する．提案手法により，時間指定を含め指定した経路の一部またはすべてをたどったユーザの探索が効率的に実現できる．また，ユーザ探索におけるメッセージ数を削減し，検索適合率を上昇させるため，行動範囲が類似したユーザのピアIDが近傍となるピアIDの割当て法（地理的ピアID）を提案する．提案手法の有効性をシミュレーションにより評価し，従来手法であるMulti-key Skip Graph（MKSG）との比較により1,000ピアがそれぞれ100の移動履歴を持つ状況での経路検索でAND検索において，メッセージ数は80%，OR検索においては，88% 削減できることを確認した．

In this paper, we propose a P2P user search method based on movement records. In our proposal, a Bloom Filter is applied to each spotID and time to combine all movement records for one user (peer) as a fixed length bit array. To search a user who followed specified course, we propose a AND/OR search method based on Bloom Finger Table (BFT), which extends finger table, a routing table of Chord DHT to achieve multiple attribute retrieval. By using proposed method, we can efficiently retrieve a user who followed a part of or all of the specified course including time. Additionally, in order to reduce the number of messages and to raise precision of search for a user search, we propose a peer-ID assignment method based on user's geographical foothold. We evaluated our proposal by simulations comparing with Multi-key Skip Graph that is an existing search method on P2P networks. In AND search, we confirmed the number of messages can be reduced by 80% and in OR search, 88% when there are 1,000 peers and each peer has 100 movement records.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ