{'fraction_non_alphanumeric': 0.032580969312823685, 'fraction_numerical': 0.009546262657494009, 'mean_word_length': 4.891393442622951, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Linking geospatial data with Geo-L -- analysis and experiments of big data readiness of common technologies

Geospatial Linked Data is an emerging domain, with growing interest in research and industry. The growing sources of open-source geospatial Linked Data need to be interlinked and easily integrated with private and industrial linked data clouds, e.g., in the agricultural domain. The presented paper analyzes common link discovery tools for the feasibility of big linked data processing. Further, it introduces Geo-L, a system for discovery of RDF spatial links based on topological relations. Experiments show that the proposed system improves state-of-the-art spatial linking processes in terms of mapping-time and -accuracy, as well as concerning resources retrieval efficiency and robustness.


Introduction
The Web of Data, or Semantic Web, is a continuously growing global data space (https://www.w3.org/2013/data/). Semantic Web standards, such as RDF [1,2], OWL [3,4], and SPARQL [5] were developed to express and exchange semantic information on the Web, which tackle the challenge of interoperability [6]. In the geospatial context, most prominent is the GeoSPARQL initiative, which offers a necessary vocabulary to develop geo-related data on the Semantic Web [7]. In recent years, geospatial linked data gained increasing attention [8], also due to advances in the Earth Observation domain [9]. Thus, numerous resources of linked geospatial data have been developed, e.g., LinkedGeoData [10], Smart Point Of Interest [11], Spanish Cases [12], and Ireland's national geospatial data [13]; and the domain is constantly growing within the Linked Data Cloud. Notably, the domain of geospatial data contains complex datasets, as NUTS [14], which describe territories using polygons that may be more than 1700 points long.
According to the Linked Data principles, published data should be interlinked with other datasets on the Web [15]. In general, linking (and fusing) of geospatial linked data sources enable large-scale inferences and data integration [16]. Nevertheless, clear links are often not part of the dataset and should be discovered automatically, even in a distributed cloud environment and huge datasets. These linking activities are one pillar to foster the development of innovative software solutions. In particular, the linking of geospatial data is a challenging task, since the links express relations which depend on complex geometric computations. Based on a comparison of existing approaches, services and tools, the goal of the paper is to give an overview and introduce a novel specialized tool for link discovery on geospatial link data with the following requirements: to handle big data sets. The idea is to provide a service for different Linked Data environments (open or closed). Therefore, the time efforts have to be reduced on a significant minimum. The vision is to discover even extensive data sets in near real-time. 2. Robustness: The service must retain functionality under unforeseen conditions, as missing or corrupted data. This is especially true for crowd-sourced or automatically generated data sets, which are likely to include errors as the size of data grows. 3. Interoperability and flexibility: The service has to be handled as easy and transparent as possible. The (SPARQL affine) user should be able to easily formulate queries to retrieve source and target datasets, as well as the linking condition. This includes the ability to handle data whose representation is not compatible for computing of, e.g., topological relations. Further, the service has to handle on-the-fly requests by a RESTful input processing. It has to operate easily as a standalone system or as a module integrated into other applications. The paper is structured as follows: Firstly, we introduce the theoretical background of geospatial link discovery. Secondly, we describe previous work related to geospatial link discovery. Thirdly, we present our solution. Fourthly, we evaluate our solution and compare it to the state-of-the-art system.

Background
Linked (Open) Data refer to an area which focuses on the publishing of RDF (Resource Description Framework) on the Web of Data. However, the Linked Data approach is strongly linked to the Tim Berners-Lee Linked Data Principles [15]. The basic idea of link discovery is to find data items within the target dataset which are logically connected to the source dataset. More formaly this means: Given and , sets of RDF resources, called source and target resources respectively, and a relation , the aim of link discovery methods is to find a mapping = {( , ) ∈ × ∶ ( , )}. Naive computation of M requires quadratic time complexity to test for every ∈ and ∈ whether holds, which is unfeasible for large data sets.
In geospatial context, and are geometries in a two dimensional space, and the links may be based on proximity or on topological relations. In the latter case, relations are expressed by the Dimensionally Extended nine-Intersection Model (DE+9IM) [17,18], which was accepted as an ISO standard [19]. DE+9IM classifies binary spatial relationships two between geometries, and , which may be points, lines, or polygons, based on intersection of interiors (I), boundaries (B) exteriors (E) of with those of .
A combination of these six geometric parts/features define topological relations, which are described in a 3 × 3 matrix as follows: The intersection of some feature of with a feature of the , may be either empty or in itself a geometric object, namely: a point, a line, or a polygon.
( ) returns the dimension of the geometry ; if consists of multiple geometries then ( ) is the maximal dimension of intersection if it is a of multiple parts.
0 if contains at least one point, but no lines or polygons 1 if contains at least one line, but no polygons 2 if contains at least one polygon In addition to the dimensions values the matrix may contain the values ( ( ) ≥ 0), ( ( ) = −1), and * ("don't-care" value, which means that the value in this matrix cell has no influence on the outcome of a function applied to this matrix). The model defines topological predicates to describe the spatial relations between the two geometries in a compact and human-interpretable manner, which are defined by pattern matrices: equals, disjoint, intersects, touches, crosses, overlaps, within, and contains. For example, the pattern matrix for the relation within is defined by the following pattern matrix 1

Related Work
Link discovery of topological relations among RDF data sets has received growing interest in recent years, and various methods for this problem have been proposed. These methods usually define the topological relations between two 1 see also Strobl [20] geometries based on their relations computed between their minimum bounding boxes. A minimum bounding box (MBB) is the rectangle of minimum area that encloses all coordinates of geometry and is a commonly used as an approximation to the geometry to reduce computational costs that involve this geometry [21]. Smeros and Koubarakis [22] use the MultiBlocking technique [23] to discover topological relations. This technique divides the earth surface into curved rectangles, and assigns each geometry to all blocks in which it intersects, based on the geometry's MBB. Relations discovered within each block are then aggregated to construct the links. This method is embedded in the Silk framework [24].
RADON [25] divides the space into hyper-cubes and uses optimized sparse space tiling to index geometries. This is done by mapping each geometry to the set of hyper-cubes over which it's minimum bounding box (MBB) spans. The method first indexes geometries ∈ and then only index geometries ∈ that may potentially reside in hypercubes already contained in the index. To minimize the size of the index, the method implements a swapping strategy, that is, prior to the indexing phase it calculates an estimated total hypervolume ( ℎ) for each of the datasets and . If ℎ( ) < ℎ( ) then it swaps the two datasets and computes the reverse relation of the requested relation . The link generation itself is done using a method that reduces computations on a subset of DE+9IM relations. RADON is implemented as part of the LIMES framework [26] Faria et al. [27] adapt the AgreementMakerLight (AML) [28], a framework for automated ontology matching, to tackle the task of topological relations. This is done by utilizing ESRI Geometry API 3 , which uses quadtree as means to index geometries and detect topological relationship among them.
These methods, as well as OntoIdea [29], were evaluated on several sets of geometries: Achichi et al. [30] apply them to discover topological relations between LineStrings, constructed of trajectories from the TomTom 4 dataset. [31] apply these methods to find relations between LineStrings to LineStrings and between LineStrings to Polygons, from TomTom dataset and Spaten dataset [32] respectively. All datasets included at most 2000 instances. Both evaluations report that the methods mentioned above discover links correctly, that is, the -score of most of them is 1.0 (apart from OntoIdea which -score lies between 0.91 and 0.99, and did not take part in the tasks for link discovery between linestrings and polygons).
Strabon [33] is an open-source geospatial RDF store. It is based on the RDF4J (previously Sesame) RDF store and adds geospatial capabilities to it by implementing the OGCstandard GeoSPARQL, where as part of the implementation the stored geometries in Strabon are indexed with an R-Treeover-GiST. Implementing GeoSPARQL means that Strabon includes topological functions; thus, queries that use these functions can be viewed as a means to discover topological relations. Sherif et al. [25] compares the performance of Silk, Strabon, and RADON where they are applied to discover links between different subsets of NUTS and CORINE Land Cover 5 datasets, which map land and land-usage re-spectively. The biggest dataset used in their experiments is of size 2, 209, 538.
The evaluations compare the running times of these methods with different dataset sizes. It has already been acknowledged that a significant portion big data is geospatial data [34,35], thus our interest lies in the performance of these systems on large datasets. Table 1 summarizes how well the methods described above perform, regarding the criteria for useful geospatial link discovery systems, discussed in Section 1, as reported in the literature [25,30,31].
As can be observed in Table 1, the LIMES system, that implements RADON, was the one who completed all the link discovery task for all topological relations and performed best for most of them. We, therefore, take LIMES as our main reference point. Nevertheless, LIMES as it is 6 , is not sufficiently flexible to accommodate geospatial data of different formats, and requires external pre-processing of input. Additionally, LIMES assumes an error-free download and curated data-sets, which is not always the case in reality. This motivates us to incorporate advantages of existing techniques in a single solution and test what existing technologies might be used for an efficient, flexible, robust and interoperable system for on-the-fly semantic linking of geospatial data.

Geo-L
As shown, LIMES performs the geospatial linking tasks very well, but lacks flexibility and accurate error handling. Starting as an experiment, we do not expand LIMES for this special case of linking big geospatial data (LIMES is the state-of-the-art tool for various kinds of link discovery tasks), but rather build a new geospatial linking tool to meet the requirements mentioned above. Our implementation focuses on allowing flexible input, short download and caching time as well as efficient link discovery.

Input
The input for a link discovery task provides the resources to be linked and the conditions upon which the links are generated, in a simple, yet flexible manner. In particular, our method offers a way to retrieve relevant properties from the endpoint via a SPARQL query; thus it natively supports manipulation of data, without any need for external pre-processing. This is useful, for example, when geometry values at the endpoint are not represented in a format that directly allows computations of topological relations.

Download
Downloading from a SPARQL endpoint might occasionally be interrupted before the complete dataset has been delivered. To avoid a total loss of the data our solution does not store all the data in memory while downloading, but instead, periodically write smaller chunks to disk. In addition, download might take a relatively long time due to application implementation itself. Our solution seeks to improve this state by reducing the application overhead when querying the remote endpoint.

Caching
To accelerate access to the source-and target-resources we incorporate a caching mechanism. Data retrieved from the SPARQL endpoint are stored in a central data store with an internal index. Further requests for data items from the same endpoint will be first served from the cache if the items are already indexed. This ensures a single local resource parallel to the endpoint, which serves arbitrarily many configurations, thus saves both time and storage. This differs from the behavior of LIMES, where data items may be downloaded multiple times, and duplicates of the data may be then stored. Algorithm 1 sketches the caching process. The method essentially compares the required triples range to the triple indices stored in an internal database, based on offset and limit parameters given in the configuration. It detects the indices of triples which are not already stored, retrieves the respective triples in chunks from the endpoint, and stores them in the database.

Link Discovery
The task of geo-links discovery requires efficient processing of spatial data, and therefore we use R-trees [36] as our underlying data structure. An R-tree is a data structure used to store and query multi-dimensional objects, in a way that and preserves spatial relations, as vicinity and nesting, among the indexed objects. An R-tree represents each object by its minimum bounding box (MBB), i.e., the smallest rectangle that encloses it, and a leaf node stores the MBB of that object and a pointer to the actual geometry. An R-tree is organized hierarchically; it groups MBBs by proximity and represents them by their MBB in a higher level of the tree. This process proceeds until all the MBBs are nested in a single bounding box -the tree root. R-Trees have shown to be efficient in processing spatial joins, to find topological relations between different data sets [37]. R-Trees support both individual elements search as well as range search, where all the items within a rectangle are retrieved.
A practical problem occurs when the data contain errors, i.e., invalid geometries. The implications of using such data are wrong results, application performance issues, etc. For this reason, geometries are examined before indexing; invalid geometries are not indexed, and thus do not participate in the link discovery.

Implementation
We use Python as our preferred programming language, since it became the language of choice for data science in general, and provides useful tools for handling geospatial data, in particular. We have experimented with the following technologies:

GeoPandas
Our initial implementation involved custom built caching and mapping mechanisms. We use Python's GeoPandas library [38], which implements data structures for storing geometric types, as well as analysis tools for geospatial data. In particular, GeoPandas provides an interface for spatial joins, which allow combining observations stored in these data structures based on their spatial relations. For this purpose GeoPandas indexes geometries using R * -Tree [39], a variant of R-Tree that provides better search performance, at the cost of increased construction time. GeoPandas currently supports finding the following spatial relations: within, intersects, and contains.

PostgreSQL
Furthermore, we implement the system using PostgreSQL, an open source object-relational DBMS, with PostGIS extension, which provides functionality to manage geospatial data, such as geometry data types, efficient indexing, and spatial joins, and is compliant with the Open Geometry Consortium (OGC) OpenGIS specifications. PostGIS implements spatial indexing with an R-Tree-over-GiST [41]. GiST, Generalized Search Tree [42], is a height-balanced tree structure and allows arbitrary indexing schemes. The choice to use this as the backend of our is multi-fold: • The database facilitates the implementation of the resource caching mechanism • GiST indexes are "null safe", therefore attempting to build an R-Tree on data which contains an empty geometry field will fail.
• GiST uses a compression technique which results in fast indexing.
The source code of Geo-L is available at https://github. -data or server error interrupt whole process + can be applied as part of a framework or as a part of an application via its API + achieves the best run-time performance for most of the topological relations (except intersect, and touches)

com/DServSys/Geo-L
-strict linkage definition (XML), no direct SPARQL support Table 1 Comparison of properties of systems for geospatial link discovery

Datasets
The evaluation has been done by finding different relations between points to polygons, and polygons to polygons in the following datasets.
• SPOI -Smart Points of Interest: A data set, which contains over 30 million Points of Interest important for tourism around the world [43].
• OLU -Open Land-Use: Maps land use on local and regional level; contains over 11 million geometries -Polygons and MultiPolygons [44].
• NUTS -Nomenclature of Territorial Units for Statistics: A standard for referencing European countries and their regions, for statistical processes [14]. We compare the performance of LIMES and Geo-L with respect to both topological relations discovery and data retrieval time from endpoints.

Experiments
The performance of the Geo-L systems is evaluated in terms of runtime by conducting experiments on simulations test-sets as well as real-world scenarios. In order to compare the performance of our system with that LIMES, which is implemented using parallel processing. The task is viewed as consisting of two stages: download and caching, and linking; we report the performance for each of them. The simulations enable evaluation of system performance under realistic conditions, with scenarios which otherwise might not be explored, and at the same time providing reliable way confirm their results. All experiments have been performed on a 64-bit Linux machine with an Intel Core i7-7800X CPU @ 3.50GHz and total of 12 threads (6 CPU cores × 2 threads per core).

Simulation
Our simulations consist of finding topological relations where the subsets of OLU dataset are used as both source and target datasets. This setting has multiple advantages: First, it allows to demonstrate the benefits of caching, regarding data sets retrieval. Additionally, the structure of the OLU set, which consists of separate geometries with nonhierarchical relations, facilitates the link quality evaluation. We used this approach to perform a preliminary comparison of three implementations on a subset of 165,000 entities (as source and target sets) and observed that the implementations which used GeoPandas performed considerably slower than the one which employed PostgreSQL with Post-GIS. For example, the mapping time required for calculating the within relation was 38 seconds for the implementation which used GeoPandas, about 20 minutes for the GeoPandas cython implementation, and less than 4 seconds for the implementation which used PostgreSQL. Therefore, in the following experiments, the latter serves as our reference system.
We tested the systems with two subsets: the one contains the first 165,000 geometries, and the other the first 400,000 geometries. Figure 1 compares the dataset the retrieval times of OLU subsets for both LIMES and Geo-L. The first scenario shows that retrieval time for LIMES is about twice as long compared to Geo-L. The reason is that LIMES does not detect whether data already exist, and download the same OLU subset twice, both as source and target datasets. The second scenario emphasizes this phenomenon: Whereas Geo-L retrieves the data which has not already been downloaded yet, and does it only once, LIMES retrieves twice the subset of 400,000 geometries, which takes more than six times longer.
Moreover, LIMES stores redundant data e.g., the subset of the first 165,000 geometries is store four times, as it is contained in the 400,000 geometries subset.
Experiments have been repeated ten times for each topological relation type per subset, and the average mapping times are shown for both LIMES and Geo-L in Figure 2 and Figure 3. As can be observed, Geo-L discover topological links faster than LIMES, for all relations in these experiments. The coefficients of variation (CV) of runtimes for the different experiments were found to be low in all cases (CV < 0.1), which indicates that these results are consistent.
In addition, we found discrepancies between the links discovered by each system. For example, when looking for links of entities which stand in the equals relation in two sets with identical entities, the expected result is that each item in the source set would stand in this relation with exactly one entity of the target set, and that the size of the returned set would be equal to the size of each of sets. However, for the 165 ⋅ 10 3 OLU subset Geo-L found 164, 935 links, whereas LIMES found 157, 513. The 65 entities which Geo-L did not include had invalid geometries, which were detected already during construction and omitted from the search space. We examined the result computed by LIMES and noticed errors were mostly "false negatives", i.e., valid geometries which were omitted from the result set. Also, there were also "false positives", i.e., invalid geometries, which were included in the result set. Similar errors occurred also for other topological relations.

Real-World Scenarios
We experiment with topological relation discovery between pairs of geospatial resources mentioned in Section 5.1,   and compare their performance to that of LIMES. Figure 4 shows the performance, in terms of mapping runtime, on different subsets of SPOI and OLU. In this example the largest subset does not contain the other two: the first 500 ⋅ 10 3 entities of OLU contain geometries which caused LIMES system to crash, and therefore we chose a subset of the same size but specified a different offset. Figure 5 shows the running times for mapping SPOI to NUTS with different subset sizes of SPOI. Since NUTS geometries are not represented in WKT format we used a configuration feature which defines a resource via a SPARQL query. In this case, the query also transforms the geometries into the required format. This, however, is not possible in LIMES, and therefore comparison of the systems is not presented.

LIMES Geo-L
Figrue 6 shows mapping runtime for different subsets of OLU to NUTS, for different topological relations.  165 400 500

Conclusions
This paper presented Geo-L, a system for discovering RDF links between geospatial entities, based on topological relations. We conducted experiments to detect topological relations between points and polygons, and between polygons and polygons. The experiments show that Geo-L outperforms LIMES [26], a state-of-the-art link discovery system, for this task in several aspects: • Scalability and efficiency: Geo-L configuration allows to form a dataset directly by the SPARQL query that defines it. This feature is, in particular, useful when data at the SPARQL endpoint are stored differently than specified for the linking task, but could be transformed into the required format through SPARQL functions.
-Download time: Datasets are cached not for a single task but are regarded as resources of their own. Thanks to its caching mechanism, Geo-L accesses the SPARQL endpoints only when data required in the dataset are missing, and expands existing datasets where possible.
-Mapping time: Geo-L utilizes PostgreSQL with PostGIS index for storing and indexing of the data. This enables efficient spatial joins between source-and target-datasets.
• Robustness: Geo-L includes multiple features that strengthen the robustness of the application.
-Caching: Geo-L caches portions of the data as they are downloaded, rather than writing the whole dataset after being downloaded. This property prevents data loss when, e.g., connection to the remote endpoint is lost. -Mapping accuracy: Geo-L detects entities with invalid geometries (compliant to OGC OpenGIS specification) and does not include them in the search space. In addition, in several cases LIMES did not include valid geometries in the result set, whereas Geo-L correctly did.
• Interoperability and flexibility: Geo-L can be used as a stand-alone application or as a REST service (in a docker), which allows it to be integrated with other applications. The easy SPARQL-based and slim set-up of target and source configuration (as JSON) enables a very free usage of the tool.
Future work will examine relations between other types of geometries as well as explore geospatial relations based on various distance measures. The current implementation recalls the same items for each dataset once they are cached. In the future we will also address re-caching in case data at the SPARQL endpoint have been modified, an issue which is, to the best of our knowledge, not handled by other geospatiallinking systems.