Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks

1 Introduction

One of the major concerns in AI is dealing with spatiotemporal information, which is involved in many AI applications, such as automatic data maintenance and visualization in Geographic Information Systems (e.g., [Wallgr¨un, 2012]), robotic navigation (e.g., [Wolter, 2008]), and computer-aided design (e.g., [Bhatt et al., 2009]). Qualitative Spatial and Temporal Reasoning (QSTR) is devoted to processing such kind of information correctly and efficiently. In particular, the techniques in QSTR focus on finding ways to efficiently solve several fundamental reasoning problems, such as the consistency problem, the minimal labelling problem, and the redundancy problem. The consistency problem asks if a constraint network has a solution. The minimal labelling problem requests the strongest implied relations in a constraint network, i.e., the implied relations comprising only tuples that participate in a solution of the network. The redundancy problem [Li et al., 2015] is a newly studied problem in QSTR that aims to simplify the representation of a constraint network by removing its redundant constraints, i.e., the constraints that

⇤Corresponding author.

Sanjiang Li

UTS-AMSS Joint Lab QCIS, FEIT University of Technology Sydney Australia Sanjiang.Li@uts.edu.au

can be entailed by the rest of the network. We refer to [Cohn and Renz, 2008] for more information regarding fundamental reasoning problems in QSTR.

Path consistency (PC) is an important local consistency condition for constraint networks. Given a constraint network N, PC can be established in N by applying the path consistency algorithm (PC) 1 in [Montanari, 1974; van Beek, 1989], which makes all pairs of variables path consistent with any third variable in N by considering the completion of the underlying constraint graph of N. It has long been known that PC can decide the consistency of maximal tractable subalgebras of several very important qualitative spatial and temporal calculi. Recently, PC became more useful as it was shown to be able to solve the minimal labelling problem and decisively assist in solving the redundancy problem of any distributive subalgebra of several well-known calculi. A subalgebra is called distributive if (weak) composition distributes over nonempty intersections of its relations. The concept of distributive subalgebras was recently proposed in [Li et al., 2015] and further discussed in [Long and Li, 2015]; some previous related work identified certain subalgebras to be distributive as well (cf. [van Beek and Cohen, 1990]).

With the expansion of the internet, the age of Big Data has arrived. Without emphasis on scalability, the current techniques in QSTR have become less suitable to deal with the situation where tens of thousands or even millions of spatiotemporal objects are involved. For example, PC has a time complexity of O(n3 ), which already makes it hardly scalable for large real-world datasets with even less than a few thousands of variables. In the past few years, research in QSTR has focused on trying to deal with this situation. In particular, Chmeiss and Condotta [2011] and Sioutis and Koubarakis [2012] adopted the partial path consistency algorithm (PPC) [Bliek and Sam-Haroud, 1999], as a substitute for the original path consistency algorithm PC, for some fundamental reasoning tasks of certain qualitative spatial and temporal calculi. Given a constraint network N, PPC enforces partial path consistency (PPC) on N, which is PC restricted to a triangulation of the underlying constraint graph of N . As such, PPC can exploit the sparseness of a constraint graph, in contrast to PC, and therefore be more efficient than PC, especially when dealing with large and sparsely structured qualitative constraint networks. Note that when the result of a triangulation for a given constraint network N is a complete graph, PPC will enforce PC on N. Further, it was shown by Sioutis et al. [2015b] and Long and Li [2015] that PPC can have the same reasoning power as PC on the common edges between a triangulation and the completion of the underlying constraint graph of N. In particular, if N is defined over some distributive subalgebra, the relations on these edges will be minimal after enforcing PPC w.r.t. a triangulation on N , as would be the case with PC. This kind of hybrid restrictions on both the structure of the constraint graph and the allowed relations have also been discussed in the context of constraint satisfaction problems to identify tractable subclasses (see [Cohen et al., 2012]). PPC can also be helpful to efficiently identify the same set of non-redundant constraints in N as PC, by only considering the relations on these edges.

