文献

J-GLOBAL ID：200902221281432824   整理番号：09A0040362

移動オブジェクトの更新に適した領域分割形木構造:kdm-tree

著者 (4件)： 西川嘉人 (埼玉大 大学院理工学研究科) ,  辻俊明 (埼玉大 大学院理工学研究科) ,  金子裕良 (埼玉大 大学院理工学研究科) ,  阿部茂 (埼玉大 大学院理工学研究科)
資料名： 電子情報通信学会論文誌 D  (IEICE Transactions on Information and Systems (Japanese Edition))
巻： J92-D  号： 1  ページ： 1-11  発行年： 2009年01月01日 
JST資料番号： S0757C  ISSN： 1880-4535  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *移動体 ,  *位置情報 ,  データ管理 ,  *データ構造 ,  ツリー構造 ,  木構造 ,  データ更新 ,  高次元 ,  検索効率 ,  データ検索
準シソーラス用語： 位置管理

分類 (1件)： システムプログラミング一般  (JD03010Y)

引用文献 (16件)：

• D. Kwon, S. Lee, and S. Lee, “Indexing the current positions of moving objects using lazy update r-tree,” Third International Conference on Mobile Data Management, p. 113, Singapore, Jan.2002
• M. L. Lee, W. Hsu, C. S. Jensen, B. Cui, and K. L. Teo, “Supporting frequent updates in R-trees: A bottomup approach,” Proc. VLDB, 2003.
• X. Xiong and W. G. Aref, “R-trees with update Memos,” Proc. International Conference on Data Engineering, vol.22, 2006.
• C. S. Jensen, D. Lin, and B. C. Ooi, “Query and update efficient B⁺-tree based indexing of moving objects,” Proc. VLDB, 2004.
• S. Guo, Z. Huang, H. V. Jagadish, B. C. Ooi, and Z. Zhang, “Relaxed space bounding for moving objects: A case for the buddy tree,” SIGMOD Record, vol.35, no.4, pp. 24-29, 2006.

タイトルに関連する用語 (5件)： オブジェクト ,  更新 ,  領域分割 ,  木構造 ,  KDM