Efficient Methods for Qualitative Spatial Reasoning

The theoretical properties of qualitative spatial reasoning in the RCC-8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC-8 instances, even if they are in the phase transition region - provided that one uses the maximal tractable subsets of RCC-8 that have been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.

• Publication year

  2001

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  2001-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1613/jair.872arXiv 1106.0679
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Qualitative Spatial Reasoning with Topological Information

  2002cited by this paper
• On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus

  1999cited by this paper
• Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis

  1999cited by this paper
• Efficient Methods for Qualitative Spatial Reasoning

  1998cited by this paper
• Logical representations for automated reasoning about spatial relationships

  1997cited by this paper
• An Economics Approach to Hard Computational Problems

  1997cited by this paper
• The Constrainedness of Search

  1996cited by this paper
• Computational Properties of Qualitative Spatial Reasoning: First Results

  1995cited by this paper
• The Design and Experimental Analysis of Algorithms for Temporal Reasoning

  1995cited by this paper
• Exploiting the Deep Structure of Constraint Problems

  1994cited by this paper
• Spatial Reasoning with Propositional Logics

  1994cited by this paper
• Complexity and algorithms for reasoning about time: a graph-theoretic approach

  1993cited by this paper
• A Spatial Logic based on Regions and Connection

  1992cited by this paper
• Computing Transivity Tables: A Challenge For Automated Theorem Provers

  1992cited by this paper
• Effective Solution of Qualitative Interval Constraint Problems

  1992cited by this paper
• A New Method for Solving Hard Satisfiability Problems

  1992cited by this paper
• Where the Really Hard Problems Are

  1991cited by this paper
• The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems

  1985cited by this paper
• Maintaining knowledge about temporal intervals

  1983cited by this paper
• Increasing Tree Search Efficiency for Constraint Satisfaction Problems

  1979cited by this paper
• Consistency in Networks of Relations

  1977cited by this paper
• Networks of constraints: Fundamental properties and applications to picture processing

  1974cited by this paper

• A Framework for Hybrid Set-Theoretic and Numerical Problem Solving

  2025cites this paper
• Learning to resolve inconsistencies in qualitative constraint networks

  2025influential citation
• A Reinforcement Learning Approach for Resolving Inconsistencies in Qualitative Constraint Networks

  2024cites this paper
• On prime scenarios in qualitative spatial and temporal reasoning

  2024cites this paper
• Embarrassingly Greedy Inconsistency Resolution of Qualitative Constraint Networks

  2023cites this paper
• Qualitative spatial reasoning with uncertain evidence using Markov logic networks

  2023cites this paper
• A Paraconsistency Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning

  2023cites this paper
• HyperQuaternionE: A hyperbolic embedding model for qualitative spatial and temporal reasoning

  2022cites this paper
• The Spatio-temporal Hybrid Development Methodology for Smart IoT: A Review based Study

  2022cites this paper
• Dynamic branching in qualitative constraint-based reasoning via counting local models

  2021cites this paper
• Robust Vs Fast Solving of Qualitative Constraints: Can we do Both?

  2021cites this paper
• Qualitative Spatial and Temporal Reasoning: Current Status and Future Challenges

  2021cites this paper
• Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms

  2021cites this paper
• Artificial Intelligence - Way Forward in Livestock Industry

  2020cites this paper
• Just-In-Time Constraint-Based Inference for Qualitative Spatial and Temporal Reasoning

  2020cites this paper
• Tractable Fragments of Temporal Sequences of Topological Information

  2020cites this paper
• Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property

  2020influential citation
• Dynamic Branching in Qualitative Constraint Networks via Counting Local Models

  2020cites this paper
• The Horn Fragment of Branching Algebra

  2020cites this paper
• A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory

  2020cites this paper
• Collective singleton-based consistency for qualitative constraint networks: Theory and practice

  2019influential citation
• Large scale distributed spatio-temporal reasoning using real-world knowledge graphs

  2019cites this paper
• An Incremental SAT-Based Approach to Reason Efficiently on Qualitative Constraint Networks

  2018cites this paper
• Qualitative spatial reasoning on topological relations by combining the semantic web and constraint satisfaction

  2018cites this paper
• Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints

  2018cites this paper
• Deciding the Consistency of Branching Time Interval Networks

  2018cites this paper
• Efficient Dynamic Methods for Qualitative Constraint-based Spatial and Temporal Reasoning (Position Paper)

  2018influential citation
• SSQUSAR : A Large-Scale Qualitative Spatial Reasoner Using Apache Spark SQL

  2017cites this paper
• A Model-Theoretic View on Qualitative Constraint Reasoning

  2017influential citation
• Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction

  2017cites this paper
• Collective Singleton-Based Consistency for Qualitative Constraint Networks

  2017cites this paper
• Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  2017influential citation
• A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks

  2017cites this paper
• An initial study of time complexity in infinite-domain constraint satisfaction

  2017influential citation
• Qualitative spatial and temporal representation and reasoning : efficiency in time and space

  2017cites this paper
• Qualitative Spatio-Temporal Stream Reasoning with Unobservable Intertemporal Spatial Relations Using Landmarks

  2016influential citation
• Answer Set Programming for Qualitative Spatio-Temporal Reasoning: Methods and Experiments

  2016cites this paper
• An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks

  2016cites this paper
• Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework

  2015cites this paper
• Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks

  2015cites this paper
• A Simple Decomposition Scheme for Large Real World Qualitative Constraint Networks

  2015cites this paper
• Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs

  2015cites this paper
• On the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  2015influential citation
• A Practical Approach for Maximizing Satisfiability in Qualitative Spatial and Temporal Constraint Networks

  2015influential citation
• Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning

  2014influential citation
• Spatio-Temporal Stream Reasoning with Incomplete Spatial Information

  2014cites this paper
• Triangulation Versus Graph Partitioning for Tackling Large Real World Qualitative Spatial Networks

  2014influential citation
• A Path-Consistency based Algorithm for Anomaly Detection of Spatial Constraints in GeoXACML Policies

  2014cites this paper
• A Reasoner for the RCC-5 and RCC-8 Calculi Extended with Constants

  2014influential citation
• A Concise Horn Theory for RCC8

  2014cites this paper
• Vertex Incremental Path Consistency for Qualitative Constraint Networks

  2014influential citation
• Incrementally Building Partially Path Consistent Qualitative Constraint Networks

  2014cites this paper
• Artificial Intelligence: Methodology, Systems, and Applications

  2014influential citation
• Qualitative Spatio-Temporal Representation and Reasoning : Trends and Future Directions

  2013cites this paper
• Twenty Years of Topological Logic

  2013cites this paper
• Qualitative Spatio-Temporal Representation and Reasoning for robotic applications

  2013cites this paper
• Querying Incomplete Geospatial Information in RDF

  2013cites this paper
• Decomposition and tractability in qualitative spatial and temporal reasoning

  2013cites this paper
• Ontologies for the VO for TerraSAR-X data

  2012cites this paper
• Data Models and Query Languages for Linked Geospatial Data

  2012cites this paper
• Nogoods in Qualitative Constraint-Based Reasoning

  2012cites this paper
• Constraints to the implementation of a market development approach to the delivery of business Development Services within the Makana municipal area

  2012cites this paper
• Knowledge representation and reasoning for qualitative spatial change

  2012cites this paper
• An implementation of a temporal and spatial extension of RDF and SPARQL on top of MonetDB - phase I

  2012cites this paper
• Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions

  2012cites this paper
• Consistency of Chordal RCC-8 Networks

  2012influential citation
• Mereotopology and Beyond

  2012cites this paper
• Region-Based Theories of Space: Mereotopology and Beyond

  2012cites this paper
• Extending the Stream Reasoning in DyKnow with Spatial Reasoning in RCC-8

  2012cites this paper
• Solving non-linear arithmetic constraints in soft realtime environments

  2012cites this paper
• Topological Logics with Connectedness over Euclidean Spaces

  2011cites this paper
• CHOROS: A Reasoning and Query Engine for Qualitative Spatial Information

  2011cites this paper
• Combining Spatial and Temporal Logics: Expressiveness vs. Complexity

  2011cites this paper
• TELEIOS FP 7-257662 Deliverable D 2 . 3 Theoretical results on query processing for RDF / SPARQL with time and space

  2011cites this paper
• AI Approaches to Cognitive Systems – The Example of Spatial Cognition

  2011cites this paper
• On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

  2011cites this paper
• Qualitative reasoning with directional relations

  2010cites this paper
• A modal logic framework for reasoning about comparative distances and topology

  2010cites this paper
• Etude de systèmes de contraintes pour le raisonnement qualitatif temporel et spatial

  2010cites this paper
• Spatial reasoning in a fuzzy region connection calculus

  2009cites this paper
• Supporting Frameworks for the Geospatial Semantic Web

  2009cites this paper
• Confirming the QSR Promise

  2009influential citation
• A critical analysis of current approaches to SMME development and support within the Ethekwini Municipal area

  2009influential citation
• A Continuation Method for Nash Equilibria in Structured Games

  2009influential citation
• Modelling and solving temporal reasoning as propositional satisfiability

  2008cites this paper
• A Literature Review on Artificial Intelligence

  2008cites this paper
• Dynamical Spatial Systems - A Potential Approach for the Application of Qualitative Spatial Calculi

  2008cites this paper
• Fast Qualitative Reasoning about Actions for Computing Anticipatory Systems

  2008cites this paper
• A Representation Scheme for Description and Reconstruction of Object Configurations Based on Qualitative Relations

  2008cites this paper
• Automated Complexity Proofs for Qualitative Spatial and Temporal Calculi

  2008cites this paper
• Principles of Knowledge Representation and Reasoning

  2008cites this paper
• Spatial Description Logic and Its Application in Geospatial Semantic Web

  2008cites this paper
• GQR – A Fast Reasoner for Binary Qualitative Constraint Calculi

  2008influential citation
• Eligible and Frozen Constraints for Solving Temporal Qualitative Constraint Networks

  2007cites this paper
• Qualitative Representation and Reasoning

  2007cites this paper
• Qualitative Spatial Reasoning Using Constraint Calculi

  2007cites this paper
• Customizing Qualitative Spatial and Temporal Calculi

  2007cites this paper
• Chapter 14 MATHEMATICAL MORPHOLOGY

  2007cites this paper
• Éligibilité de contraintes pour la résolution de réseaux de contraintes qualitatives temporelles et spatiales

  2007cites this paper
• Qualitative Spatial and Temporal Reasoning: Efficient Algorithms for Everyone

  2007cites this paper