Search

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.

We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network N, our algorithm utilizes a particular directional local consistency, which we denote by (sic)-consistency, in order to efficiently decide the satisfiability of N. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing (sic)-consistency in a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability, and obtain similar useful results for the problems of minimal labelling and redundancy. Further, we present a generic method that allows extracting a scenario from a satisfiable network, i.e., an atomic satisfiable subnetwork of that network, in a very simple and effective manner. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus and the Interval Algebra, shows that our approach exhibits unparalleled performance against state-of-the-art approaches for checking the satisfiability of such constraint networks., Funding Agency:MoveCare project - European Commission 732158

Qualitative Spatial and Temporal Reasoning (QSTR) provides a human-friendly abstract way to describe and to interpret spatial and temporal information. To describe the qualitative information, QSTR makes use of qualitative relations between entities and usually stores them in a qualitative constraint network (QCN). The QCNs are then used as the basis to process qualitative spatial and temporal information, including qualitative reasoning and query answering. Time efficiency of reasoning techniques in QSTR is critical for applications to deal with qualitative spatial and temporal information in large-scale datasets. In this thesis, we present a special family of tractable subclasses of relations, called distributive subalgebras. We show that several efficient algorithms are applicable to the QCNs over distributive subalgebras for solving important reasoning problems. We also identify maximal distributive subalgebras for popular relation models in QSTR and point out their connections with several previously identified important subclasses. Regarding the network representation in QSTR, there are two important problems, which in turn affect the time efficiency of other applications. First, the network representation can have redundant relations, which will significantly increase the efforts needed for tasks whose efficiency is strongly related to the number of relations in a network. Fortunately, for any QCN over distributive subalgebras of qualitative calculi PA, RCC5, and RCC8, we show that essentially it has a unique subset consisting of non-redundant relations, which expresses the same qualitative information as the original QCN. We also devise an efficient algorithm to construct such subsets. Second, the network representation sometimes requires a large storage space when encoding large-scale data. This could severely limit the ability of relation retrieval for any two given spatial entities. In fact, when the size of a QCN becomes large, it might be too costly or