1 In what follows, we use bold sans serif font to denote an algorithm name (e.g., the PC enforcing algorithm is denoted by PC).

In addition, there is a parallel research stream in the field of the Simple Temporal Problem (STP). Xu and Choueiry [2003] realized that the STP has convexity properties analogous to those of convex CSPs and, thus, implemented a particular PPC enforcing algorithm for the STP, much like PPC, which was originally implemented for convex CSPs [Bliek and Sam-Haroud, 1999]. Later, Planken et al. [2008] noticed that the algorithm of Xu and Choueiry is not very efficient, as it is sometimes quadratic in the number of triangles in a triangulation of the underlying constraint graph of a given STP instance, which is also the case with PPC for CSPs and qualitative constraint networks. Therefore, based on an algorithm developed by Dechter et al. [1991], viz., the directional path consistency algorithm (DPC), Planken et al. proposed a new PPC enforcing algorithm, called P 3 C, which has a worst-case time complexity that is linear in the aforementioned number of triangles.

It is then natural to ask if there is a similar algorithm to P 3 C for qualitative spatial and temporal calculi, as it would be quite useful for solving the associated reasoning tasks more efficiently, especially when large and sparsely structured qualitative constraint networks were involved. Our contributions with respect to answering that question are as follows. We develop a similar algorithm to P 3 C, called DPC+, and prove that it can correctly enforce PPC on a qualitative constraint network that is defined over some distributive subalgebra. DPC+ can achieve PPC (and PC when a complete graph is used as the result of a triangulation) by processing each triangle in a triangulation of the underlying constraint graph of a given qualitative constraint network no more than three times. As PPC (and PC) in general process each such triangle many more times than that, we show that DPC+ is more efficient than PPC (and PC) in theory. Our experimental results with both real-world and synthetic datasets also confirm in practice that DPC+ can be significantly more efficient than PPC (and PC).

The remainder of the paper is organized as follows. After introducing some related concepts and results in Sections 2 and 3 respectively, we present and analyse our new algorithm for achieving PPC in Section 4, and experimentally illustrate its efficiency in Section 5. Section 6 concludes the paper.

2 Preliminaries

A binary relation is a set of ordered pairs of entities. Suppose U is a domain of spatial or temporal entities. We write Rel(U) for the Boolean algebra of binary relations on U. A qualitative calculus [Ligozat and Renz, 2004] M on U is defined as a finite Boolean subalgebra of Rel(U) that has an atom corresponding to the identity relation idU on U, and that is closed under converse, i.e., R is inMiff its converse

is inM. The basic relations in a qualitative calculus M are the atoms in M, which form a partition of U ⇥ U. In what follows, we denote the set of basic relations by B. A relation R inM is a subset of B, i.e., an element of 2B . Specifically, the set of all basic relations in M is the universal relation, denoted by ?. For example, PA has the basic relations <, >, and =, and the universal relation ? in PA is ¶<↪ >↪ =♦.

In this paper, we are interested in the six well-known qualitative calculi of Point Algebra (PA) [Vilain and Kautz, 1986], Interval Algebra (IA) [Allen, 1983], Cardinal Relation Algebra (CRA) [Frank, 1991; Ligozat, 1998], Block Algebra (BA) [Balbiani et al., 2002], and two instances of the Region Connection Calculus (RCC5/8) [Randell et al., 1992].

Let ◦ denote the usual composition of relations, i.e., R ◦ S = ¶(x↪ y) : 9z s.t. (x↪ z) 2 R ^ (z↪ y) 2 S♦. The weak composition of two basic relations ↵ and β, denoted by ↵ ⇧ β, is defined as ¶γ 2 B : γ \ (↵ ◦ β) 6= ?♦. When the relations are not basic, we have R ⇧ S = S¶↵ ⇧ β : ↵ 2 R↪ β 2 S♦.

A constraint (xRy) associates a relation Rij 2 2B with the pair of variables (x↪ y). For example, for two time point variables t1 and t2, t1 < t2 suggests that any assignment to t1 and t2 respectively should satisfy relation <.

