ピアの近接性を考慮したスキップグラフの構築

• Item type: SIG Technical Reports(1)
• 公開日: 2009-11-19
• タイトル: ピアの近接性を考慮したスキップグラフの構築
• タイトル / 言語: en
• タイトル: Constructing Skip Graphs with Proximity
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: セッション02 P2Pと無線通信
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: 牧川, 文紀; 土屋, 達弘; 菊野, 亨
• 著者名(英): Fuminori, Makikawa; Tatsuhiro, Tsuchiya; Tohru, Kikuno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: キーの検索に特化したグラフであるスキップグラフは，ネットワーク上に点在するピアが持つキーを管理するために有効なグラフ構造である．しかし，通常のスキップグラフはピアの物理的な位置やピア間の通信時間などを考慮していない．そのため，部分的に通信時間が非常に大きいリンクがグラフ内に存在してしまう可能性がある．本論文ではスキップグラフを構築する際にピア間の通信時間を計測し，より通信時間が小さくなるようにグラフの構築を行う．また，グラフ全体のバランスを取るための手法も合わせて提案する．シミュレーションにより，提案した手法が通常のスキップグラフと比較して小さい検索時間でキーの検索ができることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10116224
• 書誌情報: 研究報告マルチメディア通信と分散処理（DPS）; 巻 2009-DPS-141, 号 5, p. 1-8, 発行日 2009-11-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会