Modeling and Processing Directional Relationships in Spatial Databases

Abstract

Direction based spatial relationships are critical in many domains including geographic information systems (GIS) and image interpretation. They are also frequently used as selection conditions in spatial queries. Previous work modeled directions as binary boolean relationships and performed qualitative reasoning by enumerating a large number of inference rules without an independent interpretation model. The research of query processing in previous work has focused on processing absolute directions using range query strategies. However, many direction queries depend on the orientation of reference objects (or the viewer), which may change due to motion. Classical methods are inefficient when the orientation of the reference object is different from that of the global reference system.The goal of this research is to define and explore new direction models and new processing strategies for direction queries. As a departure from traditional methods, we propose a vector-based framework to model direction as a spatial object. This object view of direction enables the definition of new spatial data types such as open shapes and oriented objects at the abstract object level. By extending to equivalence classes of direction objects, we can unify spatial reasoning with different direction predicate sets. The equivalence classes together with the algebra defined on them provide an independent interpretation model for qualitative direction reasoning. We also propose a new, efficient and scalable algorithm, namely open shape-based strategy (OSS), to process direction queries in spatial databases. OSS converts the processing of the directional queries to the processing of topological operations between open shapes and objects. It eliminates false hits at the earliest opportunity while recursively searching hierarchical indices like R-tree. Since OSS models the direction region as an open shape, it also eliminates the computation related to the embedding world boundary. We explore the behavior of OSS in detail by performing algebraic analysis and experimental evaluation on different datasets. The results show that OSS consistently outperforms classical range query strategies in terms of both I/O and CPU cost. OSS also shows better scalability for large data sets.