Definition 1. A qualitative constraint network (QCN) over a qualitative calculus M is a tuple (V↪ C), where V = ¶v1↪ ▷ ▷ ▷ ↪ vn♦ is a non-empty finite set of variables and C is a set of constraints for each pair (vi↪ vj) of V ⇥ V .

In this paper, we require that the relations between variables in a QCN are symmetric, i.e., Rij = R-1 ji , and Rii = idU for all vi↪ vj 2 V . A subnetwork N 0 = (V 0 ↪ C 0 ) of N = (V↪ C) is a network such that V 0 = V and 8vi↪ vj 2 V we have R0ij ✓ Rij, where R0ij is a relation in C 0 and Rij a relation in C.

In graph theory, there is a special family of undirected graphs, called the triangulated or chordal graphs. An undirected graph G = (V↪E) is chordal if every cycle of length greater than 3 has a chord, i.e., an edge connecting two nonconsecutive vertices of the cycle [Blair and Peyton, 1993]. Note that a complete graph of any order is also a chordal graph. For each v 2 V , the adjacency set adj(v) is defined as ¶w 2 V : ¶v↪w♦ 2 E♦. A vertex v is simplicial if adj(v) induces a complete graph. Every chordal graph has a simplicial vertex. Moreover, after removing a simplicial vertex and its incident edges from a chordal graph, the resulting subgraph

The (underlying) constraint graph of a QCN N, denoted by GN, is a graph that has the variables of N as its set of vertices, and a set of edges, denoted by E(GN ), that contains an edge ¶vi↪ vj♦ iff Rij 6= ? and vi 6= vj .

remains chordal. The order in which simplicial vertices of sequential subgraphs are successively removed is called a perfect elimination ordering. Suppose that (vn↪ vn-1↪ ▷ ▷ ▷ ↪ v1) is a perfect elimination ordering of G, then we will denote by Fk the set ¶vj : ¶vj↪ vk♦ 2 E ^ j < k♦. Note that the subgraph induced by Fk is a complete subgraph of G.

Let M be a qualitative calculus. A subalgebra S of M contains all basic relations and a subset of non-basic relations in M, and is closed under converse, weak composition, and intersection. The concept of a distributive subalgebra, first proposed in [Li et al., 2015] and further discussed in [Long and Li, 2015], turns out to be useful for developing efficient algorithms to accomplish reasoning tasks such as deciding the consistency or solving the minimal labelling problem of a given qualitative constraint network.

Definition 2. A subalgebra S of M is distributive if R⇧ (S \ T ) = (R ⇧ S) \ (R ⇧ T ) and (S \ T ) ⇧ R = (S ⇧ R) \ (T ⇧ R) for any R↪ S↪ T 2 S with S \ T 6= ?.

Throughout the paper, we consider the calculi of PA, IA, RCC5/8, CRA, and BA, and the term "distributive subalgebra" specifically refers to a distributive subalgebra of one of these calculi. WhenM is one of these calculi, it satisfies the following property [Dylla et al., 2013; D¨untsch, 2005].

The Peircean Law (also known as the Cycle Law) [Dylla et al., 2013; Long and Li, 2015] holds for relation algebras.

Fact 1. For relations R↪ S↪ T of a relation algebra, the Peircean Law requires that

Distributive subalgebras also have a useful property that is closely related to the well-known Helly's Theorem [Danzer et al., 1963].

Definition 3. A subclass S of a qualitative calculus is called Helly if, for any finite n relations R1↪ ▷ ▷ ▷ ↪ Rn 2 S, we have

Theorem 2 ([Long and Li, 2015]). Suppose M is a qualitative calculus that is also a relation algebra. Let S be a subalgebra of M. Then S is distributive iff it is Helly.

With this property, to check if a set of relations have a nonempty intersection, one only needs to check if the intersection of each pair of relations from that set is non-empty.

3 Properties of PC and PPC

Path consistency is an important local consistency condition for several reasoning problems of CSPs. In the context of qualitative spatial and temporal calculi, the usual composition is replaced with weak composition. We have the following definition of path consistency regarding QCNs:

