DIRECTION RELATIONS AND 2-DIMENSIONAL RANGE QUERIES - OPTIMIZATION TECHNIQUES

This paper defines direction relations (e.g., north, northeast) betwee n two-dimensional objects and shows how they can be efficiently retrie ved 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 o f alternative indexing methods through extensive experimentation and p resent analytical models that estimate their performance. The analytic al 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 structur es 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 Elsevi er Science B.V. All rights reserved.