分散配列：効率的な論理配列を実現するP2Pデータ構造

IPSJ

Bibliographic Information

Other Title
  • Distributed Arrays: A P2P Data Structure for Efficient Logical Arrays
  • P2P

Search this article

Abstract

分散ハッシュテーブル（DHT）を用いることによりP2P環境にデータ管理システムを構築することができる．しかし，DHTは登録されるアイテムの関連性を無視しているため，関連する複数のアイテムに対してまとめて操作を行う場合には効率が悪い．本論文ではDHTをもとに分散配列を構築し，論理配列に対する操作を効率的に実現する．まず，理想的な環境におけるオーバレイネットワークの分析に基づき，複数要素へのアクセスに適するように，配列要素をオーバレイネットワーク上に配置する．この配置は，配列のインデクスのビット列を逆読みすることによって行われることになる．さらに，配列に対する有用な操作であるシーケンシャルアクセス，範囲アクセス，ソート済み配列用の探索の効率的なアルゴリズムを示す．また，オーバレイネットワークのトポロジを調整し，現実的な環境にも対応させる．結果，複数要素へのアクセスをともなう操作に必要なメッセージ数は，ノードの数が増えるほど，DHT上に論理配列を構築する場合と比較して減少する．これを理論と実験の両面から示す．

Distributed hash tables (DHT) are used for data management in peer-to-peer (P2P) environments. However, since most hash functions ignore relations between items, DHTs are not efficient for operations on related items. In this paper, we modify the DHT into a distributed array that enables efficient operations on multiple logical arrays simultaneously. First, array elements are placed in an overlay network according to an easy rule by reversing the binary bit order of their indices. Next, we devise algorithms for sequential access, range access, and searching of a sorted array according to the placement in the overlay network in ideal environments. We then tune the overlay topology to adapt it to realistic environments. As a result, the number of messages required for the operations can be greatly reduced in compared to DHTs. We demonstrate this theoretically and experimentally.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top