Computing Spatial Distance Histograms for Large Scientific Datasets On-the-Fly.

Area of Science:

• Scientific simulation data analysis
• Computational geometry
• High-performance computing

Background:

• Spatial Distance Histogram (SDH) queries are crucial for scientific simulation data analysis.
• Brute-force computation of SDH is quadratic, becoming inefficient for continuous queries over time.
• Existing methods struggle with the computational demands of large-scale, time-dependent datasets.

Purpose of the Study:

• To develop a highly efficient approximate algorithm for computing Spatial Distance Histograms (SDH) over consecutive time periods.
• To provide provable error bounds for the approximate SDH computation.
• To optimize the algorithm for performance using Graphics Processing Units (GPUs).

Main Methods:

• Deriving statistical distributions of particle distances from spatiotemporal characteristics.
• Utilizing a Quad-tree data structure to organize particle data.
• Implementing and optimizing the algorithm on Graphics Processing Units (GPUs).

Main Results:

• The proposed algorithm significantly reduces computation time for SDH queries compared to brute-force methods.
• Mathematical analysis and extensive experiments validate the accuracy and efficiency of the algorithm.
• GPU implementation further enhances the performance for large-scale datasets.

Conclusions:

• The developed approximate algorithm offers an efficient solution for continuous SDH queries in scientific simulations.
• The spatiotemporal data organization and GPU optimization provide a scalable approach for complex analyses.
• The method achieves a balance between computational efficiency and accuracy, supported by rigorous validation.