高いChurn耐性と検索性能を持つキー順序保存型構造化オーバレイネットワークSuzakuの提案と評価

提供: Research

目次

書誌情報

安倍広多,寺西裕一: 高いChurn耐性と検索性能を持つキー順序保存型構造化オーバレイネットワークSuzakuの提案と評価,信学技報 Vol. 116, No. 362 (IA2016-65),pp. 11--16,(2016-12).

表彰状

Abstract

キーの値による範囲検索が可能なキー順序保存型構造化オーバレイネットワークは多くの応用があり,重要性が高い.本研究では,新しいキー順序保存型構造化オーバレイネットワークSuzakuを提案する.Suzakuは,(1)Churn時でも最大検索ホップ数がlog_2 n程度に収まる(nはノード数),(2)キーが大小どちらの方向でも近傍ノードの検索は高速に行える,(3)構造は単純で実装が容易,といった特徴を備える.本稿ではSuzakuの詳細について述べ,シミュレーションによって既存のChord#およびSkip Graphと比較する.

A "key-order preserving structured overlay network," which enables range queries, has various applications and thus be important. In this study, we propose a novel key-order preserving structured overlay network "Suzaku," which has the following properties: (1) maximum lookup hops is almost log_2 n even in churn situations, where n is the number of nodes, (2) neighbor search is fast regardless of the direction of their keys, (3) the structure is simple and easy to implement. In this paper, we describe the principles and detailed algorithm of Suzaku. We also show simulation results comparing Suzaku with existing Chord# and Skip Graph.

論文

  • PDF (Copyright (C) 2016 IEICE)

訂正

原稿の擬似コード(図2)に間違いがありました.修正した擬似コードを以下に示します.

Presentation

Photo

Ia-hiroshima.jpg


個人用ツール