Use-based optimization of Spatial access methods

Abstract

Spatial access methods have been extensively studied in the literature, during last decades. Access methods were designed for efficient processing of demanding queries and extensive comparisons between such methods have been presented. However, choosing the best values for the parameters that affect the performance of a spatial access method when such a method is expected to be utilized within a specific workload/context of operations has not been studied, so far. In this paper, we present the design and implementation of a framework to evaluate and optimize a spatial index. The (very popular) family of R-trees is chosen as the index of focus, though the same process can be applied for other (spatial, or not) indexes or combinations of them. We elaborate on the antagonizing aspects in the design of an R-tree, present the design and implementation of a benchmarking framework and develop a performance model for this index that incorporates benchmarking results. Next, we develop an optimization framework that uses this model to provide an optimized set up (node occupancies and node splitting method) for a specific use context (dataset type, tree size, number of queries and type of queries). We also present experimental results of an indicative use of the developed benchmarking framework and optimizer for a limited range of use contexts. © 2017 Association for Computing Machinery.