Bulk insertion for R-trees by seeded clustering

Abstract: We propose a scalable technique called Seeded Clustering that allows us to maintain R-tree indices by bulk insertion while keeping pace with high data arrival rates. Our approach uses a seed tree, which is copied from the top k levels of a target R-tree, to classify input data objects into clusters. We then build an R-tree for each of the clusters and insert the input R-trees into the target R-tree in bulk one at a time. We present detailed algorithms for the seeded clustering and bulk insertion. The experimental results show that the bulk insertion by seeded clustering outperforms the previously known methods. [Copyright &y& Elsevier]