Nearest neighbor-based similarity searching is a common task in chemistry,
with notable use cases in drug discovery. Yet, some of the most commonly used
approaches for this task still leverage a brute-force approach. In practice
this can be computationally costly and overly time-consuming, due in part to
the sheer size of modern chemical databases. Previous computational
advancements for this task have generally relied on improvements to hardware or
dataset-specific tricks that lack generalizability. Approaches that leverage
lower-complexity searching algorithms remain relatively underexplored. However,
many of these algorithms are approximate solutions and/or struggle with typical
high-dimensional chemical embeddings. Here we evaluate whether a combination of
low-dimensional chemical embeddings and a k-d tree data structure can achieve
fast nearest neighbor queries while maintaining performance on standard
chemical similarity search benchmarks. We examine different dimensionality
reductions of standard chemical embeddings as well as a learned,
structurally-aware embedding -- SmallSA -- for this task. With this framework,
searches on over one billion chemicals execute in less than a second on a
single CPU core, five orders of magnitude faster than the brute-force approach.
We also demonstrate that SmallSA achieves competitive performance on chemical
similarity benchmarks.

在化学中，最邻近基于相似性搜索是一项常见任务，但其中一些常用方法仍然采用蛮力算法。本研究评估了低维化学嵌入和 k-d 树数据结构相结合的方法，能在标准化学相似性搜索基准下实现快速最近邻查询，并证明了这种方法在超过十亿种化学物质的搜索中，仅用一个 CPU 核心能在一秒钟内执行，比蛮力算法快五个数量级，并且在化学相似性基准中表现出竞争性能。