Browsing by Author "Liu, Xuan"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Consistency Checking for Euclidean Spatial Constraints: A Dimension Graph Approach
    (2000-07-11) Liu, Xuan; Shekhar, Shashi; Chawla, Sanjay
    In this paper, we address the problem of consistency checking for Euclidean spatial constraints. A dimension graph representation is proposed to maintain the Euclidean spatial constraints among objects. The basic idea is to project the spatial constraints on both X and Y dimensions, and the dimension graph is constructed on each dimension. By using the dimension graph representation, the problem of consistency checking is then transformed to a graph cycle detection problem. The consistency checking can be achieved with O(N+E) time as well as space complexity, where N is the number of spatial object, and E is the number of spatial predicates in the constraint. The proposed approach to consistency checking for spatial constraints is faster than O(N2) when the number of predicates is much smaller than N2 and there are few disjunctions in the spatial constraint. The dimension graph and consistency checking algorithm can be used for points, intervals and polygons in 2 dimensional space. The algorithm can guarantee the global consistency.
  • Thumbnail Image
    Item
    Equivalence Classes of Direction Objects and Applications
    (1999-07-21) Shekhar, Shashi; Liu, Xuan; Chawla, Sanjay
    Direction is an important spatial relationship that is used in many fields such as geographic information systems (GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. In our recent work we have described a novel viewpoint to model direction as a `spatial object' based upon the concepts of vectors, points and angles. This was a departure from the conventional approach of treating direction as a spatial relationship between objects. In this paper, based upon `direction objects', we partition the directional space into a set of equivalence classes. By defining an algebra on equivalence classes we provide a framework to model semantics of direction predicates for qualitative spatial reasoning. We then proceed to extrapolate the definition of direction equivalence classes to define `path' equivalence classes with an application to the landmark-based route description problem. Keywords: Directional relationships, Direction objects, Equivalence Classes, Landmark-based routing.
  • Thumbnail Image
    Item
    Modeling and Processing Directional Relationships in Spatial Databases
    (2000-08-21) Liu, Xuan
    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.
  • Thumbnail Image
    Item
    Processing Object-Orientation-based Direction Queries in Spatial Databases
    (2000-05-04) Liu, Xuan; Shekhar, Shashi; Chawla, Sanjay
    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. In this paper, we explore processing of queries based on object-orientation-based directional relationships. A new Open Shape based strategy (OSS) is proposed. OSS converts the processing of the direction predicates to the processing of topological operations between open shapes and closed geometry objects. Since OSS models the direction region as an Open Shape, it does not need to know the boundary of the embedding world, and also eliminating the computation related to the world boundary. We perform algebraic analysis as well as experimental evaluation for OSS. The experimental result demonstrates that the OSS consistently outperforms classical range query strategy both in I/O and CPU cost.