A path-based distance for street map comparison

被引：9
作者：
Ahmed, Mahmuda [1 ]
Fasy, Brittany Terese [2 ]
Hickmann, Kyle S. [3 ]
Wenk, Carola [2 ]
机构：
[1] Department of Computer Science, University of Texas at San Antonio, One UTSA Circle, San Antonio, 78249-0667, TX
[2] Department of Computer Science, Tulane University, 6823 St. Charles Ave, New Orleans, 70118, LA
[3] Center for Computational Science, Tulane University, 6823 St. Charles Ave, New Orleans, 70118, LA
来源：
ACM Transactions on Spatial Algorithms and Systems | 2015年 / 1卷 / 01期
基金：
美国国家科学基金会;
关键词：
Geometric graphs; Map comparison; Street maps;
D O I：
10.1145/2729977
中图分类号：
学科分类号：
摘要：
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. © 2015 ACM.
引用
收藏
相关论文
共 18 条
[1]  
Aanjaneya M., Chazal F., Chen D., Glisse M., Guibas L.J., Morozov D., Metric graph reconstruction from noisy data, Proceedings of the ACM Symposium on Computational Geometry, pp. 37-46, (2011)
[2]  
Ahmed M., Fasy B.T., Wenk C., Local persistent homology based distance between maps, Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 43-52, (2014)
[3]  
Ahmed M., Karagiorgou S., Pfoser D., Wenk C., A comparison and evaluation of map construction algorithms, Geoinformatica, 19, 3, pp. 601-632, (2014)
[4]  
Ahmed M., Wenk C., Constructing street networks from GPS trajectories, Proceedings of the European Symposium on Algorithms, pp. 60-71, (2012)
[5]  
Alt H., Efrat A., Gunter Rote, Wenk C., Matching planar maps, Journal of Algorithms, 49, pp. 262-283, (2003)
[6]  
Alt H., Godau M., Computing the Fréchet distance between two polygonal curves, International Journal of Computational Geometry and Applications, 5, pp. 75-91, (1995)
[7]  
Bharath A., Madhvanath S., Allograph modeling for online handwritten characters in devanagari using constrained stroke clustering, ACM Transactions on Asian Language Information Processing, 13, 3, pp. 121-1221, (2014)
[8]  
Biagioni J., Eriksson J., Map inference in the face of noise and disparity, Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 79-88, (2012)
[9]  
Chen D., Guibas L., Hershberger J., Sun J., Road network reconstruction for organizing paths, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1309-1320, (2010)
[10]  
Cheong O., Gudmundsson J., Hyo-Sil Kim, Schymura D., Stehn F., Measuring the similarity of geometric graphs, Proceedings of the 8th International Symposium on Experimental Algorithms, pp. 101-112, (2009)
12