{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:40:11Z","timestamp":1755870011440,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","funder":[{"name":"NSERC","award":["RGPIN-2020-06639"],"award-info":[{"award-number":["RGPIN-2020-06639"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,8]]},"DOI":"10.1145\/3721145.3730415","type":"proceedings-article","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T12:57:17Z","timestamp":1755867437000},"page":"236-249","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["CLOVER: A GPU-native, Spatio-graph-based Approach to Exact kNN"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1999-6577","authenticated-orcid":false,"given":"Victor","family":"Kamel","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3128-9093","authenticated-orcid":false,"given":"Hanxueyu","family":"Yan","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1065-605X","authenticated-orcid":false,"given":"Sean","family":"Chester","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,22]]},"reference":[{"key":"e_1_3_3_2_2_2","series-title":"(SODA \u201907)","first-page":"1027","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii. 2007. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana) (SODA \u201907). Society for Industrial and Applied Mathematics, USA, 1027\u20131035."},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23400-2_35"},{"key":"e_1_3_3_2_4_2","unstructured":"Jose\u00a0Luis Blanco and Pranjal\u00a0Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN a library for Nearest Neighbor (NN) with KD-trees. https:\/\/github.com\/jlblancoc\/nanoflann."},{"key":"e_1_3_3_2_5_2","first-page":"574","volume-title":"Proc. of the 21st VLDB Conference","author":"Brin Sergey","year":"1995","unstructured":"Sergey Brin. 1995. Near Neighbor Search in Large Metric Spaces. In Proc. of the 21st VLDB Conference. 574\u2013584."},{"key":"e_1_3_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Christian B\u00f6hm and Florian Krebs. 2004. The k-Nearest Neighbour Join: Turbo Charging the KDD Process. Know. Inf. Sys. 6 (2004) 728\u2013749. 10.1007\/s10115-003-0122-9","DOI":"10.1007\/s10115-003-0122-9"},{"key":"e_1_3_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.116"},{"key":"e_1_3_3_2_8_2","first-page":"15489","volume-title":"Advances in Neural Information Processing Systems","volume":"35","author":"Chern Felix","year":"2022","unstructured":"Felix Chern, Blake Hechtman, Andy Davis, Ruiqi Guo, David Majnemer, and Sanjiv Kumar. 2022. TPU-KNN: K Nearest Neighbor Search at Peak FLOP\/s. In Advances in Neural Information Processing Systems , Vol.\u00a035. 15489\u201315501. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/639d992f819c2b40387d4d5170b8ffd7-Paper-Conference.pdf"},{"key":"e_1_3_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237269"},{"key":"e_1_3_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Tom\u00e1\u0161 Davidovi\u010d Jaroslav K\u0159iv\u00e1nek Milo\u0161 Ha\u0161an and Philipp Slusallek. 2014. Progressive Light Transport Simulation on the GPU: Survey and Improvements. ACM Trans. Graph. 33 3 Article 29 (June 2014) 19\u00a0pages. 10.1145\/2602144","DOI":"10.1145\/2602144"},{"key":"e_1_3_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Yufei Ding Xipeng Shen Madanlal Musuvathi and Todd Mytkowicz. 2015. TOP: a framework for enabling algorithmic optimizations for distance-related problems. Proc. VLDB Endow. 8 10 (June 2015) 1046\u20131057. 10.14778\/2794367.2794374","DOI":"10.14778\/2794367.2794374"},{"key":"e_1_3_3_2_12_2","unstructured":"Iordanis Evangelou Georgios Papaioannou Konstantinos Vardis and Andreas\u00a0A. Vasilakis. 2021. Fast Radius Search Exploiting Ray Tracing Frameworks. Journal of Computer Graphics Techniques (JCGT) 10 1 (5 February 2021) 25\u201348. http:\/\/jcgt.org\/published\/0010\/01\/02\/"},{"key":"e_1_3_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2008.4563100"},{"key":"e_1_3_3_2_14_2","doi-asserted-by":"crossref","unstructured":"Andreas Geiger Philip Lenz Christoph Stiller and Raquel Urtasun. 2013. Vision meets Robotics: The KITTI Dataset. International Journal of Robotics Research (IJRR) 32 11 (2013) 1231\u20131237.","DOI":"10.1177\/0278364913491297"},{"key":"e_1_3_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630908"},{"key":"e_1_3_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503223"},{"key":"e_1_3_3_2_17_2","doi-asserted-by":"publisher","unstructured":"Fabian Groh Lukas Ruppert Patrick Wieschollek and Hendrik Lensch. 2023. GGNN: Graph-based GPU Nearest Neighbor Search. IEEE transactions on big data 9 1 (2023) 1\u20131. 10.1109\/TBDATA.2022.3161156Place: Piscataway Publisher: IEEE.","DOI":"10.1109\/TBDATA.2022.3161156"},{"key":"e_1_3_3_2_18_2","series-title":"(ICML\u201920)","volume-title":"Proceedings of the 37th International Conference on Machine Learning","author":"Guo Ruiqi","year":"2020","unstructured":"Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning(ICML\u201920). JMLR.org, Article 364, 10\u00a0pages."},{"key":"e_1_3_3_2_19_2","unstructured":"Georges Hebrail and Alice Berard. 2006. Individual Household Electric Power Consumption. UCI Machine Learning Repository. DOI: https:\/\/doi.org\/10.24432\/C58K54."},{"key":"e_1_3_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532368"},{"key":"e_1_3_3_2_21_2","doi-asserted-by":"publisher","unstructured":"Jeff Johnson Matthijs Douze and Herv\u00e9 J\u00e9gou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7 3 (2021) 535\u2013547. 10.1109\/TBDATA.2019.2921572","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_3_3_2_22_2","unstructured":"Terence Kelly. 2020. Compressed Sparse Row Format for Representing Graphs. ;login: 45 4 (2020) 76\u201382."},{"key":"e_1_3_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Ivan Komarov Ali Dashti and Roshan\u00a0M. D\u2019Souza. 2014. Fast k-NNG Construction with GPU-Based Quick Multi-Select. PLOS ONE 9 5 (05 2014) 1\u20139. 10.1371\/journal.pone.0092409","DOI":"10.1371\/journal.pone.0092409"},{"key":"e_1_3_3_2_24_2","doi-asserted-by":"publisher","unstructured":"David\u00a0G Lowe. 2004. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60 (2004) 91\u2013110. 10.1023\/B:VISI.0000029664.99615.94","DOI":"10.1023\/B:VISI.0000029664.99615.94"},{"key":"e_1_3_3_2_25_2","doi-asserted-by":"publisher","unstructured":"Yu\u00a0A. Malkov and D.\u00a0A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42 4 (apr 2020) 824\u2013836. 10.1109\/TPAMI.2018.2889473","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_3_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3650200.3656601"},{"key":"e_1_3_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.125"},{"key":"e_1_3_3_2_28_2","first-page":"331","volume-title":"International Conference on Computer Vision Theory and Application (VISSAPP\u201909)","author":"Muja Marius","year":"2009","unstructured":"Marius Muja and David\u00a0G. Lowe. 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In International Conference on Computer Vision Theory and Application (VISSAPP\u201909). INSTICC Press, 331\u2013340."},{"key":"e_1_3_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3577193.3593738"},{"key":"e_1_3_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2016.20"},{"key":"e_1_3_3_2_31_2","unstructured":"Hiroyuki Ootomo Akira Naruse Corey Nolet Ray Wang Tamas Feher and Yong Wang. 2023. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. arxiv:https:\/\/arXiv.org\/abs\/2308.15136\u00a0[cs.DS]"},{"key":"e_1_3_3_2_32_2","unstructured":"Nikhila Ravi Jeremy Reizenstein David Novotny Taylor Gordon Wan-Yen Lo Justin Johnson and Georgia Gkioxari. 2020. Accelerating 3D Deep Learning with PyTorch3D. arxiv:https:\/\/arXiv.org\/abs\/2007.08501\u00a0[cs.CV] https:\/\/arxiv.org\/abs\/2007.08501"},{"key":"e_1_3_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Nicolas Ray Dmitry Sokolov Sylvain Lefebvre and Bruno L\u00e9vy. 2018. Meshless voronoi on the GPU. ACM Trans. Graph. 37 6 Article 265 (Dec. 2018) 12\u00a0pages. 10.1145\/3272127.3275092","DOI":"10.1145\/3272127.3275092"},{"key":"e_1_3_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980567"},{"key":"e_1_3_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.8"},{"key":"e_1_3_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183735"},{"key":"e_1_3_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408667"},{"key":"e_1_3_3_2_38_2","doi-asserted-by":"publisher","unstructured":"Volker Springel Simon D.\u00a0M. White Adrian Jenkins Carlos\u00a0S. Frenk Naoki Yoshida Liang Gao Julio Navarro Robert Thacker Darren Croton John Helly John\u00a0A. Peacock Shaun Cole Peter Thomas Hugh Couchman August Evrard J\u00f6rg Colberg and Frazer Pearce. 2005. Simulations of the formation evolution and clustering of galaxies and quasars. Nature 435 (2005) 629\u2013636. 10.1038\/nature03597","DOI":"10.1038\/nature03597"},{"key":"e_1_3_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.115"},{"key":"e_1_3_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192241"},{"key":"e_1_3_3_2_41_2","doi-asserted-by":"publisher","unstructured":"Polychronis Valentzas Michael Vassilakopoulos Antonio Corral and Christos Antonopoulos. 2023. GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Spatial Data Using Partitioning and Concurrent Kernel Execution. International Journal of Parallel Programming 51 6 (Dec. 2023) 275\u2013308. 10.1007\/s10766-023-00755-8","DOI":"10.1007\/s10766-023-00755-8"},{"key":"e_1_3_3_2_42_2","doi-asserted-by":"publisher","unstructured":"Jordi\u00a0L. Vermeulen Arne Hillebrand and Roland Geraerts. 2017. A comparative study of k-nearest neighbour techniques in crowd simulation. Computer Animation and Virtual Worlds 28 3\u20134 (2017) e1775. 10.1002\/cav.1775","DOI":"10.1002\/cav.1775"},{"key":"e_1_3_3_2_43_2","doi-asserted-by":"publisher","unstructured":"Bo Xiao and George Biros. 2016. Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions. SIAM Journal on Scientific Computing 38 5 (Jan. 2016) S667\u2013S699. 10.1137\/15M1026377","DOI":"10.1137\/15M1026377"},{"key":"e_1_3_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607062"},{"key":"e_1_3_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00094"},{"key":"e_1_3_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1457515.1409079"},{"key":"e_1_3_3_2_47_2","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10 000 3D-Printing Models. arxiv:https:\/\/arXiv.org\/abs\/1605.04797\u00a0[cs.GR]"},{"key":"e_1_3_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508409"},{"key":"e_1_3_3_2_49_2","unstructured":"Yifan Zhu Ruiyao Ma Baihua Zheng Xiangyu Ke Lu Chen and Yunjun Gao. 2024. GTS: GPU-based Tree Index for Fast Similarity Search. arXiv:https:\/\/arXiv.org\/abs\/2404.00966"}],"event":{"name":"ICS '25: 2025 International Conference on Supercomputing","location":"Salt Lake City USA","acronym":"ICS '25","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture"]},"container-title":["Proceedings of the 39th ACM International Conference on Supercomputing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721145.3730415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:03:31Z","timestamp":1755867811000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721145.3730415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,8]]},"references-count":48,"alternative-id":["10.1145\/3721145.3730415","10.1145\/3721145"],"URL":"https:\/\/doi.org\/10.1145\/3721145.3730415","relation":{},"subject":[],"published":{"date-parts":[[2025,6,8]]},"assertion":[{"value":"2025-08-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}