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 系统，能够在单个工作站上索引十亿个点，支持实时插入、删除和搜索，优化了索引保持新鲜的成本。