TY - GEN
T1 - Exploring Spatial Indexing for Accelerated Feature Retrieval in HPC
AU - Lawson, Margaret
AU - Gropp, William
AU - Lofstead, Jay
N1 - This work was supported by the U.S. Department of Energy Office of Science, under the SSIO grant series and the Data Management grant series, Decaf project, program manager Lucy Nowell.
Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.
Margaret Lawson acknowledges support from the United States Department of Energy through the Computational Sciences Graduate Fellowship (DOE CSGF) under grant number: DE-SC0020347. This work was supported in part by the State of Illinois.
PY - 2022
Y1 - 2022
N2 - Despite the critical role that range queries play in analysis and visualization for HPC applications, there has been no comprehensive analysis of indices that are designed to accelerate range queries and the extent to which they are viable in HPC. In this paper we present the first such evaluation, examining 20 open-source C and C++ libraries that support range queries. Contributions of this paper include answering the following questions: which of the implementations are viable in HPC, how do these libraries compare in terms of build time, query time, memory usage, and scalability, what are other trade-offs between these implementations, is there a single overall best solution, and when does a brute force solution offer the best performance? We also share key insights learned during this process that can assist both HPC application scientists and spatial index developers. While we find that there is no single best solution, three libraries, Boost, CGAL and R-tree, offer some of the best performance, scalability, memory overheads, and support for different mesh types. We find several areas where the spatial indices could be substantially improved: better performance when there are a large number of query matches, reduced memory overheads, and better support for GPUs or other accelerators.
AB - Despite the critical role that range queries play in analysis and visualization for HPC applications, there has been no comprehensive analysis of indices that are designed to accelerate range queries and the extent to which they are viable in HPC. In this paper we present the first such evaluation, examining 20 open-source C and C++ libraries that support range queries. Contributions of this paper include answering the following questions: which of the implementations are viable in HPC, how do these libraries compare in terms of build time, query time, memory usage, and scalability, what are other trade-offs between these implementations, is there a single overall best solution, and when does a brute force solution offer the best performance? We also share key insights learned during this process that can assist both HPC application scientists and spatial index developers. While we find that there is no single best solution, three libraries, Boost, CGAL and R-tree, offer some of the best performance, scalability, memory overheads, and support for different mesh types. We find several areas where the spatial indices could be substantially improved: better performance when there are a large number of query matches, reduced memory overheads, and better support for GPUs or other accelerators.
KW - R-tree
KW - geometric range searching
KW - k-d tree
KW - octree
KW - spatial indexing
UR - http://www.scopus.com/inward/record.url?scp=85135740322&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135740322&partnerID=8YFLogxK
U2 - 10.1109/CCGrid54584.2022.00070
DO - 10.1109/CCGrid54584.2022.00070
M3 - Conference contribution
AN - SCOPUS:85135740322
T3 - Proceedings - 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022
SP - 605
EP - 614
BT - Proceedings - 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022
A2 - Fazio, Maria
A2 - Panda, Dhabaleswar K.
A2 - Prodan, Radu
A2 - Cardellini, Valeria
A2 - Kantarci, Burak
A2 - Rana, Omer
A2 - Villari, Massimo
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022
Y2 - 16 May 2022 through 19 May 2022
ER -