Using the k-d Tree Data Structure to Accelerate Monte Carlo Simulations

Qile P. Chen, Bai Xue, J. Ilja Siepmann

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


The k-d tree data structure is implemented in a Monte Carlo (MC) molecular simulation program to accelerate the range search for particles or interaction sites within the cutoff distance when Lennard-Jones and Coulomb interactions are computed. MC simulations are performed for different molecules in various ensembles to assess the efficiency enhancements due to the k-d tree data structure. It is found that the use of k-d trees accelerates significantly simulations for Lennard-Jones particles in the NVT and NVT-Gibbs ensembles and for n-butane and 2,4,6,8,10,12,14,16,18,20,22-undecamethylpentacosane represented by the TraPPE-UA force field in the NpT ensemble. Simulations for TraPPE-UA ethanol in the NpT ensemble and for the rigid TIP4P water model in the Gibbs ensemble gain slightly in efficiency with the k-d tree, whereas simulations for TIP4P water in the NpT ensemble do not benefit from the use of the k-d tree. The speed-up can be attributed to the reduction in the number of distance calculations in the range search from scaling as O(N) to O(log2N). In addition, these tests suggest that the efficiency gain from the use of the k-d tree data structure depends on the flexibility of the molecular model (requiring configurational-bias MC moves to sample changes in conformation), on the ensemble (with open ensembles requiring special MC moves to aid particle transfers), and on the number of interaction sites per molecule (with compact multisite models not seeing an efficiency gain). Overall, the use of the k-d tree data structure can substantially enhance MC simulation efficiency for a variety of systems, and it will enable simulations for larger system sizes in the future.

Original languageEnglish (US)
Pages (from-to)1556-1565
Number of pages10
JournalJournal of Chemical Theory and Computation
Issue number4
StatePublished - Apr 11 2017

Bibliographical note

Funding Information:
This work was supported by the National Science Foundation through the University of Minnesota MRSEC under Award No. DMR-1420013. Computer resources were provided through this NSF award and also by the Minnesota Supercomputing Institute at the University of Minnesota.

Publisher Copyright:
© 2017 American Chemical Society.

Copyright 2017 Elsevier B.V., All rights reserved.

How much support was provided by MRSEC?

  • Primary

PubMed: MeSH publication types

  • Journal Article


Dive into the research topics of 'Using the k-d Tree Data Structure to Accelerate Monte Carlo Simulations'. Together they form a unique fingerprint.

Cite this