{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:18:35Z","timestamp":1776889115449,"version":"3.51.2"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,8]],"date-time":"2020-12-08T00:00:00Z","timestamp":1607385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["DE-AC05-00OR22725"],"award-info":[{"award-number":["DE-AC05-00OR22725"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>Searching for geometric objects that are close in space is a fundamental component of many applications. The performance of search algorithms comes to the forefront as the size of a problem increases both in terms of total object count as well as in the total number of search queries performed. Scientific applications requiring modern leadership-class supercomputers also pose an additional requirement of performance portability, i.e.,\u00a0being able to efficiently utilize a variety of hardware architectures. In this article, we introduce a new open-source C++ search library, ArborX, which we have designed for modern supercomputing architectures. We examine scalable search algorithms with a focus on performance, including a highly efficient parallel bounding volume hierarchy implementation, and propose a flexible interface making it easy to integrate with existing applications. We demonstrate the performance portability of ArborX on multi-core CPUs and GPUs and compare it to the state-of-the-art libraries such as Boost.Geometry.Index and nanoflann.<\/jats:p>","DOI":"10.1145\/3412558","type":"journal-article","created":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T23:11:26Z","timestamp":1607555486000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["ArborX"],"prefix":"10.1145","volume":"47","author":[{"given":"D.","family":"Lebrun-Grandi\u00e9","sequence":"first","affiliation":[{"name":"Oak Ridge National Laboratory, Oak Ridge, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-5504","authenticated-orcid":false,"given":"A.","family":"Prokopenko","sequence":"additional","affiliation":[{"name":"Oak Ridge National Laboratory, Oak Ridge, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5954-6313","authenticated-orcid":false,"given":"B.","family":"Turcksin","sequence":"additional","affiliation":[{"name":"Oak Ridge National Laboratory, Oak Ridge, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. R.","family":"Slattery","sequence":"additional","affiliation":[{"name":"Oak Ridge National Laboratory, Oak Ridge, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Annual Conference on Computer Graphics and Visual Computing (CGVC\u201914)","author":"Apetrei C.","year":"2014","unstructured":"C. Apetrei . 2014 . Fast and simple agglomerative LBVH construction . In Proceedings of the Annual Conference on Computer Graphics and Visual Computing (CGVC\u201914) , Rita Borgo and Wen Tang (Eds.). The Eurographics Association. DOI:https:\/\/doi.org\/10.2312\/cgvc. 20141206 C. Apetrei. 2014. Fast and simple agglomerative LBVH construction. In Proceedings of the Annual Conference on Computer Graphics and Visual Computing (CGVC\u201914), Rita Borgo and Wen Tang (Eds.). The Eurographics Association. DOI:https:\/\/doi.org\/10.2312\/cgvc.20141206"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231578.3231581"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"key":"e_1_2_1_5_1","unstructured":"J. L. Blanco and P. K. Rai. 2014. nanoflann: A C++ header-only fork of FLANN a library for Nearest Neighbor (NN) with KD-trees. Retrieved from https:\/\/github.com\/jlblancoc\/nanoflann.  J. L. Blanco and P. K. Rai. 2014. nanoflann: A C++ header-only fork of FLANN a library for Nearest Neighbor (NN) with KD-trees. Retrieved from https:\/\/github.com\/jlblancoc\/nanoflann."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_2_1_7_1","unstructured":"DOE. 2016. Exascale Computing Project. Retrieved from https:\/\/www.exascaleproject.org.  DOE. 2016. Exascale Computing Project. Retrieved from https:\/\/www.exascaleproject.org."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 7th Conference on High-Performance Graphics (HPG\u201915)","author":"Domingues L. R.","unstructured":"L. R. Domingues and H. Pedrini . 2015. Bounding volume hierarchy optimization through agglomerative treelet restructuring . In Proceedings of the 7th Conference on High-Performance Graphics (HPG\u201915) . ACM, New York, NY, 13--20. DOI:https:\/\/doi.org\/10.1145\/2790060.2790065 L. R. Domingues and H. Pedrini. 2015. Bounding volume hierarchy optimization through agglomerative treelet restructuring. In Proceedings of the 7th Conference on High-Performance Graphics (HPG\u201915). ACM, New York, NY, 13--20. DOI:https:\/\/doi.org\/10.1145\/2790060.2790065"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.07.003"},{"key":"e_1_2_1_10_1","first-page":"2","article-title":"Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration","volume":"3","author":"Elseberg J.","year":"2012","unstructured":"J. Elseberg , S. Magnenat Rol , and S. A. N\u00fcchter . 2012 . Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration . J. Softw. Eng. Robot. 3 , 1 (2012), 2 -- 12 . J. Elseberg, S. Magnenat Rol, and S. A. N\u00fcchter. 2012. Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration. J. Softw. Eng. Robot. 3, 1 (2012), 2--12.","journal-title":"J. Softw. Eng. Robot."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.502"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics. 59--64","author":"Garanzha K.","unstructured":"K. Garanzha , J. Pantaleoni , and D. McAllister . 2011. Simpler and faster HLBVH with work queues . In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics. 59--64 . K. Garanzha, J. Pantaleoni, and D. McAllister. 2011. Simpler and faster HLBVH with work queues. In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics. 59--64."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (GIS\u201998)","author":"Garc\u00eda R.","unstructured":"R. Garc\u00eda , J. Yv\u00e1n , M. A. L\u00f3pez , and S. T. Leutenegger . 1998. A Greedy algorithm for bulk loading R-trees . In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (GIS\u201998) . ACM, New York, NY, 163--164. DOI:https:\/\/doi.org\/10.1145\/288692.288723 R. Garc\u00eda, J. Yv\u00e1n, M. A. L\u00f3pez, and S. T. Leutenegger. 1998. A Greedy algorithm for bulk loading R-trees. In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (GIS\u201998). ACM, New York, NY, 163--164. DOI:https:\/\/doi.org\/10.1145\/288692.288723"},{"key":"e_1_2_1_14_1","unstructured":"B. Gehrels B. Lalande M. Loskot A. Wulkiewicz M. Karavelas and M. Fisikopoulos. 2017. Boost geometry. Retrieved from https:\/\/www.boost.org\/doc\/libs\/1_67_0\/libs\/geometry\/doc\/html\/geometry\/spatial_indexes\/introduction.html.  B. Gehrels B. Lalande M. Loskot A. Wulkiewicz M. Karavelas and M. Fisikopoulos. 2017. Boost geometry. Retrieved from https:\/\/www.boost.org\/doc\/libs\/1_67_0\/libs\/geometry\/doc\/html\/geometry\/spatial_indexes\/introduction.html."},{"key":"e_1_2_1_15_1","unstructured":"Google. 2018. Google benchmark. Retrieved from https:\/\/github.com\/google\/benchmark.  Google. 2018. Google benchmark. Retrieved from https:\/\/github.com\/google\/benchmark."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.commatsci.2019.04.004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Y. Hu W. Wang D. Li Q. Zeng and Y. Hu. 2019. Parallel BVH construction using locally-density clustering. IEEE Access PP (07 2019) 1--1. DOI:https:\/\/doi.org\/10.1109\/ACCESS.2019.2932151  Y. Hu W. Wang D. Li Q. Zeng and Y. Hu. 2019. Parallel BVH construction using locally-density clustering. IEEE Access PP (07 2019) 1--1. DOI:https:\/\/doi.org\/10.1109\/ACCESS.2019.2932151","DOI":"10.1109\/ACCESS.2019.2932151"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383795.2383801"},{"key":"e_1_2_1_21_1","unstructured":"T. Karras. 2012b. Thinking parallel Part I: Collision detection on the GPU. Retrieved from https:\/\/devblogs.nvidia.com\/thinking-parallel-part-i-collision-detection-gpu.  T. Karras. 2012b. Thinking parallel Part I: Collision detection on the GPU. Retrieved from https:\/\/devblogs.nvidia.com\/thinking-parallel-part-i-collision-detection-gpu."},{"key":"e_1_2_1_22_1","volume-title":"Thinking parallel","author":"Karras T.","unstructured":"T. Karras . 2012c. Thinking parallel , Part II: Tree traversal on the GPU. Retrieved from https:\/\/devblogs.nvidia.com\/thinking-parallel-part-ii-tree-traversal-gpu. T. Karras. 2012c. Thinking parallel, Part II: Tree traversal on the GPU. Retrieved from https:\/\/devblogs.nvidia.com\/thinking-parallel-part-ii-tree-traversal-gpu."},{"key":"e_1_2_1_23_1","volume-title":"Computer Graphics Forum","volume":"28","author":"Lauterbach C.","unstructured":"C. Lauterbach , M. Garland , S. Sengupta , D. Luebke , and D. Manocha . 2009. Fast BVH construction on GPUs . In Computer Graphics Forum , Vol. 28 . Wiley Online Library, 375--384. C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha. 2009. Fast BVH construction on GPUs. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 375--384."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Computer Vision Theory and Application (VISSAPP\u201909)","author":"Muja M.","unstructured":"M. Muja and D. G. Lowe . 2009. Fast approximate nearest neighbors with automatic algorithm configuration . In Proceedings of the International Conference on Computer Vision Theory and Application (VISSAPP\u201909) . INSTICC Press, 331--340. M. Muja and D. G. Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In Proceedings of the International Conference on Computer Vision Theory and Application (VISSAPP\u201909). INSTICC Press, 331--340."},{"key":"e_1_2_1_26_1","unstructured":"OLCF. 2018. OLCF Summit. Retrieved from https:\/\/www.olcf.ornl.gov\/olcf-resources\/compute-systems\/summit\/.  OLCF. 2018. OLCF Summit. Retrieved from https:\/\/www.olcf.ornl.gov\/olcf-resources\/compute-systems\/summit\/."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Conference on High Performance Graphics. 87--95","author":"Pantaleoni J.","unstructured":"J. Pantaleoni and D. Luebke . 2010. HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry . In Proceedings of the Conference on High Performance Graphics. 87--95 . J. Pantaleoni and D. Luebke. 2010. HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In Proceedings of the Conference on High Performance Graphics. 87--95."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916)","author":"Patwary M. M. A.","year":"2016","unstructured":"M. M. A. Patwary , N. R. Satish , N. Sundaram , J. Liu , P. Sadowski , E. Racah , S. Byna , C. Tull , W. Bhimji , Prabhat, and P. Dubey . 2016. PANDA: Extreme scale parallel K-nearest neighbor on distributed architectures . In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916) . 494--503. DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2016 .57 M. M. A. Patwary, N. R. Satish, N. Sundaram, J. Liu, P. Sadowski, E. Racah, S. Byna, C. Tull, W. Bhimji, Prabhat, and P. Dubey. 2016. PANDA: Extreme scale parallel K-nearest neighbor on distributed architectures. In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916). 494--503. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2016.57"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV). IEEE, 91--98","author":"Sewell C.","unstructured":"C. Sewell , L. Lo , K. Heitmann , S. Habib , and J. Ahrens . 2015. Utilizing many-core accelerators for halo and center finding within a cosmology simulation . In Proceedings of the 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV). IEEE, 91--98 . C. Sewell, L. Lo, K. Heitmann, S. Habib, and J. Ahrens. 2015. Utilizing many-core accelerators for halo and center finding within a cosmology simulation. In Proceedings of the 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV). IEEE, 91--98."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.11.055"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Extended morton codes for high performance bounding volume hierarchy construction. In Proceedings of the High Performance Graphics (HPG\u201917). ACM, New York, NY","volume":"9","author":"Vinkler M.","year":"2017","unstructured":"M. Vinkler , J. Bittner , and V. Havran . 2017 . Extended morton codes for high performance bounding volume hierarchy construction. In Proceedings of the High Performance Graphics (HPG\u201917). ACM, New York, NY , Article 9 , 9: 1 \u2013 9 :8 pages. DOI:https:\/\/doi.org\/10.1145\/3105762.3105782 M. Vinkler, J. Bittner, and V. Havran. 2017. Extended morton codes for high performance bounding volume hierarchy construction. In Proceedings of the High Performance Graphics (HPG\u201917). ACM, New York, NY, Article 9, 9:1\u20139:8 pages. DOI:https:\/\/doi.org\/10.1145\/3105762.3105782","journal-title":"Article"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412558","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3412558","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3412558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:02Z","timestamp":1750195502000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412558"}},"subtitle":["A Performance Portable Geometric Search Library"],"short-title":[],"issued":{"date-parts":[[2020,12,8]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3412558"],"URL":"https:\/\/doi.org\/10.1145\/3412558","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,8]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}