Definition 4. A QCN N = (V↪ C) is path consistent (PC) iff 8vi↪ vk↪ vj 2 V we have that Rij ✓ Rik ⇧ Rkj .

Path consistency concerns all triples of variables. This could be an overkill for many reasoning tasks. The idea of enforcing path consistency on a triangulation of the constraint graph of a given CSP was first proposed by Bliek and SamHaroud [1999] through the partial path consistency algorithm (PPC). Later, Chmeiss and Condotta [2011] and Sioutis and Koubarakis [2012] adopted PPC for IA and RCC8 respectively, and Amaneddine et al. [2013] and Long and Li [2015] further extended this idea to all of the calculi discussed here.

Definition 5. A QCN N = (V↪ C) is partially path consistent (PPC) w.r.t. a graph G = (V↪E) iff 8¶vi↪ vj♦, ¶vi↪ vk♦, ¶vk↪ vj♦ 2 E we have that Rij ✓ Rik ⇧ Rkj .

Note that PPC is the same as PC when the graph G in the definition of PPC is complete. In this paper, every considered calculus also satisfies the following property:

Every atomic QCN overMthat is PC is satisfiable▷ (2)

For a calculus with Properties (1) and (2), PPC has the same reasoning power as PC on the common edges between a triangulation and the completion of the constraint graph of a qualitative constraint network that is defined over a distributive subalgebra, in the following sense.

Proposition 3 ([Sioutis et al., 2015b; Long and Li, 2015]). Let N = (V↪ C) be a QCN that is defined over a distributive subalgebra of a qualitative calculus that satisfies (1) and (2), and G = (V↪E) a chordal graph such that GN ✓ G. Then, enforcing PPC w.r.t. G on N decides the consistency of N, and results in the same labelling of the relations that correspond to the edges of G as enforcing PC.

We say that N is minimal if for each constraint (xRy) in N, R is the minimal (or strongest) relation between x and y that is entailed by N, where (xRy) is entailed by N if every solution of N satisfies (xRy).

Theorem 4 ([Long and Li, 2015; Li et al., 2015]). Let S be a distributive subalgebra of a qualitative calculus that satisfies (1) and (2). Then every path consistent QCN that is defined over S is minimal.

The last two results show that given a QCN that is defined over a distributive subalgebra, enforcing PPC on it is able to make the relations corresponding to the edges of a triangulation of its constraint graph become minimal.

PC and PPC are also useful with regard to the redundancy problem. A constraint (xRy) in a QCN N is redundant if N ∩ ¶(xRy)♦ entails (xRy).

Definition 6. A QCN = (V↪ C) is all-different if 8vi 6= vj 2 V , N does not entail (viidUvj).

The following result regarding the redundancy problem was first shown for RCC5/8, but applies to any of the calculi considered here (cf. [Sioutis et al., 2015b, Appendix]).

Theorem 5 ([Sioutis et al., 2015b]). Let N = (V↪ C) be a satisfiable all-different QCN that is defined over a distributive subalgebra satisfying (1) and (2), and G = (V↪ E) a chordal graph such that GN ✓ G. Then, if N is PPC w.r.t. G, a constraint (viRijvj) is non-redundant in the PC subnetwork of N if and only if we have that ¶vi↪ vj♦ 2 E and Rij 6= T¶Rik ⇧ Rkj : ¶vi↪ vk♦↪ ¶vk↪ vj♦ 2 E♦.

Algorithm 1: DPC(N ,↵)

