An adaptive indexing technique using spatio-temporal query workloads

Abstract

Many spatio-temporal access methods, such as the HR-tree, the 3DR-tree, and the MV3R-tree, have been proposed for timestamp and interval queries. However, these access methods have the following problems: the poor performance of the 3DR-tree for timestamp queries, the huge size and the poor performance of the HR-tree for interval queries, and the large size and the high update cost of the MV3R-tree. We address these problems by proposing an adaptive partitioning technique called the Adaptive Partitioned R-tree (APR-tree) using workloads with timestamp and interval queries. The APR-tree adaptively partitions the time domain using query workloads. Since the time domain of the APR-tree is automatically fitted to query workloads, the APR-tree outperforms the other access methods for various query workloads. The size of the APR-tree is on the average 1.3 times larger than that of the 3DR-tree which has the smallest size. The update cost of the APR-tree is on the average similar to that of the 3DR-tree which has the smallest update cost. (C) 2003 Elsevier B.V. All rights reserved.