Mahmuda Ahmed
Brittany Terese Fasy
Abstract
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.
- Mridul Aanjaneya, Frederic Chazal, Daniel Chen, Marc Glisse, Leonidas J. Guibas, and Dmitriy Morozov. 2011. Metric graph reconstruction from noisy data. In Proceedings of the ACM Symposium on Computational Geometry. 37--46. Google Scholar
Digital Library
- Mahmuda Ahmed, Brittany Terese Fasy, and Carola Wenk. 2014a. Local persistent homology based distance between maps. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 43--52. Google ScholarDigital Library
- Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. 2014b. A Comparison and Evaluation of Map Construction Algorithms. Geoinformatica 19, 3, 601--632. Google ScholarDigital Library
- Mahmuda Ahmed and Carola Wenk. 2012. Constructing street networks from GPS trajectories. In Proceedings of the European Symposium on Algorithms. 60--71. Google ScholarDigital Library
- Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. 2003. Matching planar maps. Journal of Algorithms 49, 262--283. Google ScholarDigital Library
- Helmut Alt and Michael Godau. 1995. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications 5, 75--91.Google ScholarCross Ref
- A. Bharath and Sriganesh Madhvanath. 2014. Allograph modeling for online handwritten characters in devanagari using constrained stroke clustering. ACM Transactions on Asian Language Information Processing 13, 3 (2014), 12:1--12:21. Google ScholarDigital Library
- James Biagioni and Jakob Eriksson. 2012. Map inference in the face of noise and disparity. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 79--88. Google ScholarDigital Library
- Daniel Chen, Leonidas Guibas, John Hershberger, and Jian Sun. 2010. Road network reconstruction for organizing paths. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1309--1320. Google ScholarDigital Library
- Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, and Fabian Stehn. 2009. Measuring the similarity of geometric graphs. In Proceedings of the 8th International Symposium on Experimental Algorithms. 101--112. Google ScholarDigital Library
- Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence 18, 3, 265--298.Google ScholarCross Ref
- David Eppstein. 1995. Subgraph isomorphism in planar graphs and related problems (SODA). SIAM, Philadelphia, PA, 632--640. Google ScholarDigital Library
- Xiaoyin Ge, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. Data skeletonization via Reeb graphs. In 25th Annual Conference on Neural Information Processing Systems. 837--845.Google Scholar
- Sophia Karagiorgou and Dieter Pfoser. 2012. On vehicle tracking data-based road network generation. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 89--98. Google ScholarDigital Library
- Hang Joon Kim, Jong Wha Jung, and Sang Kyoon Kim. 1996. On-line Chinese character recognition using ART-based stroke classification. Pattern Recognition Letters 17, 12, 1311--1322. Google ScholarDigital Library
- Xuemei Liu, James Biagioni, Jakob Eriksson, Yin Wang, George Forman, and Yanmin Zhu. 2012. Mining large-scale, sparse GPS traces for map inference: Comparison of approaches. In KDD. ACM, New York, NY, 669--677. DOI:http://dx.doi.org/10.1145/2339530.2339637 Google ScholarDigital Library
- Juliane Mondzech and Monika Sester. 2011. Quality analysis of OpenStreetMap data based on application needs. Cartographica 46, 115--125.Google ScholarCross Ref
- Daming Shi, Robert I. Damper, and Steve R. Gunn. 2003. Offline handwritten Chinese character recognition by radical decomposition. ACM Transactions on Asian Language Information Processing 2, 1, 27--48. Google ScholarDigital Library
Index Terms
- A Path-Based Distance for Street Map Comparison
Recommendations
Graph Sampling for Map Comparison
Comparing two road maps is a basic operation that arises in a variety of situations. A map comparison method that is commonly used, mainly in the context of comparing reconstructed maps to ground truth maps, is based on graph sampling. The essential idea ...
On grids in topological graphs
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryA topological graph is a graph drawn in the plane with vertices represented by points and edges as arcs connecting its vertices. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset ...
Group path covering and distance two labeling of graphs
For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)-f(v)|>=d if uv@?E(G), and |f(u)-f(v)|>=1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the ...
Comments