{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:21:52Z","timestamp":1773886912294,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T00:00:00Z","timestamp":1691107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"This work was funded by the Korea Meteorological Administration Research and Development Program Developing Intelligent Assistant Technology and Its Application for Weather Forecasting Process under Grant (KMA2021-00123)","award":["KMA2021-00123"],"award-info":[{"award-number":["KMA2021-00123"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,8,6]]},"DOI":"10.1145\/3580305.3599327","type":"proceedings-article","created":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T18:13:58Z","timestamp":1691172838000},"page":"1097-1106","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Distributed Approximate k-Nearest Neighbor Graph Construction by Multiway Random Division Forest"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-0159-6215","authenticated-orcid":false,"given":"Sang-Hong","family":"Kim","sequence":"first","affiliation":[{"name":"Kookmin University, Seoul, Republic of Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6421-8880","authenticated-orcid":false,"given":"Ha-Myung","family":"Park","sequence":"additional","affiliation":[{"name":"Kookmin University, Seoul, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2023,8,4]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Anastasiu and George Karypis","author":"David","year":"2015","unstructured":"David C. Anastasiu and George Karypis . 2015 . L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning. In CIKM, James Bailey, Alistair Moffat, Charu C. Aggarwal, Maarten de Rijke, Ravi Kumar, Vanessa Murdock, Timos K. Sellis, and Jeffrey Xu Yu (Eds.). ACM , 791--800. https:\/\/doi.org\/10.1145\/2806416.2806534 10.1145\/2806416.2806534 David C. Anastasiu and George Karypis. 2015. L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning. In CIKM, James Bailey, Alistair Moffat, Charu C. Aggarwal, Maarten de Rijke, Ravi Kumar, Vanessa Murdock, Timos K. Sellis, and Jeffrey Xu Yu (Eds.). ACM, 791--800. https:\/\/doi.org\/10.1145\/2806416.2806534"},{"key":"e_1_3_2_2_2_1","volume-title":"Lempitsky","author":"Babenko Artem","year":"2016","unstructured":"Artem Babenko and Victor S . Lempitsky . 2016 . Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR. IEEE Computer Society , 2055--2063. Artem Babenko and Victor S. Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR. IEEE Computer Society, 2055--2063."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5308"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Leonid Boytsov David Novak Yury Malkov and Eric Nyberg. 2016. Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search. In CIKM Snehasis Mukhopadhyay ChengXiang Zhai Elisa Bertino Fabio Crestani Javed Mostafa Jie Tang Luo Si Xiaofang Zhou Yi Chang Yunyao Li and Parikshit Sondhi (Eds.). ACM 1099--1108.  Leonid Boytsov David Novak Yury Malkov and Eric Nyberg. 2016. Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search. In CIKM Snehasis Mukhopadhyay ChengXiang Zhai Elisa Bertino Fabio Crestani Javed Mostafa Jie Tang Luo Si Xiaofang Zhou Yi Chang Yunyao Li and Parikshit Sondhi (Eds.). ACM 1099--1108.","DOI":"10.1145\/2983323.2983815"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1755852"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.16"},{"key":"e_1_3_2_2_7_1","volume-title":"WWW,, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar","author":"Dong Wei","unstructured":"Wei Dong , Moses Charikar , and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures . In WWW,, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar , M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM , 577--586. Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW,, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM, 577--586."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408889"},{"key":"e_1_3_2_2_9_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai . 2016 . EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR , Vol. abs\/ 1609 .07228 (2016). Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR, Vol. abs\/1609.07228 (2016)."},{"key":"e_1_3_2_2_10_1","volume-title":"LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI","author":"Goodge Adam","year":"2022","unstructured":"Adam Goodge , Bryan Hooi , See-Kiong Ng , and Wee Siong Ng . 2022 . LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022. AAAI Press , 6737--6745. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/20629 Adam Goodge, Bryan Hooi, See-Kiong Ng, and Wee Siong Ng. 2022. LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022. AAAI Press, 6737--6745. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/20629"},{"key":"#cr-split#-e_1_3_2_2_11_1.1","doi-asserted-by":"crossref","unstructured":"Rachid Guerraoui Anne-Marie Kermarrec Olivier Ruas and Francc ois Ta\"i ani. 2020. Smaller Faster & Lighter KNN Graph Constructions. In WWW Yennun Huang Irwin King Tie-Yan Liu and Maarten van Steen (Eds.). ACM \/ IW3C2 1060--1070. https:\/\/doi.org\/10.1145\/3366423.3380184 10.1145\/3366423.3380184","DOI":"10.1145\/3366423.3380184"},{"key":"#cr-split#-e_1_3_2_2_11_1.2","doi-asserted-by":"crossref","unstructured":"Rachid Guerraoui Anne-Marie Kermarrec Olivier Ruas and Francc ois Ta\"i ani. 2020. Smaller Faster & Lighter KNN Graph Constructions. In WWW Yennun Huang Irwin King Tie-Yan Liu and Maarten van Steen (Eds.). ACM \/ IW3C2 1060--1070. https:\/\/doi.org\/10.1145\/3366423.3380184","DOI":"10.1145\/3366423.3380184"},{"key":"e_1_3_2_2_12_1","volume-title":"Outlier Detection Using k-Nearest Neighbour Graph","author":"Ville","unstructured":"Ville Hautam\"a ki, Ismo K\"a rkk\"a inen, and Pasi Fr\"a nti. 2004. Outlier Detection Using k-Nearest Neighbour Graph . In ICPR. IEEE Computer Society , 430--433. Ville Hautam\"a ki, Ismo K\"a rkk\"a inen, and Pasi Fr\"a nti. 2004. Outlier Detection Using k-Nearest Neighbour Graph. In ICPR. IEEE Computer Society, 430--433."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_12"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094114.2094118"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3021903"},{"key":"e_1_3_2_2_18_1","volume-title":"Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses. CoRR","author":"Liu Yingfan","year":"2021","unstructured":"Yingfan Liu , Hong Cheng , and Jiangtao Cui . 2021. Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses. CoRR , Vol. abs\/ 2112 .02234 ( 2021 ). showeprint[arXiv]2112.02234 https:\/\/arxiv.org\/abs\/2112.02234 Yingfan Liu, Hong Cheng, and Jiangtao Cui. 2021. Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses. CoRR, Vol. abs\/2112.02234 (2021). showeprint[arXiv]2112.02234 https:\/\/arxiv.org\/abs\/2112.02234"},{"key":"e_1_3_2_2_19_1","volume-title":"Karina Figueroa, and Gonzalo Navarro.","author":"Paredes Rodrigo","year":"2006","unstructured":"Rodrigo Paredes , Edgar Ch\u00e1 vez , Karina Figueroa, and Gonzalo Navarro. 2006 . Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces. In WEA (Lecture Notes in Computer Science , Vol. 4007), Carme \u00c0 lvarez and Maria J. Serna (Eds.). Springer, 85-- 97 . Rodrigo Paredes, Edgar Ch\u00e1 vez, Karina Figueroa, and Gonzalo Navarro. 2006. Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces. In WEA (Lecture Notes in Computer Science, Vol. 4007), Carme \u00c0 lvarez and Maria J. Serna (Eds.). Springer, 85--97."},{"key":"e_1_3_2_2_20_1","volume-title":"WWW,, Leslie Carr, Alberto H. F. Laender","author":"Park Youngki","unstructured":"Youngki Park , Sungchan Park , Sang-goo Lee, and Woosung Jung . 2013. Scalable k-nearest neighbor graph construction based on greedy filtering . In WWW,, Leslie Carr, Alberto H. F. Laender , Bernadette Farias L\u00f3 scio, Irwin King, Marcus Fontoura, Denny Vrandecic, Lora Aroyo, Jos\u00e9 Palazzo M. de Oliveira, Fernanda Lima, and Erik Wilde (Eds.). International World Wide Web Conferences Steering Committee \/ ACM , 227--228. https:\/\/doi.org\/10.1145\/2487788.2487905 10.1145\/2487788.2487905 Youngki Park, Sungchan Park, Sang-goo Lee, and Woosung Jung. 2013. Scalable k-nearest neighbor graph construction based on greedy filtering. In WWW,, Leslie Carr, Alberto H. F. Laender, Bernadette Farias L\u00f3 scio, Irwin King, Marcus Fontoura, Denny Vrandecic, Lora Aroyo, Jos\u00e9 Palazzo M. de Oliveira, Fernanda Lima, and Erik Wilde (Eds.). International World Wide Web Conferences Steering Committee \/ ACM, 227--228. https:\/\/doi.org\/10.1145\/2487788.2487905"},{"key":"e_1_3_2_2_21_1","volume-title":"Manning","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington , Richard Socher , and Christopher D . Manning . 2014 . Glove : Global Vectors for Word Representation. In EMNLP,, Alessandro Moschitti, Bo Pang, and Walter Daelemans (Eds.). ACL , 1532--1543. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global Vectors for Word Representation. In EMNLP,, Alessandro Moschitti, Bo Pang, and Walter Daelemans (Eds.). ACL, 1532--1543."},{"key":"e_1_3_2_2_22_1","volume-title":"ICBDC (Shenzhen, China)","author":"Sieranoja Sami","year":"2019","unstructured":"Sami Sieranoja and Pasi Fr\"anti. 2018. Fast Random Pair Divisive Construction of KNN Graph Using Generic Distance Measures . In ICBDC (Shenzhen, China) . Association for Computing Machinery , New York, NY, USA , 95--98. https:\/\/doi.org\/10.1145\/32 2019 9.3220215 10.1145\/3220199.3220215 Sami Sieranoja and Pasi Fr\"anti. 2018. Fast Random Pair Divisive Construction of KNN Graph Using Generic Distance Measures. In ICBDC (Shenzhen, China). Association for Computing Machinery, New York, NY, USA, 95--98. https:\/\/doi.org\/10.1145\/3220199.3220215"},{"key":"e_1_3_2_2_23_1","volume-title":"WWW,, Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, and Ben Y","author":"Tang Jian","unstructured":"Jian Tang , Jingzhou Liu , Ming Zhang , and Qiaozhu Mei . 2016. Visualizing Large-scale and High-dimensional Data . In WWW,, Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, and Ben Y . Zhao (Eds.). ACM , 287--297. Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. 2016. Visualizing Large-scale and High-dimensional Data. In WWW,, Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, and Ben Y. Zhao (Eds.). ACM, 287--297."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187718"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_2_26_1","volume-title":"Large-Scale Approximate k-NN Graph Construction on GPU. CoRR","author":"Wang Hui","year":"2021","unstructured":"Hui Wang , Wan-Lei Zhao , and Xiangxiang Zeng . 2021. Large-Scale Approximate k-NN Graph Construction on GPU. CoRR , Vol. abs\/ 2103 .15386 ( 2021 ). Hui Wang, Wan-Lei Zhao, and Xiangxiang Zeng. 2021. Large-Scale Approximate k-NN Graph Construction on GPU. CoRR, Vol. abs\/2103.15386 (2021)."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6247790"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2022.102124"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2014EDP7108"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2021.107295"},{"key":"e_1_3_2_2_31_1","volume-title":"MM,, Heng Tao Shen, Yueting Zhuang, John R","author":"Zhang Jinghao","unstructured":"Jinghao Zhang , Yanqiao Zhu , Qiang Liu , Shu Wu , Shuhui Wang , and Liang Wang . 2021a. Mining Latent Structures for Multimedia Recommendation . In MM,, Heng Tao Shen, Yueting Zhuang, John R . Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM , 3872--3880. https:\/\/doi.org\/10.1145\/3474085.3475259 10.1145\/3474085.3475259 Jinghao Zhang, Yanqiao Zhu, Qiang Liu, Shu Wu, Shuhui Wang, and Liang Wang. 2021a. Mining Latent Structures for Multimedia Recommendation. In MM,, Heng Tao Shen, Yueting Zhuang, John R. Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM, 3872--3880. https:\/\/doi.org\/10.1145\/3474085.3475259"},{"key":"e_1_3_2_2_32_1","volume-title":"Mining Latent Structures for Multimedia Recommendation. In MM '21: ACM Multimedia Conference","author":"Zhang Jinghao","year":"2021","unstructured":"Jinghao Zhang , Yanqiao Zhu , Qiang Liu , Shu Wu , Shuhui Wang , and Liang Wang . 2021 b. Mining Latent Structures for Multimedia Recommendation. In MM '21: ACM Multimedia Conference , Virtual Event, China, October 20 - 24 , 2021. ACM, 3872--3880. https:\/\/doi.org\/10.1145\/3474085.3475259 10.1145\/3474085.3475259 Jinghao Zhang, Yanqiao Zhu, Qiang Liu, Shu Wu, Shuhui Wang, and Liang Wang. 2021b. Mining Latent Structures for Multimedia Recommendation. In MM '21: ACM Multimedia Conference, Virtual Event, China, October 20 - 24, 2021. ACM, 3872--3880. https:\/\/doi.org\/10.1145\/3474085.3475259"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40991-2_42"}],"event":{"name":"KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Long Beach CA USA","acronym":"KDD '23","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599327","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580305.3599327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:47Z","timestamp":1750178267000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,4]]},"references-count":34,"alternative-id":["10.1145\/3580305.3599327","10.1145\/3580305"],"URL":"https:\/\/doi.org\/10.1145\/3580305.3599327","relation":{},"subject":[],"published":{"date-parts":[[2023,8,4]]},"assertion":[{"value":"2023-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}