Jul, 2018

ANN-Benchmarks：一种用于近似最近邻算法基准测试的工具

PDF
TL;DR本文介绍了 ANN-Benchmarks，这是一种用于评估内存中近似最近邻算法的性能的工具，它提供了一个标准接口来测量不同标准数据集上最近邻算法的性能和质量，并支持多种不同方式的 k-NN 算法集成，其配置系统自动测试每个算法的一系列参数设置。ANN-Benchmarks 旨在提供 k-NN 算法的最新发展概述，并对评估结果进行了评估，并指出了未来工作的方向。
ann-benchmarksnearest neighbor algorithmsperformance evaluationquality measuresparameter tuning
发现论文，激发创造
  • 高维数据的近似最近邻搜索：实验、分析与改进（v1.0）

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

    Oct, 2016

  • 基于图的近似最近邻搜索的综合调查和实验比较

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

    Jan, 2021

  • 动态数据集上的近似最近邻搜索：一项调查

    近似 k 最近邻（ANN）方法常用于大规模高维数据集上的信息挖掘和机器学习，针对动态数据集和在线特征学习等应用，我们通过实证评估了 5 种流行的 ANN 方法，结果表明在动态数据集中，k-d 树方法不适用，并且在在线数据收集和在线特征学习方面，层次可导航小世界图方法和可扩展最近邻方法分别比基线方法更快速。

    Apr, 2024

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

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

    May, 2023

  • 使用松弛度的随机嵌入和高维近似最近邻

    本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义，并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中；通过 BBD 树等数据结构，可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时，此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{ ho})$ 的查询时间，并可直接解决 approximate nearest neighbor problem 问题，具有比基于 BBD 树的方法更好的查询时间指数。

    Dec, 2014

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

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

    Feb, 2022

  • UCI 机器学习库中 11 个不同数据集上 KNN、SVM、LMNN 和 ENN 算法准确率变化的研究和观察

    本研究实现四种主流的机器学习算法在十一个数据集上，分析它们的准确性，并且探讨机器学习算法与数据维度之间的关系。

    Sep, 2018

  • CANDY：基于动态数据插入的连续近似最近邻搜索的基准

    CANDY 是一个定制的连续近似最近邻搜索基准，能够全面评估广泛的 AKNN 算法，并通过集成机器学习驱动的推断和改进的距离计算方法来提高检索效果和减少计算开销。实验证明，相对简单的 AKNN 基线通常在召回率和延迟方面超越更复杂的替代方案，这一发现对高性能所需的算法复杂性的现有信念提出了质疑，并强调了现有挑战和未来研究机会。

    Jun, 2024

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

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

    Sep, 2016

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

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

    May, 2021