{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:26Z","timestamp":1740109586576,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:00:00Z","timestamp":1694736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:00:00Z","timestamp":1694736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1602\/19","1086\/18"],"award-info":[{"award-number":["1602\/19","1086\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001658","name":"Minerva Foundation","doi-asserted-by":"publisher","award":["1042\/22"],"award-info":[{"award-number":["1042\/22"]}],"id":[{"id":"10.13039\/501100001658","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00454-023-00565-2","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T15:06:28Z","timestamp":1694790388000},"page":"849-871","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":false,"given":"Arnold","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Lee-Ad","family":"Gottlieb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,15]]},"reference":[{"issue":"6","key":"565_CR1","doi-asserted-by":"publisher","first-page":"3026","DOI":"10.1016\/j.aim.2011.08.003","volume":"228","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026\u20133126 (2011)","journal-title":"Adv. Math."},{"key":"565_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Filtser, A., Gupta, A., Neiman, O.: Metric embedding via shortest path decompositions. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 952\u2013963. ACM, New York (2018)","DOI":"10.1145\/3188745.3188808"},{"key":"565_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: 25th Annual ACM Symposium on Principles of Distributed Computing (Denver 2006), pp. 188\u2013197. ACM, New York (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"565_CR4","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.jcss.2019.04.006","volume":"105","author":"Y Bartal","year":"2019","unstructured":"Bartal, Y., Filtser, A., Neiman, O.: On notions of distortion and an almost minimum spanning tree with constant average distortion. J. Comput. System Sci. 105, 116\u2013129 (2019)","journal-title":"J. Comput. System Sci."},{"key":"565_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2018.07.011","volume":"757","author":"Y Bartal","year":"2019","unstructured":"Bartal, Y., Gottlieb, L.-A.: Approximate nearest neighbor search for $$\\ell _p$$-spaces ($$2<p<\\infty $$) via embeddings. Theor. Comput. Sci. 757, 27\u201335 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"565_CR6","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Isr. J. Math."},{"key":"565_CR7","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"MM Deza","year":"1997","unstructured":"Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)"},{"key":"565_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.06.021","volume":"697","author":"M Elkin","year":"2017","unstructured":"Elkin, M., Filtser, A., Neiman, O.: Terminal embeddings. Theor. Comput. Sci. 697, 1\u201336 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"565_CR9","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/17M1118749","volume":"47","author":"M Elkin","year":"2018","unstructured":"Elkin, M., Filtser, A., Neiman, O.: Prioritized metric structures and embedding. SIAM J. Comput. 47(3), 829\u2013858 (2018)","journal-title":"SIAM J. Comput."},{"key":"565_CR10","unstructured":"Elkin, M., Neiman, O.: Near isometric terminal embeddings for doubling metrics. In: 34th International Symposium on Computational Geometry (Budapest 2018). Leibniz International Proceedings in Informatics, vol. 99, #\u00a036. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"565_CR11","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Lossless prioritized embeddings. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 1049\u20131062. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.64"},{"issue":"3","key":"565_CR12","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. System Sci."},{"key":"565_CR13","doi-asserted-by":"crossref","unstructured":"Filtser, A., Gottlieb, L.-A., Krauthgamer, R.: Labelings vs. embeddings: On distributed representations of distances. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 1063\u20131075. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.65"},{"issue":"1","key":"565_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"565_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P.: On approximate nearest neighbors in non-Euclidean spaces. In: 39th Annual Symposium on Foundations of Computer Science (Palo Alto 1998), pp. 148\u2013155. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743438"},{"key":"565_CR16","doi-asserted-by":"crossref","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability (New Haven 1982). Contemporary Mathematics, vol. 26, pp. 189\u2013206. American Mathematical Society, Providence (1984)","DOI":"10.1090\/conm\/026\/737400"},{"key":"565_CR17","unstructured":"Klein, P.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: 13th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco 2002), pp. 820\u2013827. ACM, New York (2002)"},{"issue":"4","key":"565_CR18","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839\u2013858 (2005)","journal-title":"Geom. Funct. Anal."},{"issue":"2","key":"565_CR19","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Yu.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"565_CR20","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93(1), 333\u2013344 (1996)","journal-title":"Isr. J. Math."},{"key":"565_CR21","unstructured":"Matou\u0161ek, J.: Lecture notes on metric embeddings. Technical report, ETH Z\u00fcrich (2013). https:\/\/kam.mff.cuni.cz\/~matousek\/ba-a4.pdf"},{"key":"565_CR22","doi-asserted-by":"crossref","unstructured":"Narayanan, S., Nelson, J.: Optimal terminal dimensionality reduction in Euclidean space. In: 51st Annual ACM SIGACT Symposium on Theory of Computing (Phoenix 2019), pp. 1064\u20131069. ACM, New York (2019)","DOI":"10.1145\/3313276.3316307"},{"issue":"1","key":"565_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.: Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B 89(1), 43\u201376 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"565_CR24","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"565_CR25","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures (Hersonissos 2001), pp. 1\u201310. ACM, New York (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"565_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00565-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00565-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00565-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T05:02:41Z","timestamp":1730091761000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00565-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,15]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["565"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00565-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,9,15]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}