An Index Structure for Updating Continuously Moving Objects Efficiently


The KIPS Transactions:PartD, Vol. 13, No. 4, pp. 477-490, Aug. 2006
10.3745/KIPSTD.2006.13.4.477,   PDF Download:

Abstract

Existing index structures need very much update cost because they repeat delete and insert operations in order to update continuously moving objects. In this paper, we propose a new index structure which reduces the update cost of continuously moving objects. The proposed index structure consists of a space partitioning index structure that stores the location of the moving objects and an auxiliary index structure that directly accesses to their current positions. In order to increase the fanout of the node, it stores not the real partitioning area but kd-tree as the information about the child node of the node. In addition, we don't traverse a whole index structure, but access the leaf nodes directly and accomplish a bottom-up update strategy for efficiently updating the positions of moving objects. We show through the various experiments that our index structure outperforms the existing index structures in terms of insertion, update and retrieval.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. S. Bok, H. W. Yoon, M. H. Kim, K. H. Cho, J. S. Yoo, "An Index Structure for Updating Continuously Moving Objects Efficiently," The KIPS Transactions:PartD, vol. 13, no. 4, pp. 477-490, 2006. DOI: 10.3745/KIPSTD.2006.13.4.477.

[ACM Style]
Kyoung Soo Bok, Ho Won Yoon, Myoung Ho Kim, Ki Hyung Cho, and Jae Soo Yoo. 2006. An Index Structure for Updating Continuously Moving Objects Efficiently. The KIPS Transactions:PartD, 13, 4, (2006), 477-490. DOI: 10.3745/KIPSTD.2006.13.4.477.