On Redundant Topological Constraints (Extended Abstract)

1 Introduction

Qualitative spatial reasoning (QSR) is a common subfield of artificial intelligence and geographical information science, and has applications in GIS, cognitive robotics, high-level understanding of video data etc. The region connection calculus (RCC) [Randell et al., 1992] is perhaps the most wellknown calculus for representing qualitative spatial information. Based on a binary connectedness relation, it defines a class of binary topological relations between regions in a connected topological space (e.g., the real plane). The RCC is an expressive formalism for representing topological information, and the computational complexity of reasoning with RCC has been investigated in depth in the literature. Most of these works focus on the consistency or satisfiablility of RCC constraint networks.

In this paper, we consider the important problem of redundant RCC constraints. Given a set Γ of RCC constraints, we say a constraint (xRy) in Γ is redundant if it can be entailed by the rest of Γ, i.e., removing (xRy) from Γ will not change the solution set of Γ. It is natural to ask when a network is redundant and how to get an irredundant subset without changing the solution set. We call a subset of Γ a prime subnetwork of Γ if it contains no redundant constraints but has the same solution set as Γ.

∗This is an extended abstract of the same titled article published in Artificial Intelligence, 225: 51-76 (2015).

We show that it is in general co-NP hard to determine if a constraint is redundant in a network of RCC constraints, but if Γ is over a tractable subclass, then a prime subnetwork can be found in O(n5 ) time. If in addition weak composition distributes over non-empty intersections of relations in S, then Γ has a unique prime subnetwork, which is obtained by removing all redundant constraints from Γ.

As in the case of propositional logic formulas [Liberatore, 2005], redundancy of RCC constraints "often leads to unnecessary computation, wasted storage, and may obscure the structure of the problem" [Belov et al., 2012]. Finding a prime subnetwork can be useful in at least the following aspects: a) computing and storing the relationships between spatial objects and hence saving space for storage and communication; b) facilitating comparison between different constraint networks; c) unveiling the essential graphical structure of a network; and d) adjusting geometrical objects to meet topological constraints [Wallgrün, 2012].

1.1 Motivational Example: Placename Footprints

To motivate our discussion, we focus briefly on one specific application to illustrate how the use of prime subnetworks can save space for storage. Figure 1 gives a small example of a set of spatial regions formed by the geographic "footprints" associated with placenames in the Southampton area of the UK. The footprints are derived from crowd-sourced data, formed from the convex hull of the sets of coordinate locations at which individuals used the placenames on social media. Using such data sets in natural language placename searches frequently requires queries over the topological relationships between footprints (e.g., "is Clarence Pier in Southampton?"). Computing such relationships on-the-fly requires computationally intensive and slow geometric operations; by contrast Web-search queries demand rapid responses.

One potential solution is to cache the topological relations between all footprints of interest. However, even the small example in Figure 1, the 84 footprints then require 84 ∗ 83/2 = 3486 stored relations. The moderate-sized footprint data set from which Figure 1 is adapted contains a total of 3443 footprints leads to a constraint network with 5, 925, 403 relations. It is easy to see that as crowd-sourced data sources continue to grow, the volumes of such data is set to explode. In the case of footprints, many of the relationships can be inferred, and computing the prime subnetwork can reduce the number of stored relationships to be approximately linear in the number of footprints. In the case of the Southampton constraint network, 1324 redundant relations lead to a prime subnetwork with only 2162 relations needing to be stored. For the full data set, 5, 604, 200 redundant relations lead to a prime subnetwork of just 321, 203 relations (in contrast to the full network of almost 6 million relations).

In Section 2 we recall the RCC constraint language and then discuss the redundancy and prime subnetwork problem in general in Section 3. We present our major results and an efficient algorithm in Section 4, and present the empirical evaluation in Section 5. The last section concludes the paper.

2 RCCConstraint Language

The RCC was introduced in [Randell et al., 1992]. Let U be the set of nonempty regular closed sets of R2 . We call each element in U a region. For two regions a, b, we say a is a part of b, written aPb, if a ⊆ b; say a is connected to b, written aCb, if a ∩ b ̸= ∅. Using C and P, we define

Write PP-1 , TPP-1 and N-1 for the converses of PP, TPP and NTPP, respectively. Then B5 = {DR, PO, EQ, PP, PP-1 }

