{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:50:44Z","timestamp":1759683044061},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>\n            Given a query object\n            <jats:italic>q,<\/jats:italic>\n            reverse\n            <jats:italic>k<\/jats:italic>\n            -nearest neighbor (R\n            <jats:italic>k<\/jats:italic>\n            NN) search aims to locate those objects of the database that have\n            <jats:italic>q<\/jats:italic>\n            among their\n            <jats:italic>k<\/jats:italic>\n            -nearest neighbors. In this paper, we propose an approximation method for solving R\n            <jats:italic>k<\/jats:italic>\n            NN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.\n          <\/jats:p>","DOI":"10.14778\/3067421.3067426","type":"journal-article","created":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T12:17:14Z","timestamp":1494591434000},"page":"769-780","source":"Crossref","is-referenced-by-count":17,"title":["Dimensional testing for reverse\n            <i>k<\/i>\n            -nearest neighbor search"],"prefix":"10.14778","volume":"10","author":[{"given":"Guillaume","family":"Casanova","sequence":"first","affiliation":[{"name":"ONERA-DCSD, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elias","family":"Englmeier","sequence":"additional","affiliation":[{"name":"LMU, Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael E.","family":"Houle","sequence":"additional","affiliation":[{"name":"NII, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peer","family":"Kr\u00f6ger","sequence":"additional","affiliation":[{"name":"LMU, Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Nett","sequence":"additional","affiliation":[{"name":"Google, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erich","family":"Schubert","sequence":"additional","affiliation":[{"name":"Heidelberg U., Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arthur","family":"Zimek","sequence":"additional","affiliation":[{"name":"SDU, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.111"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183731"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142531"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-007-0027-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783405"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_7_1","first-page":"131","article-title":"Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables","volume":"24","author":"Blackard J. A.","year":"1999","unstructured":"J. A. Blackard and D. J. Dean . Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables . Comp Ag , 24 : 131 -- 151 , 1999 . J. A. Blackard and D. J. Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Comp Ag, 24:131--151, 1999.","journal-title":"Comp Ag"},{"key":"e_1_2_1_8_1","volume-title":"MMCBIR","author":"Boujemaa N.","year":"2001","unstructured":"N. Boujemaa , J. Fauqueur , M. Ferecatu , F. Fleuret , V. Gouet , B. LeSaux , and H. Sahbi . IKONA: Interactive specific and generic image retrieval . In MMCBIR , 2001 . N. Boujemaa, J. Fauqueur, M. Ferecatu, F. Fleuret, V. Gouet, B. LeSaux, and H. Sahbi. IKONA: Interactive specific and generic image retrieval. In MMCBIR, 2001."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767904"},{"key":"e_1_2_1_10_1","first-page":"426","volume-title":"VLDB","author":"Ciaccia P.","year":"1997","unstructured":"P. Ciaccia , M. Patella , and P. Zezula . M-tree: An efficient access method for similarity search in metric spaces . In VLDB , pages 426 -- 435 , 1997 . P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, pages 426--435, 1997."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.151"},{"key":"e_1_2_1_13_1","volume-title":"Mathematical Foundations and Applications","author":"Falconer K.","year":"2003","unstructured":"K. Falconer . Fractal Geometry : Mathematical Foundations and Applications . Wiley , 2003 . K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, 2003."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000042993.50813.60"},{"key":"e_1_2_1_15_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999","unstructured":"A. Gionis , P. Indyk , and R. Motwani . Similarity search in high dimensions via hashing . In VLDB , pages 518 -- 529 , 1999 . A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518--529, 1999."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21830-4_12"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018429.1021000"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102388"},{"key":"e_1_2_1_20_1","first-page":"468","volume-title":"ICDMW","author":"Houle M. E.","year":"2013","unstructured":"M. E. Houle . Dimensionality , discriminability, density & distance distributions . In ICDMW , pages 468 -- 473 , 2013 . M. E. Houle. Dimensionality, discriminability, density & distance distributions. In ICDMW, pages 468--473, 2013."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2012.94"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.91"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2475740"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.01.008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.66"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_68"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335415"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.144"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"e_1_2_1_32_1","volume-title":"UCI machine learning repository","author":"Lichman M.","year":"2013","unstructured":"M. Lichman . UCI machine learning repository , 2013 . University of California , Irvine, School of Information and Computer Sciences. M. Lichman. UCI machine learning repository, 2013. University of California, Irvine, School of Information and Computer Sciences."},{"key":"e_1_2_1_33_1","first-page":"128","volume-title":"CCCG","author":"Maheshwari A.","year":"2002","unstructured":"A. Maheshwari , J. Vahrenhold , and N. Zeh . On reverse nearest neighbor queries . In CCCG , pages 128 -- 132 , 2002 . A. Maheshwari, J. Vahrenhold, and N. Zeh. On reverse nearest neighbor queries. In CCCG, pages 128--132, 2002."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5186\/aasfm.1975.0110"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.85"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIDM.2007.368917"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2365790"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-015-0816-y"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824115"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956882"},{"key":"e_1_2_1_41_1","first-page":"44","volume-title":"SIGMODW","author":"Stanoi I.","year":"2000","unstructured":"I. Stanoi , D. Agrawal , and A. El Abbadi . Reverse nearest neighbor queries for dynamic databases . In SIGMODW , pages 44 -- 53 , 2000 . I. Stanoi, D. Agrawal, and A. El Abbadi. Reverse nearest neighbor queries for dynamic databases. In SIGMODW, pages 44--53, 2000."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0091924"},{"key":"e_1_2_1_43_1","first-page":"744","volume-title":"VLDB","author":"Tao Y.","year":"2004","unstructured":"Y. Tao , D. Papadias , and X. Lian . Reverse kNN search in arbitrary dimensionality . In VLDB , pages 744 -- 755 , 2004 . Y. Tao, D. Papadias, and X. Lian. Reverse kNN search in arbitrary dimensionality. In VLDB, pages 744--755, 2004."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.148"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(88)91016-X"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.25"},{"key":"e_1_2_1_47_1","first-page":"194","volume-title":"VLDB","author":"Weber R.","year":"1998","unstructured":"R. Weber , H.-J. Schek , and S. Blott . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB , pages 194 -- 205 , 1998 . R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, pages 194--205, 1998."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0230-1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453970"},{"key":"e_1_2_1_50_1","first-page":"946","volume-title":"VLDB","author":"Xia T.","year":"2005","unstructured":"T. Xia , D. Zhang , E. Kanoulas , and Y. Du . On computing top-t most influential spatial sites . In VLDB , pages 946 -- 957 , 2005 . T. Xia, D. Zhang, E. Kanoulas, and Y. Du. On computing top-t most influential spatial sites. In VLDB, pages 946--957, 2005."},{"key":"e_1_2_1_51_1","first-page":"485","volume-title":"ICDE","author":"Yang C.","year":"2001","unstructured":"C. Yang and K.-I. Lin . An index structure for efficient reverse nearest neighbor queries . In ICDE , pages 485 -- 492 , 2001 . C. Yang and K.-I. Lin. An index structure for efficient reverse nearest neighbor queries. In ICDE, pages 485--492, 2001."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3067421.3067426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:19:39Z","timestamp":1672219179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3067421.3067426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3]]},"references-count":50,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["10.14778\/3067421.3067426"],"URL":"https:\/\/doi.org\/10.14778\/3067421.3067426","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,3]]}}}