title: Anatomy of high-performance 2D similarity calculations.
abstract: Similarity measures based on the comparison of dense bit vectors of two-dimensional chemical features are a dominant method in chemical informatics. For large-scale problems, including compound selection and machine learning, computing the intersection between two dense bit vectors is the overwhelming bottleneck. We describe efficient implementations of this primitive as well as example applications using features of modern CPUs that allow 20-40× performance increases relative to typical code. Specifically, we describe fast methods for population count on modern x86 processors and cache-efficient matrix traversal and leader clustering algorithms that alleviate memory bandwidth bottlenecks in similarity matrix construction and clustering. The speed of our 2D comparison primitives is within a small factor of that obtained on GPUs and does not require specialized hardware.
authors.affiliation: Department of Computer Science, Stanford University, Stanford, California 94305, United States.
authors.forename: Imran S
authors.initials: IS
authors.lastname: Haque
authors.forename: Vijay S
authors.initials: VS
authors.lastname: Pande
authors.forename: W Patrick
authors.initials: WP
authors.lastname: Walters
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D054852:Small Molecule Libraries
chemical_list: D054852:Small Molecule Libraries