Active adjustment: An effective method for keeping the TPR*-tree compact

Sang-Wook Kim, Min Hee Jang, Lim Sungchae

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Recently, with the advent of diverse applications based on locations of moving objects, it has becom e 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 ar e 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 pr oblem, we propose a novel m ethod 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 ar e 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.

Original languageEnglish
Pages (from-to)1583-1600
Number of pages18
JournalJournal of Information Science and Engineering
Volume26
Issue number5
StatePublished - 2010 Sep 1

Fingerprint

Query processing
performance
Degradation
Costs
Bayerischer Rundfunk
costs
Processing
Experiments
examination
experiment
evaluation
time

Keywords

  • -tree
  • Futuretime queries
  • Moving objects
  • Spatio-temporal databases
  • Spatio-temporal indexing
  • TPR-tree
  • Tpr*

Cite this

@article{8b08cefda0574dbf8a8c00b360ea774f,
title = "Active adjustment: An effective method for keeping the TPR*-tree compact",
abstract = "Recently, with the advent of diverse applications based on locations of moving objects, it has becom e 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 ar e 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 pr oblem, we propose a novel m ethod 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 ar e 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 = "-tree, Futuretime queries, Moving objects, Spatio-temporal databases, Spatio-temporal indexing, TPR-tree, Tpr*",
author = "Sang-Wook Kim and Jang, {Min Hee} and Lim Sungchae",
year = "2010",
month = "9",
day = "1",
language = "English",
volume = "26",
pages = "1583--1600",
journal = "Journal of Information Science and Engineering",
issn = "1016-2364",
number = "5",

}

Active adjustment : An effective method for keeping the TPR*-tree compact. / Kim, Sang-Wook; Jang, Min Hee; Sungchae, Lim.

In: Journal of Information Science and Engineering, Vol. 26, No. 5, 01.09.2010, p. 1583-1600.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Active adjustment

T2 - An effective method for keeping the TPR*-tree compact

AU - Kim, Sang-Wook

AU - Jang, Min Hee

AU - Sungchae, Lim

PY - 2010/9/1

Y1 - 2010/9/1

N2 - Recently, with the advent of diverse applications based on locations of moving objects, it has becom e 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 ar e 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 pr oblem, we propose a novel m ethod 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 ar e 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.

AB - Recently, with the advent of diverse applications based on locations of moving objects, it has becom e 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 ar e 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 pr oblem, we propose a novel m ethod 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 ar e 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.

KW - -tree

KW - Futuretime queries

KW - Moving objects

KW - Spatio-temporal databases

KW - Spatio-temporal indexing

KW - TPR-tree

KW - Tpr

UR - http://www.scopus.com/inward/record.url?scp=77957985517&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:77957985517

VL - 26

SP - 1583

EP - 1600

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

SN - 1016-2364

IS - 5

ER -