Compact geometric representation of qualitative directional knowledge

摘要

To effectively and efficiently deal with large-scale spatial data is critical for applications in the age of information technology. Compact representation of spatial knowledge is one of the emerging research techniques that contribute to this capability. In this article, we consider the problem of compactly representing qualitative directional relations between extended objects, modelled in the Cardinal Direction Calculus (CDC) of Goyal and Egenhofer. For a large dataset of regions, this approach first constructs a simplified geometry for each region, which preserves CDC relations between regions, and then represents each simplified geometry compactly, so that the storage size is small while retrieving CDC relations from the representation is still reasonably fast. More specifically, the method called necessary cut is used to construct simple geometries, and the two methods, viz. the polygon representation and the rectangle representation, are devised to compactly represent the constructed geometries in cubic time w.r.t. the size of the corresponding simple geometry. Theoretical analyses demonstrate that the two representations, especially the rectangle representation, are promising to have small storage size. Moreover, our empirical evaluations on real-world datasets show that, for each dataset the new approach can produce a rectangle representation that has dominant performance against the state of the art techniques in reducing the storage size of the relations, while the average efficiency of retrieving CDC relations based on the rectangle representation is about the same as the fastest method in the literature.