Z曲線を用いた効率的な2次元位置情報の分散管理手法の提案とその評価

書誌情報

秋山大輔・細川和宏・安倍広多・石橋勇人・松浦敏雄，Z曲線を用いた効率的な2次元位置情報の分散管理手法の提案とその評価，情報処理学会研究報告，Vol. 2010-IOT-8, No. 9, pp. 1–6, (2010-3).

Abstract

本稿では，多数の2次元位置情報をP2Pネットワークを用いて分散管理する一手法を提案する．提案手法では，2次元平面をZ曲線を用いて分割し，各領域を一つのピアが管理する．管理領域内のデータ数が一定数を越えると領域を分割することでピアの負荷を一定に保つ．範囲検索のためには構造化オーバレイネットワークの一種であるSkip graphを用いる．範囲検索に要するホップ数を削減するために，領域の分割方法を工夫している．提案手法はシミュレーションにより範囲検索に要するホップ数と管理に必要なノード数を評価した．

In this paper, we propose a distributed management scheme for 2D location information using Peer-to-Peer network. In the proposed scheme, a 2D plane is divided into fragments with Z-curve and each fragments is managed by a peer. Skip graphs, a kind of structured overlay network, are used for range queries. To reduce hop counts required for range queries, we devised a method to choose appropriate points on dividing. We have evaluated the method with regard to number of hops required for range queries and number of required peers.