{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:54:22Z","timestamp":1772909662399,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,8,21]],"date-time":"2024-08-21T00:00:00Z","timestamp":1724198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF 1637576"],"award-info":[{"award-number":["CCF 1637576"]}]},{"name":"R.I.S.","award":["PID2019-104129GB-I00\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104129GB-I00\/AEI\/10.13039\/501100011033"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            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\n            <jats:italic>graph sampling<\/jats:italic>\n            . The essential idea is to first compute a set of point samples on each map and then to match pairs of samples\u2014one from each map\u2014in a one-to-one fashion. For deciding whether two samples can be matched, different criteria, e.g., based on distance or orientation, can be used. The total number of matched pairs gives a measure of how similar the maps are.\n          <\/jats:p>\n          <jats:p>\n            Since the work of Biagioni and Eriksson [\n            <jats:xref ref-type=\"bibr\">11<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">12<\/jats:xref>\n            ], graph sampling methods have become widely used. However, there are different ways to implement each of the steps, which can lead to significant differences in the results. This means that conclusions drawn from different studies that seemingly use the same comparison method cannot necessarily be compared.\n          <\/jats:p>\n          <jats:p>In this work we present a unified approach to graph sampling for map comparison. We present the method in full generality, discussing the main decisions involved in its implementation. In particular, we point out the importance of the sampling method (GEO vs. TOPO) and that of the matching definition, discussing the main options used, and proposing alternatives for both key steps. We experimentally evaluate the different sampling and matching options considered on map datasets and reconstructed maps. Furthermore, we provide a code base and an interactive visualization tool to set a standard for future evaluations in the field of map construction and map comparison.<\/jats:p>","DOI":"10.1145\/3662733","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T11:56:23Z","timestamp":1714737383000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Graph Sampling for Map Comparison"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4837-2236","authenticated-orcid":false,"given":"Jordi","family":"Aguilar","sequence":"first","affiliation":[{"name":"Department of Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3022-7877","authenticated-orcid":false,"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3446-4343","authenticated-orcid":false,"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ruhr-Universitat Bochum, Bochum, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2548-7428","authenticated-orcid":false,"given":"Erfan","family":"Hosseini Sereshgi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tulane University, New Orleans, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0202-4543","authenticated-orcid":false,"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[{"name":"Department of Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9275-5336","authenticated-orcid":false,"given":"Carola","family":"Wenk","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tulane University, New Orleans, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,21]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3617291.3617293"},{"key":"e_1_3_4_3_2","article-title":"Path-based distance for street map comparison","author":"Ahmed M.","year":"2015","unstructured":"M. Ahmed, B. T. Fasy, K. S. Hickmann, and C. Wenk. 2015. Path-based distance for street map comparison. ACM Transactions on Spatial Algorithms and Systems 1, 1 (2015), 1--28.","journal-title":"ACM Transactions on Spatial Algorithms and Systems"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666390"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0222-6"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/2878633"},{"key":"e_1_3_4_7_2","first-page":"60","volume-title":"Proceedings of the 20th Annual European Symposium on Algorithms","author":"Ahmed M.","year":"2012","unstructured":"M. Ahmed and C. Wenk. 2012. Constructing street networks from GPS trajectories. In Proceedings of the 20th Annual European Symposium on Algorithms. 60\u201371."},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"101743","DOI":"10.1016\/j.comgeo.2020.101743","article-title":"Distance measures for embedded graphs","author":"Akitaya H. A.","year":"2021","unstructured":"H. A. Akitaya, M. Buchin, B. Kilgus, S. Sijben, and C. Wenk. 2021. Distance measures for embedded graphs. Computational Geometry: Theory and Applications 95 (2021), 101743.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/S0196-6774(03)00085-3","article-title":"Matching planar maps","author":"Alt H.","year":"2003","unstructured":"H. Alt, A. Efrat, G. Rote, and C. Wenk. 2003. Matching planar maps. Journal of Algorithms 49, 2 (2003), 262\u2013283.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_4_10_2","first-page":"121","volume-title":"Handbook of Computational Geometry","author":"Alt H.","year":"1999","unstructured":"H. Alt and L. J. Guibas. 1999. Discrete geometric shapes: Matching, interpolation, and approximation\u2014a survey. In Handbook of Computational Geometry. Elsevier, 121\u2013154."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00496"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.3141\/2291-08"},{"key":"e_1_3_4_13_2","first-page":"79","volume-title":"Proceedings of the 20th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS","author":"Biagioni J.","year":"2012","unstructured":"J. Biagioni and J. Eriksson. 2012. Map inference in the face of noise and disparity. In Proceedings of the 20th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS. 79\u201388."},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3423334.3431451"},{"key":"e_1_3_4_15_2","first-page":"2443\u2013-2455","volume-title":"Proceedings of the 28th Annual ACM Symposium on Discrete Algorithms (SODA)","author":"Buchin K.","year":"2017","unstructured":"K. Buchin, T. Ophelders, and B. Speckmann. 2017. Computing the Fr\u00e9chet distance between real-valued surfaces. In Proceedings of the 28th Annual ACM Symposium on Discrete Algorithms (SODA). ACM, 2443\u2013-2455."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","unstructured":"M. Buchin E. Chambers P. Fang B. T. Fasy E. Gasparovic E. Munch and C. Wenk. 2021. Distances Between Immersed Graphs: Metric Properties. La Matematica 2 (2023) 197--222. 10.1007\/s44007-022-00037-8","DOI":"10.1007\/s44007-022-00037-8"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653776"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939833"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_11"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2006.83"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00386-7"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/865449.865460"},{"key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"1775","DOI":"10.1109\/WACV45572.2020.9093593","volume-title":"IEEE Winter Conference on Applications of Computer Vision (WACV)","author":"Etten A. Van","year":"2020","unstructured":"A. Van Etten. 2020. City-scale road extraction from satellite imagery v2: Road speeds and travel times. In IEEE Winter Conference on Applications of Computer Vision (WACV). IEEE, 1775\u20131784."},{"key":"e_1_3_4_25_2","first-page":"62:1\u201362:5","volume-title":"European Workshop on Computational Geometry","author":"Fang P.","year":"2021","unstructured":"P. Fang and C. Wenk. 2021. The Fr\u00e9chet distance for plane graphs. In European Workshop on Computational Geometry. 62:1\u201362:5."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_3_4_27_2","first-page":"837","volume-title":"Proceedings of the 25th Annual Conference on Neural Information Processing Systems","author":"Ge X.","year":"2011","unstructured":"X. Ge, I. Safa, M. Belkin, and Y. Wang. 2011. Data skeletonization via Reeb graphs. In Proceedings of the 25th Annual Conference on Neural Information Processing Systems. 837\u2013845."},{"key":"e_1_3_4_28_2","first-page":"3","volume-title":"Proceedings of the 26th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS","author":"He S.","year":"2018","unstructured":"S. He, F. Bastani, S. Abbar, M. Alizadeh, H. Balakrishnan, S. Chawla, and S. Madden. 2018. RoadRunner: Improving the precision of road network inference from GPS trajectories. In Proceedings of the 26th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS. 3\u201312."},{"key":"e_1_3_4_29_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-030-58586-0_4","volume-title":"Proceedings of the 16th European Conference on Computer Vision","volume":"12369","author":"He S.","year":"2020","unstructured":"S. He, F. Bastani, S. Jagwani, M. Alizadeh, H. Balakrishnan, S. Chawla, M. M\u0303. Elshrif, S. Madden, and M. A. Sadeghi. 2020. Sat2Graph: Road graph extraction through graph-tensor encoding. In Proceedings of the 16th European Conference on Computer Vision(Lecture Notes in Computer Science, Vol. 12369). Springer, 51\u201367."},{"key":"e_1_3_4_30_2","first-page":"89","volume-title":"Proceedings of the 20th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS","author":"Karagiorgou S.","year":"2012","unstructured":"S. Karagiorgou and D. Pfoser. 2012. On vehicle tracking data-based road network generation. In Proceedings of the 20th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) GIS. 89\u201398."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339637"},{"key":"e_1_3_4_32_2","unstructured":"W. Meert and M. Verbeke. 2018. HMM with Non-Emitting States for Map Matching. https:\/\/lirias.kuleuven.be\/retrieve\/512781Dmapmatching_ecda18.pdf"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.15"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi8090411"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662733","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3662733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:11Z","timestamp":1750291031000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,21]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3662733"],"URL":"https:\/\/doi.org\/10.1145\/3662733","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,21]]},"assertion":[{"value":"2022-04-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}