A deep learning architecture for semantic address matching

ABSTRACT

Address matching is a crucial step in geocoding, which plays an important role in urban planning and management. To date, the unprecedented development of location-based services has generated a large amount of unstructured address data. Traditional address matching methods mainly focus on the literal similarity of address records and are therefore not applicable to the unstructured address data. In this study, we introduce an address matching method based on deep learning to identify the semantic similarity between address records. First, we train the word2vec model to transform the address records into their corresponding vector representations. Next, we apply the enhanced sequential inference model (ESIM), a deep text-matching model, to make local and global inferences to determine if two addresses match. To evaluate the accuracy of the proposed method, we fine-tune the model with real-world address data from the Shenzhen Address Database and compare the outputs with those of several popular address matching methods. The results indicate that the proposed method achieves a higher matching accuracy for unstructured address records, with its precision, recall, and F1 score (i.e., the harmonic mean of precision and recall) reaching 0.97 on the test set.     

Geometric-based approach for integrating VGI POIs and road networks

Integrating heterogeneous spatial data is a crucial problem for geographical information systems (GIS) applications. Previous studies mainly focus on the matching of heterogeneous road networks or heterogeneous polygonal data sets. Few literatures attempt to approach the problem of integrating the point of interest (POI) from volunteered geographic information (VGI) and professional road networks from official mapping agencies. Hence, the article proposes an approach for integrating VGI POIs and professional road networks. The proposed method first generates a POI connectivity graph by mining the linear cluster patterns from POIs. Secondly, the matching nodes between the POI connectivity graph and the associated road network are fulfilled by probabilistic relaxation and refined by a vector median filtering (VMF). Finally, POIs are aligned to the road network by an affine transformation according to the matching nodes. Experiments demonstrate that the proposed method integrates both the POIs from VGI and the POIs from official mapping agencies with the associated road networks effectively and validly, providing a promising solution for enriching professional road networks by integrating VGI POIs.     

A probabilistic relaxation approach for matching road networks

Geospatial data matching is an important prerequisite for data integration, change detection and data updating. At present, crowdsourcing geospatial data are attracting considerable attention with its significant potential for timely and cost-effective updating of geospatial data and Geographical Information Science (GIS) applications. To integrate the available and up-to-date information of multi-source geospatial data, this article proposes a heuristic probabilistic relaxation road network matching method. The proposed method starts with an initial probabilistic matrix according to the dissimilarities in the shapes and then integrates the relative compatibility coefficient of neighbouring candidate pairs to iteratively update the initial probabilistic matrix until the probabilistic matrix is globally consistent. Finally, the initial 1:1 matching pairs are selected on the basis of probabilities that are calculated and refined on the basis of the structural similarity of the selected matching pairs. A process of matching is then implemented to find M:N matching pairs. Matching between OpenStreetMap network data and professional road network data shows that our method is independent of matching direction, successfully matches 1:0 (Null), 1:1 and M:N pairs, and achieves a robust matching precision of above 95%.     

A metaheuristic approach for efficient and effective sketch-to-metric map alignment

Sketching as a natural mode for human communication and creative processes presents opportunities for improving human–computer interaction in geospatial information systems. However, to use a sketch map as user input, it must be localized within the underlying spatial data set of the information system, the base metric map. This can be achieved by a matching process called qualitative map alignment in which qualitative spatial representations of the two input maps are used to establish correspondences between each sketched object and one or more objects in the metric map. The challenge is that, to the best of our knowledge, no method for matching qualitative spatial representations suggested so far is applicable in realistic scenarios due to excessively long runtimes, incorrect algorithm design or the inability to use more than one spatial aspect at a time. We address these challenges with a metaheuristic algorithm which uses novel data structures to match qualitative spatial representations of a pair of maps. We present the design, data structures and performance evaluation of the algorithm using real-world sketch and metric maps as well as on synthetic data. Our algorithm is novel in two main aspects. Firstly, it employs a novel system of matrices known as local compatibility matrices, which facilitate the computation of estimates for the future size of a partial alignment and allow several types of constraints to be used at the same time. Secondly, the heuristic it computes has a higher accuracy than the state-of-the-art heuristic for this task, yet requires less computation. Our algorithm is also a general method for matching labelled graphs, a special case of which is the one involving complete graphs whose edges are labelled with spatial relations. The results of our evaluation demonstrate practical runtime performance and high solution quality.     

