A path-based distance for street map comparison

被引：8
作者：
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 条
  • [11] Conte D., Foggia P., Sansone C., Vento M., Thirty years of graph matching in pattern recognition, International Journal of Pattern Recognition and Artificial Intelligence, 18, 3, pp. 265-298, (2004)
  • [12] Eppstein D., Subgraph Isomorphism in Planar Graphs and Related Problems (SODA, pp. 632-640, (1995)
  • [13] Ge X., Safa I., Belkin M., Wang Y., Data skeletonization via Reeb graphs, 25th Annual Conference on Neural Information Processing Systems, pp. 837-845, (2011)
  • [14] Karagiorgou S., Pfoser D., On vehicle tracking data-based road network generation, Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 89-98, (2012)
  • [15] Kim H.J., Jung J.W., Kim S.K., On-line Chinese character recognition using ART-based stroke classification, Pattern Recognition Letters, 17, 12, pp. 1311-1322, (1996)
  • [16] Liu X., Biagioni J., Eriksson J., Wang Y., Forman G., Zhu Y., Mining large-scale, sparse GPS traces for map inference: Comparison of approaches, KDD, pp. 669-677, (2012)
  • [17] Mondzech J., Sester M., Quality analysis of OpenStreetMap data based on application needs, Cartographica, 46, pp. 115-125, (2011)
  • [18] Shi D., Damper R.I., Gunn S.R., Offline handwritten Chinese character recognition by radical decomposition, ACM Transactions on Asian Language Information Processing, 2, 1, pp. 27-48, (2003)
12