On Redundancy in Linked Geospatial Data

Abstract

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. As such, RCC8 has been recently adopted by GeoSPARQL in an e ort to enrich the Semantic Web with qualitative spatial relations. We focus on the redundancy that these data might harbor, which can throttle graph related applications, such as storing, representing, querying, and reasoning. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N . A prime network of N is a network which contains no redundant constraints, but has the same solution set as N . In this paper, we present a practical approach for obtaining the prime networks of RCC8 networks that originate from the Semantic Web, by exploiting the sparse and loosely connected structure of their constraint graphs, and, consequently, contribute towards o ering Linked Geospatial Data of high quality. Experimental evaluation exhibits a vast decrease in the total number of non-redundant constraints that we can obtain from an initial network, while it also suggests that our approach signi cantly boosts the state-of-the-art approach.

-

The Region Connection Calculus (RCC) is the dominant approach in Arti cial Intelligence for representing and reasoning about topological relations [ 10 ]. RCC can be used to describe regions that are non-empty regular subsets of some topological space by stating their topological relations to each other. RCC8 is the constraint language formed by the following 8 binary topological base relations of RCC: disconnected (DC), externally connected (EC), equal (EQ), partially overlapping (P O), tangential proper part (T P P ), tangential proper part inverse (T P P i), non-tangential proper part (N T P P ), and non-tangential proper part inverse (N T P P i). These 8 relations are depicted in [10, Fig. 4].

RCC8 has been recently adopted by GeoSPARQL [ 9 ], and there has been an ever increasing interest in coupling qualititave spatial reasoning techniques with Linked Geospatial Data that are constantly being made available [ 5, 7 ]. Thus, there is a real need for scalable implementations of constraint network algorithms for qualitative and quantitative spatial constraints, as RDF stores supporting Linked Geospatial Data are expected to scale to billions of triples [ 5, 7 ]. In this context, literature has mainly focused on the satis ability problem of a RCC8 network, which is deciding if there exists a solution of the network. Towards e ciently deciding the satis ability of large real world RCC8 networks that originate from the Semantic Web, there has already been a fair amount of work carried out, presenting promising results, as described in [ 13, 12, 15 ]. Lately, the important problem of deriving redundancy in a RCC8 network has been considered and well-established in [ 6 ]. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N . A prime network of N is a network which contains no redundant constraints, but has the same solution set as N . Finding a prime network can be useful in many applications, such as computing, storing, and compressing the relationships between spatial objects and, hence, saving space for storage and communication, merging networks [ 1 ], aiding querying in spatially-enhanced databases [ 7, 9 ], and adjusting geometrical objects to meet topological constraints [ 17 ]. Due to space constraints, we refer the reader to [ 6 ] for a well-depicted real motivational example and further application possibilities.

In this paper, we propose a practical approach for obtaining the prime networks of RCC8 networks that have been harvested from the Semantic Web. In particular, we exploit the sparse and loosely connected structure of their constraint graphs, by establishing results that allow us to build on the simple decomposition scheme presented in [ 15 ]. The paper is organized as follows: in Section 2 we give some preliminaries concerning RCC8, redundant constraints, and the notion of a prime network, in Section 3 we present our practical approach for obtaining the prime networks of RCC8 networks that have been harvested from the Semantic Web, in Section 4 we experimentally show that we can have a vast decrease in the total number of non-redundant constraints that we can obtain from an initial RCC8 network of the considered dataset, with signi cantly improved performance over the state-of-the-art approach, and, nally, in Section 5 we conclude and make a connection with a relevant late breaking research e ort. 2

Preliminaries

