| 講演名 | 2004/7/8 P2Pネットワークにおける一般化Kautzダイグラフに基づく分散ハッシュ表を用いた検索アルゴリズム(セッション10B : P2P)(夏のデータベースワークショップ : DBWS2004) 岡下 綾, 有次 正義, 柴田 幸夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | P2P(Peer-to-Peer)ネットワークではデータを動的なネットワーク上のノードに分散させるため,データを効率良く検索することが本質的に重要な課題となる.そこで,ネットワーク上の各ノードに経路情報として分散ハッシュ表(DHT)を持たせることにより,位置に依存せず効率的にデータを検索するアプローチが注目を集めている.本稿では一般化Kautzダイグラフに基づく定数サイズのDHTを提案する.各ノードは他の二つのノードに関する情報を持つだけで,Koordeよりも拡張性の高いネットワークの上で,ノード数nに対してホップ数O(log n)の検索を実現する. |
| 抄録(英) | In peer-to-peer(P2P) networks, it is important to efficiently locate nodes assigned to data items. This paper proposes lookup algorithm with a distributed hash table(DHT) based on generalized Kautz digraphs as a routing table. This is a family of constant-degree routing networks of logarithmic diameter. Generalized Kautz digraphs have an optimal diameter and higher scalability than de Bruijn digraphs. In our method, each node needs to store routing information about only 2 other nodes. Our algorithm guarantees O(log n) hops, for the nurnber of nodes n. |
| キーワード(和) | P2Pネットワーク / 分散ハッシュ表 / 一般化Kautzダイグラフ / 分散データ発見アルゴリズム |
| キーワード(英) | Peer-to-Peer Network / Distributed Hash Table / Generalized Kautz Digraph / Lookup Algorithm |
| 資料番号 | DE2004-101 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2004/7/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | P2Pネットワークにおける一般化Kautzダイグラフに基づく分散ハッシュ表を用いた検索アルゴリズム(セッション10B : P2P)(夏のデータベースワークショップ : DBWS2004) |
| サブタイトル（和） | |
| タイトル（英） | On Lookup Algorithm with a Generalized Kautz-based Distributed Hash Table |
| サブタイトル（和） | |
| キーワード(1)（和/英） | P2Pネットワーク / Peer-to-Peer Network |
| キーワード(2)（和/英） | 分散ハッシュ表 / Distributed Hash Table |
| キーワード(3)（和/英） | 一般化Kautzダイグラフ / Generalized Kautz Digraph |
| キーワード(4)（和/英） | 分散データ発見アルゴリズム / Lookup Algorithm |
| 第 1 著者 氏名（和/英） | 岡下 綾 / Aya OKASHITA |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Faculty of Engineering, Gunma University |
| 第 2 著者 氏名（和/英） | 有次 正義 / Masayoshi ARITSUGI |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Faculty of Engineering, Gunma University |
| 第 3 著者 氏名（和/英） | 柴田 幸夫 / Yukio SHIBATA |
| 第 3 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Faculty of Engineering, Gunma University |
| 発表年月日 | 2004/7/8 |
| 資料番号 | DE2004-101 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 178 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |