MISS-ACCUMULATION IN A BINARY SPACE PARTITIONING TREE

摘要

Embodiments of the invention provide a technique for improving the efficiency of a molecular modeling simulation. In one embodiment, the simulation may parse a kd-tree representing a receptor atom to identify atoms of the receptor within a specified distance of a target point. The target point may represent the center of a spherical envelope enclosing atoms of a ligand atom. A miss-accumulation vector may be used to accumulate a miss distance representing the minimum distance between a target point and a given node of the kd-tree. Thus, although the search algorithm may only evaluate the distance between the target point and a splitting dimension at each node of the kd-tree, the miss-accumulation vector may be used to account for distances over multiple dimensions.