WeR-trees

Abstract

R-tree has been proven to be one of the most practical and well-behaved data structures for accommodating dynamic massive sets of low dimensionality geometric objects and conducting a very diverse set of queries on such data sets in real-world applications. In this paper, we present weighted R-trees-WeR-trees-a new practical and efficient scheme for dynamic manipulation of multi-dimensional data sets, which applies for the first time the technique of partial rebuildings to the case of the R-tree family. Partial rebuildings refer to the method of progressive reconstruction of whole subtrees across update paths in order to keep them in perfect balance from the performance perspective. An analytical investigation is performed, showing amortized bounds for the update operations while detailed experimental results concerning both synthetic and real data sets confirm the applicability of the proposed method and demonstrate its superiority over R*-trees, the most well-behaved and widely accepted variant of R-trees: node space utilization reaches up to 98.1%, query savings vary between 25% and 50% and even more for skewed data, while the scheme scales up linearly with respect to the number of inserted items. (c) 2007 Elsevier B.V. All rights reserved.