Input: A QCN N = (V↪ C) with n variables, and an ordering ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) of V . Output: True or False, a graph G = (V↪ E), and an updated N . 1 G (V↪E E(GN)); 2 for vk from vn to v1 do 3 Fk ¶vs : ¶vs↪ vk♦ 2 E ^ s < k♦; 4 foreach vi↪ vj 2 Fk with i < j do 5 if ¶vi↪ vj♦ 62 E then 6 E E [ ¶¶vi↪ vj♦♦; 7 temp Rij \ (Rik ⇧ Rkj); 8 if temp ⇢Rij then 9 Rij temp; 10 Rji temp-1 ; 11 if Rij = ; then 12 return (False,G↪ N ); 13 return (True,G↪N);

Note that when G is a complete graph, this result falls back to the case where N is PC, as discussed in [Li et al., 2015].

Because of these observations, it is clear that PC and PPC are quite useful in solving various reasoning tasks. It is then reasonable and important to develop an algorithm that can achieve PC or PPC as efficiently as possible.

4 NewAlgorithm for PPC

In this section, we show how to enforce PC or PPC on a QCN that is defined over a distributive subalgebra in an efficient manner. Before introducing our algorithm, we first take a look at a weaker local consistency condition that is, nevertheless, sufficient to decide the consistency of such a QCN.

4.1 Directional Path Consistency

Directional path consistency is another important local consistency condition, which can be used for deciding the consistency of a QCN that is defined over a distributive subalgebra. It was first proposed in the context of the Simple Temporal Problem (STP; [Dechter et al., 1991]).

Definition 7. A QCN N = (V↪ C) is directionally path consistent (DPC) with respect to an ordering of its variables ↵ = (v1↪ ▷ ▷ ▷ ↪ vn) iff for all vi↪ vk↪ vj 2 V with i↪ j < k we have that Rij ✓ Rik ⇧ Rkj .

As noted, DPC is already sufficient to decide the consistency of a QCN that is defined over a distributive subalgebra.

Proposition 6 ([Sioutis et al., 2016]). Let N = (V↪ C) be a QCN that is defined over a distributive subalgebra of a qualitative calculus that satisfies (1) and (2). Then, if N is DPC with respect to an ordering of its variables and does not contain an empty relation, N is satisfiable.

DPC (Algorithm 1) achieves DPC by using the idea of variable elimination [Sioutis et al., 2016]. It iterates variables with respect to an ordering, and propagates the constrainedness of the constraints involving a variable vk, to the

Algorithm 2: DPC+(N ↪ ↵)

Input: A QCN N = (V↪ C) with n variables, and an ordering ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) of V . Output: True or False, a graph G = (V↪ E), and an updated N . 1 (result,G↪N) DPC(N,↵); 2 if result = False then 3 return (False,G↪ N ); 4 for vk from v1 to vn do 5 foreach vi s.t. i < k and ¶vi↪ vk♦ 2 E(G) do 6 Fk ¶vj : ¶vj↪ vk♦ 2 E(GN) ^ j < k♦; 7 Rik Tvj2Fk Rij ⇧ Rjk; 8 Rki R-1 ik ; 9 return (True,G↪N);

constraints involving only subsequent variables in the ordering, with the update rule Rij Rij \ (Rik ⇧ Rkj). This is as if the variable vk is "eliminated" from the QCN. As a by-product, DPC also triangulates the constraint graph of a QCN and produces a chordal graph G that has the ordering ↵ as a perfect elimination ordering.

Theorem 7 ([Sioutis et al., 2016]). Let N = (V↪ C) be a QCN that is defined over a distributive subalgebra of a qualitative calculus satisfying (1) and (2), and ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) an ordering of V . Then, DPC returns (True↪G↪N 0 ) if and only if N is satisfiable, where G is a chordal graph such that GN ✓ G and ↵ is a perfect elimination ordering of it, and N 0 is the DPC w.r.t. ↵ subnetwork of N.

4.2 The NewAlgorithmDPC+

Although enforcing DPC is efficient, it is not guaranteed to achieve PPC or PC and, thus, cannot solve the minimal labelling problem or assist in solving the redundancy problem of a given QCN. We hereby propose a new algorithm that achieves PPC (and PC with a simple modification) by building on the DPC enforcing algorithm DPC. Given a QCN N and an ordering ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) of its variables, we first enforce DPC w.r.t. ↵ on N using DPC. Then, we update relations by iterating the variables in reverse order. In particular, for a variable vk (k is from 1 to n), we consider the set Fk of variables that are adjacent to vk and preceded by vk in ↵. The relation between each vi 2 Fk and vk is updated with Tvj2Fk Rij ⇧ Rjk. The detailed steps are shown in Algorithm 2. We call this new algorithm DPC+.

