2026-07-22T18:26:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16890 2024-03-06T10:58:17Z ddc:004 open_access

An Incremental Algorithm for Handling Qualitative Spatio-Temporal Information Long, Zhiguo Hu, Qiyuan Meng, Hua Sioutis, Michael Online algorithm qualitative data spatio-temporal reasoning satisfiability checking knowledge representation and reasoning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhiguo Long and Qiyuan Hu and Hua Meng and Michael Sioutis 2022 Is Part Of LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.COSIT.2022.5 urn:nbn:de:0030-drops-168907 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode