Document Open Access Logo

An Incremental Algorithm for Handling Qualitative Spatio-Temporal Information

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

PDF
Thumbnail PDF

File

LIPIcs.COSIT.2022.5.pdf
  • Filesize: 0.89 MB
  • 13 pages

Document Identifiers

Author Details

Zhiguo Long
  • School of Computing and Artificial Intelligence, Southwest Jiaotong University, Chengdu, China
Qiyuan Hu
  • School of Computing and Artificial Intelligence, Southwest Jiaotong University, Chengdu, China
Hua Meng
  • School of Mathematics, Southwest Jiaotong University, Chengdu, China
Michael Sioutis
  • Faculty of Information Systems and Applied Computer Sciences, Universität Bamberg, Germany

Funding

This work was supported by the National Natural Science Foundation of China (61806170), the Humanities and Social Sciences Fund of Ministry of Education (18XJC72040001), and the National Key Research and Development Program of China (2019YFB1706104).

Cite AsGet BibTex

Zhiguo Long, Qiyuan Hu, Hua Meng, and Michael Sioutis. An Incremental Algorithm for Handling Qualitative Spatio-Temporal Information. In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.COSIT.2022.5

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Computing methodologies → Temporal reasoning
  • Computing methodologies → Spatial and physical reasoning
Keywords
  • Online algorithm
  • qualitative data
  • spatio-temporal reasoning
  • satisfiability checking
  • knowledge representation and reasoning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509-512, 1999. Google Scholar
  2. Anne Berry, Pinar Heggernes, and Yngve Villanger. A vertex incremental approach for maintaining chordality. Discrete Mathematics, 306(3):318-336, 2006. Google Scholar
  3. Mehul Bhatt, Frank Dylla, and Joana Hois. Spatio-terminological Inference for the Design of Ambient Environments. In COSIT, pages 371-391, 2009. Google Scholar
  4. Nicolas Chleq. Efficient Algorithms for Networks of Quantitative Temporal Constraints. In CONSTRAINT@FLAIRS Conference, pages 901-907, 1995. Google Scholar
  5. Jean-François Condotta, Issam Nouaouri, and Michael Sioutis. A SAT Approach for Maximizing Satisfiability in Qualitative Spatial and Temporal Constraint Networks. In KR, pages 432-442, 2016. Google Scholar
  6. Krishna Sandeep Reddy Dubba, Anthony G. Cohn, David C. Hogg, Mehul Bhatt, and Frank Dylla. Learning Relational Event Models from Video. J. Artif. Intell. Res., 53:41-90, 2015. Google Scholar
  7. Frank Dylla, Jae Hee Lee, Till Mossakowski, Thomas Schneider, André van Delden, Jasper van de Ven, and Diedrich Wolter. A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties. ACM Comput. Surv., 50(1):7:1-7:39, 2017. Google Scholar
  8. Frank Dylla, Till Mossakowski, Thomas Schneider, and Diedrich Wolter. Algebraic Properties of Qualitative Spatio-temporal Calculi. In COSIT, pages 516-536, 2013. Google Scholar
  9. Frank Dylla and Jan Oliver Wallgrün. Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control. J. Intell. Robotic Syst., 48(1):55-78, 2007. Google Scholar
  10. Max J. Egenhofer. Toward the semantic geospatial web. In ACM-GIS, pages 1-4, 2002. Google Scholar
  11. Delbert Ray Fulkerson and Oliver Alfred Gross. Incidence matrices and interval graphs. Pacific J. Math., 15(3):835-855, 1965. Google Scholar
  12. Martin Charles Golumbic and Ron Shamir. Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. J. ACM, 40(5):1108-1133, 1993. Google Scholar
  13. Georg Gottlob. On minimal constraint networks. Artif. Intell., 191-192:42-60, 2012. Google Scholar
  14. Thiago Pedro Donadon Homem, Paulo Eduardo Santos, Anna Helena Reali Costa, Reinaldo Augusto da Costa Bianchi, and Ramón López de Mántaras. Qualitative case-based reasoning & learning. Artif. Intell., 283:103258, 2020. Google Scholar
  15. Zina Ibrahim, Honghan Wu, and Richard Dobson. Modeling Rare Interactions in Time Series Data Through Qualitative Change: Application to Outcome Prediction in Intensive Care Units. In ECAI, pages 1826-1833, 2020. Google Scholar
  16. Orestis Kostakis, Nikolaj Tatti, and Aristides Gionis. Discovering recurring activity in temporal networks. Data Min. Knowl. Discov., 31(6):1840-1871, 2017. Google Scholar
  17. Manolis Koubarakis, Manos Karpathiotakis, Kostis Kyzirakos, Charalampos Nikolaou, and Michael Sioutis. Data Models and Query Languages for Linked Geospatial Data. In Reasoning Web, pages 290-328, 2012. Google Scholar
  18. Sanjiang Li, Zhiguo Long, Weiming Liu, Matt Duckham, and Alan Both. On redundant topological constraints. Artif. Intell., 225:51-76, 2015. Google Scholar
  19. Gérard Ligozat. Qualitative Spatial and Temporal Reasoning. ISTE Series. Wiley, 2011. Google Scholar
  20. Gérard Ligozat and Jochen Renz. What Is a Qualitative Calculus? A General Framework. In PRICAI, pages 53-64, 2004. Google Scholar
  21. Zhiguo Long and Sanjiang Li. On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi. In COSIT, pages 354-374, 2015. Google Scholar
  22. Zhiguo Long, Michael Sioutis, and Sanjiang Li. Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks. In IJCAI, pages 1202-1208, 2016. Google Scholar
  23. David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions and Connection. In KR, pages 165-176, 1992. Google Scholar
  24. Jochen Renz. A Canonical Model of the Region Connection Calculus. J. Appl. Non Class. Logics, 12(3-4):469-494, 2002. Google Scholar
  25. Jochen Renz and Bernhard Nebel. Qualitative Spatial Reasoning Using Constraint Calculi. In Handbook of Spatial Logics, pages 161-215. Springer, 2007. Google Scholar
  26. Michael Sioutis, Zhiguo Long, and Sanjiang Li. Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints. Int. J. Artif. Intell. Tools, 27(4):1-37, 2018. Google Scholar
  27. Michael Sioutis and Diedrich Wolter. Qualitative Spatial and Temporal Reasoning: Current Status and Future Challenges. In IJCAI, pages 4594-4601, 2021. Google Scholar
  28. Philip A. Story and Michael F. Worboys. A Design Support Environment for Spatio-Temporal Database Applications. In COSIT, pages 413-430, 1995. Google Scholar
  29. Jakob Suchan, Mehul Bhatt, and Srikrishna Varadarajan. Out of Sight But Not Out of Mind: An Answer Set Programming Based Online Abduction Framework for Visual Sensemaking in Autonomous Driving. In IJCAI, pages 1879-1885, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact