Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2017 Volume 32
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  • Artois

More Information
  • Abstract: We survey the use and effect of decomposition-based techniques in qualitative spatial and temporal constraint-based reasoning, and clarify the notions of a tree decomposition, a chordal graph, and a partitioning graph, and their implication with a particular constraint property that has been extensively used in the literature, namely, patchwork. As a consequence, we prove that a recently proposed decomposition-based approach that was presented in the study by Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial constraint networks lacks soundness. Therefore, the approach becomes quite controversial as it does not seem to offer any technical advance at all, while results of an experimental evaluation of it in a following work presented in the study by Sioutis become questionable. Finally, we present a particular tree decomposition that is based on the biconnected components of the constraint graph of a given large network, and show that it allows for cost-free utilization of parallelism for a qualitative constraint language that has patchwork for satisfiable atomic networks.
  • 加载中
  • Allen J. F.1981. An interval-based representation of temporal knowledge. InIJCAI.

    Google Scholar

    Amaneddine N., Condotta J.-F. & Sioutis M.2013. Efficient approach to solve the minimal labeling problem of temporal and spatial qualitative constraints. InIJCAI.

    Google Scholar

    Baget J.-F. & Tognetti Y. S.2001. Backtracking through biconnected components of a constraint graph. In IJCAI.

    Google Scholar

    Balbiani P., Condotta J.-F. & Cerro L. F. d.2002. Tractability results in the block algebra. Journal of Logic and Computation12,885–909.

    Google Scholar

    Barabasi A.-L. & Bonabeau E.2003. Scale-free networks.Scientific American288,50–59.

    Google Scholar

    Beek P. v. & Manchak D. W.1996. The design and experimental analysis of algorithms for temporal reasoning. Journal of Artificial Intelligence Research4, 1–18.

    Google Scholar

    Bhatt M., Guesgen H., Wölfl S. & Hazarika S.2011. Qualitative spatial and temporal reasoning: emerging applications, trends, and directions.Spatial Cognition & Computation11, 1–14.

    Google Scholar

    Bliek C. & Sam-Haroud D.1999. Path consistency on triangulated constraint graphs. InIJCAI.

    Google Scholar

    Bodirsky M. & Wölfl S.2011. RCC8 is polynomial on networks of bounded treewidth. InIJCAI.

    Google Scholar

    Brand S.2004. Relation variables in qualitative spatial reasoning. InKI.

    Google Scholar

    Chmeiss A. & Condotta J.-F.2011. Consistency of triangulated temporal qualitative constraint networks. In ICTAI.

    Google Scholar

    Condotta J.-F. & D’Almeida D.2011. Consistency of qualitative constraint networks from tree decompositions. In TIME.

    Google Scholar

    Condotta J.-F., Dalmeida D., Lecoutre C. & Sais L.2006. From qualitative to discrete constraint networks. InKI Workshop on Qualitative Constraint Calculi.

    Google Scholar

    Dechter R.2003. Constraint Processing.Elsevier Morgan Kaufmann.

    Google Scholar

    Dechter R. & Pearl J.1989. Tree clustering for constraint networks. Artificial Intelligence38,353–366.

    Google Scholar

    Del Genio C. I., Gross T. & Bassler K. E.2011. All scale-free networks are sparse. Physical Review Letters107, 178701.

    Google Scholar

    Diestel R.2012. Graph Theory, 4th Edition, 173.Springer.

    Google Scholar

    Duckham M., Li S., Liu W. & Long Z.2014. On redundant topological constraints. InKR.

    Google Scholar

    Dylla F., Mossakowski T., Schneider T. & Wolter D.2013. Algebraic properties of qualitative spatio-temporal calculi. In COSIT.

    Google Scholar

    Elidan G. & Gould S.2008. Learning bounded treewidth Bayesian networks. InNIPS.

    Google Scholar

    Frank A. U.1991. Qualitative spatial reasoning with cardinal directions. InÖGAI.

    Google Scholar

    Gantner Z., Westphal M. & Wölfl S.2008. GQR—a fast reasoner for binary qualitative constraint calculi. In AAAI Workshop on Spatial and Temporal Reasoning.

    Google Scholar

    Garey M. R., Johnson D. S. & Stockmeyer L. J.1976. Some simplified NP-complete graph problems. Theoretical Computer Science1,237–267.

    Google Scholar

    Goodwin J., Dolbear C. & Hart G.2008. Geographical linked data: the administrative geography of Great Britain on the semantic web.Transactions in GIS12,19–30.

    Google Scholar

    Gottlob G., Leone N. & Scarcello F.2000. A comparison of structural CSP decomposition methods. Artificial Intelligence124,243–282.

    Google Scholar

    Hazarika S. M.2012. Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions. IGI Global.

    Google Scholar

    Huang J.2012. Compactness and its implications for qualitative spatial and temporal reasoning. In KR.

    Google Scholar

    Huang J., Li J. J. & Renz J.2013. Decomposition and tractability in qualitative spatial and temporal reasoning. Artificial Intelligence195,140–164.

    Google Scholar

    Jégou P., Ndiaye S. & Terrioux C.2005. Computing and exploiting tree-decompositions for solving constraint networks. In CP.

    Google Scholar

    Jégou P., Ndiaye S. & Terrioux C.2006. An extension of complexity bounds and dynamic heuristics for tree-decompositions of CSP. In CP.

    Google Scholar

    Jégou P., Ndiaye S. & Terrioux C.2007. Dynamic heuristics for backtrack search on tree-decomposition of CSPs. In IJCAI.

    Google Scholar

    Jégou P. & Terrioux C.2003. Hybrid backtracking bounded by tree-decomposition of constraint networks.Artificial Intelligence146,43–75.

    Google Scholar

    Jégou P. & Terrioux C.2014a. Bag-connected tree-width: a new parameter for graph decomposition. In ISAIM.

    Google Scholar

    Jégou P. & Terrioux C.2014b. Tree-decompositions with connected clusters for solving constraint networks. In CP.

    Google Scholar

    Ladkin P. B. & Maddux R. D.1994. On binary constraint problems.Journal of the ACM41,435–469.

    Google Scholar

    Li J. J., Huang J. & Renz J.2009. A divide-and-conquer approach for solving interval algebra networks. In IJCAI.

    Google Scholar

    Li S., Long Z., Liu W., Duckham M. & Both A.2015. On redundant topological constraints. Artificial Intelligence225,51–76.

    Google Scholar

    Ligozat G.1998. Reasoning about cardinal directions. Journal of Visual Languages and Computing9, 23–44.

    Google Scholar

    Ligozat G.2011. Qualitative Spatial and Temporal Reasoning, Iste Series. Wiley.

    Google Scholar

    Liu W. & Li S.2012. Solving minimal constraint networks in qualitative spatial and temporal reasoning. In CP.

    Google Scholar

    Lutz C. & Milicic M.2007. A tableau algorithm for DLs with concrete domains and GCIs. Journal of Automated Reasoning38,227–259.

    Google Scholar

    Montanari U.1974. Networks of constraints: fundamental properties and applications to picture processing.Information Sciences7,95–132.

    Google Scholar

    Nebel B.1997. Solving hard qualitative temporal reasoning problems: evaluating the efficiency of using the ORD-Horn class. Constraints1,175–190.

    Google Scholar

    Nebel B. & Bürckert H.-J.1995. Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra.Journal of the ACM42,43–66.

    Google Scholar

    Nikolaou C. & Koubarakis M.2014. Fast consistency checking of very large real-world RCC-8 constraint networks using graph partitioning. InAAAI.

    Google Scholar

    Randell D. A., Cui Z. & Cohn A.1992. A spatial logic based on regions and connection. InKR.

    Google Scholar

    Renz J.1999. Maximal tractable fragments of the region connection calculus: a complete analysis. In IJCAI.

    Google Scholar

    Renz J.2002a. A canonical model of the region connection calculus. Journal of Applied Non-Classical Logics12,469–494.

    Google Scholar

    Renz J.2002b. Qualitative Spatial Reasoning with Topological Information.Springer-Verlag.

    Google Scholar

    Renz J. & Ligozat G.2005. Weak composition for qualitative spatial and temporal reasoning. In CP.

    Google Scholar

    Renz J. & Nebel B.1999. On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artificial Intelligence108,69–123.

    Google Scholar

    Renz J. & Nebel B.2001. Efficient methods for qualitative spatial reasoning. Journal of Artificial Intelligence Research15,289–318.

    Google Scholar

    Sioutis M.2014. Triangulation versus graph partitioning for tackling large real world qualitative spatial networks. InICTAI.

    Google Scholar

    Sioutis M. & Condotta J.-F.2014. Tackling large qualitative spatial networks of scale-free-like structure. In SETN.

    Google Scholar

    Sioutis M., Condotta J.-F. & Koubarakis M.2016. An efficient approach for tackling large real world qualitative spatial networks. International Journal of Artificial Intelligence Tools25, 1–33.

    Google Scholar

    Sioutis M. & Koubarakis M.2012. Consistency of chordal RCC-8 networks. InICTAI.

    Google Scholar

    Sioutis M., Li S. & Condotta J.-F.2015b. Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks. InIJCAI.

    Google Scholar

    Sioutis M., Salhi Y. & Condotta J.-F.2015c. A simple decomposition scheme for large real world qualitative constraint networks. In FLAIRS.

    Google Scholar

    Sioutis M., Salhi Y. & Condotta J.-F.2015d. On the use and effect of graph decomposition in qualitative spatial and temporal reasoning. In SAC.

    Google Scholar

    Tarjan R. E. & Yannakakis M.1984. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing13,566–579.

    Google Scholar

    Tarski A.1941. On the calculus of relations.Journal of Symbolic Logic6, 73–89.

    Google Scholar

    Vilain M., Kautz H. & Beek P. v.1990. Readings in qualitative reasoning about physical systems. InConstraint Propagation Algorithms for Temporal Reasoning: A Revised Report, Weld, D. S. & de Kleer, J. (eds). Morgan Kaufmann Publishers Inc., 373–381.

    Google Scholar

    Walsh T.2001. Search on high degree graphs. InIJCAI.

    Google Scholar

    Westphal M. & Hué J.2014. A concise Horn theory for RCC8. InECAI.

    Google Scholar

    Westphal M., Hué J. & Wölfl S.2013. On the propagation strength of SAT encodings for qualitative temporal reasoning. In ICTAI.

    Google Scholar

    Westphal M. & Wölfl S.2009. Qualitative CSP, finite CSP, and SAT: comparing methods for qualitative constraint-based reasoning. InIJCAI.

    Google Scholar

    Yannakakis M.1981. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods2, 77–79.

    Google Scholar

  • Cite this article

    Michael Sioutis, Yakoub Salhi, Jean-François Condotta. 2017. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891600014X
    Michael Sioutis, Yakoub Salhi, Jean-François Condotta. 2017. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891600014X
    shu
