{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:44Z","timestamp":1740109244726,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0915984","CCF- 1217462"],"award-info":[{"award-number":["CCF-0915984","CCF- 1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231"],"award-info":[{"award-number":["CCF-1421231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0254-4","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T16:26:53Z","timestamp":1480350413000},"page":"279-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Robust Proximity Search for Balls Using Sublinear Space"],"prefix":"10.1007","volume":"80","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6601-2790","authenticated-orcid":false,"given":"Nirman","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"issue":"1","key":"254_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/1327452.1327494","volume":"51","author":"A Andoni","year":"2008","unstructured":"Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1), 117\u2013122 (2008)","journal-title":"Commun. ACM"},{"key":"254_CR2","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T.: Linear-size approximate Voronoi diagrams. In: Proceedings of the 13th ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 147\u2013155 (2002)","DOI":"10.1145\/509907.510011"},{"key":"254_CR3","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Space\u2013time tradeoffs for approximate spherical range counting. In: Proceedings of the 16th ACM-SIAM Symposium Discrete Algs (SODA), pp. 535\u2013544 (2005)"},{"issue":"1","key":"254_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1613676.1613677","volume":"57","author":"S Arya","year":"2009","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Space\u2013time tradeoffs for approximate nearest neighbor searching. J. Assoc. Comput. Mach. 57(1), 1\u201354 (2009)","journal-title":"J. Assoc. Comput. Mach."},{"key":"254_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"S Arya","year":"2000","unstructured":"Arya, S., Mount, D.M.: Approximate range searching. Comput. Geom. Theory Appl. 17, 135\u2013152 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"6","key":"254_CR6","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. Assoc. Comput. Mach. 45(6), 891\u2013923 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"254_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to $$k$$-nearest-neighbors and $$n$$-body potential fields. J. Assoc. Comput. Mach. 42, 67\u201390 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"254_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00453-004-1130-1","volume":"41","author":"P Carmi","year":"2005","unstructured":"Carmi, P., Dolev, S., Har-Peled, S., Katz, M.J., Segal, M.: Geographic quorum systems approximations. Algorithmica 41(4), 233\u2013244 (2005)","journal-title":"Algorithmica"},{"key":"254_CR9","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","volume-title":"Nearest-Neighbor Methods for Learning and Vision: Theory and Practice","author":"KL Clarkson","year":"2006","unstructured":"Clarkson, K.L.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp. 15\u201359. MIT Press, Cambridge (2006)"},{"key":"254_CR10","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/j.comgeo.2009.11.001","volume":"43","author":"M de Berg","year":"2010","unstructured":"de Berg, M., Haverkort, H., Thite, S., Toma, L.: Star-quadtrees and guard-quadtrees: I\/O-efficient indexes for fat triangulations and low-density planar subdivisions. Comput. Geom. Theory Appl. 43, 493\u2013513 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"254_CR11","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proceedings of the 42nd Annual IEEE Symposium Foundations of Computer Science (FOCS), pp. 94\u2013103 (2001)","DOI":"10.1109\/SFCS.2001.959884"},{"key":"254_CR12","series-title":"Mathematical Surveys and Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Boston (2011)"},{"key":"254_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. Theory Comput. 8, 321\u2013350 (2012). Special issue in honor of Rajeev Motwani","journal-title":"Theory Comput."},{"issue":"4","key":"254_CR14","doi-asserted-by":"publisher","first-page":"1486","DOI":"10.1137\/130916448","volume":"43","author":"S Har-Peled","year":"2014","unstructured":"Har-Peled, S., Kumar, N.: Down the rabbit hole: robust proximity search in sublinear space. SIAM J. Comput. 43(4), 1486\u20131511 (2014)","journal-title":"SIAM J. Comput."},{"key":"254_CR15","unstructured":"Har-Peled, S., Kumar, N.: Robust proximity search for balls using sublinear space. In: Proceedings of the 34th Conference Foundation of Software Technology and Theoretical Computer Science (FFSTTCS), LIPIcs, vol. 29, pp. 315\u2013326 (2014)"},{"issue":"4","key":"254_CR16","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1137\/140959067","volume":"44","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Kumar, N.: Approximating minimization diagrams and generalized proximity search. SIAM J. Comput. 44(4), 944\u2013974 (2015)","journal-title":"SIAM J. Comput."},{"key":"254_CR17","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the 30th Annual ACM Symposium Theory Computing (STOC), pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"254_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4908.001.0001","volume-title":"Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. Neur. Info. Proc.","author":"G Shakhnarovich","year":"2006","unstructured":"Shakhnarovich, G., Darrell, T., Indyk, P.: Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. Neur. Info. Proc. The MIT Press, Cambridge (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0254-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0254-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0254-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T02:45:30Z","timestamp":1692585930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0254-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["254"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0254-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,11,28]]},"assertion":[{"value":"8 September 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}