The following theorem shows that DPC+ establishes PPC in a satisfiable QCN that is defined over a distributive subalgebra. Note that if we replace the graph G in line 1 with the complete graph of the same order, DPC+ will achieve PC.

Theorem 8. Let N = (V↪ C) be a QCN that is defined over a distributive subalgebra of a qualitative calculus that satisfies (1) and (2), and ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) an ordering of V . Then, DPC+ returns (True↪G↪N 0 ) if and only if N is satisfiable, where G is a chordal graph such that GN ✓ G and ↵ is a perfect elimination ordering of it, and N 0 is the PPC w.r.t. G subnetwork of N .

Proof. After calling DPC in line 1, N becomes DPC w.r.t. ↵ and we get a chordal graph G such that GN ✓ G and ↵ is a perfect elimination ordering of it. In what follows, we denote by N (0) the DPC network before applying the next steps of DPC+ and by N the updated network obtained afterwards.

To simplify our proof, we first adjust the updating rule in line 7 of DPC+ from Rik Tvj2Fk Rij ⇧ Rjk to Rik Tvj2Fk Rij ⇧ R(0) jk , whereR(0) jk is the relation between vj and vk in the original DPC network, viz., N (0) . We denote the adjusted algorithm by DPC+⇤ . We will first prove that the conclusion holds for DPC+⇤ .

Suppose that Nk is the partial network of the updated N restricted to variables ¶vk↪ vk-1↪ ▷ ▷ ▷ ↪ v1♦, i.e., the updated partial network after considering ¶vk↪ vk-1↪ ▷ ▷ ▷ ↪ v1♦ in the for loop in line 4 of DPC+. Note that Nn = N. It suffices to show that Nk is PPC given that Nk-1 is PPC. To this end, we only need to consider Fk and show that 8vi↪ vj 2 Fk, we have Rik 6= ;, Rij ✓ Rik ⇧ Rkj , and Rik ✓ Rij ⇧ Rjk.

We first show that Rik 6= ; for all vi 2 Fk. Note that 8vj↪ vj 0 2 Fk, by DPC of N (0) , we have Rjj 0 ✓ R(0) jj 0 ✓ R(0) jk ⇧ R(0) kj 0 . By DPC of Nk-1, we have Rjj 0 ✓ Rji ⇧ Rij 0 . Therefore, ; 6= Rjj 0 ✓ R(0) jk ⇧ R(0) kj 0 \ Rji ⇧ Rij 0 . By the Peircean Law, we have (Rij ⇧ R(0) jk ) \ (Rij 0 ⇧ R(0) j 0 k ) 6= ;. According to the Helly property of distributive subalgebras, we have Rik = Tvj2Fk Rij ⇧ R(0) jk 6= ;.

Next, we show that Rij ✓ Rik ⇧ Rkj . Note that as Rjk = Tvj002Fk Rjj 00 ⇧ R(0) j 00 k , we have

By distribution of weak composition, we have

As N (0) is DPC, we have Rj 0 j 00 ✓ R(0) j 0 j 00 ✓ R(0) j 0 k ⇧ R(0) kj 00 , and as Nk-1 is PPC, we have Rij ✓ Rij 0 ⇧ Rj 0 j 00 ⇧ Rj 00 j. Therefore Rij ✓ Rij 0 ⇧ R(0) j 0 k ⇧ R(0) kj 00 ⇧ Rj 00 j, 8vj 0 ↪ vj 00 2 Fk, and hence Rij ✓ Rik ⇧ Rkj .

Next, we show that Rik ✓ Rij ⇧ Rjk. In fact,

Since vj is arbitrary in Fk and Rj 0 k ✓ R(0) j 0 k , we also have