are two jointly exhaustive and pairwise disjoint (JEPD) sets of relations, i.e., for any two regions a, b ∈ U, a, b is related by exactly one relation in Bl (l = 5, 8). Figure 2 illustrates these basic RCC5/8 relations. We call the Boolean algebra generated by relations in Bl the RCCl algebra, which consists all relations that are unions of the basic relations in Bl. For convenience, we denote a non-basic RCCl relation R as the subset of Bl it contains. For example, we write {DR,PO,PP} for the relation DR∪PO∪PP, and write ⋆5 and ⋆8 for the correponding universal relation in RCC5 and RCC8.

The composition of two basic RCC5/8 relations is not necessarily a relation in RCC5/8. For two RCC5/8 relations R and S, we call the smallest relation in RCC5/8 that contains R ◦ S the weak composition of R and S, written R ⋄ S [Düntsch et al., 2001; Li and Ying, 2003].

2.1 RCC5/8 Constraint Network

An RCC5/8 constraint has the form (xRy), where x, y are variables taking values from U, the set of regions, R is an RCC5/8 relation (not necessarily basic). Given a set Γ of RCC5/8 constraints over variables V = {v1, v2, ..., vn}, we say Γ is consistent or satisfiable if there is an assignment σ : V → U such that (σ(vi), σ(vj)) satisfies the constraint in Γ that relates vi to vj.

Without loss of generality, we assume Γ has the form {xiRijxj}ni,j=1 , where, for any 1 ≤ i, j ≤ n, there is a unique constraint Rij, and Rji = R-1 ij and Rii = EQ. In this sense, we call Γ a constraint network. Let Γ = {xiRijxj}ni,j=1 and Γ′ = {xiR′ij xj}ni,j=1 be two RCC5/8 constraint networks. We say Γ and Γ′ are equivalent if they have the same set of solutions; and say Γ refines Γ′ if Rij ⊆ R′ij for all (i, j). We say an RCC5/8 network Γ is a basic network if each constraint is either the universe relation or a basic relation; and say a basic network complete if there are no universal relations.

Suppose S is a subset of RCC5/8. We say an RCC5/8 network Γ = {viRijvj} is over S if Rij ∈ S for every pair of variables vi, vj. The consistency problem over S, written as CSP(S), is the decision problem of the consistency of an arbitrary constraint network over S. It is well known that the consistency problem over RCC5/8, i.e., CSP(RCC5/8), is NP-complete and RCC8 has three maximal tractable subclasses that contain all basic relations [Renz, 1999] and RCC5 has only one [Jonsson and Drakengren, 1997].

We say a network Γ = {viRijvj} path-consistent if for every 1 ≤ i, j, k ≤ n, we have Rij ⊆ Rik ⋄ Rkj. A cubic algorithm, henceforth called the path-consistency algorithm or PCA, has been devised to enforce path-consistency. For any RCC5/8 network Γ, the PCA either detects inconsistency of Γ or returns a path-consistent network, written Γp, which is equivalent to Γ and known as the algebraic closure or aclosure of Γ [Ligozat and Renz, 2004]. It is easy to see that in this case Γp also refines Γ, i.e., we have Sij ⊆ Rij for each constraint (xiSijxj) in Γp.

Proposition 1. Let S be a tractable subclass of RCC5/8 which contains all basic relations. An RCC5/8 network Γ over S is consistent if applying PCA to Γ does not result inconsistency.

This is particularly true for basic RCC5/8 networks.

2.2 Distributive Subalgebra

Write ̂ B5 for the closure of B5 under converse, intersection, and weak composition in RCC5. Then ̂ B5 contains the basic relations as well as

where ⋆5 = {DR,PO,PP,PP-1 ,EQ}. It is interesting to note that in ̂ B5 the weak composition operation is distributive over nonempty intersections in the following sense.

Lemma 2. Let R, S, T be three relations in ̂ B5. Suppose S ∩ T is nonempty. Then we have

In general, we have the following definition.

Definition 1. Let S be a subclass of RCC5/8. We say S is a subalgebra if S contains all basic relations, and is closed under converse, weak composition, and intersection. We say a subalgebra S is distributive if weak composition distributes over nonempty intersections of relations in S.

Clearly, every distributive subalgebra of RCCl contains ̂ Bl . The following lemma shows that relations in a distributive subalgebra have the Helly property.

Lemma 3. Let S be a distributive subalgebra of RCC5/8. Suppose R, S, T are three relations in S. Then R∩S∩T = ∅ iff R ∩ S = ∅, or R ∩ T = ∅, or S ∩ T = ∅.

