Could spatial features help the matching of textual data?

Abstract

Textual data is available to an increasing extent through different media (social networks, companies data, data catalogues, etc.). New information extraction methods are needed since these new resources are highly heterogeneous. In this article, we propose a text matching process based on spatial features and assessed through heterogeneous textual data. Besides being compatible with heterogeneous data, it comprises two contributions: first, spatial information is extracted for comparison purposes and subsequently stored in a dedicated spatial textual representation (STR); and then two transformations are applied on STR to improve the spatial similarity estimation. This article outlines the proposed approach with new contributions: (i) a new geocoding methods using general co-occurrences between entities, and (ii) a thorough evaluation followed by (iii) an in-depth discussion. The results obtained on two corpora demonstrate that good spatial matches ( $\approx$ 80% precision on major criteria) can be obtained between the most similar STRs with further enhancement achieved via STR transformation.

Keywords

Textual data heterogeneity text matching graph matching spatial similarity

1. Introduction

Significant growth in textual data has taken place over the last decade as a result of the rapid propagation of information systems and “computerization of society” [37]. Governments and companies such as Google, Twitter and Facebook provide users with access to huge amounts of textual data for them to plod through. Textual data volumes and their heterogeneity are thus markedly increasing. Textual data heterogeneity is reflected by the variety of file formats, structures (press article vs. thesis), syntax (SMS vs. official statement), language, and vocabulary (tweet vs. technical manual). Improved heterogenous textual data management thus enables access to new information or new information perceptions (statistical, sociological, political, etc.). Among these improvements, the computation of similarity [12] between such resources benefits many methods such as automatic summarizing [28], document classification, and ETL (extract-transform-load) [62]. Another improvement involves retrieving a similarity gradient based on different dimensions [32, 48] such as theme, time, and space to, for example, provide access to new analyses of events such as natural disasters [5, 54] or elections [61]. In this article, we focus on the data matching task [13].

A wide range of methods are already available to match structured heterogeneous data [44, 16, 35], but a few of them also cover unstructured data. Furthermore, little has been done to date to address the spatial similarity between heterogeneous textual data [47]. Here, we discuss the heterogeneous textual (structured and unstructured) data matching through the spatial dimension. In this paper, spatial text matching aims to return documents with a high spatial similarity for each document. Moreover, heterogeneity in textual data is based on the variety of content (structured, unstructured, mixed), format (open, proprietary) vocabulary (tweet vs academic literature), and languages. Therefore, a common representation for each document is required. Generally, proposed representations [67, 3, 33, 48] are based on toponyms, “a general name for any place, geographical entity, or topological feature. associated information (e.g. geographical footprint)” [26]. In addition to geoparsing,1

¹
Identication of toponyms errors.

spatial conception is subjective and information (e.g. toponyms) can be missing due to a perception or a context known only to the writer and reader. Text features combined with spatial information are therefore needed to obtain accurate information necessary to extract a complete spatial representation.

To address the issue of matching heterogeneous textual data, we present our text matching framework based on preliminary work published in [24]: (i) the general workflow, (ii) STR generation for a document, (iii) the document association process using graph matching algorithms, and (iv) the evaluation protocol based on 4-criteria to assess the association quality. The new contributions in this article are:

Extensions of the methods used to generate STR: (i) WikiCooc, a new geocoding method using spatial entity co-occurrences detected in a Wikipedia corpus; and (ii) integration of a baseline geocoding method, i.e. Mordecai[29].

An in-depth evaluation of geoparsing and matching algorithms followed by discussions of the results.

The article is organized as follows. In Section 2, we introduce related work on spatial representation of text and their comparison. In Section 3, we detail the overall text matching process based on spatial features. In Section 4, we present our experiments and results. Finally, in Section 5, we discuss our results and conclude in Section 6.

2. Related work

Considerable works on the exploitation of spatial information in texts have been carried out using geographical information retrieval (GIR), an extension of Information Retrieval that focuses on the geographical dimension of data. While most of GIS (Geographic Information Science) contributions are based on structured data stored in geographic databases, the GIR is particularly interested in the use of unstructured documents on the Web [30]. The exploitation of the geographical information of this data is faced with several obstacles such as the detection of geographical references (toponyms) in documents, the link between these references, a geographical representation of documents, the indexing of documents, the definition of new measures of similarity and the evaluation of search engines [30]. Most of the GIR approaches are based on the extraction and resolution of toponyms (place name) in textual data [67, 3, 33, 48]. In [67], the authors propose to generate a representation based on the aggregation of the polygons of each place mentioned in a document. In [3], the authors propose a document representation according to a geographic focus; i.e a central place connected to the other places mentioned in a document, e.g. $\textit{focus(Paris, Cherbourg, Montpellier)}=\textit{France}$ . Like [3], the authors of [34] introduce a geographic information search system, STEWARD, based on the creation of a geographic focus. Unlike [3], the definition of focus is based on the structure of the document. Here, a place is defined as a geographical focus if it co-exists with as many places as possible in the same document. Finally, in [48], the authors present an Information Retrieval (IR) system, called SPIRIT, based on an indexing method using a spatial grid. Each cell in the grid corresponds to a bounding box delimited by coordinates on the globe. A cell is associated with a document if it has a spatial footprint.

