Bulk-loading xBR+-trees

Abstract

Spatial indexes are important in spatial databases for efficient execution of queries involving spatial constraints. The xBR+-tree is a balanced disk-resident quadtree-based index structure for point data, which is very efficient for processing such queries. Bulk-loading refers to the process of creating an index from scratch as a whole, when the dataset to be indexed is available beforehand, instead of creating (loading) the index gradually, when the dataset items are available one-by-one. In this paper, we present an algorithm for bulk-loading xBR+-trees for big datasets residing on disk, using a limited amount of RAM. Moreover, using real and artificial datasets of various cardinalities, we present an experimental comparison of this algorithm vs. the algorithm loading items one-by-one, regarding performance (I/O and execution time) and the characteristics of the xBR+-trees created. We also present experimental results regarding the efficiency of bulk-loaded xBR+-trees vs. xBR+-trees where items are loaded one-by-one for query processing. © Springer International Publishing Switzerland 2016.