Therefore, under the updating rule of DPC+⇤ , we have that Nk is PPC if Nk-1 is PPC and, thus, DPC+⇤ enforces PPC on N. Regarding DPC+, its updating rule will update the first Rik by using relations in Nk-1 and N (0) , and then update the following Ri0 k by using the updated Rik, and so on. By induction, we can prove that each updated Rik is stronger than R(0) ik and weaker than Tvj02Fk Rij 0 ⇧ R⇤ j 0 k , where R⇤ j 0 k is obtained by DPC+⇤ . By (3), the relations obtained by DPC+ are the same as those obtained by DPC+⇤ . As DPC+⇤ enforces PPC on N, we have that DPC+ also enforces PPC on N .

4.3 Analysis of the DPC+Algorithm

As an adaptation of the P 3 C algorithm in [Planken et al., 2008] to qualitative spatial and temporal calculi, the DPC+ algorithm only needs to update each triangle in a graph at most three times. This means that the time complexity of DPC+ is linear in the number of triangles t in the graph, if we assume that t dominates the number of vertices and edges.

Theorem 9. Let N = (V↪ C) be a QCN, and ↵ = (vn↪ ▷ ▷ ▷ ↪ v1) an ordering of V . Then, DPC+ returns (True↪ G↪ N 0 ) in ⇥(t+♣V ♣+♣E♣) time when N is satisfiable, where G = (V↪E) is a chordal graph such that GN ✓ G, and t is the number of triangles in G.

Proof. The DPC algorithm considers each triangle in G exactly once. For each ¶vi↪ vk♦ 2 E such that i < k, lines 6-8 in DPC+ will consider all the triangles involving vi and vk once. Therefore, each triangle ¶vi↪ vj↪ vk♦ such that i↪ j < k and ¶vi↪ vk♦↪ ¶vj↪ vk♦ 2 E will be considered at most twice and, as such, by iterating vk from v1 to vn, every triangle in the graph will be considered at most twice. Note that as DPC+ needs to scan through the vertices and edges, DPC+ runs in ⇥(t + ♣V ♣ + ♣E♣) time when N is satisfiable.

In terms of the maximum vertex degree ∆ of G, with the above analysis, it is easy to see that DPC+ has a time complexity of O(n∆2 ), where n is the number of variables.

While DPC+ only needs to check each triangle in a graph at most three times, the state-of-the-art PPC enforcing algorithm PPC usually requires to check each such triangle many more times than that (e.g., as many times as 3♣B♣). This is also the case with the PC enforcing algorithm PC, since when a complete graph is used as the result of a triangulation, PPC falls back to PC. Therefore, we expect DPC+ to be more efficient than PPC and PC. Indeed, as shown in the following section, for large and sparsely structured networks, the advantage of DPC+ over PPC (and PC) is very significant.

5 Experimental Results

We evaluate the performance of our implementation of the DPC+ algorithm, against an implementation of the state-ofthe-art PPC enforcing algorithm (PPC), for QCNs that are defined over a distributive subalgebra. We also employ an implementation of the state-of-the-art DPC enforcing algorithm (DPC) to pinpoint the overhead that DPC+ adds to DPC.

Technical Specifications. The experimentation was carried out on a computer with an Intel Core i7-2820QM processor with a 2.30 GHz frequency per CPU core, 8 GB of RAM, and the Trusty Tahr x86 64 OS. All algorithms were coded in Python and run with PyPy 2.2.1 [PyPy Team, 2015], which implements Python 2.7. Only one CPU core was used.

Datasets and Measures. We considered random RCC8 networks generated by the BA(n↪m) model [Barabasi and Albert, 1999], the use of which in qualitative constraint-based spatial and temporal reasoning is well motivated in [Sioutis et al., 2015a], and real-world RCC8 datasets that have been recently used in [Sioutis et al., 2015b; Li et al., 2015]

