Direction relations and two-dimensional range queries: optimisation techniques

This paper defines direction relations (e.g., north, northeast) between two-dimensional objects and shows how they can be efficiently retrieved using B-, KDB- and R- tree-based data structures. Essentially, our work studies optimisation techniques for 2D range queries that arise during the processing of direction relations. We test the efficiency of alternative indexing methods through extensive experimentation and present analytical models that estimate their performance. The analytical estimates are shown to be very close to the actual results and can be used by spatial query optimizers in order to predict the retrieval cost. In addition, we implement modifications of the existing structures that yield better performance for certain queries. We conclude the paper by discussing the most suitable method depending on the type of the range and the properties of the data. (C) 1998 Published by Elsevier Science B.V. All rights reserved.