|
|||||
|
|
Collision-free spatial hash functions for structural analysis of billion-vertex chemical bond networks |
|
| Authors: | Cheng Zhang Paulo S Branicio Rajiv K Kalia Ashish Sharma Priya Vashishta |
| Affiliation: | a Collaboratory for Advanced Computing and Simulations, Department of Computer Science, Department of Physics & Astronomy, Department of Chemical Engineering & Materials Science, University of Southern California, Los Angeles, CA 90089-0242, USA b Department of Biomedical Informatics, Ohio State University, Columbus, OH 43210, USA c Departmento de Física, Universidade Federal de São Carlos, São Carlos, SP 13565, Brazil |
| Abstract: | State-of-the-art molecular dynamics (MD) simulations generate massive datasets involving billion-vertex chemical bond networks, which makes data mining based on graph algorithms such as K-ring analysis a challenge. This paper proposes an algorithm to improve the efficiency of ring analysis of large graphs, exploiting properties of K-rings and spatial correlations of vertices in the graph. The algorithm uses dual-tree expansion (DTE) and spatial hash-function tagging (SHAFT) to optimize computation and memory access. Numerical tests show nearly perfect linear scaling of the algorithm. Also a parallel implementation of the DTE + SHAFT algorithm achieves high scalability. The algorithm has been successfully employed to analyze large MD simulations involving up to 500 million atoms. |
| Keywords: | 07 05 Kf 07 05 Tp 61 43 Bn 61 72 Ff 82 20 Wt 89 20 Ff |
| 本文献已被 ScienceDirect 等数据库收录！ | |