Actually, the inverse of the above result is also true (see [Long and Li, 2015]). We say a distributive subalgebra S is maximal if there is no other distributive subalgebra that properly contains S. To find all maximal distributive subalgebras, we start with ̂ Bl and then try to add other relations to this subalgebra to get larger distributive subalgebras. It turns out that RCC5 (RCC8, resp.) has only two maximal distributive subalgebras, which are all contained in H5, the maximal tractable subclass of RCC5 identified in [Renz and Nebel, 1997; Jonsson and Drakengren, 1997] ( ̂H8, one of the three maximal subclasses of RCC8 identified in [Renz, 1999], resp.).

3 Prime Subnetwork

Given an RCC5/8 network Γ, a very interesting question is, how to find a prime subnetwork of Γ? This problem is clearly at least as hard as determining if Γ has a redundant constraint. Similar to the case of propositional logic formulars [Liberatore, 2005], we have the following result for RCC5/8.

Proposition 4. Let Γ be an RCC5/8 network and suppose (xRy) is a constraint in Γ. It is co-NP-complete to decide if (xRy) is redundant in Γ.

A naive method to obtain a prime subnetwork is to remove redundant constraints one by one from Γ until we get an irreducible network. Suppose we have an oracle which can tell if a constraint is redundant. Then in an additional O(n2 ) time we can find an irreducible network that is equivalent to Γ by removing several constraints from Γ.

Suppose S is a tractable subalgebra of RCC5/8. Then, for any network Γ over S, we can determine whether a constraint is redundant in Γ in O(n3 ) time and find all redundant constraints of Γ in O(n5 ) time. A prime subnetwork for Γ can also be found in O(n5 ) time.

Are prime subnetworks unique? In general this is not the case, but it is easy to see that the core of Γ, i.e. the set of non-redundant constraints in Γ, is contained in every prime subnetwork of Γ. In the following we assume that Γ is an alldifferent constraint network, i.e. it has the following property:

This property ensures that no two variables have to be identical. In other words, there is no 'redundant' variables.

We next show that, if Γ is an all-different constraint network over a distributive subalgebra of RCC5/8, then Γc is the unique prime network of Γ. This is quite surprising, as, in general, knowing that both (xRy) and (uSv) are redundant in Γ does not imply that (uSv) is redundant in Γ \ {(xRy)}.

4 Networks over a Distributive Subalgebra

In this section, we assume S is a distributive subalgebra of RCC5/8. Let Γ be an all-different consistent network over S. We show that Γc is equivalent to Γ and hence the unique prime network of Γ.

Definition 2 (cf. [Chandra and Pujari, 2005; Liu and Li, 2012]). Suppose Θ = {viTijvj}ni,j=1 is an RCC5/8 network. We say Θ is minimal if for every pair of variables vi, vj (i ̸= j) and every basic relation α in Tij, there exists a solution {a1, a2, · · · , an} of Θ s.t. (ai, aj) is an instance of α.

Each consistent RCC5/8 constraint network has a unique minimal network, but it is in general NP-hard to compute it (see e.g. [Liu and Li, 2012]).

Notation: We write Γm for the minimal network of Γ, Γp for the a-closure of Γ, and Γc for the core of Γ.

To prove that Γc is equivalent to Γ, we need two important results. The first result, stated in Thm. 5, shows that Γm is exactly Γp. The second result, stated in Prop. 6, shows that a particular constraint (xRy) is redundant in Γ iff its corresponding constraint in Γp is redundant. Our main result, stated in Thm. 7, then follows immediately.

Theorem 5. Suppose Γ is a consistent network over S and Γp its a-closure. Then Γp is Γm, the minimal network of Γ.

Proposition 6. Suppose Γ is a consistent network over S which satisfies (3). Assume that (xRy) and (xSy) are the constraints from x to y in Γ and Γp respectively. Then (xRy) is redundant in Γ iff (xSy) is redundant in Γp.

Recall that Thm. 5 asserts that Γp is minimal. As a consequence, we have our main result.

Theorem 7. Suppose Γ is a consistent network over S which satisfies (3) and Γc the core of Γ. Then Γc is equivalent to Γ and hence the unique prime network of Γ.

In general, the core of an RCC5/8 network over a tractable subclass can be found in O(n5 ) time. This can be improved for networks over a distributive subalgebra. To show this, we need the following result for path-consistent networks.

Lemma 8. Suppose Γ is a path-consistent network over S. Then a constraint (viRijvj) is redundant in Γ iff

i.e., Rij is the intersection of the weak compositions of all paths from vi to vj with length 2.

Algorithm 1: Algorithm for finding all redundant constraints, where ⋆l is the universal relation in RCCl.

