{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T12:55:32Z","timestamp":1676465732563},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            A R\n            <jats:italic>k<\/jats:italic>\n            NN query returns all objects whose nearest\n            <jats:italic>k<\/jats:italic>\n            neighbors contain the query object. In this paper, we consider R\n            <jats:italic>k<\/jats:italic>\n            NN query processing in the case where the distances between attribute values are not necessarily metric. Dissimilarities between objects could then be a monotonic aggregate of dissimilarities between their values, such aggregation functions being specified at query time. We outline real world cases that motivate R\n            <jats:italic>k<\/jats:italic>\n            NN processing in such scenarios. We consider the AL-Tree index and its applicability in R\n            <jats:italic>k<\/jats:italic>\n            NN query processing. We develop an approach that exploits the group level reasoning enabled by the AL-Tree in R\n            <jats:italic>k<\/jats:italic>\n            NN processing. We evaluate our approach against a Naive approach that performs sequential scans on contiguous data and an improved block-based approach that we provide. We use real-world datasets and synthetic data with varying characteristics for our experiments. This extensive empirical evaluation shows that our approach is better than existing methods in terms of computational and disk access costs, leading to significantly better response times.\n          <\/jats:p>","DOI":"10.14778\/1920841.1920995","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1243-1254","source":"Crossref","is-referenced-by-count":1,"title":["Efficient RkNN retrieval with arbitrary non-metric similarity measures"],"prefix":"10.14778","volume":"3","author":[{"given":"P.","family":"Deepak","sequence":"first","affiliation":[{"name":"IBM Research - India, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad M.","family":"Deshpande","sequence":"additional","affiliation":[{"name":"IBM Research - India, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"How fast is your disk? http:\/\/www.linuxinsight.com\/how_fast_is_your-disk.html January 2007.  How fast is your disk? http:\/\/www.linuxinsight.com\/how_fast_is_your-disk.html January 2007."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142531"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516462"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497441"},{"key":"e_1_2_1_5_1","first-page":"475","volume-title":"VLDB","author":"Bast H.","year":"2006","unstructured":"H. Bast , D. Majumdar , R. Schenkel , M. Theobald , and G. Weikum . Io-top-k: Index-access optimized top-k query processing . In VLDB , pages 475 -- 486 , 2006 . H. Bast, D. Majumdar, R. Schenkel, M. Theobald, and G. Weikum. Io-top-k: Index-access optimized top-k query processing. In VLDB, pages 475--486, 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11827405_83"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/INGS.2008.12"},{"key":"e_1_2_1_9_1","volume-title":"abs\/0905.4441","author":"Vigneron O Cheong A","year":"2009","unstructured":"O Cheong A Vigneron and J Yon Reverse nearest neighbor queries in fixed dimension. CoRR , abs\/0905.4441 , 2009 . O Cheong A Vigneron and J Yon Reverse nearest neighbor queries in fixed dimension. CoRR, abs\/0905.4441, 2009."},{"key":"e_1_2_1_10_1","volume-title":"Microsoft Research TR","author":"Chung W.","year":"2000","unstructured":"W. Chung , Gray and Horst . Windows 2000 disk io performance . Microsoft Research TR , June 2000. W. Chung, Gray and Horst. Windows 2000 disk io performance. Microsoft Research TR, June 2000."},{"key":"e_1_2_1_11_1","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 , 1997 . P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, 1997."},{"key":"e_1_2_1_12_1","first-page":"291","volume-title":"VLDB","author":"Dellis E.","year":"2007","unstructured":"E. Dellis and B. Seeger . Efficient computation of reverse skyline queries . In VLDB , pages 291 -- 302 , 2007 . E. Dellis and B. Seeger. Efficient computation of reverse skyline queries. In VLDB, pages 291--302, 2007."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353388"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/641007.641107"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335415"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02279-1_32"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.36"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972788.60"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.92.3.289"},{"key":"e_1_2_1_22_1","volume-title":"EDBT","author":"Deshpande D. P, P. M.","year":"2009","unstructured":"D. P, P. M. Deshpande , D. Majumdar , and R. Krishnapuram . Efficient skyline retrieval with arbitrary similarity measures . In EDBT , 2009 . D. P, P. M. Deshpande, D. Majumdar, and R. Krishnapuram. Efficient skyline retrieval with arbitrary similarity measures. In EDBT, 2009."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956882"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85654-2_30"},{"key":"e_1_2_1_25_1","first-page":"44","volume-title":"In SIGMOD Workshop on DMKD","author":"Stanoi I.","year":"2000","unstructured":"I. Stanoi , D. Agrawal , and A. E. Abbadi . Reverse nearest neighbor queries for dynamic databases . In In SIGMOD Workshop on DMKD , pages 44 -- 53 , 2000 . I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In In SIGMOD Workshop on DMKD, pages 44--53, 2000."},{"key":"e_1_2_1_26_1","volume-title":"VLDB","author":"Tao Y.","year":"2004","unstructured":"Y. Tao , D. Papadias , and X. Lian . Reverse knn search in arbitrary dimensionality . In VLDB , 2004 . Y. Tao, D. Papadias, and X. Lian. Reverse knn search in arbitrary dimensionality. In VLDB, 2004."},{"key":"e_1_2_1_27_1","first-page":"2002","article-title":"Robust similarity measures for mobile object trajectories","author":"Vlachos M.","year":"2002","unstructured":"M. Vlachos , D. Gunopulos , and G. Kollios . Robust similarity measures for mobile object trajectories . In DEXA 2002 , 2002 . M. Vlachos, D. Gunopulos, and G. Kollios. Robust similarity measures for mobile object trajectories. In DEXA 2002, 2002.","journal-title":"DEXA"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099697"},{"key":"e_1_2_1_29_1","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 , 2001 . C. Yang and K.-I. Lin. An index structure for efficient reverse nearest neighbor queries. In ICDE, 2001."},{"key":"e_1_2_1_30_1","volume-title":"ISKE","author":"Yanmin Luo J. L.","year":"2008","unstructured":"J. L. Yanmin Luo , Canhong Lian and H. Chen . Finding rknn by compressed straightforward index . In ISKE , 2008 . J. L. Yanmin Luo, Canhong Lian and H. Chen. Finding rknn by compressed straightforward index. In ISKE, 2008."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.47"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:51:06Z","timestamp":1672228266000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920995"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920995","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}