{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T21:35:30Z","timestamp":1777325730988,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>\n            Given a set of users, a set of facilities and a query facility\n            <jats:italic>q<\/jats:italic>\n            , a reverse\n            <jats:italic>k<\/jats:italic>\n            nearest neighbors (R\n            <jats:italic>k<\/jats:italic>\n            NN) query returns every user\n            <jats:italic>u<\/jats:italic>\n            for which the query is one of its\n            <jats:italic>k<\/jats:italic>\n            closest facilities. R\n            <jats:italic>k<\/jats:italic>\n            NN queries have been extensively studied under a variety of settings and many sophisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limitations. For example, some studies\n            <jats:italic>estimate<\/jats:italic>\n            the I\/O cost by charging a fixed penalty per I\/O and we show that this may be misleading. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvantage. We show that the performance of these algorithms is significantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed algorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessarily true as shown in our experimental study. Motivated by these limitations, we present a comprehensive experimental study that addresses these limitations and compares some of the most notable algorithms under a wide variety of settings. Furthermore, we also present a carefully developed filtering strategy that significantly improves TPL which is one of the most popular R\n            <jats:italic>k<\/jats:italic>\n            NN algorithms. Specifically, the optimized version is up to 20 times faster than the original version and reduces its I\/O cost up to two times.\n          <\/jats:p>","DOI":"10.14778\/2735479.2735492","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"605-616","source":"Crossref","is-referenced-by-count":45,"title":["Reverse k nearest neighbors query processing"],"prefix":"10.14778","volume":"8","author":[{"given":"Shiyu","family":"Yang","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muhammad Aamir","family":"Cheema","sequence":"additional","affiliation":[{"name":"Monash University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"HP Technical Brief","year":"2012"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516462"},{"key":"e_1_2_1_3_1","first-page":"44","volume-title":"IDEAS","author":"Benetis R.","year":"2002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2021017.2021024"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.108"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767904"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687755"},{"key":"e_1_2_1_8_1","first-page":"427","volume-title":"Proc. 17th International Conference on Extending Database Technology (EDBT)","author":"Cheema M. A.","year":"2014"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0265-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0235-9"},{"key":"e_1_2_1_11_1","first-page":"291","volume-title":"PVLDB","author":"Dellis E.","year":"2007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263689"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335415"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556580"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry An Introduction","author":"Preparata F. P.","year":"1985"},{"key":"e_1_2_1_16_1","first-page":"405","volume-title":"USENIX Winter","author":"Ruemmler C.","year":"1993"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920994"},{"key":"e_1_2_1_18_1","first-page":"44","volume-title":"ACM SIGMOD Workshop","author":"Stanoi I.","year":"2000"},{"key":"e_1_2_1_19_1","first-page":"99","volume-title":"PVLDB","author":"Stanoi I.","year":"2001"},{"key":"e_1_2_1_20_1","first-page":"744","volume-title":"PVLDB","author":"Tao Y.","year":"2004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0168-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.148"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559854"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447890"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453970"},{"key":"e_1_2_1_26_1","unstructured":"www.census.gov\/geo\/maps-data\/data\/tiger line.html.  www.census.gov\/geo\/maps-data\/data\/tiger line.html."},{"key":"e_1_2_1_27_1","unstructured":"www.cs.fsu.edu\/%7Elifeifei\/SpatialDataset.htm.  www.cs.fsu.edu\/%7Elifeifei\/SpatialDataset.htm."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816698"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.62"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.47"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.67"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732276"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735479.2735492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:19:37Z","timestamp":1672226377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735492"}},"subtitle":["experiments and analysis"],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735492"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735492","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}