2026-04-17T13:09:12Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00066749 2025-01-22T00:53:45Z 1164:2836:5643:5919

ピアの近接性を考慮したスキップグラフの構築 Constructing Skip Graphs with Proximity 牧川, 文紀 土屋, 達弘 菊野, 亨 Fuminori, Makikawa Tatsuhiro, Tsuchiya Tohru, Kikuno セッション02 P2Pと無線通信 キーの検索に特化したグラフであるスキップグラフは，ネットワーク上に点在するピアが持つキーを管理するために有効なグラフ構造である．しかし，通常のスキップグラフはピアの物理的な位置やピア間の通信時間などを考慮していない．そのため，部分的に通信時間が非常に大きいリンクがグラフ内に存在してしまう可能性がある．本論文ではスキップグラフを構築する際にピア間の通信時間を計測し，より通信時間が小さくなるようにグラフの構築を行う．また，グラフ全体のバランスを取るための手法も合わせて提案する．シミュレーションにより，提案した手法が通常のスキップグラフと比較して小さい検索時間でキーの検索ができることを確認した． A skip graph is a valuable overlay network for searching for keys in a peer-to-peer application. A problem with the construction algorithm for skip graphs is that it considers neither peers' physical location nor communication cost between peers. Because of this, a skip graph often contains links with considerably high communication time. In this paper, we propose a communication cost-aware construction to reduce the time required to search for keys. We also propose a method for dynamically keeping the balance of a skip graph. The results of simulations show that in the skip graph constructed by our approach, a peer can search for keys with lower time than in the original skip graph. 情報処理学会 2009-11-19 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/66749 AN10116224 研究報告マルチメディア通信と分散処理（DPS） 2009-DPS-141 5 1 8 https://ipsj.ixsq.nii.ac.jp/record/66749/files/IPSJ-DPS09141005.pdf application/pdf 1.0 MB 2011-11-19