ALGORITHMS AND DATA STRUCTURES FOR NEAREST NEIGHBOUR SEARCH IN MOLECULAR DYNAMICS: EXACT METHODS IN REAL SPACE

Abstract

Efficient nearest neighbour search is a decisive factor in the performance of computational molecular dynamics (MD), since the evaluation of local interactions within the potential cutoff radius accounts for the dominant share of the computational cost of a simulation, while the direct evaluation of all pairwise distances scales quadratically with the number of particles and becomes intractable for systems of realistic size. The aim of this article is to systematise and comparatively analyse the algorithms and data structures used for nearest neighbour search in MD and to assess the relationship between their computational efficiency and scalability. The study distinguishes two fundamentally different regimes of nearest neighbour search in contemporary MD. The first concerns the three-dimensional real space in which interatomic forces are computed; here the classical data structures are analysed in detail, namely cell (linked) lists, Verlet neighbour lists with a skin radius, and spatial trees such as KD-trees and octrees, which reduce the algorithmic complexity from quadratic to near-linear or O(N log N) order and are, in low dimensionality, close to optimal. The second regime has emerged with the proliferation of machine-learning interatomic potentials, in which each local atomic environment is encoded as a high-dimensional descriptor vector; in this regime nearest neighbour search underpins active-learning workflows, uncertainty quantification, farthest-point sampling of representative configurations, and the assessment of environment similarity, and exact tree-based structures lose efficiency owing to the curse of dimensionality, motivating approximate methods such as metric trees (Ball-Trees), locality-sensitive hashing based on p-stable distributions, and graph-based structures (HNSW). As the methodological contribution, a computational experiment on the canonical Lennard-Jones fluid is designed to quantitatively compare brute-force search, cell lists, Verlet lists, and a KD-tree as functions of system size, skin radius, and number density. The measured complexity exponents (2.01 for brute force and 0.96-1.05 for the scalable methods) closely reproduce the theoretical estimates, with a gap of nearly three orders of magnitude between brute force and cell lists at the largest system size (N about 10^6). The study concludes that, in the low-dimensional real-space regime, cell- and tree-based structures are close to optimal and provide a baseline against which the high-dimensional regime, the subject of a companion study on a real material, is to be assessed.