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

Jun, 2018

每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度 “top-k” 范数的迭代乘积的低扭曲嵌入。同时，我们证明这些方法无法推广到一般范数。

Nov, 2016

研究了度量空间中近似最近邻的问题，其中查询点被限制在低重复维度的子空间上，而数据则是高维的。我们展示了尽管数据是高维的，这个问题仍能得到有效的解决。

Jul, 2010

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

Dec, 2014

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

Jun, 2013

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

Oct, 2005

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

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

Aug, 2016

本文研究欧几里得空间中距离草图和维度约简等方面的问题，并讨论了相应的算法和理论。

Oct, 2016

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

Dec, 2015