提出了一个新的数据结构用于解决欧几里得空间中近似最近邻问题，其查询时间和空间复杂度分别为 O (n^ρ + dlogn) 和 O (n^(1+ρ)+dlogn)，这是对先前算法性能的改进，同时也是第一个突破已有局部敏感哈希下界的数据结构。并可通过标准归约获取解决海明空间和 l1 范数的数据结构。

Jun, 2013

我们定义和研究了 $ extit {c - 近似窗口搜索}$ 的问题，即在数据集中每个点具有数字标签，并且目标是在任意标签范围内找到 Queries 的最近邻。我们提出并理论分析了基于模块化树结构的方法，用于将解决传统 c - 近似最近邻问题的索引转换为解决窗口搜索的数据结构。在标准最近邻基准数据集上，对于具有随机标签值、对抗构建嵌入和具有实际时间戳的图像搜索嵌入，我们在相同召回级别上获得高达 75 倍的加速。

Feb, 2024

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

Sep, 2016

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

Dec, 2014

提出一种基于局部敏感过滤的相似性搜索框架，扩展了 Indyk-Motwani (STOC 1998) 的局部敏感哈希 (LSH) 框架以支持时空权衡。

May, 2016

本文提出了一种名为 Constrained Approximate Nearest Neighbors (CANN) 的近似 K 最近邻联合解决方案，该方案只使用局部特征进行跨几何和外观空间的 K 最近邻检索以提高视觉定位的性能，并且在公共定位基准测试中成功地优于现有方法。

Jun, 2023

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

Oct, 2023

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

Jan, 2021

本文提出了一种基于数据的哈希方案，用于解决近似最近邻问题，对于 $n$ 个 $d$ 维数据集，我们的数据结构实现了查询时间 $O (d n^{ ho+o (1)})$ 和空间复杂度 $O (n^{1+ ho+o (1)}+dn)$，其中 $ ho= frac {1}{2c^2-1}$，而在 Hamming 空间中，我们获得了指数 $ ho= frac {1}{2c-1}$。此外，我们的结果比所有逼近因子 $c>1$ 的最佳 LSH 数据结构 [IM98, AI06] 更优。

Jan, 2015

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

Feb, 2022