In particular, we used the BA(n↪m) model to create random scale-free graphs as the constraint graphs of the RCC8 QCNs. We considered 10 satisfiable RCC8 networks of model BA(n↪m) for each order 1000  n  10000 of their constraint graphs with a 1000-vertex step and a preferential attachment value of m = 2. The edges of these graphs were labelled with relations from the maximal distributive subclass D64 8 of RCC8 [Li et al., 2015]. Regarding real-world RCC8 datasets, we employed the ones recently used in [Sioutis et al., 2015b; Li et al., 2015], viz., nuts (nomenclature of territorial units) 2 with 2 235/3 176 variables/constraints (by constraints we mean non-universal relations), adm1 (administrative geography of Great Britain) [Goodwin et al., 2008] with 11 762/44 832 variables/constraints, gadm1 (German administrative units) 2 with 42749/159600 variables/constraints, gadm2 (the world's administrative areas) [GeoVocab, 2012] with 276729/589573 variables/constraints, adm2 (the administrative geography of Greece) 2 with 1 732 999/5 236 270 variables/constraints, fprints (geographic "footprints" in the Southampton area of the UK) [Li et al., 2015] with 3470/446847 variables/constraints, and stareas (statistical areas in Tasmania) [Li et al., 2015] with 1 562/10 101 variables/constraints. These datasets are satisfiable. Each dataset comprises only relations that are contained in one of the maximal distributive subclasses of RCC8 [Li et al., 2015].

The maximum cardinality search algorithm [Tarjan and Yannakakis, 1984] was used to obtain a variable elimination ordering for DPC and DPC+, and a triangulation of the constraint graph of a given QCN for PPC as described in [Sioutis et al., 2015a]. We note that in our case any variable elimination ordering would be adequate for the evaluation to follow, as it would affect all involved algorithms proportionally and would not qualitatively distort the obtained result.

Our experimentation involves the following two measures. The first measure considers the number of constraint checks performed by a local consistency enforcing algorithm implementation. Given a QCN N = (V↪ C) and vi↪ vk↪ vj 2 V , a constraint check is performed when we compute relation r = Rij \ (Rik ⇧ Rkj) and check if r ⇢ Rij , so that we can propagate its constrainedness. Weak compositions that yield relation ? are disregarded. The second measure concerns the CPU time and is strongly correlated with the first one, as the runtime of these implementations relies heavily on the number of constraint checks performed.

Results. The experimental results for random scale-free RCC8 networks are summarized in Table 1, where a fraction xy denotes that an approach required x seconds of CPU time and performed y constraint checks on average per dataset of networks during its operation. It is clear that DPC+ performs significantly fewer constraint checks and is much faster than PPC for all considered networks, while retaining the good time complexity characteristics of DPC. In particular, DPC+ enforces PPC on a random scale-free RCC8 network of model BA(n = 10000↪m = 2) in around 2 sec, when PPC requires approximately 8 times more time than that for the same task. Regarding real-world RCC8 datasets, the experimental results are summarized in Table 2, where a fraction xy has the same meaning as before. Again, we can see that DPC+ significantly outperforms PPC with regard to both the CPU time required and the number of constraint checks performed for all datasets (with the exception of nuts, whose constraint graph is almost a tree and, thus, neither of the algorithms is challenged enough), while adding only limited overhead to the performance of DPC. As illustration, DPC+ enforces PPC on the largest of the datasets (adm2) in 8▷97 sec, when PPC requires over 44 times more time than that, viz., a total of 398▷63 sec, for the same task. In general, we noted much more inference occurring with realworld datasets than with random networks.

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

6 Conclusion

We proposed a new algorithm, called DPC+, that enforces partial path consistency (PPC) on a qualitative constraint network w.r.t. a triangulation of its underlying constraint graph. In particular, we showed that DPC+ can correctly establish PPC in a qualitative constraint network that is defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra. We also showed that DPC+ only needs to process the triangles in a given graph at most three times, and is therefore much more efficient than the state-of-theart PPC enforcing algorithm; experimental results with both real-world and synthetic datasets confirm this.

Acknowledgements

We thank the anonymous reviewers for their helpful suggestions. This work was supported by the ARC grants DP120104159 and FT0990811 and a PhD grant from the University of Artois and the Nord-Pas-de-Calais region.