| 講演名 | 2021-01-29 Skip Graphにおける迂回経路を活用した範囲検索クエリルーティング手法 三木 友弥(東工大), 金子 孟司(東工大), 坂野 遼平(東工大/工学院大), 首藤 一幸(東工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ノード群による自律分散的なネットワークを構築し，効率的なルーティングを実現するための技術として構造化オーバーレイが知られている．Skip Graphは，構造化オーバーレイのデータ構造の1つであり，範囲検索が可能であるという特長を有する．本稿では，Skip Graphにおける新たな範囲検索クエリのルーティング手法を提案する．提案手法では，クエリを受信したノードが，下位ノード列の中央に基づいて当該クエリの対象範囲を分割し，部分領域を隣接ノードに委譲していく．これにより，ノード数が十分に多い場合，平均経路長が既存手法よりも20%程度短縮できることを確認した． |
| 抄録(英) | A structured overlay is a technique to construct an autonomous decentralized network of nodes and to achieve efficient routing. Skip Graph is a structured overlay and one of its advantages is capability for range queries. In this paper, we propose a new routing method for range queries in Skip Graph. In the proposed method, a node which receives a query, divides its target range into subranges by the key of the center of the subordinate node sequence, and delegates the subranges to its neighbor nodes. We confirmed that the average path length of the proposed method is about 20% shorter than that of the existing methods when the number of nodes is sufficiently large. |
| キーワード(和) | Skip Graph / 構造化オーバーレイ / P2Pネットワーク / ルーティングアルゴリズム / 範囲検索クエリ |
| キーワード(英) | Skip Graph / Structured overlay / Peer-to-peer network / Routing algorithm / Range query |
| 資料番号 | IA2020-33 |
| 発行日 | 2021-01-22 (IA) |
| 研究会情報 | |
| 研究会 | IA |
|---|---|
| 開催期間 | 2021/1/29(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | センサー ネットワーク, IoT, M2M, 一般 |
| テーマ（英） | Senser Network, IoT, M2M, etc. |
| 委員長氏名（和） | 大崎 博之(関西学院大) |
| 委員長氏名（英） | Hiroyuki Osaki(Kwansei Gakuin Univ.) |
| 副委員長氏名（和） | 新 麗(IIJ) / 近堂 徹(広島大) / 山本 寛(立命館大) |
| 副委員長氏名（英） | Rei Atarashi(IIJ) / Toru Kondo(Hiroshima Univ.) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| 幹事氏名（和） | 作元 雄輔(関西学院大) / 屏 雄一郎(KDDI総合研究所) / 渡辺 俊貴(NEC) |
| 幹事氏名（英） | Yusuke Sakumoto(Kwansei Gakuin Univ.) / Yuichiro Hei(KDDI Research) / Toshiki Watanabe(NEC) |
| 幹事補佐氏名（和） | 大平 健司(阪大) / 野林 大起(九工大) / 坂野 遼平(工学院大) |
| 幹事補佐氏名（英） | Kenji Ohira(Osaka Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) / Ryohei Banno(Kogakuin Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Internet Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Skip Graphにおける迂回経路を活用した範囲検索クエリルーティング手法 |
| サブタイトル（和） | |
| タイトル（英） | A Routing Method for Range Queries Utilizing Detour Routes on Skip Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Skip Graph / Skip Graph |
| キーワード(2)（和/英） | 構造化オーバーレイ / Structured overlay |
| キーワード(3)（和/英） | P2Pネットワーク / Peer-to-peer network |
| キーワード(4)（和/英） | ルーティングアルゴリズム / Routing algorithm |
| キーワード(5)（和/英） | 範囲検索クエリ / Range query |
| 第 1 著者 氏名（和/英） | 三木 友弥 / Yuya Miki |
| 第 1 著者 所属（和/英） | 東京工業大学(略称：東工大) Tokyo Institute of Technology(略称：Tokyo Tech) |
| 第 2 著者 氏名（和/英） | 金子 孟司 / Takeshi Kaneko |
| 第 2 著者 所属（和/英） | 東京工業大学(略称：東工大) Tokyo Institute of Technology(略称：Tokyo Tech) |
| 第 3 著者 氏名（和/英） | 坂野 遼平 / Ryohei Banno |
| 第 3 著者 所属（和/英） | 東京工業大学/工学院大学(略称：東工大/工学院大) Tokyo Institute of Technology/Kogakuin University(略称：Tokyo Tech/Kogakuin Univ.) |
| 第 4 著者 氏名（和/英） | 首藤 一幸 / Kazuyuki Shudo |
| 第 4 著者 所属（和/英） | 東京工業大学(略称：東工大) Tokyo Institute of Technology(略称：Tokyo Tech) |
| 発表年月日 | 2021-01-29 |
| 資料番号 | IA2020-33 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IA-356 |
| ページ範囲 | pp.15-20(IA), |
| ページ数 | 6 |
| 発行日 | 2021-01-22 (IA) |