Merging R-trees

Abstract

R-trees, since their introduction in 1984, have been proven to be one of the most well-behaved practical data structures for accommodating dynamic massive sets of geometric objects and conducting a diverse set of queries on such data-sets in real-world applications. In this paper we introduce a new technique for merging two R-trees into a new one of very good quality. Our method avoids both the employment of bulk insertions and the solution of bulk-loading, from scratch, the new tree using the data of the original trees. Additionally, unlike previous approaches, it does not make any assumptions about data-set distributions. Experimental results provide evidence on the runtime efficiency of our method and illustrate the good query performance of the produced indices.