Search

In several applications, there is the need to reason about spatial relations using multiple local frames of reference organized in aggregation hierarchies. In this paper we deal with direction relations, a special class of spatial relations that describe order in space (e.g., north, northeast). We assume a spatial database of points and regions. Points belong to regions, which may be parts of larger regions and so on. The direction relations between points in the same region are explicitly represented. Inference mechanisms are applied to extract the relation between points in different regions and detect inconsistencies. We study two complementary types of inference. The first one derives the relation between two points that exist in different regions through chains of common points using path consistency. The second type of inference uses the relation between ancestor regions to infer the relation between the points. The paper describes algorithms for both types of inference and discusses their computational complexity.

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.

Recent developments in spatial relations have led to their use in numerous applications involving spatial databases. This paper is concerned with the retrieval of topological relations in Minimum Bounding Rectangle-based data structures. We study the topological information that Minimum Bounding Rectangles convey about the actual objects they enclose, using the concept of projections. Then we apply the results in R-trees and their variations, R+ and R* trees in order to minimize disk accesses for queries involving topological relations. We also investigate queries that involve complex spatial conditions in the form of disjunctions and conjunctions and we discuss possible extensions.