Exact nearest neighbor search is a computationally intensive process, and
even its simpler sibling -- vector retrieval -- can be computationally complex.
This is exacerbated when retrieving vectors which have high-dimension $d$
relative to the number of vectors, $N$, in the database. Exact nearest neighbor
retrieval has been generally acknowledged to be a $O(Nd)$ problem with no
sub-linear solutions. Attention has instead shifted towards Approximate
Nearest-Neighbor (ANN) retrieval techniques, many of which have sub-linear or
even logarithmic time complexities. However, if our intuition from binary
search problems (e.g. $d=1$ vector retrieval) carries, there ought to be a way
to retrieve an organized representation of vectors without brute-forcing our
way to a solution. For low dimension (e.g. $d=2$ or $d=3$ cases),
\texttt{kd-trees} provide a $O(d\log N)$ algorithm for retrieval. Unfortunately
the algorithm deteriorates rapidly to a $O(dN)$ solution at high dimensions
(e.g. $k=128$), in practice. We propose a novel algorithm for logarithmic Fast
Exact Retrieval for Nearest-neighbor lookup (FERN), inspired by
\texttt{kd-trees}. The algorithm achieves $O(d\log N)$ look-up with 100\%
recall on 10 million $d=128$ uniformly randomly generated
vectors.\footnote{Code available at this https URL}

我们提出了一种受 kd 树启发的新算法，名为快速精确最近邻查找 (FERN)，该算法实现了 O (dlogN) 的查找并在一千万个由 128 维度均匀随机生成的向量上实现了 100% 的召回率。

最近邻查找的快速精确检索（FERN）

Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)

Nowadays, data is represented by vectors. Retrieving those vectors, among
millions and billions, that are similar to a given query is a ubiquitous
problem of relevance for a wide range of applications. In this work, we present
new techniques for creating faster and smaller indices to run these searches.
To this end, we introduce a novel vector compression method, Locally-adaptive
Vector Quantization (LVQ), that simultaneously reduces memory footprint and
improves search performance, with minimal impact on search accuracy. LVQ is
designed to work optimally in conjunction with graph-based indices, reducing
their effective bandwidth while enabling random-access-friendly fast similarity
computations. Our experimental results show that LVQ, combined with key
optimizations for graph-based indices in modern datacenter systems, establishes
the new state of the art in terms of performance and memory footprint. For
billions of vectors, LVQ outcompetes the second-best alternatives: (1) in the
low-memory regime, by up to 20.7x in throughput with up to a 3x memory
footprint reduction, and (2) in the high-throughput regime by 5.8x with 1.4x
less memory.

本文介绍了一种新的矢量压缩方法 LVQ，与基于图的索引优化技术相结合能够提高性能，降低内存占用率，在亿级矢量检索中优于目前的最佳解决方案，其中低内存区间性能提高 20.7 倍，内存占用下降 3 倍。