{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:53Z","timestamp":1763458073675,"version":"3.45.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,10,10]],"date-time":"2017-10-10T00:00:00Z","timestamp":1507593600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007523","name":"Advanced Cyberinfrastructure","doi-asserted-by":"publisher","award":["ACI-1443046"],"award-info":[{"award-number":["ACI-1443046"]}],"id":[{"id":"10.13039\/100007523","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["GRF-621413, GRF-16211614, GRF-16200415"],"award-info":[{"award-number":["GRF-621413, GRF-16211614, GRF-16200415"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-09-40671, CCF-10-12254, CCF-11-61359, CCF-08-30691, CCF-11-17336, CCF-12-18791, CCF-09-15984, CCF-12- 17462, CCF-1350888"],"award-info":[{"award-number":["CCF-09-40671, CCF-10-12254, CCF-11-61359, CCF-08-30691, CCF-11-17336, CCF-12-18791, CCF-09-15984, CCF-12- 17462, CCF-1350888"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-14- 08846, IIS-1251019"],"award-info":[{"award-number":["IIS-14- 08846, IIS-1251019"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009226","name":"National Security Agency","doi-asserted-by":"publisher","award":["H98230-10-1-0210"],"award-info":[{"award-number":["H98230-10-1-0210"]}],"id":[{"id":"10.13039\/100009226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"<jats:p>Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has a wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.<\/jats:p>","DOI":"10.1145\/2955098","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T14:01:35Z","timestamp":1476194495000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Nearest-Neighbor Searching Under Uncertainty II"],"prefix":"10.1145","volume":"13","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}]},{"given":"Boris","family":"Aronov","sequence":"additional","affiliation":[{"name":"New York University, Brooklyn, New York"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL, USA"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[{"name":"University of Utah, UT, USA"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Wuzhou","family":"Zhang","sequence":"additional","affiliation":[{"name":"Apple Inc., CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,10,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496791"},{"key":"e_1_2_1_2_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Agarwal P. K.","unstructured":"P. K. Agarwal. 2016. Range searching. In Handbook of Discrete and Computational Geometry (3rd ed.), J. E. Goodman, J. O\u2019Rourke, and C. Toth (Eds.). CRC Press, Chapter 41, to appear.","edition":"3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281840"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213588"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"P. K. Agarwal and M. Sharir. 2000. Arrangements and their applications. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia (Eds.). North-Holland Publishing Co. Amsterdam 49--119. 10.1016\/B978-044482537-7\/50003-6","DOI":"10.1016\/B978-044482537-7\/50003-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09690-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00164401"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767908"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453895"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497506"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516438"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.46"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447917"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_23"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.192"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.10.010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"H. Kaplan W. Mulzer L. Roditty P. Seiferth and M. Sharir. 2016. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. CoRR abs\/1604.03654 (2016).","DOI":"10.1137\/1.9781611974782.165"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783823.1783863"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367940"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK. 10.1017\/CBO9780511814075","DOI":"10.1017\/CBO9780511814075"},{"volume-title":"Proc. 20th Canad. Conf. Comput. Geom. 207--210","author":"Sember J.","key":"e_1_2_1_26_1","unstructured":"J. Sember and W. Evans. 2008. Guaranteed Voronoi diagrams of uncertain sites. In Proc. 20th Canad. Conf. Comput. Geom. 207--210."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press.","DOI":"10.5555\/235229"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.137"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544822"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955098","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2955098","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2955098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:16:19Z","timestamp":1763457379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,10]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2955098"],"URL":"https:\/\/doi.org\/10.1145\/2955098","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,10,10]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}