{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T17:00:56Z","timestamp":1772038856998,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>Uncertainty pervades many domains in our lives. Current real-life applications, e.g., location tracking using GPS devices or cell phones, multimedia feature extraction, and sensor data management, deal with different kinds of uncertainty. Finding the nearest neighbor objects to a given query point is an important query type in these applications.<\/jats:p>\n          <jats:p>In this paper, we study the problem of finding objects with the highest marginal probability of being the nearest neighbors to a query object. We adopt a general uncertainty model allowing for data and query uncertainty. Under this model, we define new query semantics, and provide several efficient evaluation algorithms. We analyze the cost factors involved in query evaluation, and present novel techniques to address the trade-offs among these factors. We give multiple extensions to our techniques including handling dependencies among data objects, and answering threshold queries. We conduct an extensive experimental study to evaluate our techniques on both real and synthetic data.<\/jats:p>","DOI":"10.14778\/1453856.1453895","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"326-339","source":"Crossref","is-referenced-by-count":100,"title":["Efficient search for the top-k probable nearest neighbors in uncertain databases"],"prefix":"10.14778","volume":"1","author":[{"given":"George","family":"Beskales","sequence":"first","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed A.","family":"Soliman","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Topologically integrated geographic encoding and referencing (tiger) system http:\/\/www.census.gov\/geo\/www\/tiger\/.  Topologically integrated geographic encoding and referencing (tiger) system http:\/\/www.census.gov\/geo\/www\/tiger\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational geometry algorithms and applications","author":"Berg M.","year":"2000","unstructured":"M. Berg , M. Kreveld , M. Overmars , and O. Schwarzkopf . Computational geometry algorithms and applications , 2 nd ed. springer verlag, 2000 . M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf. Computational geometry algorithms and applications, 2nd ed. springer verlag, 2000.","edition":"2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564731"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367904"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497506"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.46"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_23"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097070"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_11_1","volume-title":"Estimation and mapping of forest stand density, volume, and cover type using the k-nearest neighbors method. Remote Sensing of Environment","author":"Franco-Lopez H.","year":"2001","unstructured":"H. Franco-Lopez , A. R. Ek , and M. E. Bauer . Estimation and mapping of forest stand density, volume, and cover type using the k-nearest neighbors method. Remote Sensing of Environment 2001 . H. Franco-Lopez, A. R. Ek, and M. E. Bauer. Estimation and mapping of forest stand density, volume, and cover type using the k-nearest neighbors method. Remote Sensing of Environment 2001."},{"key":"e_1_2_1_12_1","volume-title":"Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface","author":"Geweke J.","year":"1991","unstructured":"J. Geweke . Efficient simulation from the multivariate normal and student---t distributions subject to linear constraints and the evaluation of constraint probabilities . In Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface , 1991 . J. Geweke. Efficient simulation from the multivariate normal and student---t distributions subject to linear constraints and the evaluation of constraint probabilities. In Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, 1991."},{"key":"e_1_2_1_13_1","unstructured":"M. Hadjieleftheriou. Spatial index library http:\/\/research.att.com\/~marioh\/spatialindex\/.  M. Hadjieleftheriou. Spatial index library http:\/\/research.att.com\/~marioh\/spatialindex\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/647224.718930"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183471.1183504"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783823.1783863"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375718"},{"key":"e_1_2_1_18_1","author":"Li E.","year":"2001","unstructured":"E. Li , D. Boos , and M. Gumpertz . Simulation study in statistics. Journal of Interconnection Networks , 2001 . E. Li, D. Boos, and M. Gumpertz. Simulation study in statistics. Journal of Interconnection Networks, 2001.","journal-title":"Journal of Interconnection Networks"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2006.890"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367940"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223794"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_1_28_1","volume-title":"VLDB","author":"Tao Y.","year":"2005","unstructured":"Y. Tao , R. Cheng , X. Xiao , W. K. Ngai , B. Kao , and S. Prabhakar . Indexing multi-dimensional uncertain data with arbitrary probability density functions . In VLDB , 2005 . Y. Tao, R. Cheng, X. Xiao, W. K. Ngai, B. Kao, and S. Prabhakar. Indexing multi-dimensional uncertain data with arbitrary probability density functions. In VLDB, 2005."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645340.650234"},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Weber R.","year":"1998","unstructured":"R. Weber , H. Schek , and S. Blott . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB , 1998 . R. Weber, H. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, 1998."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/VETECS.2001.944065"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:08Z","timestamp":1672225868000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453895"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453895","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}