Input: An all-different consistent RCC5/8 network Γ = {viRijvj : 1 ≤ i, j ≤ n} over S and

V = {vi : 1 ≤ i ≤ n}. Output: Redun: the set of redundant constraints of Γ, and Core: the core of Γ. 1 Redun←∅ 2 Core ←Γ 3 Γp ← the a-closure of Γ 4 for each constraint (viSijvj) ∈ Γp do 5 Qij ← ⋆l 6 for each variable vk ∈ V \ {vi, vj} do 7 Qij ← Qij ∩ Sik ⋄ Skj 8 if Qij = Sij then 9 Redun ← Redun ∪ {(viRij vj )} 10 Core ← Core \ {(viRij vj )} 11 break the inner loop;

Suppose Γ is an all-different consistent network over a distributive subalgebra of RCC5/8. Prop. 6 and Lemma 8 suggest a simple way for computing Γc, the unique prime network of Γ. By Prop. 6, a constraint (viRijvj) in Γ is redundant iff the corresponding constraint (viSijvj) in Γp is redundant. Furthermore, Lemma 8 shows that (viSijvj) is redundant in Γp iff Sij is the intersection of all Sik ⋄ Skj (k ̸= i, j). We hereby have the cubic algorithm Algorithm 1 for finding all redundant constraints in Γ. For each constraint (viSijvj), to verify if Sij = ⋂{Sik ⋄ Skj : k ̸= i, j}, we introduce a relation Pij which consists of all basic relations α that are not in Sik ⋄ Skj for some k ̸= i, j and then check if Pij ∪Sij is the universal relation.

5 Empirical evaluation

In this section, we empirically evaluate our method in comparison with the two greedy methods for removing redundant constraints proposed in [Wallgrün, 2012]: the basic and extended simplification algorithms (hereafter SIMPLE and SIMPLEX). SIMPLE loops through all triples of regions i, j, and k and identifies as redundant any constraints Rik such that Rij ⋄ Rjk ⊆ Rik. A drawback of SIMPLE is that redundant relations removed may affect subsequent iterations of the algorithm. Hence, the order in which triples are visited by SIMPLE can alter the resulting subnetwork. SIMPLEX solves this issue by first marking potentially redundant relations for removal, subject to a consistency check, before removing all marked relations in a final loop. SIMPLE and SIMPLEX are not guaranteed to provide a prime subnetwork.

In the evaluation, two real data sets were used: the UK geographic "footprint" dataset introduced in Section 1.1 (total 3443 regions) and the statistical areas levels 1-4 dataset for Tasmania (in total 1559 regions), provided by the Australian Bureau of Statistics. Both datasets are complete basic constraint networks, i.e., there is a single basic relation between each pair of regions. Derived from social media, the footprint data set contains a variety of regions of differing sizes and shapes, but relatively unstructured sharing almost no adjacent boundaries. In stark contrast the Tasmanian statistical areas are highly structured, made up of four levels of spatially contiguous and nested but non-overlapping regions. To aid in our analysis, five subsets of each of the two datasets were generated in addition to the full datasets.

Our empirical analysis showed that for real geographic data sets the prime subnetwork can lead to significant increases in the number of redundant relations identified when compared with the approximations proposed by [Wallgrün, 2012]. In practice, the algorithm was efficient, exhibiting average case O(n2 ) scalability. The redundant relations identified by the prime subnetwork can also significantly outnumber DC relations, especially in less structured geographic data sets that may contain a significant minority of PO relations.

6 Conclusion and Further Development

In this paper, we have systematically investigated the computational complexity of redundancy checking for RCC5/8 constraints. Although it is in general intractable, we have shown that, if the constraints are taken from a distributive subalgebra, then the core of the constraint network is the unique prime network and can be found in cubic time.

Algorithm 1 can be significantly improved if we enforce partial path-consistency [Bliek and Sam-Haroud, 1999] instead of path-consistency. Indeed, it is showed in [Sioutis et al., 2015] that the thus revised redundancy removing algorithm significantly progresses the state-of-the-art for practical reasoning with very large real RCC8 networks.

Some of our results (e.g., all results before Thm. 5) can be immediately applied to several other qualitative calculi e.g. Interval Algebra [Allen, 1983], but Prop. 6 and Thm. 7 do use the particular algebraic properties of RCC5/8. However, the same results actually apply to the simple temporal problem (STP) [Dechter et al., 1991]. In [Lee et al., 2016], it was shown that every non-degenerated STP instance has a unique prime subnetwork and evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.