This paper focuses on an important query in
scientific simulation data analysis: the spatial distance histogram (sdh). The
computation time of an sdh query using brute force method is quadratic. Often,
such queries are executed continuously over certain time periods, increasing
the computation time. We propose highly efficient approximate algorithm to
compute sdh over consecutive time periods with provable error bounds. The key
idea of our algorithm is to derive statistical distribution of distances from
the spatial and temporal characteristics of particles. Upon organizing the data
into a quad-tree based structure, the spatio temporal characteristics of
particles in each node of the tree are acquired to determine the particles’
spatial distribution as well as their temporal locality in consecutive time
periods. we report our efforts in implementing and optimizing the above
algorithm in graphics processing units (gpus) as means to further improve the
efficiency. The accuracy and efficiency of the proposed algorithm is backed by
mathematical analysis and results of extensive experiments using data generated
from real simulation studies.
No comments:
Post a Comment