title: Distance Histogram Computation Based on Spatiotemporal Uniformity in Scientific Data.
abstract: Large data generated by scientific applications imposes challenges in storage and efficient query processing. Many queries against scientific data are analytical in nature and require super-linear computation time using straightforward methods. Spatial distance histogram (SDH) is one of the basic queries to analyze the molecular simulation (MS) data, and it takes quadratic time to compute using brute-force approach. Often, an SDH query is executed continuously to analyze the simulation system over a period of time. This adds to the total time required to compute SDH. In this paper, we propose an approximate algorithm to compute SDH efficiently over consecutive time periods. In our approach, data is organized into a Quad-tree based data structure. The spatial locality of the particles (at given time) in each node of the tree is acquired to determine the particle distribution. Similarly, the temporal locality of particles (between consecutive time periods) in each node is also acquired. The spatial distribution and temporal locality are utilized to compute the approximate SDH at every time instant. The performance is boosted by storing and updating the spatial distribution information over time. The efficiency and accuracy of the proposed algorithm is supported by mathematical analysis and results of extensive experiments using biological data generated from real MS studies.
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620, USA.
authors.forename: Anand
authors.initials: A
authors.lastname: Kumar
authors.affiliation: School of Economics and Management, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, China.
authors.forename: Vladimir
authors.initials: V
authors.lastname: Grupcev
authors.affiliation: Department of Statistics, North Dakota State University, 201H Waldron Hall, NDSU Dept. 2770, P. O. Box 6050, Fargo, ND 58108, USA.
authors.forename: Yongke
authors.initials: Y
authors.lastname: Yuan
authors.forename: Yi-Cheng
authors.initials: YC
authors.lastname: Tu
authors.forename: Gang
authors.initials: G
authors.lastname: Shen
keywords: Algorithms; Experimentation; Performance; Scientific data; density map; quad-tree; spatial distance histogram; spatiotemporal locality