Aug, 2023

CAGRA: 高并行图构建和 GPU 上的近似最近邻搜索

PDF
TL;DR通过使用现代硬件的高性能能力，我们的方法在构建接近图时，构建时间比 HNSW 快 2.2~27 倍；在大批量查询吞吐量方面，在 90% 至 95% 召回范围内，我们的方法比 HNSW 快 33~77 倍，并且比 GPU 的最新实现快 3.8~8.8 倍；对于单个查询，在 95% 召回率时我们的方法比 HNSW 快 3.4~53 倍。
approximate nearest neighbor searchgraph-based approachesparallel computingproximity graphefficiency gains
发现论文，激发创造
  • 基于图的近似最近邻搜索的综合调查和实验比较

    本文综述了 13 个代表性的基于图的近似最近邻搜索算法，通过新的分类和细粒度的流程进行了比较分析和实验评估。该研究提供了优化算法的原则并设计了一种优化方法，可以优于现有的基于图的近似最近邻算法。同时还提供了关于有前途的研究方向和适合不同领域从业者使用的算法的经验建议。

    Jan, 2021

  • 基于图的概率路由的近似最近邻搜索

    通过引入具有概率保证的方法，该研究旨在增强基于图的最近邻搜索中的路由，提出了 PEOs，一种有效地确定图中应考虑的邻居进行准确距离计算的新方法，实验证明其在常用图索引（HNSW）上可以提高吞吐量 1.6 到 2.5 倍，并且其效率始终比最先进的路由技术提高 1.1 到 1.4 倍。

    Feb, 2024

  • 流行近似最近邻搜索实现的最坏情况性能：保证和限制

    图形化相似最近邻搜索算法的最坏情况性能研究，以 HNSW、NSG 和 DiskANN 为例，发现其实际查询时间与实例大小成线性关系，并证明其具有常数近似比和多对数查询时间的边界维数据集。

    Oct, 2023

  • 将基于图的 ANNS 算法扩展到十亿级数据集：一份比较分析

    本文提出了一组基于可扩展性的原则度量 ANNS 算法的评估标准，包括并行性能、建树时间、性能随数据集增加的扩展性以及机器无关的度量方法等，并优化了四种基于图的算法，提供了一种通用的无锁的递增 ANNS 图算法框架来应对现代应用所需的更高难度的准确性评价

    May, 2023

  • 高维数据的近似最近邻搜索：实验、分析与改进（v1.0）

    本文详细评估了 16 种不同算法在 20 个不同数据集、多个评估指标和不同查询工作负载下的性能表现，并提出了一种新的方法以提高查询效率和召回率。

    Oct, 2016

  • 在 GPU 上高效地进行大规模近似最近邻搜索

    本研究提出基于 Product Quantization 的两层向量量化树的 ANN 搜索新方法，在 GPU 实现方面取得了比 CPU 更高的性能表现，适用于视频中循环关闭等对时间敏感的高维问题。

    Feb, 2017

  • EFANNA：一种基于 kNN 图的极速近邻搜索算法

    本文提出了一种基于 KNN 图的近似最近邻搜索算法 EFANNA，通过提供 NN 扩展的良好初始化方式，很好地解决了收敛到局部最优解和 K 近邻图构建耗时问题。实验证明，EFANNA 算法在近似最近邻搜索和 K 近邻图的构建两个方面均优于现有的算法，是目前最快的算法，同时已在 Github 上发布了 EFANNA 库。

    Sep, 2016

  • PECANN：基于图的近似最近邻搜索的并行高效聚类

    该研究论文通过抽象密度峰聚类算法中的关键步骤，如使用基于图的近似最近邻搜索（ANNS）方法来寻找满足预测函数的最近邻，提出了一种统一的框架 PECANN。通过在合成和真实数据集上评估，该方法在大规模高维度数据集上实现了高速的聚类效果，并在性能和准确性上超越了现有的算法。

    Dec, 2023

  • FreshDiskANN：一种用于流式相似度搜索的快速准确基于图的 ANN 索引

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

    May, 2021

  • 基于神经相似性度量的大规模推荐系统近似最近邻搜索

    本研究中，我们提出了一种新的方法来扩展近似最近邻搜索到任意匹配函数（例如深度神经网络），并使用可插拔的对抗性训练任务来保证搜索结果的准确性；通过在开源和工业数据集上的实验证明了我们方法的有效性，并在淘宝展示广告平台上进行了全面部署，带来了相当可观的广告收入增长。

    Feb, 2022