Map construction methods automatically produce and or update street map datasets using vehicle tracking data. Enabled by the ubiquitous generation of geo-referenced tracking data, there has been a recent surge in map construction algorithms coming from different computer science domains. A cross-comparison of the various algorithms is still very rare, since (i) algorithms and constructed maps are generally not publicly available and (ii) there is no standard approach to assess the result quality, given the lack of benchmark data and quantitative evaluation methods. This work represents a first comprehensive attempt to benchmark such map construction algorithms. We provide an evaluation and comparison of seven algorithms using four datasets and four different evaluation measures. In addition to this comprehensive comparison, we make our datasets, source code of map construction algorithms and evaluation measures publicly available on http: mapconstruction.org. . This site has been established as a repository for map construction data and algorithms and we invite other researchers to contribute by uploading code and benchmark data supporting their contributions to map construction algorithms.
For on the other hand, the underlying idea is to represent the graphs by sets of paths, and then define a distance measure based on distances between the paths. This captures some of the topological information in the graphs, and paths are of importance for street maps in particular since the latter are often used for routing applications for which similar connectivity is desirable. Mondzech and Sester @cite_21 use shortest paths to compare the suitability of two road networks for pedestrian navigation by considering basic properties such as respective path length. Karagiorgou and Pfoser @cite_24 also use shortest paths, but to actually assess the similarity of road network graphs. Computing random sets of start and end nodes, the computed paths are compared using Discrete and the Average Vertical distance. Using those sets of distances, a global network similarity measure is derived. In another effort, Ahmed and Wenk @cite_7 cover the networks to be compared with paths of @math link-length and map-match the paths to the other graph using the . They are the first to introduce the concept local signature to identify how and where two graphs differ.
@cite_24 @cite_21 @cite_7
1527105738 2153482597 1991924366 2964124596
Comparing two geometric graphs embedded in space is important in the field of transportation network analysis. Given street maps of the same city collected from different sources, researchers often need to know how and where they differ. However, the majority of current graph comparison algorithms are based on structural properties of graphs, such as their degree distribution or their local connectivity properties, and do not consider their spatial embedding. This ignores a key property of road networks since the similarity of travel over two road networks is intimately tied to the specific spatial embedding. Likewise, many current algorithms specific to street map comparison either do not provide quality guarantees or focus on spatial embeddings only. Motivated by road network comparison, we propose a new path-based distance measure between two planar geometric graphs that is based on comparing sets of travel paths generated over the graphs. Surprisingly, we are able to show that using paths of bounded link-length, we can capture global structural and spatial differences between the graphs. We show how to utilize our distance measure as a local signature in order to identify and visualize portions of high similarity in the maps. Finally, we present an experimental evaluation of our distance measure and its local signature on street map data from Berlin, Germany and Athens, Greece. We consider the problem of constructing street networks from geo-referenced trajectory data: Given a set of trajectories in the plane, compute a street network that represents all trajectories in the set. We present a simple and practical incremental algorithm that is based on partial matching of the trajectories to the graph. We use minimumlink paths to reduce the complexity of the reconstructed graph. We provide quality guarantees and experimental results based on both real and synthetic data. For the partial matching we introduce a new variant of partial Frechet distance. In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogota’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine. The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) ⊆ V to each node u ∈ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) ∩ S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.