Download PDF

Article Metrics

Article views(28) PDF downloads(28)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  • Artois

  • Published online: 12 October 2016
The Knowledge Engineering Review  32,  2017, 32(1)  |  Cite this article

Abstract: Abstract: We survey the use and effect of decomposition-based techniques in qualitative spatial and temporal constraint-based reasoning, and clarify the notions of a tree decomposition, a chordal graph, and a partitioning graph, and their implication with a particular constraint property that has been extensively used in the literature, namely, patchwork. As a consequence, we prove that a recently proposed decomposition-based approach that was presented in the study by Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial constraint networks lacks soundness. Therefore, the approach becomes quite controversial as it does not seem to offer any technical advance at all, while results of an experimental evaluation of it in a following work presented in the study by Sioutis become questionable. Finally, we present a particular tree decomposition that is based on the biconnected components of the constraint graph of a given large network, and show that it allows for cost-free utilization of parallelism for a qualitative constraint language that has patchwork for satisfiable atomic networks.

    HTML

    Acknowledgments

    • This work was funded by a PhD grant from Université d’Artois and region Nord-Pas-de-Calais. The material presented in this paper draws from the work of Sioutis et al. (2015c,2015d).

    • In what follows, a tractable (resp. intractable) QCN will be a QCN whose satisfiability problem is tractable (resp. intractable).

    • The result of the weak composition between any relation and the universal relation is the universal relation.

    • This term is also found by the name ‘refined QCN’ throughout the literature.

    • The literature suggests the term algebraic closure (Renz & Ligozat, 2005) instead, which is equivalent to a path-consistency algorithm where the weak composition operator ◊ is used instead of the relational composition operator ○ (Renz & Ligozat, 2005), so we will use this more traditional term throughout the paper.

    • Some of the cited works are based on encodings of QCNs into Boolean formulas. However, the Boolean formulas are constructed in such a way that each solution of a formula corresponds to a not trivially inconsistent and path-consistent QCN defined over some maximal tractable subclass of relations, and vice versa.

    • Some of the cited works use a property called amalgamation, which is equivalent to patchwork for satisfiable atomic networks when the satisfiability of atomic networks can be decided by path consistency.

    • https://www.dropbox.com/sh/h61edhshw5p8ne2/AAAuO0WyYB5r8cLmoRBLV8xla?dl=0

    • Good in terms of obtaining smaller components that meet specific properties, for example, a good partitioning can be defined as a partitioning in which the number of edges running between separated components is relatively small.

    • http://glaros.dtc.umn.edu/gkhome/views/metis

    • Retrieved from http://www.linkedopendata.gr/

    • http://gadm.geovocab.org/

    • http://pypy.org

    • https://networkx.github.io/

    Rights and permissions
    • © Cambridge University Press, 2017 2017Cambridge University Press
References (67)
  • About this article
    Cite this article
    Michael Sioutis, Yakoub Salhi, Jean-François Condotta. 2017. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891600014X
    Michael Sioutis, Yakoub Salhi, Jean-François Condotta. 2017. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891600014X
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return