基于图的近似最近邻搜索的自适应入口点选择的理论和实证分析
内容提要
该文综述基于图的近似最近邻搜索算法，提出新分类并进行实验评估，给出优化原则与方法，性能优于现有算法。研究还涵盖可扩展性评估标准、无锁递增框架、多算法多数据集评测、任意匹配函数扩展、最坏情况性能分析、AdANNS自适应表示框架、高性能构建与查询加速、ANN-Benchmarks工具、FreshDiskANN实时更新系统，以及强化学习与进化算法优化图神经网络比较。
延伸解读
算法优化与性能提升
文章综述了13个基于图的近似最近邻搜索算法，通过新的分类和细粒度流程进行比较分析，并提出了优化原则和方法，性能优于现有算法。此外，还介绍了高性能构建与查询加速技术，构建时间比HNSW快2.2~27倍，大批量查询吞吐量在90%至95%召回范围内比HNSW快33~77倍，比GPU实现快3.8~8.8倍，单查询在95%召回率时比HNSW快3.4~53倍。
可扩展性与评估标准
文章提出了一组基于可扩展性的原则度量ANNS算法的评估标准，包括并行性能、建树时间、性能随数据集增加的扩展性以及机器无关的度量方法等，并优化了四种基于图的算法，提供了一种通用的无锁递增ANNS图算法框架。此外，还详细评估了16种不同算法在20个不同数据集、多个评估指标和不同查询工作负载下的性能表现，并提出新方法提高查询效率和召回率。
自适应表示与实时更新
文章介绍了基于Matryoshka Representations的ANNS设计框架AdANNS，通过自适应表示实现更好的准确性和计算效率平衡。例如，在图像检索上，AdANNS-IVF比基于刚性表示的IVF准确率提高1.5%，速度快90倍；在自然问题上，32字节的AdANNS-OPQ与64字节OPQ准确率相同，成本减半。同时，FreshDiskANN系统支持实时插入、删除和搜索，能在单个工作站上索引十亿个点。
扩展应用与未来方向
文章探讨了将近似最近邻搜索扩展到任意匹配函数（如深度神经网络），并使用可插拔的对抗性训练任务保证准确性，在淘宝展示广告平台部署后带来广告收入增长。此外，比较了基于强化学习和进化算法的神经架构搜索优化图神经网络，发现两种方法的准确性与随机搜索相似，引出了搜索空间维度相关性的问题。
Q&A
基于图的近似最近邻搜索算法有哪些代表性的优化方法？
文章综述了13个代表性算法，并提出了优化原则和一种优化方法，可以优于现有的基于图的近似最近邻算法。此外，还介绍了可扩展性评估标准、无锁递增框架、高性能构建与查询加速等方法。
如何评估近似最近邻搜索算法的可扩展性？
文章提出了一组基于可扩展性的原则度量标准，包括并行性能、建树时间、性能随数据集增加的扩展性以及机器无关的度量方法等。
AdANNS框架是如何提高近似最近邻搜索的准确性和效率的？
AdANNS基于Matryoshka Representations，使用不同容量的自适应表示来平衡准确性和计算效率。例如，在图像检索上，AdANNS-IVF比基于刚性表示的IVF在相同计算预算下准确性提高1.5%，速度快90倍；在自然问题上，32字节的AdANNS-OPQ与64字节的OPQ准确性相同，成本减半。
FreshDiskANN系统如何实现实时更新？
FreshDiskANN使用update rules实现了实时反映文本更新的图形近似最近邻搜索，能够在单个工作站上索引十亿个点，支持实时插入、删除和搜索，并优化了索引保持新鲜的成本。
基于图的近似最近邻搜索算法的最坏情况性能如何？
以HNSW、NSG和DiskANN为例，研究发现其实际查询时间与实例大小成线性关系，并证明其具有常数近似比和多对数查询时间的边界维数据集。
ANN-Benchmarks工具的作用是什么？
ANN-Benchmarks是一个用于评估内存中近似最近邻算法性能的工具，提供标准接口来测量不同标准数据集上最近邻算法的性能和质量，支持多种k-NN算法集成，并自动测试参数设置，旨在提供k-NN算法的最新发展概述。