Other methods in the language modeling domain [53, 66, 39], use the entire document to determine its spatial footprint. A language model is represented by a probability distribution of word sequences in a document. For an IR system, it defines $P(Q|D)$ the probability of the terms of a query $Q$ being associated with a document $D$ . In a spatial context, these approaches are used to calculate the probability $P(Q|(D,E)$ that the terms of a query $Q$ appear in a $D$ document associated with $E$ , a geographic footprint (point, region, polygon).

One of the obstacles to the proposed GIR approaches rests on the identification and resolution of toponyms (geoparsing). To this end, other approaches to spatial analysis in the documents are based on qualitative analysis. The Qualitative Spatial Reasoning is a sub-domain of knowledge representation based on the definition of qualitative spatial relationships. These qualitative relationships, or Qualitative Spatial Calculus[65], connect different objects from a particular domain. Among the proposed representations, the Qualitative Constraint Network (QCN) links different entities according to qualitative spatial relationships. Among the relationships used are topology (e.g. included in, equal), distance (e.g. near, far), orientation (e.g. north of, opposite) [51, 2] or mobility[68]. These structures enable users to be independent of georeferencing or any knowledge base, but the relation consistency – e.g. if A is north of B, B is north of C, C cannot be north of B – must nevertheless be checked and, depending on the graph density, this process could be expensive [64]. Various contributions rely on such representations. The authors of [64, 2, 40] generate such representations in the analysis of a route description or a specific location. Once generated, these representations can be analyzed and matched to geographic data in a GIS database [64, 2, 55]. Other approaches [8, 64] propose to generate new representations (i.e. map). Using a spatial ontology, the authors of [8] propose to build a spatial network to generate a map.

In the definition of a matching process based on spatial features, the definition of similarity between two documents is crucial. The geographic similarity notion applied in many articles [48, 7, 41] are based on Tobler’s [60] first law of geography: “everything is related to everything else, but near things are more related than distant things”. In addition, an extension of Tobler’s work in [41] illustrates the importance of the feature effect which implies that two places are spatially similar if they belong to a same feature (e.g. cluster). Based on these contributions, we defined three spatial similarity criteria. The first criterion indicates that matched documents should share spatial entities. The second criterion states that two documents spatially similar should have closed spatial entities. Finally, the third criterion states that similar clusters of spatial entities maximize the spatial similarity.

According to this hypothesis, we based our text matching process on a representation generated from two complementary features. The first feature is the spatial entity, a reliable spatial indicator which comes with additional data and enables to detect shared spatial references between documents. Then, for encoding the topology, spatial entities are connected using spatial relations that make emerge features such as clusters.

3. A text matching method based on spatial features

According to the previous assumptions, we designed a text matching process [24] divided into two steps as illustrated in Fig. 1. The first step, i.e. georepresentation, produces a common representation of a document, while in the second so-called geomatching step, the generated representation is compared using appropriate similarity measures. In the following subsections, we first present and define the essential notions underlying this contribution (see Section 3.1), then each step is described in Sections 3.2 and 3.3.

Table 1
Information associated with a spatial entity

Field	Source	Example value
Unique ID	Generated	GD1286273
Labels	Wikidata	fr: Cologne, de: Köln, etc.
Administrative Boundaries	OpenStreetMap	[[0,1],[1,0], …]
Coordinates	Wikidata	(6.95,50.94)
Class(es)/Concept(s)	Geonames	(P, PPLA) ${}^{}$*
Spatial relationships	Wikidata	included_in(Germany)

${}^{*}$ Seat of a first-order administrative division.

Figure 1.

Text matching process using spatial features.

3.1 Notions

3.1.1 Spatial entity

A spatial entity designates an entity located in a defined space [11] and associated with name, or toponym, and additional information – coordinates, country, boundaries, etc. – collected from a georeferential [23]. Table 1 shows an example of the information associated with a spatial entity.

3.1.2 Spatial relation

A spatial relation connects two entities based on spatial properties, e.g. adjacency, inclusion and distance. Prades-Le-Lez and Montpellier, for instance, are two spatial entities in the South of France that share an adjacency relation due to their geographical demarcation.

3.2 Stage 1: Georepresentation

A common representation which integrates extracted features is required for comparisons. To this end, we propose to represent spatial features in the spatial textual representation2

²
A python module that implements the STR is available at: https://gitlab.irstea.fr/jacques.fize/str-python.

(STR) [22]. STR is a graph structure generated from text features, i.e. toponyms, as well as from available spatial information on external resources, i.e. a gazetteer. An STR is composed of two components: spatial entities, i.e. vertices, and spatial relations, i.e. edges.

Based on a document, an STR is generated through a two-step process, as illustrated in Fig. 2. First, we identify toponyms and link them to a georeferential identifier in the so-called geoparsing step. The second geocompletion step improves the representation by adding spatial relations and modifying spatial entities. Both steps are defined in Sections 3.2.1 and 3.2.2.

Figure 2.

Illustration of the georepresentation process for a document.

3.2.1 Geoparsing

Fundamentally, an STR is generated on spatial entities, thus spatial entity extraction, or geoparsing, is essential. The geoparsing process extracts spatial entities in the document through a two-step process (see Fig. 2). First, toponyms are tagged in the text (geotagging) and then tagged toponyms are linked to a georeferential identifier and they become spatial entities (geocoding).

Geotagging identifies toponyms (or place names) in text via different methods from the named entity recognition (NER). NER methods aim to identify units in text such as person, organization, date, and finally location. These methods can be separated into two categories: rule-based [58, 27] and machine-learning [17, 1] approaches. The major error that arises in geotagging is the geo/non-geo[3] confusion, where a non-geographical object, e.g. a person, may be detected as a geographical entity, e.g. Merkel,Texas (a city) vs. Angela Merkel (a German politician).

Using toponyms detected during the geotagging process, geocoding[40, 38, 39, 46] associates each toponym with a corresponding entry in a georeferential. For example, in the following sentence “Paris is the capital of France”, Paris will be associated with the identifier GD5400765 and France with GD3117352. The main difficulty in geocoding based on toponyms is referent ambiguity [48], when there are multiple associations of a toponym with spatial entities. Toponym geocoding is carried out in two phases. First, potential candidates for each toponym are selected from a georeferential. Second, a candidate from each group is selected by using a disambiguation algorithm.

Here, we compare the following disambiguation algorithms:

•
MostCommon. This simple yet intuitive algorithm uses the commonness of an entity to disambiguate toponyms, e.g. Paris is mostly associated with Paris, France. A spatial entity is selected based on a specific criterion that quantify the commonness of an association. For example, [57, 50] propose to use statistical criteria such as the demography. Here, the commonness of each entity is a page rank [43] value computed on the Wikipedia corpus [59]. For example, the toponym Paris is associated with several spatial entities including Paris,FR and Paris,TX. Since the page rank of Paris,FR is equal to 4712 and the one of Paris,TX is equal to 3.27, the algorithm will associate Paris,FR with the toponym Paris.
•
SharedProp. Even though MostCommon is intuitive, the most common entity associated with a toponym sometimes may not be spatially consistent with other entities in the text. Based on the disambiguation of the toponym Paris, Paris,FR is the most frequent outcome. However, there is a possibility that Paris,FR may not be spatially consistent with the rest of the entities in a document. For example, in a document that contains the spatial entities Brookston,TX, Powderly,TX (cities in the state of Texas), the spatial entity Paris,TX is more consistent.

Inspired by [31], we propose an approach [23] that selects an entity based on its spatial proximity with fixed entities, i.e. they do not share their toponym with other entities. Spatial proximity is based on identified relations between entities, e.g. belong to or is close to, etc. Then, each ambiguous toponym is associated with the one having the highest similarity. The whole process is illustrated in Fig. 3.

Figure 3.
SharedProp disambiguation algorithm with Paris.

•
WikiCooc. The SharedProp disambiguation algorithm is born out of the necessity to obtain spatial consistency between the entities identified in a document. However, it happens that spatial entities in a document do not necessarily share a spatial proximity relationship but a contextual proximity. For instance, Paris,FR and New York City are two entities mentioned regularly in different medium (encyclopedia, press, etc.). In [15], the authors use geocoded documents3
³
Here Wikipedia article associated with coordinates.

to compute the probability of words associated with a region on the surface of the globe. Apart from performing outstandingly, Delozier’s approach allows geocoding of toponyms/document without requiring a georeferential, which for historical documents is crucial because of the lack of past geographical information. We consider that this approach requires the storage of all co-occurrence values is a drawback because it can be expensive, depending on the number of variables, i.e. in this case, the number of words in a corpus and regions.

In our work, we are dealing with contemporary documents and the use of co-occurrence data between spatial entities in our gazetteer is sufficient. Therefore, we propose a similar approach, WikiCooc, which relies solely on the frequency of co-occurrences between spatial entities. We use Wikipedia to recover spatial entity co-occurrences using the internal links.4
⁴
Internal link refers to another entity URI in Wikipedia.

The disambiguation algorithm WikiCooc is a two-step process. The first step consists in generating a co-occurrence graph integrating the frequency of co-occurrences between each of the spatial entities candidates of toponyms in a document. For example, Fig. 4 illustrates the resulting graph for the following toponyms: Paris, Cherbourg, Montpellier. In this graph, spatial entities are represented by vertices and edges that integrate co-occurrence values with each other. Once the graph is generated, the second step consists in measuring the weighted degree of each vertex, i.e. candidate spatial entities. In graph theory, the degree of a vertex corresponds to the number of incident edges. The weighted degree of a vertex corresponds to the sum of incident edges weights. In the graph of Fig. 4, the weighted degree $w$ of the vertex Paris,FR is equal to $w=5+5=10$ . Finally, for each toponym, the candidate spatial entity with the highest weighted degree is selected.

Figure 4.
Co-occurrence graph generated in the WikiCooc disambiguation algorithm.

•
Mordecai. Finally, we compare previous methods with an existing geocoding algorithm recently presented in Mordecai[29]. Mordecai is a geoparsing system which use the Spacy library for geotagging and a language-agnostic architecture for inferring the correct entry of each spatial entity in a text. At the end of the process, each toponym is linked to an entry from the Geonames gazetteer.

Candidate selections. To select the candidates for a toponym, we use a dedicated georeferential called Geodict,5
⁵
Geodict is available at: https://dx-doi-org.web.bisu.edu.cn/10.18167/DVN1/MWQQOQ.

that contains various information (name, coordinates, class, etc.) for each spatial entity stored. Geodict[23] is a gazetteer generated from three sources, i.e. Wikidata, OpenStreetMap and Geonames. Each entry is associated with the information provided in Table 1. For Geodict queries, data is stored in a DBMS6
⁶
Database management system.

called ElasticSearch.7
⁷
https://www.elastic.co/fr/products/elasticsearch.

Candidate selection is based on three types of query: the first one returns entries which toponym fit as it is in the document; the second query returns entries with an alias equal to the toponym; and finally, the third one returns entries similar to the toponym based on string similarity. The latter helps overcome toponyms errors, such as missing capitals (prades-le-Lez vs Prades-le-Lez) and missing words (Region Alaotra-Mangoro vs Alaotra-Mangoro).
3.2.2 Geocompletion

Once the spatial entities are extracted, the related spatial information may be incomplete. We designed the geocompletion process to fill in the missing information. First, we extract and integrate spatial relations between available entities, which gives the STR its first form, then we transform the STR to increase the probability of finding common features between two STRs.

In the first step, we extract the spatial relation to highlight proximities between certain spatial entities in a text. This enables the use of topology-based comparison algorithms while improving the similarity returned by only comparing spatial entities. For example, if we have two STRs, i.e. $\textit{STR}_{1}=\{A\rightarrow B\}$ and $\textit{STR}_{2}=\{A\rightarrow C\}$ , both STR share a common entity A, along with a relation from A. In this approach, we use two spatial relations, i.e. inclusion and adjacency, e.g Paris is included in France and France is adjacent to Belgium. We use information from the Geonames hierarchy and Wikidata P1318

⁸
Located in the administrative territorial entity (P131).

property to extract the inclusion relations. As for adjacency relations, we use both the shape of administrative boundaries and the Wikidata P479

⁹

Shares border with (P47).

property.

Spatial entities may be omitted during the extraction process depending on the georeferential, the geoparsing process, or the data itself. To address this issue, we propose to fill in missing spatial features by applying the so-called STR transformation process.

For example, we have two very different STRs, i.e., $\textit{STR}_{1}=\{\textit{Clapiers, Montpellier}\}$ and $\textit{STR}_{2}=\{\textit{Caen, Cherbourg}\}s$ , two strictly different STRs. Intuitively, we notice that both STR entities share a common ancestor, i.e. France. We propose STR Abstraction process (see Fig. 5) to exploit these implicit similarities. This process abstracts all spatial entities up to a maximum level (department, region, country). Concretely, we replace each entity by one of its parents. For example, if the level is set at “department”, Cherbourg (city) becomes Manche (French administrative department), and Caen (city) becomes Calvados (French administrative department).

Figure 5.

An illustration of a STR (left) and its abstracted version (right). The gray arrows symbolize the abstraction of spatial entites from the STR to its abstracted version. In this example, the abstraction limit is set to “département” (second administrative division in France).

However, STR Abstraction decreases the representation precision due to the new higher granularity. Therefore we propose to only extend low-impact spatial entities in a second transformation, i.e. STR Extension (see Fig. 6). Two features then characterize low-impact spatial entities: their low granularity (town, village, hamlet) and their low commonness score (see Section 3.2.1). Once identified, each spatial entity is linked to $n$ new and more “common” entities within a defined radius. For example, Clapiers, a small municipality located in the South of France, will be linked to Montpellier.

Figure 6.

An illustration of a STR (left) and its extended form (right). In the extended form, green vertices represent spatial entities added during the extension process. Here the extension parameter $n$ is set to $1$ .

In the next section, we present the methods used to match this type of representation.

3.3 Stage 2: Geomatching

We compute the spatial similarity through STR by using graph matching algorithms [25, 63, 18, 10] implemented in Gmatch4py,10

¹⁰
Available at: https://github.com/Jacobe2169/GMatch4py.

i.e. a Python library. Gmatch4py uses Cython, a Python-C++ binding dedicated library, thus reducing the algorithm execution times. In the following subsections, we present the two kinds of graph matching approaches used for STR comparison, and baseline methods to reveal the potential of our approach.

Table 2

Notations used in graph matching formulas

Graph attributes
$E_{G_{1}}$	edges of the graph $G_{1}$
$V_{G_{1}}$	vertices of the graph $G_{1}$
$\|G_{1}\|$	size of the graph (number of nodes) $G_{1}$
Graph edit distance
$\mathcal{P}(G_{1},G_{2})$	set of transformation applied to $G_{1}$ to become $G_{2}$
$C_{G_{1},G_{2}}$	cost matrix to pass from $G_{1}$ to $G_{2}$
$c(e_{i})$	cost of a transformation
Subgraph
$\textit{mcs}(G_{1},G_{2})$	maximum common subgraph between $G_{1}$ and $G_{2}$

3.3.1 Structure-based algorithms

Structure-based algorithms compare only graph attributes such as vertices, edges, edge attributes, etc. Among these algorithms, we compare the Vertex/Edge Overlap[45] (VEO), Maximum Common Subgraph[10] (MCS), a measure derived from the Jaccard Index (Jaccard), and finally different graph edit distance computations.

Since VEO, MCS and Jaccard are straightforward, we indicate their formula in Eqs (1)–(3).

$\displaystyle\textit{MCS}(G_{1},G_{2})=\frac{|\textit{mcs}(G_{1},G_{2})|}{% \textit{max}(G_{1},G_{2})}$ (1) $\displaystyle\textit{VEO}(G_{1},G_{2})=\frac{|V_{G_{1}}\cap V_{G_{2}}|+|E_{G_{% 1}}\cap E_{G_{2}}|}{|V_{G_{1}}|+|V_{G_{2}}|+|E_{G_{1}}|+|E_{G_{2}}|}$ (2) $\displaystyle\textit{Jaccard}(G_{1},G_{2})=\frac{|E_{G_{1}}\cap E_{G_{2}}|}{|E% _{G_{1}}\cup E_{G_{2}}|}\times\frac{|V_{G_{1}}\cap V_{G_{2}}|}{|V_{G_{1}}\cup V% _{G_{2}}|}$ (3)

The Graph Edit Distance (GED) [18] is the minimum cost for transforming a graph $G_{1}$ into a graph $G_{2}$ (see Eq. (4)). As the graph sizes and densities increase, finding the minimum cost can be expensive, so GED approximations have been proposed.

$\displaystyle\textit{GED}(G_{1},G_{2})=\min_{(e_{1},\ldots,e_{k})\in\mathcal{P% }(G_{1},G_{2})}\sum_{i=1}^{k}c(e_{i})$ (4)

According to [18], we opt to compare three GED implementations:

•

Bipartite Graph Matching (BP). This algorithm reduces the graph edit distance to an optimal assignment problem (OAP). Usually, OAP generally aims to assigned a set of workers to tasks based on their execution costs. Here both workers and jobs are replaced by vertices and $\epsilon$ . An assignment ( $\epsilon\rightarrow A$ ) is the insertion of the node A, and ( $B\rightarrow A$ ) the substitution of B with A. The Munkres algorithm [42] is used to find the optimal assignments. In this algorithm, assignment costs are integrated in a matrix $C_{G_{1},G_{2}}$ , like that illustrated in Fig. 7. The BP distance corresponds to the sum of the optimal assignments found by the Munkres algorithm.

Figure 7.

Example of cost matrix generated for the computation of BP between $G_{1}$ and $G_{2}$ .

In the example illustrated in Fig. 7, each transformation cost is set to 1. From the $G_{1}$ graph to $G_{2}$ , two transformations are required: (i) adding the vertex with the $C$ label and (ii) adding the edge $e=(B,C)$ . In $C_{G_{1},G_{2}}$ , the sum of the costs of these two operations is equal to 2 ( $\epsilon\rightarrow C$ ).11

¹¹

The insertion calculation of a node takes into account the addition of incident edges.

Therefore, the algorithm should return an editing distance equal to 2 between

G_{1}

and

G_{2}

. In this example, the value returned by the

B P

algorithm is well equal to 2.

•

BP-Greedy (BPG). Unlike BP, BPG opts for naive use of the cost matrix. BPG only takes the minimum value of each line. Each time, a minimum value is selected, its column is erased from the cost matrix.

•

Hausdorff Edit Distance (HED). HED is a graph edit distance derived from the Hausdorff Distance $H(A,B)=\textit{max}(\underset{a\in A}{\textit{max}}\text{ }\underset{b\in B}{% \textit{min}}\text{ }d(a,b),\underset{b\in B}{\textit{max}}\text{ }\underset{a% \in A}{\textit{min}}\text{ }d(a,b))$ .

3.3.2 Pattern-based algorithms

We propose to use pattern-based algorithms for geomatching in order to take advantage of the connectivity offered by spatial relations. Pattern-based algorithms compare graph based patterns such as the shortest path, community, etc. In this category, we choose the Bag of Cliques, an original graph representation, and the Weisfeiler-Lehman Subtree Kernel, an algorithm from the graph kernels.

Figure 8.

Example of bag-of-words representation.

Bag of Cliques exploits the connectivity represented by spatial relations. To this end, we propose to use the bag of words model (see Fig. 8) to vectorize graphs using cliques12

¹²

Highly connected subgraph.

as vocabulary units, i.e. each vector dimension corresponds to a clique found in the dataset. Once the vocabulary is built, we generate the feature vector with boolean values, i.e. contains this clique or not. An example is given in Fig. 9.

Figure 9.

BOC representation of a graph.

In addition, we selected the Weisfeiler-Lehman Subtree Kernel (WLK)[56] as part of pattern-based algorithms. WLK is part of graph kernels [63], a large graph matching family that propose efficient algorithms. Compared to standard algorithms, graph kernels exploit the topology of graph and can bridge the gap between the graph structure and machine learning algorithms such as SVM. Based on the Weisfeiler-Lehman isomorphism test, WLK iteratively renames vertices in both graphs based on their neighborhood. At the end of each step, the number of similar vertices found is added to the similarity value. WLK iteratively renames vertices based on their neighborhood, thus offering an efficient graph topology comparison method.

3.4 Baseline

In order to evaluate STR representations, we compare graph matching methods using the STR and baseline approaches detailed in the following subsections.

3.4.1 Bag of Spatial Entities (BOSE)

The first baseline approach called Bag of Spatial Entities (BOSE) uses the cosine similarity between document vectors consisting of the appearance of toponyms in the document.

3.4.2 Polygon Intersection (PolyIntersect)

The second baseline method uses the geometric property of spatial entities to compute the spatial similarity. To this end, we merge the geometry of each spatial entity within a STR, hence returning an unique geometry, i.e. a MultiPolygon. Then, the similarity between two STR corresponds to the intersection (see Fig. 10) area of their new geometry.

Figure 10.

Intersection area between two sets of spatial entities.

4. Experiments

We previously introduced a text matching process based on spatial features. In the following section, we present an experiment to assess the efficiency of this process. In the first subsection, we introduce each corpus used in the experiment and then we present the georepresentation and geomatching evaluation protocols and their results.

4.1 Datasets

4.1.1 PadiWeb corpus [49]

Padi-Web [4, 6] is an epidemiology surveillance system implemented by the French Agricultural Research Centre for International Development (CIRAD) in collaboration with the French National Institute for Agricultural Research (INRA). Padi-Web produces a classification and extracts information from unofficial sources (Google News) dealing with epidemics outbreaks in order to remedy delays in the publication of official decrees. A gold standard corpus composed of 442 documents has been built to assess the volume and accuracy of the extracted information.

4.1.2 AgroMada corpus [19]

In recent decades, CIRAD has been involved in developing sustainable agricultural practices in Madagascar and a significant amount of data, including theses, reports, technical manuals, field data and presentations, has been produced during this period. This corpus is highly heterogeneous compared to PadiWeb. The original corpus is composed of 13,742 documents in different file formats.

Based on this corpus, we selected documents corresponding to a specific thematic focus (agroecology) and location (Madagascar). We built two dedicated lists of terms to enable automatic document extraction. One is composed of terms13

¹³
Built from DicoAE (available at https://dicoagroecologie.fr/).

related to agroecology and the second consists of the 31 main towns in Madagascar.14

¹⁴

https://fr.wikipedia.org/wiki/Villes_de_Madagascar.

Documents not containing at least one term on the lists were discarded. The final corpus (called AgroMada) is composed of 5552 documents in English and French. Table 3 lists the file format frequencies in both the original and final corpora.

Table 3

File format frequencies

Format	Original corpus #	AgroMada corpus #
doc	6651	2163
docx	838	194
html	3465	791
pdf	1931	598
ppt	228	–
pptx	40	–
sql	1	–
txt	157	43
xls	2544	826
xlsx	126	35
xml	29	7

4.2 Georepresentation evaluation

Geoparsing is a decisive step in the georepresentation process and has a direct influence on geomatching. The geomatching quality increases with the geoparsing method reliability. We used documents in PadiWeb and in AgroMada to evaluate both geotagging and geocoding. Since the PadiWeb corpus comes with a full annotation of spatial entities, we used the whole corpus. As for AgroMada, we built a 232 document sample with annotated spatial entities [20].

4.2.1 Evaluation protocol

Regarding geotagging, a wide range of named entity recognition methods are implemented in software such as StanfordNER[36], Gate[14], NLTK[9] and Spacy15

¹⁵
https://spacy.io/.

and Polyglot[1]. For each method, we compute the precision, recall, and F-measure (see Eqs (5) and (6)).

$\displaystyle\text{precision}=\frac{\textit{TP}}{\textit{TP}+\textit{FP}}% \qquad\text{recall}=\frac{\textit{TP}}{\textit{TP}+\textit{FN}}$ (5) $\displaystyle\text{F-measure}=2\cdot\frac{\text{precision}\cdot\text{recall}}{% \text{precision}+\text{recall}}\quad\begin{array}[]{ll}\textit{TP}=\text{True % Positive; }&\textit{FN}=\text{False Negative;}\\ \textit{FP}=\text{False Positive; }&\end{array}$ (6)

Concerning geocoding, we evaluate each disambiguation algorithm (see Section 3.2.1) using three scores: accuracy (Acc), accuracy@k (Acc@k) and the average distance error (ME). The accuracy returns the exactitude of the spatial entity found. However, for a system to return the exact spatial entity is hard. Therefore we compute the accuracy@k, which considers that an entity found within a distance of less than a value $k$ from the expected entity is relevant. Lastly, we computed the average distance error (ME), i.e. the average distance between the expected entry and that found by the algorithm. Formulas for each score are indicated in Eqs (7) and (8).

$\displaystyle\textit{Acc(F,T)}=\frac{\sum\limits_{i=0}^{|F|}F[i]==T[i]}{|F|}% \quad\textit{Acc@k(F,T,k)}=\frac{\sum\limits_{i=0}^{|F|}\textit{dist}(F[i],T[i% ])<k}{|F|}$ (7) $\displaystyle\textit{ME(F,T)}=\frac{\sum\limits_{i=0}^{|F|}\textit{dist}(F[i],% T[i])}{|F|}\quad F=\text{Entity Found; }T=\text{Correct Entity}$ (8)

4.2.2 Results

For geotagging, Table 4 indicates the results obtained on both corpora. First, these results confirmed the apparent dependence of geotagging on the text structure. For example, we observed 30% difference in the precision of StanfordNER between the PadiWeb and AgroMada corpora. Second, the results showed that NER could produce a significant amount of false-positives, particularly with the Spacy system, despite the fact that this system identified most of the toponyms in AgroMada.

Table 4
Geotagging performance on the two samples

	PadiWeb			AgroMada
	Precision	Recall	F-measure	Precision	Recall	F-measure
StanfordNER	0.59	0.77	0.67	0.31	0.16	0.22
Polyglot	0.53	0.72	0.61	0.20	0.35	0.26
NLTK	0.42	0.66	0.52	0.13	0.15	0.14
Spacy	0.40	0.65	0.50	0.14	0.84	0.25

Concerning geocoding, Table 5 indicates the accuracy (Acc), accuracy@k(Acc@k) and the average error distance (ME) obtained by each algorithm (see Section 3.2.1) on samples from the two corpora. Surprisingly, these results revealed that the SharedProp and Mordecai spatial similarity based method were less efficient than context methods such as MostCommon and WikiCooc. Between MostCommon and WikiCooc, WikiCooc outperformed MostCommon in the AgroMada corpus and obtain equal performance in PadiWeb (slight increase of the average distance error for WikiCooc).

Table 5

Geocoding performances on the two samples

	PadiWeb				AgroMada
	Acc	Acc@0.5	Acc@1	ME	Acc	Acc@0.5	Acc@1	ME
MostCommon	0.71	0.84	0.85	2.43	0.94	0.97	0.97	0.49
SharedProp	0.66	0.78	0.79	4.82	0.88	0.89	0.90	3.36
WikiCooc	0.71	0.83	0.85	2.53	0.96	0.97	0.97	0.62
Mordecai	0.74	0.76	0.77	2.73	0.55	0.61	0.64	13

Based on previous observations, we estimated that Spacy combined with the WikiCooc geocoding strategy improved the completeness of STRs generated for a document. STR generated from both corpora are available on the CIRAD data catalog [21]. In addition, maps showing the spatial entity frequencies of each corpus are available in Appendix B (Figs 13 and 12).

4.3 Geomatching evaluation

In the previous subsection, we evaluated which geoparsing parameters maximized STR completeness. In this subsection, we evaluate the matching quality of the different geomatching configurations (algorithms, STR type) using a four-step evaluation protocol:

1.
Extract $n$ -most similar STRs from a sample of 100 documents
2.
Assess the matching quality using four criteria
3.
Measure the average performances obtained with the precision@n.

Before presenting the results, first we detail the criteria used to determine the quality of a match between two STRs. The four criteria are defined as follows:

1.
Shared Spatial Entities (SSE). This criterion is satisfied if the two STRs share at least one common spatial entity.
2.
Close Spatial Entities (CSE). This criterion is satisfied if one or more spatial entities share proximity with a different entity in the other STR. Proximity is induced by a short geographic distance or a spatial relationship such as adjacency or inclusion.
3.
Significant Spatial Coverage (SSC). Dense and significant groups of spatial entities located close to one another may be found in STRs. The criterion is satisfied if one of these groups is found in both graphs.
4.
Strict Spatial Coverage (SCSC). Distinct groups of spatial entities can be found in STRs. The criterion is satisfied if the spatial dispersion of these groups in both STRs is respected. The spatial dispersion is the configuration defined by the position of each group of spatial entities in a space (here geographic).

We then measured the matching performance using precision@n or $P @ n$ . Precision@n has been widely used in information retrieval to estimate the relevance of returned results to a query. Concretely, precision@n returns the percentage of relevant results among the top-n results. Here we computed the average precision@n or $A P @ n$ for each criterion, which led to the following formulas:

$\displaystyle\textit{AP@n (G,c)}=\frac{\sum^{N}_{i=1}\textit{P@n}(G_{i},c)}{N}$ $\displaystyle\textit{P@n}(G_{i},c)=\frac{1}{n}\sum^{n}_{k=1}\left\{\begin{% array}[]{ll}1,&\text{if}\ c(G_{i},G_{ik})\ \text{true}\\ 0,&\text{otherwise}\end{array}\right.$

where: $c$ satisfaction of a criterion; $G_{ik}$ the $k^{th}$ similar STR $G_{i}$ ; $N=|G|$ number of graph in $G$ .

Table 6 indicates the overall precision@k obtained by each graph matching algorithm. Then using criteria’s precision@k, we computed the Pareto Front, which determines the combinations (algorithm, STR type) that dominate the others. Tables 7 and 8 show the combinations of graph matching algorithms with STR types that form the Pareto Front. The BP (weight $=$ distance) corresponds to a version of the graph edit distance BP that includes the weight of the edges in the cost matrix computation. In this experiment, an edge that represents a spatial relation between two entities is weighted by the distance between them.

Table 6
Average Precision@5 obtained for each measure

Mesure PadiWeb AgroMada

SSE CSE SSC SCSC SSE CSE SSC SCSC

Baseline BOSE 0.91 0.27 0.90 0.42 0.96 0.25 0.59 0.49

PolyIntersect 0.83 0.40 0.89 0.25 0.58 0.47 0.73 0.12

S-Based ${}^{*}$ BP ${}^{**}$ 0.69 0.22 0.69 0.32 0.94 0.22 0.62 0.47

BP (weight $=$ distance) 0.69 0.22 0.69 0.32 0.93 0.21 0.95 0.47

HED 0.75 0.18 0.74 0.33 0.90 0.22 0.54 0.37

Jaccard 0.88 0.31 0.89 0.39 0.94 0.47 0.53 0.23

MCS 0.91 0.33 0.91 0.43 0.95 0.42 0.69 0.38

VertexEdgeOverlap 0.91 0.28 0.90 0.40 0.95 0.34 0.69 0.37

P-Based ${}^{*}$ BagOfCliques 0.76 0.25 0.75 0.28 0.89 0.30 0.62 0.36

WLK ${}^{**}$ 0.53 0.39 0.59 0.12 0.65 0.81 0.53 0.00

${}^{*}$ S-Based: Structure-based algorithms; P-Based: Pattern-based algorithms. ${}^{**}$ WLK $=$ Weisfeiler-Lehman Subtree Kernel [56]; BP $=$ Bipartite Graph Matching [52].

Table 7
Combination of measure and STR type forming the Pareto front (PadiWeb)

Measure Type SSE CSE SSC SCSC

VertexEdgeOverlap Bounded (Country) 0.83 0.33 0.88 0.40

PolyIntersect Normal 0.84 0.38 0.88 0.25

BP ${}^{}$ Extension ( $n=$ 1) 0.67 0.18 0.67 0.30

${}^{}$ BP $=$ Bipartite Graph Matching [52].

Table 8
Combination of measure and STR type forming the Pareto front (AgroMada)

Measure Type SSE CSE SSC SCSC

VertexEdgeOverlap Normal 0.97 0.31 0.97 0.36

MCS Extension ( $n=$ 2) 0.96 0.43 0.96 0.38

MCS Extension ( $n=$ 1) 0.97 0.42 0.96 0.37

Types of STR (transformed or not), MCS and VertexEdgeOverlap generally obtained high average precision@5 for all criteria. Therefore, structure-based algorithms proved to be efficient solutions for measuring spatial similarity through STRs. Tables 7 and 8 revealed the same behavior with MCS (AgroMada) and VertexEdgeOverlap (PadiWeb, AgroMada) along with the transformed version of STR. Tables 7 and 8 also revealed that almost all combinations (4/6) used the transformed version of STR. STR transformation thus had a positive impact on the matching quality.

If we compare these results to the baseline approaches, BOSE obtained the highest score in overall precision@5 on strict criteria (SSE, SCSC), but the score was lower than the fuzzy one (CSE, SSC). BOSE is thus less efficient for identifying common groups of spatial entities between STRs, unlike PolyIntersect, which increases specific criteria (i.e. CSE, SSC). Furthermore, based on Tables 7 and 8, PolyIntersect is part of the dominant combination but only in the PadiWeb dataset. As PolyIntersect uses polygons intersections to compute the similarity, its efficiency depends on the granularity formed by the spatial entities. For example, entities with a large polygon geometry, i.e. country, region and district, will have a higher probability of finding overlapping geometries. As illustrated in Fig. 11, PadiWeb contains a large proportion of country (A-PCLI), region (A-ADM1) entities, unlike AgroMada where populated places (P-PPL) prevail, hence illustrating the weakness of such approach on this type of corpus.

Figure 11.
Entity class distribution based on the Geonames classification.

Finally, based on the highest criteria scores of each Pareto front (Tables 7 and 8), we highlighted the good quality of the matched STRs using structure-based methods like MCS or VertexEdgeOverlap.
5. Discussion

Mesure	PadiWeb	AgroMada
Baseline	BOSE	0.91	0.27	0.90	0.42	0.96	0.25	0.59	0.49
	PolyIntersect	0.83	0.40	0.89	0.25	0.58	0.47	0.73	0.12
S-Based ${}^{*}$	BP ${}^{**}$	0.69	0.22	0.69	0.32	0.94	0.22	0.62	0.47
	BP (weight $=$ distance)	0.69	0.22	0.69	0.32	0.93	0.21	0.95	0.47
	HED	0.75	0.18	0.74	0.33	0.90	0.22	0.54	0.37
	Jaccard	0.88	0.31	0.89	0.39	0.94	0.47	0.53	0.23
	MCS	0.91	0.33	0.91	0.43	0.95	0.42	0.69	0.38
	VertexEdgeOverlap	0.91	0.28	0.90	0.40	0.95	0.34	0.69	0.37
P-Based ${}^{*}$	BagOfCliques	0.76	0.25	0.75	0.28	0.89	0.30	0.62	0.36
	WLK ${}^{**}$	0.53	0.39	0.59	0.12	0.65	0.81	0.53	0.00

Measure	Type	SSE	CSE	SSC	SCSC
VertexEdgeOverlap	Bounded (Country)	0.83	0.33	0.88	0.40
PolyIntersect	Normal	0.84	0.38	0.88	0.25
BP ${}^{*}$	Extension ( $n=$ 1)	0.67	0.18	0.67	0.30

Measure	Type	SSE	CSE	SSC	SCSC
VertexEdgeOverlap	Normal	0.97	0.31	0.97	0.36
MCS	Extension ( $n=$ 2)	0.96	0.43	0.96	0.38
MCS	Extension ( $n=$ 1)	0.97	0.42	0.96	0.37

Pattern-based algorithms shortcomings. We propose here a process for matching textual data using spatial features. These features are embedded in an STR, i.e. a graph composed of spatial entities linked by spatial relations. Unfortunately, the STR connectivity is low ( $\approx$ 0.35) especially in the PadiWeb corpus. The first reason for this low connectivity is the high granularity found in PadiWeb. Depending on the granularity level16

¹⁶
Villages, town, region, country or continent scale.

of a STR, the probability of two spatial entities sharing a relationship is either high (world scale, high granularity) or low (regional scale, fine granularity). The second reason concerns the low “spatiality” of documents characterized by a low average number of spatial entities per graph (

\approx

5). Consequently, algorithms such as Bag of Cliques or graph kernels using patterns are at a disadvantage. The addition of new relations to the STR should increase the efficiency of these algorithms.

Use of weighted relations. Among the compared algorithms, the BP graph edit distance performed quite well on the different criteria. As mentioned in Section 3.3.1, graph edit distances are based on the computation and the combined transformation costs to transform a graph G into a graph H. The cost for deleting a spatial relation does not change since the spatial relations are not weighted. To test the potential of weighted relations in the matching, we tuned the generated STRs by weighting each edge by the distance between spatial entities. The results in Table 6 are associated with the BP (weight $=$ distance) row. This new combination generated a 30% increase in the SSC (entity group detection) value compared to the original BP used on non-weighted STRs. However, this increase only occurred in AgroMada, and straightforward methods still outperformed this combination.

6. Conclusion

Here we proposed a text matching process based on spatial features and involving two steps. First we built a georepresentation for each document and then matched documents sharing high similarity using graph matching algorithms. To this end, we introduced spatial textual representation (STR), i.e. a graph structure composed of spatial entities connected by spatial relations (adjacency, inclusion). Graph matching algorithms were chosen and STR transformations proposed to improve the quality of matched documents so that this representation could be used for spatial text matching. Moreover, the STR generation process was designed and assessed on heterogeneous corpora in order to address the increasing heterogeneity of available textual data. One corpus was composed of news articles dealing with animal disease outbreaks, while the second consisted of various textual data regarding agroecology research in Madagascar. Finally, the results revealed high quality matching based on spatial features.

In future research, we aim to extend this process by integrating new features such as themes and times. Then we plan to define new similarity measures based on single or combined features, e.g. combining themes and spatial features by adding new relations (shared theme) between nodes. Finally, based on similarities found between documents, we are considering the possibility of enhancing spatial visualization of the contained information.

Footnotes

Acknowledgments

This research was funded by the SONGES project and the DigitAg institute. We wish to express our gratitude to Jean-Phillipe Tonneau (UMR TETIS) for his insights on the data used in this research. This work was supported by the French National Research Agency (ANR) under the Investments for the Future Program, referred to as ANR-16-CONV-0004.

Appendix

A. Geonames classification

Along with its dataset, Geonames proposes an exhaustive classification of places with 645 classes. Table 9 contains a sample of the whole Geonames classification.

Table 9

Sample of the Geonames classification

Class code	Class label	Description
A-ADM1	First-order administrative division	A primary administrative division of a country, such as a state in the USA
A-ADM2	Second-order administrative division	A subdivision of a first-order administrative division
A-ADM3	Third-order administrative division	A subdivision of a second-order administrative division
A-ADM4	Fourth-order administrative division	A subdivision of a third-order administrative division
P-PPLA	Seat of a first-order administrative division	Seat of a first-order administrative division (PPLC takes precedence over PPLA)
P-PPL	Populated place	A city, town, village, or other agglomeration of buildings where people live and work
L-CONT	Continent	Continent: Europe, Africa, Asia, North America, South America, Oceania, Antarctica
A-PCLI	Independent political entity	–

B. Spatiality associated with corpora

Figures 12 and 13 show the spatial entities within each corpus and their frequency.

Figure 12.

Spatial entity occurrence in PadiWeb.

Figure 13.

Spatial entity occurrence in AgroMada.

References

Al-Rfou

Kulkarni

Perozzi

and Skiena

, POLYGLOT-NER: massive multilingual named entity recognition, In Proceedings of the 2015 SIAM International Conference on Data Mining, Vancouver, BC, Canada, 30 April–2 May 2015, pp. 586–594.

Al-Salman

Dylla

and Fogliaroni

, Matching geo-spatial information by qualitative spatial relations, Proceedings of the 1st ACM SIGSPATIAL International Workshop on Crowdsourced and Volunteered Geographic Information – GEOCROWD ’12, 2012, pp. 38–45.

Amitay

Har’El

Sivan

and Soffer

, Web-a-Where: Geotagging Web Content, International ACM SIGIR Conference on Research and Development in Information Retrieval, 2004, pp. 273–280.

Arsevska

Roche

Falala

Lancelot

Chavernac

Hendrikx

and Dufour

, Monitoring disease outbreak events on the web using text-mining approach and domain expert knowledge, Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), May 2016, pp. 3407–3411.

Arsevska

Roche

Lancelot

Hendrikx

and Dufour

, Exploiting Textual Source Information for Epidemiosurveillance, Communications in Computer and Information Science 478 (October 2014), 359–361.

Arsevska

Valentin

Rabatel

de Goër de Hervé

Falala

Lancelot

and Roche

, Web monitoring of emerging animal infectious diseases integrated in the French Animal Health Epidemic Intelligence System, PLOS ONE 13(8) (2018), 1–25.

Ballatore

and Adams

, Extracting Place Emotions from Travel Blogs, In AGILE 2015 – Geographic Information Science as an Enabler of Smarter Cities and Communities, Lisboa, Portugal, 9–12 June 2015, pp. 1–5.

Belouaer

Brosset

and Claramunt

, From verbal route descriptions to sketch maps in natural environments, Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems – GIS ’16, 2016, pp. 1–10.

Bird

and Loper

, NLTK: the natural language toolkit, In Proceedings of the ACL 2004 on Interactive poster and demonstration sessions, Association for Computational Linguistics, 2004, pp. 214–217.

10.

Bunke

and Allermann

, Inexact graph recognition matching for structural pattern, Pattern Recognition Letters 1 (May 1983), 245–253.

11.

Casati

and Varzi

A.C.

, Spatial entities, In Spatial and Temporal Reasoning, 1997, pp. 73–96.

12.

Choi

S.-S.

Cha

S.-H.

and Tappert

C.C.

, A survey of binary similarity and distance measures, Journal of Systemics, Cybernetics and Informatics 8(1) (2010), 43–48.

13.

Christen

, Data Matching, Springer Berlin Heidelberg, 2012.

14.

Cunningham

, Gate, a general architecture for text engineering, Computers and the Humanities 36(2) (2002), 223–254.

15.

Delozier

Baldridge

London

and Tx

, Gazetteer-Independent Toponym Resolution Using Geographic Word Profiles, Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015, pp. 2382–2388.

16.

Demisse

Tadesse

Atnafu

Hill

Wardlow

Bayissa

and Shiferaw

, Information Mining from Heterogeneous Data Sources: A Case Study on Drought Predictions, Information 8(3) (July 2017).

17.

Finkel

J.R.

Grenager

and Manning

, Incorporating non-local information into information extraction systems by gibbs sampling, In Proceedings of the 43rd annual meeting on association for computational linguistics, Association for Computational Linguistics, 2005, pp. 363–370.

18.

Fischer

Riesen

and Bunke

, Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment, Pattern Recognition Letters 87 (2017), 55–62.

19.

Fize

, Bvlac corpus – extracted data, CIRAD Dataverse, 2018, doi: 10.18167/DVN1/8LIG1D.

20.

Fize

, Données pour l’évaluation de méthodes de géocodage, CIRAD Dataverse, 2018, doi: 10.18167/DVN1/KH7YTO.

21.

Fize

, Spatial representation of the bvlac and padi-web corpora, CIRAD Dataverse, 2018, doi: 10.18167/DVN1/JLXBLA.

22.

Fize

Roche

and Teisseire

, Spatial Textual Representation (STR) ou comment représenter la spatialité des donnnées textuelles, In Spatial Analysis and GEOmatics 2017, INSA de rouen, Nov. 2017, p. 14.

23.

Fize

and Shrivastava

, Geodict: an integrated gazetteer, Proceedings of Language, Ontology, Terminology and Knowledge Structures Workshop (LOTKS 2017), 2017, p. 11.

24.

Fize

Teisseire

and Roche

, Matching Heterogeneous Textual Data Using Spatial Features, 13th International Workshop on Spatial and Spatiotemporal Data Mining SSTDM18, 2018, pp. 1389–1396.

25.

Goyal

and Ferrara

, Graph embedding techniques, applications, and performance: A survey, Knowledge-Based Systems 151 (2018), 78–94.

26.

Gritta

Pilehvar

M.T.

Limsopatham

and Collier

, What’s missing in geographical parsing? Language Resources and Evaluation 52(2) (June 2018), 603–623.

27.

Habib

M.B.

and van Keulen

, A hybrid approach for robust multilingual toponym extraction and disambiguation, In Language Processing and Intelligent Information Systems, 2013, pp. 1–15.

28.

Hahn

and Mani

, The challenges of automatic summarization, Computer 33(11) (2000), 29–36.

29.

Halterman

, Mordecai: Full Text Geoparsing and Event Geocoding, The Journal of Open Source Software 2(9) (2017).

30.

Jones

C.B.

and Purves

R.S.

, Geographical information retrieval, International Journal of Geographical Information Science 22(3) (Mar. 2008), 219–228.

31.

Srihari

K.R.

Niu

and Li

, InfoXtract location normalization: a hybrid approach to geographic references in information extraction, In Proceedings of the HLT-NAACL 2003 Workshop on Analysis of Geographic References, 2003, pp. 39–44.

32.

Chen

Andrienko

and Andrienko

, Semantics-Space-Time Cube. A Conceptual Framework for Systematic Analysis of Texts in Space and Time, IEEE Transactions on Visualization and Computer Graphics, 2018, p. 18.

33.

Lieberman

M.D.

Samet

and Sankaranarayanan

, Geotagging with local lexicons to build indexes for textually-specified spatial data, In Data Engineering (ICDE), 2010 IEEE 26th International Conference on, 2010, pp. 201–212.

34.

Lieberman

M.D.

Samet

Sankaranarayanan

and Sperling

, Steward: Architecture of a spatio-textual search engine, In Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, GIS ’07, 2007, pp. 25:1–25:8.

35.

Zhao

and Yan

, Heterogeneous fuzzy XML data integration based on structural and semantic similarities, Fuzzy Sets and Systems 351 (Nov. 2018), 64–89.

36.

Manning

Surdeanu

Bauer

Finkel

Bethard

and McClosky

, The stanford corenlp natural language processing toolkit, In Proceedings of 52nd annual meeting of the association for computational linguistics: system demonstrations, 2014, pp. 55–60.

37.

Marek

, Integration Of Data From Heterogeneous Sources Using ETL Technology, Computer Science 15(2) (2014), 109-132.

38.

Martins

Manguinhas

and Borbinha

J.L.

, Extracting and exploring the geo-temporal semantics of textual resources, In Proceedings of the 2th IEEE International Conference on Semantic Computing (ICSC 2008), 4–7 August 2008, Santa Clara, California, USA, 2008, pp. 1–9.

39.

Melo

and Martins

, Automated Geocoding of Textual Documents: A Survey of Current Approaches, Transactions in GIS 21 (2017), 3–38.

40.

Moncla

Gaio

Nogueras-Iso

and Mustière

, Reconstruction of itineraries from annotated text with an informed spanning tree algorithm, International Journal of Geographical Information Science 30(6) (2016), 1137–1160.

41.

Montello

D.R.

Fabrikant

S.I.

Ruocco

and Middleton

R.S.

, Testing the First Law of Cognitive Geography on Point-Display Spatializations, In Kuhn

Worboys

M.F.

and Timpf

, editors, Spatial Information Theory, Foundations of Geographic Information Science, 2003, pp. 316–331.

42.

Munkres

, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics 5(1) (1957), 32–38.

43.

Page

Brin

Motwani

and Winograd

, The PageRank citation ranking: Bringing order to the web, Technical report, Stanford InfoLab, 1999.

44.

Pang

L.Y.

Zhong

R.Y.

Fang

and Huang

G.Q.

, Data-source interoperability service for heterogeneous information integration in ubiquitous enterprises, Advanced Engineering Informatics 29(3) (Aug. 2015), 549–561.

45.

Papadimitriou

Dasdan

and Garcia-Molina

, Web graph similarity for anomaly detection, Journal of Internet Services and Applications 1(1) (May 2010), 19–30.

46.

Paris

P.-H.

Abadie

and Brando

, Linking Spatial Named Entities to the Web of Data for Geographical Analysis of Historical Texts, Journal of Map & Geography Libraries 13(1) (Jan. 2017), 82–110.

47.

Patanè

and Spagnuolo

, Heterogenous Spatial Data: Fusion, Modeling, and Analysis for GIS Applications, Synthesis Lectures on Visual Computing 8(2) (Apr. 2016), 1–155.

48.

Purves

R.S.

Clough

Jones

C.B.

Arampatzis

Bucher

Finch

Joho

Syed

A.K.

Vaid

and Yang

, The design and implementation of SPIRIT: a spatially aware search engine for information retrieval on the Internet, International Journal of Geographical Information Science 21(7) (Aug. 2007), 717–745.

49.

Rabatel

Arsevska

de Goër de Hervé

Falala

Lancelot

and Roche

, Padi-web corpus: news manually labeled, CIRAD Dataverse, 2018, doi: 10.18167/DVN1/KMTIFG.

50.

Rauch

Bukatin

and Baker

, A confidence-based framework for disambiguating geographic terms, In Proceedings of the HLT-NAACL 2003 workshop on Analysis of geographic references, volume 1, 2003, pp. 50–54.

51.

Renz

, Qualitative spatial reasoning with topological information, Springer-Verlag, 2002.

52.

Riesen

and Bunke

, Approximate graph edit distance computation by means of bipartite graph matching, Image and Vision Computing 27(7) (2009), 950–959.

53.

Roller

Speriosu

Rallapalli

Wing

and Baldridge

, Supervised text-based geolocation using language models on an adaptive grid, In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 2012, pp. 1500–1510.

54.

Sakaki

Okazaki

and Matsuo

, Earthquake shakes twitter users: Real-time event detection by social sensors, In Proceedings of the 19th International Conference on World Wide Web, WWW ’10, New York, NY, USA, ACM, 2010, pp. 851–860.

55.

Sallaberry

Gaio

Palacio

and Lesbegueries

, Fuzzying GIS topological functions for GIR needs, In Proceedings of the 5th Workshop on Geographic Information Retrieval, 2008, pp. 1–8.

56.

Shervashidze

Schweitzer

Jan van Leeuwen

Mehlhorn

and Borgwardt

K.M.

, Weisfeiler-Lehman Graph Kernels, Journal of Machine Learning Research 12 (2011), 2539–2561.

57.

Smith

D.A.

and Mann

G.S.

, Bootstrapping toponym classifiers, In Proceedings of the HLT-NAACL 2003 workshop on Analysis of geographic references, volume 1, 2003, pp. 45–49.

58.

Strötgen

and Gertz

, HeidelTime High Quality Rule-Based Extraction and Normalization of Temporal Expressions.pdf, Proceedings of the 5th International Workshop on Semantic Evaluation, ACL, (July 2010), pp. 321–324.

59.

Thalhammer

and Rettinger

, PageRank on Wikipedia: Towards General Importance Scores for Entities, In Sack

Rizzo

Steinmetz

Mladenić

Auer

and Lange

, editors, The Semantic Web, volume 9989, 2016, pp. 227–240.

60.

Tobler

W.R.

, A Computer Movie Simulating Urban Growth in the Detroit Region, Economic Geography 46 (1970), 234–240.

61.

Tumasjan

Sprenger

Sandner

and Welpe

, Predicting elections with twitter: What 140 characters reveal about political sentiment, In Proceedings of the 4th International AAAI Conference on Web and Social Media, 2010, pp. 178–185.

62.

Vassiliadis

, A survey of extract-transform-load technology, International Journal of Data Warehousing and Mining (IJDWM) 5(3) (2009), 1–27.

63.

Vishwanathan

Schraudolph

Kondor

and Borgwardt

, Graph Kernels, Journal of Machine Learning Research 11 (2010), 1201–1242.

64.

Wallgrün

J.O.

Wolter

and Richter

K.-F.

, Qualitative matching of spatial information, In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’10, 2010, pp. 300–309.

65.

WallgrÃ¼n

J.O.

Frommberger

Dylla

and Wolter

, SparQ user manual v0. 7, User manual, University of Bremen, 2009.

66.

Wing

and Baldridge

, Hierarchical discriminative classification for text-based geolocation, In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), Doha, Qatar, Oct. 2014. Association for Computational Linguistics, pp. 336–348.

67.

Woodruff

A.G.

and Plaunt

, GIPSY: Automated geographic indexing of text documents, Journal of the American Society for Information Science 45(9) (1994), 645–655.

68.

, A qualitative spatio-temporal modelling and reasoning approach for the representation of moving entities, PhD Thesis, Brest, 2015.

Could spatial features help the matching of textual data?

Abstract

Keywords

1. Introduction

1 Identication of toponyms errors.

3. A text matching method based on spatial features

Table 1 Information associated with a spatial entity

3.1.1 Spatial entity

3.1.2 Spatial relation

3.2 Stage 1: Georepresentation

2 A python module that implements the STR is available at: https://gitlab.irstea.fr/jacques.fize/str-python.

8 Located in the administrative territorial entity (P131).

10 Available at: https://github.com/Jacobe2169/GMatch4py.

3.4.1 Bag of Spatial Entities (BOSE)

3.4.2 Polygon Intersection (PolyIntersect)

4.1 Datasets

4.1.1 PadiWeb corpus [49]

4.1.2 AgroMada corpus [19]

13 Built from DicoAE (available at https://dicoagroecologie.fr/).

4.2.1 Evaluation protocol

15 https://spacy.io/.

Table 4 Geotagging performance on the two samples

16 Villages, town, region, country or continent scale.

Footnotes

Acknowledgments

Appendix

A. Geonames classification

B. Spatiality associated with corpora

References

¹
Identication of toponyms errors.

Table 1
Information associated with a spatial entity

²
A python module that implements the STR is available at: https://gitlab.irstea.fr/jacques.fize/str-python.

⁸
Located in the administrative territorial entity (P131).

¹⁰
Available at: https://github.com/Jacobe2169/GMatch4py.

¹³
Built from DicoAE (available at https://dicoagroecologie.fr/).

¹⁵
https://spacy.io/.

Table 4
Geotagging performance on the two samples

¹⁶
Villages, town, region, country or continent scale.