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 倍。

压缩索引下的瞬间相似度搜索

Similarity search in the blink of an eye with compressed indices

Approximate nearest neighbor search (ANNS) is a fundamental building block in
information retrieval with graph-based indices being the current
state-of-the-art and widely used in the industry. Recent advances in
graph-based indices have made it possible to index and search billion-point
datasets with high recall and millisecond-level latency on a single commodity
machine with an SSD.
However, existing graph algorithms for ANNS support only static indices that
cannot reflect real-time changes to the corpus required by many key real-world
scenarios (e.g. index of sentences in documents, email, or a news index). To
overcome this drawback, the current industry practice for manifesting updates
into such indices is to periodically re-build these indices, which can be
prohibitively expensive.
In this paper, we present the first graph-based ANNS index that reflects
corpus updates into the index in real-time without compromising on search
performance. Using update rules for this index, we design FreshDiskANN, a
system that can index over a billion points on a workstation with an SSD and
limited memory, and support thousands of concurrent real-time inserts, deletes
and searches per second each, while retaining $>95\%$ 5-recall@5. This
represents a 5-10x reduction in the cost of maintaining freshness in indices
when compared to existing methods.

本文提出了一种可以在实时反映文本更新的图形近似最近邻搜索方法，使用 update rules 实现了 FreshDiskANN 系统，能够在单个工作站上索引十亿个点，支持实时插入、删除和搜索，优化了索引保持新鲜的成本。