License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.COSIT.2022.5
URN: urn:nbn:de:0030-drops-168907
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16890/
Go to the corresponding LIPIcs Volume Portal

Long, Zhiguo ; Hu, Qiyuan ; Meng, Hua ; Sioutis, Michael

An Incremental Algorithm for Handling Qualitative Spatio-Temporal Information

pdf-format:
LIPIcs-COSIT-2022-5.pdf (0.9 MB)

Abstract

In this paper, we present an online (incremental) algorithm for checking the satisfiability of qualitative spatio-temporal data, with direct implications to other fundamental knowledge representation and reasoning problems for such data, like the problems of deductive closure and redundancy removal. In particular, qualitative data come in the form of human-like, symbolic, descriptions such as "region x contains or overlaps region y", which are abundant in the Web of Data. Our approach is also able to maintain, to some extent, any sparse graph structure that may be inherent in the data, i.e., it acts parsimoniously and only tries to infer new information when needed for soundness and completeness. To this end, we complement our practical algorithm with certain theoretical results to assert its correctness and efficiency. A subsequent evaluation with publicly available large-scale real-world and random datasets against the state of the art, shows the interest and promise of our method.

BibTeX - Entry

@InProceedings{long_et_al:LIPIcs.COSIT.2022.5,
  author =	{Long, Zhiguo and Hu, Qiyuan and Meng, Hua and Sioutis, Michael},
  title =	{{An Incremental Algorithm for Handling Qualitative Spatio-Temporal Information}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16890},
  URN =		{urn:nbn:de:0030-drops-168907},
  doi =		{10.4230/LIPIcs.COSIT.2022.5},
  annote =	{Keywords: Online algorithm, qualitative data, spatio-temporal reasoning, satisfiability checking, knowledge representation and reasoning}
}

Keywords: Online algorithm, qualitative data, spatio-temporal reasoning, satisfiability checking, knowledge representation and reasoning
Collection: 15th International Conference on Spatial Information Theory (COSIT 2022)
Issue Date: 2022
Date of publication: 22.08.2022
Supplementary Material: Software (Source Code): https://github.com/ZhiguoLong/DPCI_code

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI