{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:33:33Z","timestamp":1740137613127,"version":"3.37.3"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100015065","name":"DIMAP","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015065","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N011163\/1"],"award-info":[{"award-number":["EP\/N011163\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,4,30]]},"DOI":"10.1137\/22m1544105","type":"journal-article","created":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T08:27:55Z","timestamp":1713342475000},"page":"524-571","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear Time Approximation of the Cost of a Metric \\({k}\\)-Nearest Neighbor Graph"],"prefix":"10.1137","volume":"53","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, Coventry CV4 7AL, UK."}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Cologne, 50923 Cologne, Germany."}]}],"member":"351","published-online":{"date-parts":[[2024,4,17]]},"reference":[{"doi-asserted-by":"publisher","key":"ref1","DOI":"10.1145\/1327452.1327494"},{"doi-asserted-by":"publisher","key":"ref3","DOI":"10.1145\/2432622.2432626"},{"doi-asserted-by":"publisher","key":"ref4","DOI":"10.1137\/S0097539702403244"},{"key":"ref6","first-page":"37:1","author":"Chen Y.","year":"2023","journal-title":"ICALP"},{"doi-asserted-by":"publisher","key":"ref8","DOI":"10.1137\/S0097539703435297"},{"doi-asserted-by":"publisher","key":"ref9","DOI":"10.1137\/060672121"},{"doi-asserted-by":"publisher","key":"ref12","DOI":"10.1016\/0167-7152(91)90170-V"},{"doi-asserted-by":"publisher","key":"ref14","DOI":"10.1137\/S0097539704447304"},{"doi-asserted-by":"publisher","key":"ref16","DOI":"10.1080\/01621459.1977.10480637"},{"doi-asserted-by":"publisher","key":"ref18","DOI":"10.1002\/rsa.20203"},{"year":"1998","author":"K\u00fcnsch H. R.","journal-title":"note, ETH Z\u00fcrich","key":"ref22"},{"doi-asserted-by":"publisher","key":"ref23","DOI":"10.1023\/B:MACH.0000033114.18632.e0"},{"doi-asserted-by":"publisher","key":"ref24","DOI":"10.14778\/2824032.2824059"},{"doi-asserted-by":"publisher","key":"ref29","DOI":"10.1109\/TIT.2008.928987"},{"key":"ref30","volume-title":"Monogr. Statist. Appl. Probab.","volume":"26","author":"Silverman B. W.","year":"1986"},{"doi-asserted-by":"publisher","key":"ref31","DOI":"10.1109\/34.868688"},{"doi-asserted-by":"publisher","key":"ref32","DOI":"10.1126\/science.290.5500.2319"},{"doi-asserted-by":"publisher","key":"ref33","DOI":"10.1007\/s11222-007-9033-z"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,4,30]],"date-time":"2024-04-30T19:35:26Z","timestamp":1714505726000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1544105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,17]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1137\/22M1544105"],"URL":"https:\/\/doi.org\/10.1137\/22m1544105","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"type":"print","value":"0097-5397"},{"type":"electronic","value":"1095-7111"}],"subject":[],"published":{"date-parts":[[2024,4,17]]}}}