ST2B-tree: A self-tunable spatio-temporal B+-tree index for moving objects

Abstract

In a moving objects database (MOD) the dataset and the workload change frequently. As the locations of objects change in space and time, the data distribution also changes and the answer for a same query over the same region may vary widely over time. As a result, traditional static indexes are not able to perform well and it is critical to develop self-tuning indexes that can be reconfigured automatically based on the state of the system. Towards this goal we propose the ST2B-tree, a Self- Tunable Spatio- Temporal B +-Tree index for MODs, which is amenable to tuning. Frequent updates to its subtrees allows rebuilding (tuning) a subtree using a different set of reference points and different grid size without significant overhead. We also present an online tuning framework for the ST2B-tree, where the tuning is conducted online and automatically without human intervention, also not interfering with regular functions of the MOD. Our extensive experiments show that the self-tuning process minimizes the effectiveness degradation of the index caused by workload changes at the cost of virtually no overhead. Copyright 2008 ACM.