Automatic change detection in lane-level road networks using GPS trajectories

Lane-level road network updating is crucial for urban traffic applications that use geographic information systems contributing to, for example, intelligent driving, route planning and traffic control. Researchers have developed various algorithms to update road networks using sensor data, such as high-definition images or GPS data; however, approaches that involve change detection for road networks at lane level using GPS data are less common. This paper presents a novel method for automatic change detection of lane-level road networks based on GPS trajectories of vehicles. The proposed method includes two steps: map matching at lane level and lane-level change recognition. To integrate the most up-to-date GPS data with a lane-level road network, this research uses a fuzzy logic road network matching method. The proposed map-matching method starts with a confirmation of candidate lane-level road segments that use error ellipses derived from the GPS data, and then computes the membership degree between GPS data and candidate lane-level segments. The GPS trajectory data is classified into successful or unsuccessful matches using a set of defuzzification rules. Any topological and geometrical changes to road networks are detected by analysing the two kinds of matching results and comparing their relationships with the original road network. Change detection results for road networks in Wuhan, China using collected GPS trajectories show that these methods can be successfully applied to detect lane-level road changes including added lanes, closed lanes and lane-changing and turning rules, while achieving a robust detection precision of above 80%.     

A node semantic similarity schema-matching method for multi-version Web Coverage Service retrieval

Different versions of the Web Coverage Service (WCS) schemas of the Open Geospatial Consortium (OGC) reflect semantic conflict. When applying the extended FRAG-BASE schema-matching approach (a schema-matching method based on COMA++, including an improved schema decomposition algorithm and schema fragments identification algorithm, which enable COMA++-based support to OGC Web Service schema matching), the average recall of WCS schema matching is only 72%, average precision is only 82% and average overall is only 57%. To improve the quality of multi-version WCS retrieval, we propose a schema-matching method that measures node semantic similarity (NSS). The proposed method is based on WordNet, conjunctive normal form and a vector space model. A hybrid algorithm based on label meanings and annotations is designed to calculate the similarity between label concepts. We translate the semantic relationships between nodes into a propositional formula and verify the validity of this formula to confirm the semantic relationships. The algorithm first computes the label and node concepts and then calculates the conceptual relationship between the labels. Finally, the conceptual relationship between nodes is computed. We then use the NSS method in experiments on different versions of WCS. Results show that the average recall of WCS schema matching is greater than 83%; average precision reaches 92%; and average overall is 67%.     

Metrics for characterizing network structure and node importance in Spatial Social Networks

Social Network Analysis offers powerful tools to analyze the structure of relationships between a set of people. However, the addition of spatial information poses new challenges, as nodes are embedded simultaneously in network space and Euclidean space. While nearby nodes may not form social ties, ties may exist at a distance, a configuration ill-suited for traditional spatial metrics that assume adjacent objects are related. As such, there are relatively few metrics to describe these nuanced situations. We advance the burgeoning field of spatial social network analysis by introducing a set of new metrics. Specifically, we introduce the spatial social network schema, tuning parameter and the flattening ratio, each of which leverages the notion of ‘distance’ to augment insights obtained by relying on topology alone. These methods are used to answer the questions: What is the social and spatial structure of the network? Who are the key individuals at different spatial scales? We use two synthetic networks with properties mimicking the ones reported in the literature as validation datasets and a case study of employer–employee network. The methods characterize the employer–employee as spatially loose with predominantly local connections and identify key individuals responsible for keeping the network connected at different spatial scales.     

A polygon-based approach for matching OpenStreetMap road networks with regional transit authority data

Matching road networks is an essential step for data enrichment and data quality assessment, among other processes. Conventionally, road networks from two datasets are matched using a line-based approach that checks for the similarity of properties of line segments. In this article, a polygon-based approach is proposed to match the OpenStreetMap road network with authority data. The algorithm first extracts urban blocks that are central elements of urban planning and are represented by polygons surrounded by their surrounding streets, and it then assigns road lines to edges of urban blocks by checking their topologies. In the matching process, polygons of urban blocks are matched in the first step by checking for overlapping areas. In the second step, edges of a matched urban block pair are further matched with each other. Road lines that are assigned to the same matched pair of urban block edges are then matched with each other. The computational cost is substantially reduced because the proposed approach matches polygons instead of road lines, and thus, the process of matching is accelerated. Experiments on Heidelberg and Shanghai datasets show that the proposed approach achieves good and robust matching results, with a precision higher than 96% and a F1-score better than 90%.     

