¡@

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

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.