National Center for Geographic Information and Analysis

Despite the attention that direction relations, such as east, southeast etc., have attracted in several domains related to Spatial Databases and Geographic Information Systems (GIS), little work has been done on their formalization and efficient processing. In this paper we define direction relations between two-dimensional objects in different levels of qualitative resolution and we show how these relations can be efficiently retrieved in existing DBMSs using B- , KDB- and R- tree-based data structures. Since query processing involving direction relations maps into range queries in two- dimensional space, our work essentially studies optimization techniques for 2D ranges. We test the efficiency of alternative indexing methods through extensive experimentation and we present analytical models that estimate their performance. The analytical estimates are proved to be very close to the actual results and can be used by spatial query optimizers in order to decide the appropriate data structure for each type of range query. Although for our experiments we define a small set of representative relations motivated by geographic applications, the results of this paper are directly applicable to any type of direction relations (or range queries in general) that may arise in different application domains.