Ranking spaces for predicting human movement in an urban environment

A city can be topologically represented as a connectivity graph, consisting of nodes representing individual spaces and links if the corresponding spaces are intersected. It turns out in the space syntax literature that some defined topological metrics can capture human movement rates in individual spaces. In other words, the topological metrics are significantly correlated to human movement rates, and individual spaces can be ranked by the metrics for predicting human movement. However, this correlation has never been well justified. In this paper, we study the same issue by applying the weighted PageRank algorithm to the connectivity graph or space–space topology for ranking the individual spaces, and find surprisingly that: (1) the PageRank scores are better correlated to human movement rates than the space syntax metrics, and (2) the underlying space–space topology demonstrates small world and scale free properties. The findings provide a novel justification as to why space syntax, or topological analysis in general, can be used to predict human movement. We further conjecture that this kind of analysis is no more than predicting a drunkard's walking on a small world and scale free network.     

Possibilities of land use change analysis in a mountainous rural area: a methodological approach

Decreasing population density is a current trend in the European Union, and causes a lower environmental impact on the landscape. However, besides the desirable effect on the regeneration processes of semi-natural forest ecosystems, the lack of traditional management techniques can also lead to detrimental ecological processes. In this study we investigated the land use pattern changes in a micro-region (in North-Eastern Hungary) between 1952 and 2005, based on vectorised land use data from archive aerial photos. We also evaluated the methodology of comparisons using GIS methods, fuzzy sets and landscape metrics. We found that both GIS methods and statistical analysis of landscape metrics resulted in more or less the same findings. Differences were not as relevant as was expected considering the general tendencies of the past 60 years in Hungary. The change in the annual rate of forest recovery was 0.12%; settlements extended their area by an annual rate of 3.04%, while grasslands and arable lands had a net loss in their area within the studied period (0.60% and 0.89%, respectively). The kappa index showed a smaller similarity (~60%) between these dates but the fuzzy kappa and the aggregation index, taking into account both spatial and thematic errors, gave a more reliable result (~70–80% similarity). Landscape metrics on patch and class level ensured the possibility of a detailed analysis. We arrived at a similar outcome but were able to verify all the calculations through statistical tests. With this approach we were able to reveal significant (p < 0.05) changes; however, effect sizes did not show large magnitudes. Comparing the methods of revealing landscape change, the approach of landscape metrics was the most effective approach, as it was independent of spatial errors and ensuring a multiple way of interpretation.     

A data‐mining approach for assessing consistency between multiple representations in spatial databases

When different spatial databases are combined, an important issue is the identification of inconsistencies between data. Quite often, representations of the same geographical entities in databases are different and reflect different points of view. In order to fully take advantage of these differences when object instances are associated, a key issue is to determine whether the differences are normal, i.e. explained by the database specifications, or if they are due to erroneous or outdated data in one database. In this paper, we propose a knowledge‐based approach to partially automate the consistency assessment between multiple representations of data. The inconsistency detection is viewed as a knowledge‐acquisition problem, the source of knowledge being the data. The consistency assessment is carried out by applying a proposed method called MECO. This method is itself parameterized by some domain knowledge obtained from a second method called MACO. MACO supports two approaches (direct or indirect) to perform the knowledge acquisition using data‐mining techniques. In particular, a supervised learning approach is defined to automate the knowledge acquisition so as to drastically reduce the human‐domain expert's work. Thanks to this approach, the knowledge‐acquisition process is sped up and less expert‐dependent. Training examples are obtained automatically upon completion of the spatial data matching. Knowledge extraction from data following this bottom‐up approach is particularly useful, since the database specifications are generally complex, difficult to analyse, and manually encoded. Such a data‐driven process also sheds some light on the gap between textual specifications and those actually used to produce the data. The methodology is illustrated and experimentally validated by comparing geometrical representations and attribute values of different vector spatial databases. The advantages and limits of such partially automatic approaches are discussed, and some future works are suggested.     

