title: Computing Spatial Distance Histograms for Large Scientific Datasets On-the-Fly.
abstract: 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 spatiotemporal 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.
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620, U.S.A.
authors.forename: Anand
authors.initials: A
authors.lastname: Kumar
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620, U.S.A.
authors.forename: Vladimir
authors.initials: V
authors.lastname: Grupcev
authors.affiliation: School of Economics and Management, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, China.
authors.forename: Yongke
authors.initials: Y
authors.lastname: Yuan
authors.affiliation: Department of Computer Science, University of Texas at Arlington, 500 UTA Boulevard, Room 640, ERB Buildings, Arlington, TX 76019, U.S.A.
authors.forename: Jin
authors.initials: J
authors.lastname: Huang
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620, U.S.A.
authors.forename: Yi-Cheng
authors.initials: YC
authors.lastname: Tu
authors.affiliation: Department of Statistics, North Dakota State University, 201H Waldron Hall, Fargo, ND 58108, U.S.A.
authors.forename: Gang
authors.initials: G
authors.lastname: Shen
keywords: GPU; Scientific databases; density map; quad-tree; spatial distance histogram; spatiotemporal locality