Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 21 No. 3, pp. 643-658 (May 2005)

Efficient Update Method for Indexing Locations of Moving Objects*

Dongseop Kwon, Sangjun Lee+ and Sukho Lee
School of Electrical Engineering and Commputer Science
Seoul National University
Seoul 151-742, Korea
+School of Computing
Soongsil University
Seoul 156-743, Korea

Tracking the changing positions of moving objects is becoming increasingly feasible and necessary. However, traditional spatial index structures are not suitable for storing these positions because of numerous update operations. In this paper, we propose an efficient update method for indexing the locations of moving objects based on the R-tree. This technique updates the structure of the index only when an object moves out of the corresponding MBR (minimum bounding rectangle). If a new position of an object is in the MBR, it changes the leaf node only. Using a secondary access path to find the corresponding leaf node, the proposed technique can update the position of the object quickly and reduce update the cost greatly. In addition, our technique can be adopted in diverse variants of the R-tree and various applications that use the R-tree since it is based on the R-tree and it guarantees the correctness of the R-tree. We also present experimental results which show that our technique outperforms other techniques.

Keywords: indexing, access method, data structures, database, moving object, R-tree

Full Text () Retrieve PDF document (200505_09.pdf)

Received October 11, 2002; revised June 29 and October 13, 2004; accepted October 27, 2004.
Communicated by Ming-Syan Chen.
*This work was supported in part by the Brain Korea 21 Project and in part by the Information Technology Research Center (ITRC) Support Program in 2004.