A simplified linear feature matching method using decision tree analysis,weighted linear directional mean,and topological relationships

Linear feature matching is one of the crucial components for data conflation that sees its usefulness in updating existing data through the integration of newer data and in evaluating data accuracy. This article presents a simplified linear feature matching method to conflate historical and current road data. To measure the similarity, the shorter line median Hausdorff distance (SMHD), the absolute value of cosine similarity (aCS) of the weighted linear directional mean values, and topological relationships are adopted. The decision tree analysis is employed to derive thresholds for the SMHD and the aCS. To demonstrate the usefulness of the simple linear feature matching method, four models with incremental configurations are designed and tested: (1) Model 1: one-to-one matching based on the SMHD; (2) Model 2: matching with only the SMHD threshold; (3) Model 3: matching with the SMHD and the aCS thresholds; and (4) Model 4: matching with the SMHD, the aCS, and topological relationships. These experiments suggest that Model 2, which considers only distance, does not provide stable results, while Models 3 and 4, which consider direction and topological relationships, produce stable results with levels of accuracy around 90% and 95%, respectively. The results suggest that the proposed method is simple yet robust for linear feature matching.     

Network-scape metric analysis: a new approach for the pattern analysis of urban road networks

The spatial patterns of road networks reflect the morphological and structural characteristics of cities. Previous studies have focused mainly on seeking universal laws in road networks rather than explaining their differences. A new approach for road network pattern analysis is proposed that has been inspired by landscape metric analysis. The utility of this approach is illustrated through (but is not limited to) the extraction of the main factors in network landscapes, or network-scapes for short. Twenty-four metrics were calculated for network-scapes of 100 cities worldwide, before an exploratory analysis is performed to detect the main factors. Four main factors were revealed and may be regarded as the characteristic indicators of road networks, which were identified to be evenness, richness-density, shape irregularity, and size and shape variation. The meanings of these factors are explained, and their spatial distributions are illustrated. Compared to existing road network analytics, these factors depict better the characteristic differences of road networks. The proposed approach provides a new framework for road network pattern analysis from a cellular perspective.     

Measuring urban activities using Foursquare data and network analysis: a case study of Murcia (Spain)

Among social networks, Foursquare is a useful reference for identifying recommendations about local stores, restaurants, malls or other activities in the city. In this article, we consider the question of whether there is a relationship between the data provided by Foursquare regarding users’ tastes and preferences and fieldwork carried out in cities, especially those connected with business and leisure. Murcia was chosen for case study for two reasons: its particular characteristics and the prior knowledge resulting from the fieldwork. Since users of this network establish, what may be called, a ranking of places through their recommendations, we can plot these data with the objective of displaying the characteristics and peculiarities of the network in this city. Fieldwork from the city itself gives us a set of facilities and services observed in the city, which is a physical reality. An analysis of these data using a model based on a network centrality algorithm establishes a classification or ranking of the nodes that form the urban network. We compare the data extracted from the social network with the data collected from the fieldwork, in order to establish the appropriateness in terms of understanding the activity that takes place in this city. Moreover, this comparison allows us to draw conclusions about the degree of similarity between the preferences of Foursquare users and what was obtained through the fieldwork in the city.     

RecNet: a deep neural network for personalized POI recommendation in location-based social networks

How to exploit various features of users and points of interest (POIs) for accurate POI recommendation is important in location-based social networks (LBSNs). In this paper, a novel POI recommendation framework, named RecNet, is proposed, which is developed based on a deep neural network (DNN) to incorporate various features in LBSNs and learn their joint influence on user behavior. More specifically, co-visiting, geographical and categorical influences in LBSNs are exploited to alleviate the data sparsity issue in POI recommendation and are converted to feature vector representations of POIs and users via feature embedding. Moreover, the embedded POIs and users are fed into a DNN pairwise to adaptively learn high-order interactions between features. Our method is evaluated on two publicly available LBSNs datasets and experimental results show that RecNet outperforms state-of-the-art algorithms for POI recommendation.     

Multiple Point Metrics to Assess Categorical Variable Models