A (binary) qualitative constraint language [ 11 ] is based on a nite set B of jointly exhaustive and pairwise disjoint (JEPD) relations de ned on a domain D, called the set of base relations. The base relations of set B of a particular qualitative constraint language can be used to represent de nite knowledge between any two entities with respect to the given level of granularity. B contains the identity relation Id, and is closed under the converse operation ( 1). Inde nite knowledge can be speci ed by unions of possible base relations, and is represented by the set containing them. Hence, 2B represents the total set of relations. 2B is equipped with the usual set-theoretic operations union and intersection, the converse operation, and the weak composition operation denoted by symbol [ 11 ]. In the case of RCC8 [ 10 ], as noted in Section 1, B is the set fDC,EC,P O,T P P ,N T P P , T P P i,N T P P i,EQg, with EQ being relation Id. RCC8 networks can be viewed as qualitative constraint networks (QCNs), de ned as follows:

{EC} v0 {NTPPi} v2

{EC} v0 {NTPPi} v2

B

In what follows, given a QCN N = (V; C) and v; v0 2 V , N [v; v0] will denote the relation C(v; v0). N[v;v0]=r, with r 2 2B, is the QCN N 0 de ned by N 0[v; v0] = r, N 0[v0; v] = r 1, and N 0[v; v0] = N [v; v0] 8(v; v0) 2 (V V ) n f(v; v0); (v0; v)g. A QCN N = (V; C) is said to be trivially inconsistent i 9v; v0 2 V with N [v; v0] = ;. A solution of N is a mapping de ned from V to the domain D, yielding a valid con guration, such that for every pair (v; v0) of variables in V , ( (v); (v0)) can be described by N [v; v0], i.e., there exists a base relation b 2 N [v; v0] such that the relation de ned by ( (v); (v0)) is b. Two QCNs are equivalent i they admit the same set of solutions. The constraint graph of a QCN N = (V; C) is the graph (V; E), denoted by G(N ), for which we have that (v; v0) 2 E i N [v; v0] 6= B. (N ) denotes the re ned -consistent QCN of N , i 8v; v0; v00 2 V we have that (N )[v; v0] (N )[v; v00] (N )[v00; v0]. A sub-QCN N 0 of N = (V; C), is a QCN (V; C0) such that N 0[v; v0] N [v; v0] 8v; v0 2 V where N 0[v; v0] 6= B. Given a QCN N = (V; C), N #V 0 , with V 0 V , is QCN N restricted to V 0. If b is a base relation, then fbg is a singleton relation. A subclass of relations is a set A 2B closed under converse, intersection, and weak composition. In what follows, all the considered subclasses will contain the singleton relations of 2B. Given three relations r, r0, and r00, we say that weak composition distributes over intersection if we have that r (r0 \ r00) = (r \ r0) (r \ r00) and (r0 \ r00) r = (r0 \ r) (r00 \ r). De nition 2. A subclass A 2B is a distributive subclass if weak composition distributes over non-empty intersections for all relations r, r0, r00 2 A. A subclass A 2B is a maximal distributive subclass if there exists no other distributive subclass B with B A.

Notably, RCC8 has two maximal distributive subclasses, namely, D841 and D864 [ 6 ]. Given a QCN N = (V; C), we say that N entails a constraint r(v; v0) 2 2B, with v; v0 2 V , if for every solution of N , the relation de ned by ( (v); (v0)) is a base relation b such that b 2 r(v; v0). Relation N [v; v0] is redundant if network N[v;v0]=B entails N [v; v0]. Note that by de nition every universal relation B in a QCN is redundant. Recalling the fact that the constraint graph of a QCN involves all the non-universal relations, we can obtain the following lemma: Lemma 1. Given a QCN N = (V; C) and its constraint graph G(N ) = (V; E), a relation N [v; v0], with v; v0 2 V , is redundant if (v; v0) 62 E.

We now recall the following de nition of a reducible and a prime QCN: v0 v4

G2

G G3 G4

Fig. 2: A graph G (left) with its biconnected components (right) De nition 3 ([ 6 ]). A QCN N = (V; C) is reducible if it comprises a redundant relation other than relation B, and irreducible otherwise. An equivalent irreducible sub-QCN of N , is called a prime QCN of N . If a prime QCN of N is also unique, it is denoted by Nprime.

