Proceedings

Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3229-3234.

© 2015 International Joint Conferences on Artificial Intelligence

Abstract

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.

  1. [Allen, 1983] James F. Allen. Maintaining Knowledge about Tem- poral Intervals. Commun. ACM, 26:832-843, 1983.
  2. [Amaneddine et al., 2013] Nouhad Amaneddine, Jean-Franc ¸ois Condotta, and Michael Sioutis. Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In IJCAI, 2013.
  3. [Bliek and Sam-Haroud, 1999] Christian Bliek and Djamila Sam- Haroud. Path consistency on triangulated constraint graphs. In IJCAI, 1999.
  4. [Bodirsky and Wölfl, 2011] Manuel Bodirsky and Stefan Wölfl. RCC8 is polynomial on networks of bounded treewidth. In IJCAI, 2011. IJCAI
  5. [Chmeiss and Condotta, 2011] Assef Chmeiss and Jean-Franc ¸ois Condotta. Consistency of Triangulated Temporal Qualitative Con- straint Networks. In ICTAI, 2011.
  6. [Condotta et al., 2009] Jean-Franc ¸ois Condotta, Souhila Kaci, Pierre Marquis, and Nicolas Schwind. Merging Qualitative Con- straint Networks in a Piecewise Fashion. In ICTAI, 2009.
  7. [Diestel, 2012] Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 4th edition, 2012.
  8. [Duckham et al., 2014] Matt Duckham, Sanjiang Li, Weiming Liu, and Zhiguo Long. On Redundant Topological Constraints. In KR, 2014.
  9. [Frank, 1991] Andrew U. Frank. Qualitative Spatial Reasoning with Cardinal Directions. In ÖGAI, 1991.
  10. [Goodwin et al., 2008] John Goodwin, Catherine Dolbear, and Glen Hart. Geographical Linked Data: The Administrative Geography of Great Britain on the Semantic Web. TGIS, 12:19-30, 2008.
  11. [Guesgen, 1989] Hans Werner Guesgen. Spatial Reasoning Based on Allen's Temporal Logic. Technical report, International Com- puter Science Institute, 1989.
  12. [Huang et al., 2013] Jinbo Huang, Jason Jingshi Li, and Jochen Renz. Decomposition and tractability in qualitative spatial and temporal reasoning. AIJ, 195:140-164, 2013.
  13. [Huang, 2012] Jinbo Huang. Compactness and its implications for qualitative spatial and temporal reasoning. In KR, 2012.
  14. [Li et al., 2015] Sanjiang Li, Zhiguo Long, Weiming Liu, Matt Duckham, and Alan Both. On redundant topological constraints. AIJ, 225:51-76, 2015. In press.
  15. [Ligozat, 1998] Gerard Ligozat. Reasoning about cardinal direc- tions. J. Vis. Lang. Comput., 9(1):23-44, 1998.
  16. [Liu and Li, 2012] Weiming Liu and Sanjiang Li. Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reason- ing. In CP, 2012.
  17. [Nikolaou and Koubarakis, 2013] Charalampos Nikolaou and Manolis Koubarakis. Querying Incomplete Geospatial Informa- tion in RDF. In SSTD, 2013.
  18. [Nikolaou and Koubarakis, 2014] Charalampos Nikolaou and Manolis Koubarakis. Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning. In AAAI, 2014.
  19. [OGC, 2012] OGC. GeoSPARQL -A geographic query language for RDF data. OGC R Standard, 2012.
  20. [Parter, 1961] Seymour Parter. The use of linear graphs in Gauss elimination. SIAM Review, 3:119-130, 1961.
  21. [Randell et al., 1992] David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions and Connection. In KR, 1992.
  22. [Renz and Ligozat, 2005] Jochen Renz and Gérard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning. In CP, 2005.
  23. [Renz and Nebel, 1999] Jochen Renz and Bernhard Nebel. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. AIJ, 108:69-123, 1999. IJCAI
  24. [Renz and Nebel, 2001] Jochen Renz and Bernhard Nebel. Efficient Methods for Qualitative Spatial Reasoning. JAIR, 15:289-318, 2001.
  25. [Sioutis and Koubarakis, 2012] Michael Sioutis and Manolis Koubarakis. Consistency of Chordal RCC-8 Networks. In ICTAI, 2012.
  26. [Sioutis et al., 2015a] Michael Sioutis, Sanjiang Li, and Jean- Franc ¸ois Condotta. On Redundancy in Linked Geospatial Data. In LDQ@ESWC, 2015. To appear.
  27. [Sioutis et al., 2015b] Michael Sioutis, Yakoub Salhi, and Jean- Franc ¸ois Condotta. A Simple Decomposition Scheme For Large Real World Qualitative Constraint Networks. In FLAIRS, 2015. To appear.
  28. [Wallgrün, 2012] Jan Oliver Wallgrün. Exploiting qualitative spatial reasoning for topological adjustment of spatial data. In SIGSPA- TIAL, 2012.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards