- 著者
-
西川 嘉人
辻 俊明
金子 裕良
阿部 茂
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)
- 巻号頁・発行日
- vol.92, no.1, pp.1-11, 2009-01-01
GPS等の位置情報取得技術と移動体通信技術の進歩に伴い,車や電車,人といった時々刻々位置の変化する物体(以下,移動オブジェクトと呼ぶ)の位置情報の継続的な入手が容易となってきた.これに伴い移動オブジェクトの運行効率の向上,セキュリティ管理,位置に基づく情報提供などの応用が検討され,移動オブジェクトに適したデータ管理構造の研究が行われている.研究は目的により大きく,(1)最新位置管理,(2)未来位置予測,(3)軌跡管理,の三つに分けられる.本論文では(1)の最新位置管理を扱う.最新位置管理では,一般に1万以上の移動オブジェクトの最新位置を,秒や分単位で更新する必要があり,この頻繁な更新による処理コストがデータ管理構造の大きな問題となる.筆者らはこの解決のためには,(1)領域分割形の多次元データ管理構造が適している,(2)データの削除と挿入が同時に起こるためデータ削除の負荷が小さい構造が必要である,と考えた.本論文ではこれらを備えたバランスM分木kdm-tree (k-d tree for moving objects)を提案する.本文ではkdm-treeのアルゴリズムと特徴を述べ,他の木構造との性能比較実験を行い, kdm-treeが更新性能に優れ,メモリコストや検索性能も同等以上であることを示す.