In Figure 1, a QCN N of RCC8 and its prime QCN are depicted. Relation fDCg is redundant as it can be entailed by N[v1;v2]=B and, thus, can be replaced with relation B (denoting the lack of a constraint between two entities in a QCN). Property 1 ([ 6 ]). Let N = (V; C) be a satis able QCN of RCC8. Then, N will be said to satisfy the uniqueness property i 8u; v 2 V , with u 6= v, we have that N does not entail a relation r N [u; v] where r = fEQg.

The uniqueness property speci es that every region in a QCN of RCC8 should be unique and not identical to any other region. This is a necessary property to be able to obtain the unique prime network of a QCN [ 6 ] and will hold for all the considered QCNs in what follows. We recall the following important lemma to be used in the sequel: Lemma 2 ([ 6 ]). Let N = (V; C) be a not trivially inconsistent and -consistent QCN of RCC8 de ned on one of the maximal distributive subclasses D841, or D864, and having the uniqueness property. Then, a relation N [v; v0], with v; v0 2 V , is non-redundant in N i N [v; v0] 6= TfN [v; v00] N [v00; v0] j v00 2 V n fv; v0gg.

Finally, we have the following result with respect to the unique prime network of a QCN N of RCC8, namely, Nprime: Theorem 1 ([ 6 ]). Let N = (V; C) be a satis able QCN of RCC8 de ned on one of the maximal distributive subclasses D841, or D864, and having the uniqueness property. Further, let be the set of non-redundant relations in (N ). Then, 8u; v 2 V we have that Nprime[u; v] = (N [u; v] if (N )[u; v] 2 else B). 3

Towards E ciently Characterizing Non-Redundant

Relations in a Network

In this section we present a practical approach for characterizing non-redundant relations in QCNs that have been harvested from the Semantic Web. In particular, we exploit the sparse and loosely connected structure of their constraint graphs, by establishing results that allow building on the simple decomposition scheme of [ 15 ]. We recall the following de nition regarding biconnected graphs: Algorithm 1: Delphys+(N )

;; foreach n 2 Decomposer(N ) [ 15 ] do