Geostatistical models should be checked to ensure consistency with conditioning data and statistical inputs. These are minimum acceptance criteria. Often the first and second-order statistics such as the histogram and variogram of simulated geological realizations are compared to the input parameters to check the reasonableness of the simulation implementation. Assessing the reproduction of statistics beyond second-order is often not considered because the “correct” higher order statistics are rarely known. With multiple point simulation (MPS) geostatistical methods, practitioners are now explicitly modeling higher-order statistics taken from a training image (TI). This article explores methods for extending minimum acceptance criteria to multiple point statistical comparisons between geostatistical realizations made with MPS algorithms and the associated TI. The intent is to assess how well the geostatistical models have reproduced the input statistics of the TI; akin to assessing the histogram and variogram reproduction in traditional semivariogram-based geostatistics. A number of metrics are presented to compare the input multiple point statistics of the TI with the statistics of the geostatistical realizations. These metrics are (1) first and second-order statistics, (2) trends, (3) the multiscale histogram, (4) the multiple point density function, and (5) the missing bins in the multiple point density function. A case study using MPS realizations is presented to demonstrate the proposed metrics; however, the metrics are not limited to specific MPS realizations. Comparisons could be made between any reference numerical analogue model and any simulated categorical variable model.     

Map-matching algorithm for large-scale low-frequency floating car data

Large-scale global positioning system (GPS) positioning information of floating cars has been recognised as a major data source for many transportation applications. Mapping large-scale low-frequency floating car data (FCD) onto the road network is very challenging for traditional map-matching (MM) algorithms developed for in-vehicle navigation. In this paper, a multi-criteria dynamic programming map-matching (MDP-MM) algorithm is proposed for online matching FCD. In the proposed MDP-MM algorithm, the MDP technique is used to minimise the number of candidate routes maintained at each GPS point, while guaranteeing to determine the best matching route. In addition, several useful techniques are developed to improve running time of the shortest path calculation in the MM process. Case studies based on real FCD demonstrate the accuracy and computational performance of the MDP-MM algorithm. Results indicated that the MDP-MM algorithm is competitive with existing algorithms in both accuracy and computational performance.     

哈大城市带网络结构韧性演化研究

网络结构韧性是城市空间组织未来发展的重要指向,是社会经济稳定性与恢复力的结构保障。论文借鉴复杂网络指标,构建城市网络结构韧性演化评价模型,以哈大城市带为例,对比分析多重城市网络结构韧性的演化特征。结果表明：① 多重城市网络层级性与匹配性存在分异,在层级性上,交通和金融网络趋于扁平,信息和创新网络趋于立体;在匹配性上,交通和创新网络分别表现为同配性与异配性且特征强化,金融和信息网络为异配性但特征削弱。② 网络结构韧性类型相对稳定,交通运输网络为“同配—核心边缘网络”,金融、信息与创新网络为“韧性网络”;韧性演化综合水平表现为创新合作网络>信息关联网络>0>金融联系网络>交通运输网络。③ 可以从整体结构、片区差异和要素流动三方面优化网络结构韧性演化水平。     

Visual analytics of delays and interaction in movement data

The analysis of interaction between movement trajectories is of interest for various domains when movement of multiple objects is concerned. Interaction often includes a delayed response, making it difficult to detect interaction with current methods that compare movement at specific time intervals. We propose analyses and visualizations, on a local and global scale, of delayed movement responses, where an action is followed by a reaction over time, on trajectories recorded simultaneously. We developed a novel approach to compute the global delay in subquadratic time using a fast Fourier transform (FFT). Central to our local analysis of delays is the computation of a matching between the trajectories in a so-called delay space. It encodes the similarities between all pairs of points of the trajectories. In the visualization, the edges of the matching are bundled into patches, such that shape and color of a patch help to encode changes in an interaction pattern. To evaluate our approach experimentally, we have implemented it as a prototype visual analytics tool and have applied the tool on three bidimensional data sets. For this we used various measures to compute the delay space, including the directional distance, a new similarity measure, which captures more complex interactions by combining directional and spatial characteristics. We compare matchings of various methods computing similarity between trajectories. We also compare various procedures to compute the matching in the delay space, specifically the Fréchet distance, dynamic time warping (DTW), and edit distance (ED). Finally, we demonstrate how to validate the consistency of pairwise matchings by computing matchings between more than two trajectories.