提出评估图结构近邻索引数据删除的完整方法
How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?
- 分类三类图式近邻索引删除方法并数学建模
- 实测显示不同删除策略对查询精度与速度影响显著
- 适合需要动态更新的检索系统开发者参考
近似最近邻搜索（ANNS）因在检索增强生成等场景中的应用而受到广泛关注。这些应用要求索引支持动态数据，因此动态数据下的ANNS问题备受关注。然而，目前尚无针对数据删除的系统性评估方法。本文提出一个实验框架和全面的评估指标体系，用于衡量图结构ANNS索引在实际使用场景下数据删除的效率。具体地，我们将图式ANNS中的数据删除方法分为三类并进行数学形式化。性能评估涵盖准确性、查询速度等关键指标。最后，将该评估框架应用于当前领先的HNSW算法，分析数据删除的影响，并提出删除控制机制（Deletion Control），可根据预设搜索精度动态选择最优删除策略。
原文摘要 · Abstract (English)
Approximate Nearest Neighbor Search (ANNS) has recently gained significant attention due to its many applications, such as Retrieval-Augmented Generation. Such applications require ANNS algorithms that support dynamic data, so the ANNS problem on dynamic data has attracted considerable interest. However, a comprehensive evaluation methodology for data deletion in ANNS has yet to be established. This study proposes an experimental framework and comprehensive evaluation metrics to assess the efficiency of data deletion for ANNS indexes under practical use cases. Specifically, we categorize data deletion methods in graph-based ANNS into three approaches and formalize them mathematically. The performance is assessed in terms of accuracy, query speed, and other relevant metrics. Finally, we apply the proposed evaluation framework to Hierarchical Navigable Small World, one of the state-of-the-art ANNS methods, to analyze the effects of data deletion, and propose Deletion Control, a method which dynamically selects the appropriate deletion method under a required search accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。