Back to Search
Start Over
Collision-free spatial hash functions for structural analysis of billion-vertex chemical bond networks
- Source :
-
Computer Physics Communications . Sep2006, Vol. 175 Issue 5, p339-347. 9p. - Publication Year :
- 2006
-
Abstract
- 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00104655
- Volume :
- 175
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Computer Physics Communications
- Publication Type :
- Periodical
- Accession number :
- 21920788
- Full Text :
- https://doi.org/10.1016/j.cpc.2006.06.001