Mar, 2016

使用分层导航小世界图进行高效稳健的近似最近邻搜索

PDF
TL;DR我们提出了一种新的 K 最近邻搜索方法，它基于可控层次结构的可导航小世界图（Hierarchical NSW，HNSW）。所提出的解决方案是完全基于图的，无需任何额外的搜索结构，在多层结构中进行搜索可以提高性能，同时利用启发式算法选择近邻可以在高召回率和高密集度的情况下显著提高性能。
k-nearest neighbor searchnavigable small world graphsproximity graphhierarchical structureperformance
发现论文，激发创造
  • 流行近似最近邻搜索实现的最坏情况性能：保证和限制

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

    Oct, 2023

  • 基于邻近图的最大内积搜索的理解与改进

    分析了最大内积搜索中的范数偏差，证明了 ip-NSW 算法的性能优秀是因为其匹配了最大内积搜索的范数偏差，同时提出了 ip-NSW + 算法，通过引入角度相似性图表现出更好的性能表现。

    Sep, 2019

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

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

    Jan, 2021

  • 基于神经构造启发式算法的大邻域搜索

    本文提出了一种基于神经网络学习的建造启发式方法的大邻域搜索 (LNS) 方法，用于解决具有时间窗口的车辆路径问题 (VRPTW)。方法采用图形神经网络来编码问题，并通过强化学习在不需要监督标签的情况下训练构造任务。神经修复运算符与局部搜索例程、启发式销毁运算符和选择过程相结合，应用于小型人口来到达一个复杂的解决方案。关键思想是使用学习模型重新构造部分破坏的解决方案，并通过破坏启发式 (或随机策略本身) 引入随机性，以有效地探索大邻域。

    May, 2022

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

    通过使用现代硬件的高性能能力，我们的方法在构建接近图时，构建时间比 HNSW 快 2.2~27 倍；在大批量查询吞吐量方面，在 90% 至 95% 召回范围内，我们的方法比 HNSW 快 33~77 倍，并且比 GPU 的最新实现快 3.8~8.8 倍；对于单个查询，在 95% 召回率时我们的方法比 HNSW 快 3.4~53 倍。

    Aug, 2023

  • 高维最近邻搜索的可导航图：构建与限制

    在高维点集中，基于图的最近邻搜索方法中的可导航图构建问题引起了广泛关注，本论文首次给出了平均度为 O（√（nlogn））的可导航图的简单有效构建方式，并证明了在 O（logn）维的欧氏度量下，任意随机点集不可能存在平均度为 O（n^α）的可导航图，其中 α < 1/2。

    May, 2024

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

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

    Feb, 2024

  • 最近邻搜索的学习空间划分

    本研究提出一种新的框架用于构建空间划分，将问题转化为平衡图划分和监督分类，并结合 KaHIP 图分区器和神经网络，实现了一种新的分区过程称为神经局部敏感哈希（Neural LSH），实验证明 Neural LSH 的分区在标准最近邻搜索（NNS）基准测试中，始终优于基于量化和树的方法，以及经典的数据无关 LSH。

    Jan, 2019

  • 利用相邻图导航语义地图

    本研究探讨了分布语义模型中的最近邻搜索，并提出了使用拓扑结构来达到词义感知和确定语义范围的方法，使用相对邻域图来确认语义模型中邻域的拓扑属性，探讨了 PMI 模型、GloVe 模型和 skipgram 模型的相对邻域图。

    Jan, 2015

  • 相似性图中的路由学习

    本文探讨相似性图在最近邻搜索中的应用，提出了一种学习路由函数以克服局部极小值并显著提高整体搜索性能的方法。

    May, 2019