Apr, 2024

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

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

    提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题，并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法（LSH）

    Dec, 2015

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

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

    Sep, 2016

  • k*-最近邻居: 从全局到局部

    本文提出了一种简单的，能够使权重最优化的局部加权回归/分类方法，并能够为需要估计值的每个数据点高效地找到权重和最优化的邻居数量，从而在多个数据集上展示了比标准局部加权方法更优异的性能表现。

    Jan, 2017

  • 近似最近邻搜索中超参数的高效自动调整

    本研究提出了一种使用随机空间划分树自动调整索引方法超参数的算法，相较于现有方法，该算法在查询时间上表现优异，且建立速度更快。

    Dec, 2018

  • k-最近邻分类器：第2版（附带Python示例）

    本文介绍了最近邻分类器的技术和方法，主要关注评估相似度、处理计算问题、降低数据维度等方面，新增时间序列相似性、检索加速和固有维度的相关内容，并提供了相关Python代码。

    Apr, 2020

  • SPANN：高效的十亿级近似最近邻搜索

    本文提出了一种名为SPANN的内存磁盘混合索引和搜索系统，它采用倒排索引方法论，将单元点存储在内存中，较大的单元列表存储在磁盘中，采用分层平衡聚类算法来平衡单元列表的长度，采用查询感知方案动态修剪不必要的单元列表查询，实验证明该系统相较于现有的近似最近邻搜索（ANNS）解决方案DiskANN 在处理数十亿数据集时，可以用相同的内存成本实现同样的召回率质量，并且速度快 2 倍以上 。

    Nov, 2021

  • 学习的k-NN距离估计

    提出了一种利用全连接神经网络模型和支点来快速准确地估计查询的k-NN距离的机器学习技术。实验结果表明，该方法在大数据挖掘和近距离数据分析方面具有高效和有效的优势。

    Aug, 2022

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

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

    May, 2023

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

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

    Oct, 2023

  • 基于图的近似最近邻搜索的自适应入口点选择的理论和实证分析

    我们对于基于图的近似最近邻搜索（ANNS）的自适应入口点选择进行了理论和实证分析。我们引入了新颖的概念：b-单调路径和B-MSNET，其在实际算法中比现有的概念如MSNET更好地捕捉到了真实图形。我们证明了在比以前的工作更一般的条件下，自适应入口点选择提供了比固定中心入口点更好的性能上界。从实证上看，在各种数据集上，尤其是在包含分布之外的数据和难例的挑战情况下，我们在准确性、速度和内存使用方面验证了该方法的有效性。我们的综合研究为优化面向实际高维数据应用的基于图的ANNS的入口点提供了更深入的见解。

    Feb, 2024