Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23]

@

Journal of Information Science and Engineering, Vol. 26 No. 5, pp. 1583-1600 (September 2010)

Active Adjustment: An Effective Method for Keeping the TPR*-tree Compact*

SANG-WOOK KIM, MIN-HEE JANG AND SUNGCHAE LIM+
Department of Information and Communications
Hanyang University
Seoul, 133-791 Korea
+Department of Computer Science
Dongduk Womens University
Seoul, 136-714 Korea

Recently, with the advent of diverse applications based on locations of moving objects, it has become crucial to develop efficient index schemes for spatio-temporal databases. The TPR*-tree is popularly accepted as an index structure for processing futuretime queries on such spatio-temporal databases. In the TPR*-tree, the future locations of moving objects are predicted based on the Conservative Bounding Rectangle (CBR). Since the areas predicted from CBRs tend to grow rapidly over time, CBRs thus enlarged lead to serious performance degradation in query processing. To solve the problem, we propose a novel method to adjust CBRs to be tight, thereby preventing the performance degradation of query processing. Our method examines whether the adjustment of a CBR is necessary when accessing a leaf node for processing a user query. Thus, it does not incur extra disk I/Os in this examination. Also, in order to make a correct decision, we devise a cost model that considers the I/O overhead for the CBR adjustment and the performance gain in the future-time owing to the CBR adjustment. With the cost model, we can prevent unusual expansions of BRs even when updates on nodes are infrequent and also avoid unnecessary execution of the CBR adjustment. For performance evaluation, we conducted a variety of experiments. The results show that our method improves the performance of the original TPR*-tree significantly.

Keywords: moving objects, spatio-temporal databases, spatio-temporal indexing, futuretime queries, TPR-tree, TPR*-tree

Full Text () Retrieve PDF document (201009_02.pdf)

Received October 20, 2008; revised March 9, 2009; accepted June 4, 2009.
Communicated by Tzong-Chen Wu.
* This work was supported by the Mid-Career Researcher Program through the NRF (National Research Foundation) grant funded by the MEST (Ministry of Education, Science, and Technology) (Grant No. 2008-0061006) and by the MKE (The Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2010-(C1090-1011-0009)). This work was also supported by the Brain Korea 21 Project in 2010.