On Optimal Node Splitting for R-trees

摘要: The problem of finding an optimal bipartition a rectangle set has direct impact on query performance dynamic R-trees. During update operations, overflowed nodes need to be split (bipartitioned) with the goal minimizing resultant expected time. previous algorithm for node splitting requires exponential One contribution this paper is polynomial time bipartitions any objective function whose value depends exclusively bounding hyper-rectangles ensuing partitions. runs in O(nd) where d > 1 number dimensions input. Experimental studies indicate that use splits alone results improvements only between 5% and 15% when compared other heuristics. Thus, second demonstrate near optimality heuristics, fact suggests research should focus global rather than local optimization issues. Finally, we propose new R-tree insertion method uses more restructuring heuristic processing overflows. When coupled This work been partially supported by National Science Foundation under grant IRI-9610240 Colorado Advanced Software Institute grants m-96-05 ‘IT-9706. Permission copy without fee all or part material granted provided copies are not made distributed commercial advantage, VLDB copyright notice title publication its date appear, given copying permission Very Large Data Base Endowment. To othemise, republish, and/or special from Proceedings 24th Conference New York, USA, 1998 our up 120% over leading stan-