Improving the R*-tree with Outlier Handling Techniques Tian Xia and Donghui Zhang   View Paper (PDF)   Return to Session 4: Data Structures, Computational Geometry Abstract The R*-tree, as a state-of-the-art spatial index, has already found its way into commercial systems like Oracle. In this paper, we aim at improving query performance of the R*-tree. We focus on five widely used spatial queries: range query, aggregation query, nearest neighbor query, skyline query, and join query. The idea is to store outlier objects in internal tree nodes. The new structure is named the ROtree. Here an outlier is an object which is located far from other ... ©2006 Association for Computing Machinery