Modeling and Processing Directional Relationships in Spatial Databases
2000-08-21
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Modeling and Processing Directional Relationships in Spatial Databases
Authors
Published Date
2000-08-21
Publisher
Type
Report
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Liu, Xuan. (2000). Modeling and Processing Directional Relationships in Spatial Databases. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215431.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.