| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-09-04 10:25 DHTを用いたグラフ分散管理システムにおけるノード探索効率化 ○江口さくら・金子晋丈（慶大）  IN2025-25 |
|
| 抄録 | （和） | 大規模グラフを分散ハッシュテーブル（DHT: Distributed Hash Table）を用いた分散管理システムに保存・管理することで，各ノードに紐づけられたハッシュ値(key)を用いて効率的なグラフ探索が可能となる．しかし，既存のDHTルーティングでは1クエリにつき1ノードしか取得できず，取得したいノード数に比例して通信コストが増大する問題がある．そこで本研究ではDHTに登録されたグラフを，指定されたクエリノードを基点になるべく少ないクエリ数，ホップ数で取得するためのルーティングアルゴリズムを提案する．具体的には，あるノードのクエリ時にそのノードの管理サーバ，もしくは経路表上のサーバで管理している隣接ノードも再帰的に取得することで各ノードの取得にかかるホップ数を削減する．また，このとき経路表はグラフ用に最適化したGraph Finger Table（GFT）を数種類設計し，実世界グラフで評価を行った．その結果，グラフ取得にかかるクエリ数，ホップ数を既存のDHTルーティングからそれぞれ平均92%，平均90%軽減した． |
| （英） | Managing a large-scale graph within a Distributed Hash Table (DHT) system allows for efficient graph exploration using the hash value (key) associated with each node. However, existing DHT routing protocols retrieve only one node per query, leading to increase in communication costs in proportion to the number of nodes to be retrieved. We propose a routing algorithm that retrieves a graph registered in DHT with the minimum number of queries and hops, starting from a specified query node. Our method reduces the number of hops required to retrieve each node by recursively fetching the adjacent nodes managed by the queried node's server or servers on its routing table. We also designed several types of Graph Finger Tables (GFTs) optimized for the proposed method and evaluated them using real-world graphs. Our method reduced the number of queries and hops for graph retrieval by an average of 92% and 90%, respectively, compared to existing DHT routing. | |
| キーワード | （和） | グラフ / 分散ハッシュテーブル / グラフ探索アルゴリズム / コンテンツネットワーク / 分散環境 / / / |
| （英） | Graph / Distributed Hash Table / Graph Search Algorithms / Content Network / Distributed Environment / / / | |
| 文献情報 | 信学技報, vol. 125, no. 173, IN2025-25, pp. 7-12, 2025年9月. | |
| 資料番号 | IN2025-25 | |
| 発行日 | 2025-08-28 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2025-25 |
|
| 研究会情報 | |
| 研究会 | NS IN CS NV |
| 開催期間 | 2025-09-04 - 2025-09-05 |
| 開催地（和） | 東北大学 電気通信研究所 + オンライン開催 |
| 開催地（英） | Tohoku University + Online |
| テーマ（和） | セッション管理(SIP・IMS)，相互接続技術/標準化，次世代・新世代・将来ネットワーク，クラウド/データセンタネットワーク，SDN(OpenFlow等)・NFV，IPv6，機械学習のネットワーク適用，一般 |
| テーマ（英） | Session management (SIP/IMS), Interoperability/Standardization, NGN/NwGN/Future networks, Cloud/Data center networks, SDN (OpenFlow, etc.)/NFV, IPv6, Machine learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2025-09-NS-IN-CS-NV |
| 本文の言語 | 日本語 |
| タイトル（和） | DHTを用いたグラフ分散管理システムにおけるノード探索効率化 |
| サブタイトル（和） | |
| タイトル（英） | An Efficiency Way to Search Nodes in Graph Management Systems Using DHT |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ / Graph |
| キーワード(2)（和/英） | 分散ハッシュテーブル / Distributed Hash Table |
| キーワード(3)（和/英） | グラフ探索アルゴリズム / Graph Search Algorithms |
| キーワード(4)（和/英） | コンテンツネットワーク / Content Network |
| キーワード(5)（和/英） | 分散環境 / Distributed Environment |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 江口 さくら / Sakura Eguchi / エグチ サクラ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-09-04 10:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2025-25 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.173 |
| ページ範囲 | pp.7-12 |
| ページ数 | 6 |
| 発行日 | 2025-08-28 (IN) |
[研究会発表申込システムのトップページに戻る]