{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T15:12:52Z","timestamp":1774451572118,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,7,29]],"date-time":"2015-07-29T00:00:00Z","timestamp":1438128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-1301911"],"award-info":[{"award-number":["CCF-1301911"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2015,8,13]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/2729977","type":"journal-article","created":{"date-parts":[[2016,5,21]],"date-time":"2016-05-21T22:27:38Z","timestamp":1463869658000},"page":"1-28","source":"Crossref","is-referenced-by-count":20,"title":["A Path-Based Distance for Street Map Comparison"],"prefix":"10.1145","volume":"1","author":[{"given":"Mahmuda","family":"Ahmed","sequence":"first","affiliation":[{"name":"University of Texas at San Antonio, TX"}]},{"given":"Brittany Terese","family":"Fasy","sequence":"additional","affiliation":[{"name":"Tulane University, New Orleans, LA"}]},{"given":"Kyle S.","family":"Hickmann","sequence":"additional","affiliation":[{"name":"Tulane University, New Orleans, LA"}]},{"given":"Carola","family":"Wenk","sequence":"additional","affiliation":[{"name":"Tulane University, New Orleans, LA"}]}],"member":"320","published-online":{"date-parts":[[2015,7,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998203"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666390"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0222-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00085-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629622"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424333"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873706"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_11"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_12_1","volume-title":"Subgraph isomorphism in planar graphs and related problems (SODA)","author":"Eppstein David","unstructured":"David Eppstein . 1995. Subgraph isomorphism in planar graphs and related problems (SODA) . SIAM , Philadelphia, PA , 632--640. David Eppstein. 1995. Subgraph isomorphism in planar graphs and related problems (SODA). SIAM, Philadelphia, PA, 632--640."},{"key":"e_1_2_1_13_1","volume-title":"25th Annual Conference on Neural Information Processing Systems. 837--845","author":"Ge Xiaoyin","year":"2011","unstructured":"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 . 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."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424334"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(96)00078-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339637"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3138\/carto.46.2.115"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/964161.964163"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2729977","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2729977","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:00Z","timestamp":1750227120000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2729977"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,29]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,8,13]]}},"alternative-id":["10.1145\/2729977"],"URL":"https:\/\/doi.org\/10.1145\/2729977","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,29]]}}}