提出基于随机游走的图结构近邻搜索动态更新方法，支持高效删除。
Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
- 用随机游走理论构建动态图近邻搜索框架
- 删除节点后仍保持查询命中时间稳定，召回率更高
- 适合需频繁增删数据的实时检索系统
近似最近邻搜索（ANN）是大语言模型和检索增强生成中常用的技术。目前最广泛使用的算法是基于多层图结构的层次可导航小世界（HNSW），但该算法仅支持插入新数据，不支持删除。以往的删除方法要么增加查询延迟，降低召回率，要么耗时过长。本文提出一种基于随机游走的图结构ANN新理论框架，分析了一种随机删除策略，可保持删除前后图的命中时间统计特性。在此基础上，我们设计出一种确定性删除算法，在大规模实验中展现出更优的查询延迟、召回率、删除时间和内存使用之间的权衡。
原文摘要 · Abstract (English)
Approximate nearest neighbor search (ANN) is a common way to retrieve relevant search results, especially now in the context of large language models and retrieval augmented generation. One of the most widely used algorithms for ANN is based on constructing a multi-layer graph over the dataset, called the Hierarchical Navigable Small World (HNSW). While this algorithm supports insertion of new data, it does not support deletion of existing data. Moreover, deletion algorithms described by prior work come at the cost of increased query latency, decreased recall, or prolonged deletion time. In this paper, we propose a new theoretical framework for graph-based ANN based on random walks. We then utilize this framework to analyze a randomized deletion approach that preserves hitting time statistics compared to the graph before deleting the point. We then turn this theoretical framework into a deterministic deletion algorithm, and show that it provides better tradeoff between query latency, recall, deletion time, and memory usage through an extensive collection of experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。