単一ノードに複数キーを保持可能とするSkip Graph拡張

情報処理学会 Web Site 被引用文献5件

書誌事項

タイトル別名
  • タンイツ ノード ニ フクスウ キー オ ホジ カノウ ト スル Skip Graph カクチョウ
  • An Extension of Skip Graph to Store Multiple Keys on Single Node
  • ネットワーク・インターネット基礎

この論文をさがす

抄録

範囲検索に対応可能な構造化オーバレイネットワークであるSkip Graphでは，キーとそれを保持するピアが1対1に対応するため，端末が保持するキーが複数存在する場合にSkip Graphに参加するピアを1つ立ち上げるだけでは保持する複数のキーを検索の対象とすることができない．本研究では，単一ピアに複数キーを保持可能とするMulti-key Skip Graphを提案する．Skip Graphを複数キーに対応させるために，単一ノードに保持するキーと1対1に対応する仮想的なピアを複数配置した．しかし，仮想ピアを複数配置すると範囲検索時にホップ数が増大してしまうため，クエリを受けた単一ノード上に存在するすべての仮想ピアの保持するキーにより検索対象領域を分割し，各部分領域に対応する代表ノードにクエリを転送することでホップ数を減少させるマルチレンジフォワード方式によるMulti-key Skip Graphを提案する．提案方式は，オープンソースプラットフォームPIAX上に実装し，シミュレーション評価によりピアが保持するキー数が増加しても範囲検索のホップ数増加を抑えられることを確認した．また，クエリ転送処理時間の実測により，マルチレンジフォワード方式を採用することによる処理負荷の増加は実用上問題ないことを確認した．

A structured overlay network Skip Graph, which can support range retrievals, cannot treat searches of multiple keys on single peer since a search key corresponds to a peer. In this paper, we propose a Multi-key Skip Graph as an extension of Skip Graph. To store multiple keys, we set virtual peers coresponding with stored keys on single node. Query forwarding based on virtual peer causes an increase of query transfer hops between peers in range retrievals. To solve this issue, we propose a Multi-key Skip Graph based on Multi-range forwarding method, which decreases transfer hops by considering the relationship of virtual peers on a single node. Our proposal is implemented on an open-source platform PIAX, which we have been developing. The simulation result shows that our proposal suppress increasing query transfer hops and the result of measuring query transfer processing time shows that the influence of the load increase by adopting our proposal is small.

収録刊行物

被引用文献 (5)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