Exploring Spatial Indexing for Accelerated Feature Retrieval in HPC

Margaret Lawson, William Gropp, Jay Lofstead

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022
EditorsMaria Fazio, Dhabaleswar K. Panda, Radu Prodan, Valeria Cardellini, Burak Kantarci, Omer Rana, Massimo Villari
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages605-614
Number of pages10
ISBN (Electronic)9781665499569
DOIs
StatePublished - 2022
Event22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022 - Taormina, Italy
Duration: May 16 2022May 19 2022

Publication series

NameProceedings - 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022

Conference

Conference22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022
Country/TerritoryItaly
CityTaormina
Period5/16/225/19/22

Keywords

  • geometric range searching
  • k-d tree
  • octree
  • R-tree
  • spatial indexing

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software
  • Information Systems and Management
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Exploring Spatial Indexing for Accelerated Feature Retrieval in HPC'. Together they form a unique fingerprint.

Cite this