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

Jun, 2013

研究在选择设施位置时，考虑人口密度和均衡负载的公平算法，通过近似算法证明了 NP 难度，并在实际应用中表现出更好的性能。

Aug, 2019

本文提出了一种基于数据的哈希方案，用于解决近似最近邻问题，对于 $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

研究了关于敏感哈希族的一些性质，证明了在 $L_1$ 度量空间中，不可能构造出一个性能与 Indyk 和 Motwani 相同的敏感哈希族。

Oct, 2005

该研究论文介绍了时空权衡的上下界，并提出了第一种子线性查询时间和近似线性空间数据结构，可用于每个逼近因子 c>1 的近邻搜索问题，并通过建立一些类推到当地可解码代码的联系来表明两种探针的无条件单元格探针下限。

Aug, 2016

本文研究在高维空间中，特别是欧几里德空间中找到查询点的近似最近邻的问题，提出了一种用于解决问题的新方法，并分析了其效果，同时改进了局部保持哈希函数以提高最近邻检索效率。

Oct, 2005

我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平（$p$, $k$）- 聚类问题。我们设计了首个快速局部搜索算法，具有～$O (nk^2)$ 的运行时间，并获得了（O (1), 6）的二对象近似解，然后我们通过实验证明了我们的算法不仅比以前的工作快得多，而且产生了更低成本的解决方案。

Feb, 2024

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

Dec, 2014

此篇论文调查了近邻问题的近似解决方案，如建立数据结构以实现较高的效率，并涉及到计算几何和组合几何中的相关问题。

Jun, 2018

本文系统综述了最近邻搜索问题中的哈希学习算法，将其按照不同的相似性保存方式进行分类，并分别阐述其性能评估和效益分析，最终指出量化算法在搜索精度、搜索时间、空间花费等方面都表现优异，并介绍了一些新兴话题。

Jun, 2016