Linking geo-spatial entities is targeted only by a limited number of link discovery benchmarks. Linking spatial resources requires techniques that di er from the classical, mostly string-based approaches. In particular, considering the topology of the spatial resources and the topological relations between them is of central importance to systems that manage spatial data. Due to the large amount of available geospatial Linked Data datasets, it is critical that benchmarks for geo-spatial link discovery systems are developed that can determine the e ectiveness and the e ciency of the proposed techniques. In this paper, we propose a Spatial Benchmark generator that deals with link discovery for spatial data. Our benchmark generator can be used to test the performance of systems that deal with all the topological relations proposed in the state of the art DE-9IM (Dimensionally Extended nine-Intersection) model in the two dimensional space. We also provide a comparative analysis with benchmarks produced using the Spatial Benchmark generator to assess and identify the capabilities of RADON and Silk, two of the state of the art systems.
The number of datasets published in the Web of Data as part of the Linked Data
Cloud is constantly increasing. The Linked Data paradigm is based on the
unconstrained publication of information by di erent publishers, and the interlinking
of Web resources across knowledge bases. In most cases, the cross-dataset links
are not explicit in the dataset and must be automatically determined using link
discovery tools amongst others [
A number of real and synthetic benchmarks that address di erent data
challenges have been proposed for evaluating the performance of such systems [
Linking spatial resources requires techniques that di er from the classical mostly string-based approaches. In particular, considering the topology of the spatial resources and the topological relations between them is of central importance to systems that manage spatial data. We believe that due to the large amount of available geo-spatial datasets employed in Linked Data and in several domains, it is critical that benchmarks for geo-spatial link discovery are developed.
The present paper proposes the Spatial Benchmark generator2 that deals
with Link Discovery for spatial data. The benchmark can be used to test the
performance of systems that deal with topological relations proposed in the state
of the art DE-9IM (Dimensionally Extended nine-Intersection Model) model [
To the best of our knowledge such a generic benchmark, that takes as input
trajectories and checks the performance of linking systems for spatial data does
not exist. We also provide a comparative analysis with benchmarks produced
using the Spatial Benchmark generator to assess and identify the capabilities of
RADON [
The Spatial Benchmark is based on TomTom datasets3 provided in the context of the HOBBIT H2020 project4. TomTom's tra c data archive contains approximately 15 trillion (1:5 1013) speed measurements from hundreds of millions of road segments all over the world, mostly based on anonymized GPS positioning data collected with user's consent. This data has been used to extract the recurrent tra c patterns and adds this to digital navigation maps as a map layer. Statistical tra c data also form an important input set for TomTom's live trafc fusion engine. Probe data is being used for custom-made tra c and demand analysis. Furthermore, archived positioning data is used to improve digital maps, road geometry and map attributes.
The ontology we use to represent TomTom's data is shown in Figure 1. The main class is Trace that contains one or more points (class Point). Class Point is a subclass of wgs84 pos:Point class of the WGS84 Geo Positioning (geo)5 vocabulary that represents latitude, longitude and altitude information
in the WGS84 geodetic reference datum. Each point is associated with a velocity (class Velocity), instances of which have properties velocityMetric and velocityValue, the former taking values from a prede ned set (km per hour, miles per hour ) and the later from class xsd:Float. A point also has attribute hasTimeStamp that takes its values in class xsd:TimeStamp which designates the time an object was at this speci c point. Listing 1.1 shows an example of a Trace consisting of 4 Points.
3.1
Dimensionally Extended nine-Intersection Model (DE-9IM)
The Dimensionally Extended nine-Intersection Model (DE-9IM) [
2 dim(I(a) \ I(b)) dim(I(a) \ B(b)) dim(I(a) \ E(b)) 3 DE9IM(a; b) = 4dim(B(a) \ I(b)) dim(B(a) \ B(b)) dim(B(a) \ E(b))5 dim(E(a) \ I(b)) dim(E(a) \ B(b)) dim(E(a) \ E(b)) where dim is the maximum number of dimensions of the intersection (\) of the interior (I), boundary (B), and exterior (E) of geometries g1 and g2. Dimension (dim(x)) values are obtained mapping the value 1 (for lines) to T (true), so using the boolean domain fT; F g. The supported spatial relations of DE-9IM are formally described below (see also Figure 2). Here, we will write (I(g1)I(g2)) to show dim(I(g1) \ I(g2)) etc.
{ Equal: Two geometries g1 and g2 are topologically equal if their interiors intersect and no part of the interior or boundary of one geometry intersects the exterior of the other. Topologically equal is equivalent to Within and Contains DE-9IM relations. Formally: (I(g1)I(g2))^:(I(g1)E(g2))^:(B(g1)E(g2))^:(E(g1)I(g2))^:(E(g1)B(g2)) { Disjoint: Two geometries g1 and g2 are disjoint if they have no point in common. They form a set of disconnected geometries. Disjoint is equivalent to not Intersects. Formally:
:(I(g1)I(g2)) ^ :(I(g1)B(g2)) ^ :(B(g1)I(g2)) ^ :(B(g1)B(g2)) { Touches: A geometry g1 touches(meets) a geometry g2 if they have at least one boundary point in common, but no common interior points. Formally: (:(I(g1)I(g2)) ^ I(g1)B(g2)) _ (:(I(g1)I(g2)) ^ B(g1)I(g2))_ (:(I(g1)I(g2)) ^ B(g1)B(g2)) { Contains: A geometry g1 contains a geometry g2 if g2 lies in g1, and the interiors of the two geometries intersect. Contains is equivalent to Within(g2; g1). Formally: (I(g1)I(g2)) ^ :(E(g1)I(g2)) ^ :(E(g1)B(g2)) { Covers: A geometry g1 covers a geometry g2 if geometry g2 lies in g1.
Other de nitions: \no points of g2 lie in the exterior of g1", or \Every point of g2 is a point of (the interior or boundary of) g1". Covers is equivalent to CoveredBy(g2; g1). Formally: ((I(g1)I(g2)) ^ :(E(g1)I(g2)) ^ :(E(g1)B(g2)))_ ((I(g1)B(g2)) ^ :(E(g1)I(g2)) ^ :(E(g1)B(g2)))_ ((B(g1)I(g2)) ^ :(E(g1)I(g2)) ^ :(E(g1)B(g2)))_
((B(g1)B(g2)) ^ :(E(g1)I(g2)) ^ :(E(g1)B(g2))) { Intersects: A geometry g1 intersects g2 if they have at least one point in common. Intersects is equivalent to not Disjoint. { Within: A geometry g1 is within(inside) g2 if g1 lies in the interior of g2.
Within is equivalent to Contains(g2; g1). { Covered by: A geometry g1 is covered by g2 (extends Within) if every point of g1 is a point of g2, and the interiors of the two geometries have at least one point in common. Covered by is equivalent to Covers(g2; g1). { Crosses: A geometry g1 crosses g2 if they have some but not all interior points in common, and the dimension of the intersection is less than that of at least one of them. Mask selection rules are checked only when dim(g1) 6= dim(g2), except by line/line inputs, otherwise is false: ll((I(g1)I(g2)) = 0) for lines (I(g1)I(g2) ^ I(g1)E(g2)) when dim(g1) < dim(g2) (I(g1)I(g2) ^ E(g1)I(g2)) when dim(g1) > dim(g2) { Overlaps: A geometry g1 is overlaps g2 if they have some but not all points in common, they have the same dimension, and the intersection of the interiors of the two geometries has the same dimension as the geometries themselves. Mask selection rules are checked only when dim(g1) = dim(g2), otherwise is false:
ll((I(g1)I(g2)) ^ (I(g1)E(g2)) ^ (E(g1)I(g2))) for points or surfaces ((I(g1)I(g2)) = 1 ^ (I(g1)E(g2)) ^ (E(g1)I(g2))) for lines
3.2
Overview For the Spatial Benchmark, we focus on transformations that follow the DE9IM (Dimensionally Extended nine-Intersection Model) topological relations and determine whether the systems are able to identify such relations.
For the design of this benchmark, we focused (a) on the correct implementation of all the topological relations of the DE-9IM topological model and (b) on (a) Equals (b) Disjoint (c) Touches (d) Contains & Covers (e) Intersects
(f) Crosses (g) Overlaps producing datasets large enough to stress the systems under test. To the best of our knowledge, there exist few systems that implement the topological relations of DE-9IM, hence the benchmark already addresses the rst choke point set. Moreover, we produced very large synthetic datasets using TomTom's original data, and hence we are able to challenge the systems regarding scalabity.
The benchmark gets as input a set of traces, each trace being a sequence of points. The points are expressed using standard longitude/latitude coordinates. We preprocess the datasets to represent them in the Well-known text (WKT) format6, widely used by systems that manage geo-spatial data. WKT is a text markup language for representing vector geometry objects on a map, spatial reference systems of spatial objects and transformations among spatial reference systems. WKT o ers a compact machine and human readable representation of geometric objects. Nevertheless, if the input dataset comes in a di erent format, then we can easily transform the data in the required format. Appropriate transformations are applied to the input set of traces in order to obtain the target dataset that can be used to test the ability of systems to identify DE-9IM topological relations.
More speci cally, as shown in Figure 3, the benchmark gets as input traces represented as LineStrings, with a linestring being a one-dimensional object representing a sequence of points and the line segments connecting them, and produces a source and a target dataset. The source dataset is identical to the input dataset, whereas the target dataset is generated in such a way so that its traces have speci c topological (DE-9IM) relations with the traces of the source
dataset. The gold standard is produced after the generation of the source and target datasets.
The benchmark generator makes use of the Initialization, Resource Generator and the Resource Transformation modules: 1. The Initialization Module reads the test case generation parameters and retrieves by means of SPARQL queries each trace instance. 2. The Resource Generator uses the trace instances retrieved from the Initialization Module for the generation of the source dataset. 3. The Resource Transformation Module uses the JTS Topology Suite7 to return for each source instance si the transformed instance ti that has a certain predecided relation (from the DE-9IM set) with si.
Note that Step 3 above may lead to the creation of certain ti that inadvertently have some relation with some sj (i 6= j). To address this problem, the gold standard is produced using RADON, in order to guarantee that all existing topological relations (intended or not) will be included in the gold standard. For the generation of the source and target datasets, the user has to provide values for the following benchmark parameters: 1. Number of instances to retrieve from the input dataset. 2. Percentage of points to keep for each Trace in the input dataset (this is due to the large number of points in each trace). 3. DE-9IM topological relation that will be tested for the source and target traces. As we mentioned earlier, a target trace ti is likely to have a relation with sj (i 6= j) in addition to the source trace si from which it is generated.
3.4
Source and Target Data Generation Source Dataset In order to generate the source dataset we proceed as follows: from the input dataset, we only keep longitude and latitude information from each point. With those points, we create, for each trace, a LineString8 that is represented in the Well-known text (WKT) representation format. Target Dataset In order to produce the target dataset, we retrieve source instances in a sequential manner, and using the Extension of the JTS Topology Suite we generate one target instance for each source instance. The target instance is de ned in such a way so as the two instances (source and target) have the DE-9IM relation that was speci ed in the benchmark's con guration parameters. This process is continued until the requested number of instances is produced.
The JTS Topology Suite9 is a Java API that implements a core set of spatial data operations using an explicit precision model and robust geometric algorithms. It provides a complete model for specifying 2D linear geometries. Many common operations in computational geometry and spatial data processing are exposed in a clear, consistent and integrated API in JTS. JTS is intended to be used in the development of applications that support the validation, cleaning, integration and querying of spatial datasets. JTS is based on the notion of the bounding box (bbox), which is an area de ned by two longitudes (in the range 180 : : : 180) and two latitudes (in the range 90 : : : 90), such that the resulting box (included within these coordinates) is the minimum box that contains the geometry under study.
For generating the target data in the Spatial Benchmark, we decided to implement an extension10 of the JTS Topology Suite that allows one to generate a target geometry, given a source geometry and the intended Intersection Matrix (i.e., DE-9IM relation) between the source and target geometries. Below, we describe the algorithm of the implemented extension for each target relation of DE-9IM. As we will see, all cases are essentially based on the algorithms that generate disjoint LineStrings, along with some random selection of points and/or series of points. More speci cally: 1. equal: Given a source LineString, an equal LineString is the exact same. 2. disjoint: Given a source LineString s we determine its bbox (b(s)), and randomly de ne coordinates for a bbox (say b0) that does not intersect b(s). This is done by just taking su ciently large (or su ciently small) coordinates for the minimum (maximum) longitude or latitude coordinates. Finally, we generate a random LineString that entirely falls inside b0, thereby guaranteeing disjointness. 8 A LineString is a WKT geometric object and consists of a sequence of two or more vertices, along with all points of the linearly interpolated curves (line segments) between each pair of consecutive vertices. The line segments in the line may intersect with each other (in other words, the linestring may \curl back" in itself and selfintersect). A linestring must have either zero or two or more points.
In rare cases, it could happen that b(s) covers the entire plane, so no b0 can be de ned. In these cases, we randomly break the original LineString into several smaller LineStrings (say s1; : : : ; sk), and compute their bboxes (b(s1); : : : ; b(sk)). Then, we use the above process to identify a bbox b0 that does not intersect with any of them and create a random target LineString as above.
If, despite the partitioning of s, no appropriate b0 can be found, we de ne an alternative, more ne-grained partition and repeat the process which ends when an appropriate b0 is found, or when each pair of consecutive points of s is a partition; if even this ne-grained partition does not allow the de nition of an appropriate bbox, then the original LineString covers the entire plane and no disjoint line can be created.
An example of this partition, is shown in Figure 4. In the rst sub gure, the bbox of the LineString covers the entire plane, thus we partitioned the LineString into 3 smaller parts. Then, we computed the new smaller bounding boxes and as is shown in the second image, there is now space (blue area) where we can de ne a new bbox and create the new LineString in it. We follow the same approach for the rest of the relations. bbox 1
y bbox 2
Empty space bbox 3 x 3. contains & covers: Given a source LineString s, we randomly partition it into s1; : : : ; sn, and randomly pick one si to be the target LineString t. 4. intersects: Given a source LineString s, we randomly pick n points p1; : : : ; pn (n > 1). Then, we create disjoint LineString p1; : : : ; pk n, where k the size of LineString s. Finally, we create the nal LineString t by adjoining the LineString t and the n points. 5. within & covered by: Within and covered by are obtained from contains and covers respectively (they are their inverse relations). 6. crosses: This is the same as intersects, except that n = 1, and that the chosen point must be an intermediate one. 7. overlaps: Given a source LineString s, we pick an intermediate point, say p, essentially partitioning s into two segments, say s1; s2. Then, we create two LineStrings t1; t2. The LineString t1 is randomly chosen to be equal to either s1 or s2. Without loss of generality, let's assume that s1 is chosen. The LineString t2 is a LineString that is disjoint from s. The nal target LineString t is de ned by adjoining t1 with t2.
Gold Standard For the Spatial benchmark, the gold standard, could not be produced during the generation of the target dataset. As mentioned earlier, such an approach might lead to the creation of certain ti that inadvertently have some relation with some sj (i 6= j), thus, the gold standard would be neither complete nor correct. To support completeness and correctness of the gold standard, the benchmark should check each generated target LineString ti against all source LineStrings si for all possible relations that essentially amounts to implementing a system for the computation of the topological relations.
To avoid this problem, after all the source and target datasets are generated,
we compute the gold standard using RADON [
Key Performance Indicators (KPIs) The performance metric(s) in a
benchmark determine the e ectiveness and e ciency of the systems and tools. In this
benchmark, we focus on the quality of the output in terms of standard metrics
such as precision, recall and f-measure [
In order to show the rate between the time performance and the population (10, 100, 1K and 10K) of the traces, but also the time di erence between the topological relations, we executed a set of experiments for all the DE-9IM relations using the HOBBIT Platform11. Thus, we provide a comparative analysis with benchmarks produced using the Spatial Benchmark generator to assess and identify the capabilities of RADON and SILK, two of the state of the art systems. We should mention here that we are only presenting the time performance and not precision, recall and f-measure as all were equal to 1.0. Moreover, because of a problem encountered for SILK12, we had to select traces no larger than 64 KB from all datasets in order to get a fair comparison for the systems under test.
Table 1 and Figures 5, 6 show the results of the executed experiments. Time is measured in milliseconds but for a better presentation of the results we use log(time). Relation Disjoint, needs the shortest time for the systems to return the results if the number of traces is small. However, as the number of traces increases, Silk seems to have di culties linking all the traces fast enough, and the experiment stops due to the platform time limit (75 minutes)13.
Intersects, Touches and Overlaps, seem to be the hardest relations for the systems as they need more time than Equals, Crosses, Covers/Covered By and Contains/Within, which need approximately the same time. Speci cally, for Touches and Intersects we were not able to run experiments for the 10K traces source dataset (the target dataset consists of the same number of traces) as in the other cases the experiments stopped for both RADON and Silk. The reason that those relations need much more time is that our data contain LineStrings that have a large number of points in a rather small area. Covers/Covered By is not supported by Silk, but Contains/Within are the same when the datasets consist of LineStrings, thus, this was not an issue for the system. Generally, RADON seems to handle the growth of the dataset size smoother than Silk, meaning that when it comes to a small number of traces, RADON needs approximately the half time than Silk but as the size increases, RADON outperforms Silk by more than one order of magnitude. 11 http://master.project-hobbit.eu 12 https://github.com/silk-framework/silk/issues/57 13 The platform has a time limit for each benchmark to prevent it from binding the platform continuously. We presented HOBBIT's Spatial benchmark, a benchmark that checks whether the systems can identify DE-9IM (Dimensionally Extended nine-Intersection Model) topological relations. To the best of our knowledge, such benchmarks do not exist while the number of link discovery systems that identify links for spatial datasets are limited.
We evaluated two of the state of the art systems, RADON and Silk using the Spatial Benchmark generator to assess and identify their capabilities. Our results show that performing link discovery for some of the DE-9IM relations (touches, intersects, overlaps) takes prohibitive time. On the other hand, for the rest of the relations, the systems seem to need much less time. In future work, we aim to extend the implementation of the JTS extension in order to generate di erent classes of object geometries in addition to LineString. In addition, we will explore the possibility to include new evaluation metrics in the benchmark.