Compact geometric representation of qualitative directional knowledge

Long, Z; Meng, H; Li, T; Li, S

Compact geometric representation of qualitative directional knowledge

Long, Z Meng, H Li, T Li, S

Permalink

Publication Type:: Journal Article
Citation:: Knowledge-Based Systems, 2020, 195
Issue Date:: 2020-05-11

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 2 Jan 2022

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (1.71 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Long, Z	en_US
dc.contributor.author	Meng, H	en_US
dc.contributor.author	Li, T	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.date.issued	2020-05-11	en_US
dc.identifier.citation	Knowledge-Based Systems, 2020, 195	en_US
dc.identifier.issn	0950-7051	en_US
dc.identifier.uri	http://hdl.handle.net/10453/138861
dc.description.abstract	© 2020 Elsevier B.V. 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.	en_US
dc.relation.ispartof	Knowledge-Based Systems	en_US
dc.relation.isbasedon	10.1016/j.knosys.2020.105616	en_US
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Compact geometric representation of qualitative directional knowledge	en_US
dc.type	Journal Article
utslib.citation.volume	195	en_US
utslib.for	08 Information and Computing Sciences	en_US
utslib.for	15 Commerce, Management, Tourism and Services	en_US
utslib.for	17 Psychology and Cognitive Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
utslib.copyright.embargo	2022-01-02T00:00:00+1100
pubs.publication-status	Accepted	en_US
pubs.volume	195	en_US

Abstract:

© 2020 Elsevier B.V. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/138861