{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T20:17:29Z","timestamp":1791317849896,"version":"4.3.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor join (\n            <jats:italic>k<\/jats:italic>\n            NN join), designed to find\n            <jats:italic>k<\/jats:italic>\n            nearest neighbors from a dataset\n            <jats:italic>S<\/jats:italic>\n            for every object in another dataset\n            <jats:italic>R<\/jats:italic>\n            , is a primitive operation widely adopted by many data mining applications. As a combination of the\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor query and the join operation,\n            <jats:italic>k<\/jats:italic>\n            NN join is an expensive operation. Given the increasing volume of data, it is difficult to perform a\n            <jats:italic>k<\/jats:italic>\n            NN join on a centralized machine efficiently. In this paper, we investigate how to perform\n            <jats:italic>k<\/jats:italic>\n            NN join using MapReduce which is a well-accepted framework for data-intensive applications over clusters of computers. In brief, the mappers cluster objects into groups; the reducers perform the\n            <jats:italic>k<\/jats:italic>\n            NN join on each group of objects separately. We design an effective mapping mechanism that exploits pruning rules for distance filtering, and hence reduces both the shuffling and computational costs. To reduce the shuffling cost, we propose two approximate algorithms to minimize the number of replicas. Extensive experiments on our in-house cluster demonstrate that our proposed methods are efficient, robust and scalable.\n          <\/jats:p>","DOI":"10.14778\/2336664.2336674","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1016-1027","source":"Crossref","is-referenced-by-count":177,"title":["Efficient processing of k nearest neighbor joins using MapReduce"],"prefix":"10.14778","volume":"5","author":[{"given":"Wei","family":"Lu","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanyan","family":"Shen","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Su","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2010.92"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45227-0_50"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-003-0122-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656383"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335388"},{"key":"e_1_2_1_6_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters . In OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137--150, 2004."},{"key":"e_1_2_1_7_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_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920903"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.87"},{"key":"e_1_2_1_12_1","first-page":"392","volume-title":"VLDB","author":"Knorr E. M.","year":"1998","unstructured":"E. M. Knorr and R. T. Ng . Algorithms for mining distance-based outliers in large datasets . In VLDB , pages 392 -- 403 , 1998 . E. M. Knorr and R. T. Ng. Algorithms for mining distance-based outliers in large datasets. In VLDB, pages 392--403, 1998."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212353"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_1_15_1","first-page":"13","volume-title":"LSDS-IR","author":"Stupar A.","year":"2010","unstructured":"A. Stupar , S. Michel , and R. Schenkel . RankReduce - processing k-nearest neighbor queries on top of MapReduce . In LSDS-IR , pages 13 -- 18 , 2010 . A. Stupar, S. Michel, and R. Schenkel. RankReduce - processing k-nearest neighbor queries on top of MapReduce. In LSDS-IR, pages 13--18, 2010."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_17_1","first-page":"756","volume-title":"VLDB","author":"Xia C.","year":"2004","unstructured":"C. Xia , H. Lu , B. C. Ooi , and J. Hu . Gorder: An efficient method for knn join processing . In VLDB , pages 756 -- 767 , 2004 . C. Xia, H. Lu, B. C. Ooi, and J. Hu. Gorder: An efficient method for knn join processing. In VLDB, pages 756--767, 2004."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447837"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2006.05.006"},{"key":"e_1_2_1_20_1","first-page":"421","volume-title":"VLDB","author":"Yu C.","year":"2001","unstructured":"C. Yu , B. C. Ooi , K.-L. Tan , and H. V. Jagadish . Indexing the distance: An efficient method to knn processing . In VLDB , pages 421 -- 430 , 2001 . C. Yu, B. C. Ooi, K.-L. Tan, and H. V. Jagadish. Indexing the distance: An efficient method to knn processing. In VLDB, pages 421--430, 2001."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247602"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2336664.2336674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:46:01Z","timestamp":1672224361000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2336664.2336674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":21,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.14778\/2336664.2336674"],"URL":"https:\/\/doi.org\/10.14778\/2336664.2336674","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}