[ Delphys(n) [ 6 ]; in : A satis able QCN N = (V; C) of RCC8 de ned on D841 or D864. output : , the set of non-redundant relations in (N ). 1 begin 2 3 4 5

return ; De nition 4 ([ 2 ]). A connected graph G = (V; E) is said to have an articulation vertex u if there exist vertices v and v0 such that all paths connecting v and v0 pass through u. A graph that has an articulation vertex is called separable, and one that has none is called biconnected. A maximal biconnected subgraph is called a biconnected component.

Intuitively, an articulation vertex is any vertex whose removal increases the number of connected components in a given graph. Figure 2 depicts a graph G, along with its biconnected components. Vertices in grey are the articulation vertices of G. The biconnected components of a graph G = (V; E) can be obtained in O(jEj) time [ 2 ]. We recall the following result from [ 15 ]: Proposition 1 ([ 15 ]). Let N be a QCN of RCC8, and fG1; : : : ; Gkg the biconnected components of its constraint graph G(N ). Then, N is satis able i Ni is satis able for every i 2 f1; : : : ; kg, where Ni is N #V (Gi).

Then, by Proposition 1 and Lemma 1 we can obtain the following result: Proposition 2. Let N be a satis able QCN of RCC8, and fG1; : : : ; Gkg the biconnected components of its constraint graph G(N ). Then, a relation N [v; v0], with v; v0 2 V , is non-redundant in N i (v; v0) 2 E(Gi) and N [v; v0] is nonredundant in Ni, where Ni is N #V (Gi), for some i 2 f1; : : : ; kg. Proof. By Lemma 1 we know that a relation N [v; v0] is redundant if (v; v0) 62 E(Gi). Let us consider a relation N [v; v0] where (v; v0) 2 E(Gi). Let N 0 = N[v;v0]=B and Ni0 the restriction of N 0 to V (Gi). Then, by Proposition 1 we have that a mapping is a solution of N 0 i is a solution of Ni0. On the other hand, since Gi is a biconnected component, any solution of Ni0 is the restriction of some solution of N 0 to V (Gi). Thus, N 0 entails N [v; v0] i Ni0 entails N [v; v0], and, consequently, N [v; v0] is redundant in N i N [v; v0] is redundant in Ni. tu

An algorithm based on Lemma 2 to obtain the set of non-redundant relations was provided in [ 6 ] with a time complexity of O(jV j3) for a given QCN N = (V; C) of RCC8, which we here call Delphys. Proposition 2 allows us to establish a time complexity of O( jVc j c3) = O(jV j c2), where c jV j is the maximum order among the biconnected components of constraint graph G(N ), as it suggests that we can consider the smaller biconnected components of G(N ) instead of the entire constraint graph when characterizing non-redundant relations in N . This new approach, which we call Delphys+, is shown in Algorithm 1.3

It remains to be seen if there is any signi cant di erence between the order of the constraint graph of a QCN and the maximum order among the biconnected components of that graph, that is, if the value of the latter is signi cantly smaller than the value of the former, so that Delphys+ can be considered as an advancement over Delphys. We will see that this is indeed the case for the considered QCNs of RCC8 that have been harvested from the Semantic Web (originally appeared in [ 8 ]), which we introduce as follows.

{ nuts: a RCC8 network that describes a nomenclature of territorial units and contains 2 235/3 176 nodes/edges.4 { adm1: a RCC8 network that describes the administrative geography of Great

Britain [ 4 ] and contains 11 761/44 832 nodes/edges. { gadm1: a RCC8 network that describes the German administrative units and contains 42 749/159 600 nodes/edges.4 { gadm2: a RCC8 network that describes the world's administrative areas and contains 276 727/589 573 nodes/edges (http://gadm.geovocab.org/). { adm2: a RCC8 network that describes the Greek administrative geography and contains 1 732 999/5 236 270 nodes/edges.4

The aforementioned QCNs are satis able5, comprise relations that are properly contained in any of the two maximal distributive subclasses D841 and D864 for RCC8, and originate from the Semantic Web, also called the Web of Data, which is argued to be scale-free [ 16 ]. Graphs of scale-free structure are relatively sparse [ 3 ], as it can be also observed by the jEj ratio of the constraint jV j graphs of our real world QCNs, thus, we expect these constraint graphs to be loosely connected and yield a high number of biconnected components. We can view information regarding biconnected components of the constraint graphs of our QCNs in Table 1. The ndings are quite impressive, in the sense that the maximum order among the biconnected components of a constraint graph is signi cantly smaller than the order of that graph. For example, the constraint graph of the biggest real RCC8 network, namely, adm2, has an order of value 3Check jV (g)j > 2 within algorithm Decomposer as it appears in [ 15 ] must be removed for appropriate use of Decomposer in Delphys+.

4Retrieved from: http://www.linkedopendata.gr/ 5As obtaining the prime network of a QCN requires that the QCN is satis able (see Theorem 1), we xed some inconsistencies with gadm1 and gadm2 that were originally unsatis able. Also, identical regions were properly amalgamated to satisfy the uniqueness property. 1 733 000, but the maximum order among its biconnected components is only of value 22 808. Note also that, as the other metrics suggest, the largest proportion of the biconnected components of a graph have an order much closer to the minimum order than the maximum order among the components of that graph. 4

Experimental Evaluation

In this section, we compare the performance of Delphys+ with that of Delphys [ 6 ] using the dataset presented in Section 3. Experimentation was carried out on a PC with an Intel Core 2 Quad Q9400 processor, 8 GB RAM, and the Precise Pangolin x86 64 OS. Both Delphys and Delphys+ were written in Python and run with with PyPy 2.4.0 (http://pypy.org/). Only one CPU core was used.

The results on the performance of Delphys+ and Delphys are shown in Table 2. Note that symbol 1 signi es that a reasoner hit the memory limit. The speedup for Delphys+ reaches as high as nearly 100% for the cases where Delphys was actually able to fully reason with the networks (e.g., nuts). Regarding adm1 the speedup was limited and expected as the maximum order among the biconnected components of the constraint graph of adm1 is very close to the order of the entire graph itself (see Table 1). We also note that despite the overall much better performance of Delphys+, it was unable to fully reason with adm2. (We will refer to a late breaking research e ort regarding this issue in the closing section.)

Regarding redundancy, Table 3 shows the decrease that we can achieve with respect to the total number of non-redundant constraints that we can obtain from an initial network, which allows one to construct sparse constraint graphs that can boost various graph related tasks, such as storing, representing, querying, and reasoning. Notably, for the biggest network that Delphys+ was able to fully reason with, namely, gadm2, the decrease is more than 50%, yielding a number of non-redundant constraints which is almost linear to the number of its vertices, con rming a similar observation in [ 6 ].

Conclusion

We focused on the redundancy that is harbored in RCC8 networks that originate from the Semantic Web, and proposed a practical approach for sanitizing such networks of any redundancy, by obtaining the set of their non-redundant constraints and, consequently, o ering Linked Geospatial Data of high quality. Experimental evaluation exhibited a vast decrease in the total number of nonredundant constraints that we can obtain from an initial network, with signi cantly improved performance over the state-of-the-art approach. A late breaking research e ort, presented in [ 14 ], builds on our approach and uses a particular partial consistency to signi cantly boost its performance. Notably, it is able to tackle even the largest of networks considered in our evaluation in this paper.

References

1. Condotta , J. , Kaci , S. , Marquis , P. , Schwind , N.: Merging Qualitative Constraint Networks in a Piecewise Fashion . In: ICTAI ( 2009 )

2. Dechter , R.: Constraint processing . Elsevier Morgan Kaufmann ( 2003 )

3. Del Genio , C.I. , Gross , T. , Bassler , K.E. : All Scale-Free Networks Are Sparse . Phys. Rev. Lett . 107 , 178701 ( 2011 )

4. Goodwin , J. , Dolbear , C. , Hart , G.: Geographical Linked Data: The Administrative Geography of Great Britain on the Semantic Web . TGIS 12 , 19 { 30 ( 2008 )

5. Koubarakis , M. , et al.: Challenges for Qualitative Spatial Reasoning in Linked Geospatial Data . In: BASR@IJCAI ( 2011 )

6. Li , S. , Long , Z. , Liu , W. , Duckham , M. , Both , A. : On redundant topological constraints . AIJ 225 , 51 { 76 ( 2015 ), in press

7. Nikolaou , C. , Koubarakis , M. : Querying Incomplete Geospatial Information in RDF . In: SSTD ( 2013 )

8. Nikolaou , C. , Koubarakis , M. : Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning . In: AAAI ( 2014 )

9. Open Geospatial Consortium: OGC GeoSPARQL - A geographic query language for RDF data . OGC R Standard ( 2012 )

10. Randell , D.A. , Cui , Z. , Cohn , A. : A Spatial Logic Based on Regions and Connection . In: KR ( 1992 )

11. Renz , J. , Ligozat , G.: Weak Composition for Qualitative Spatial and Temporal Reasoning . In: CP ( 2005 )

12. Sioutis , M. : Triangulation versus Graph Partitioning for Tackling Large Real World Qualitative Spatial Networks . In: ICTAI ( 2014 )

13. Sioutis , M. , Condotta , J.F. : Tackling large Qualitative Spatial Networks of scalefree-like structure . In: SETN ( 2014 )

14. Sioutis , M. , Li , S. , Condotta , J.F. : E ciently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks . In: IJCAI ( 2015 ), to appear

15. Sioutis , M. , Salhi , Y. , Condotta , J.: A Simple Decomposition Scheme For Large Real World Qualitative Constraint Networks . In: FLAIRS ( 2015 ), to appear

16. Steyvers , M. , Tenenbaum , J.B. : The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth . Cog. Sci . 29 , 41 { 78 ( 2005 )

17. Wallgrun, J.O. : Exploiting qualitative spatial reasoning for topological adjustment of spatial data . In: SIGSPATIAL ( 2012 )