该研究介绍了一种名为优先的动态连续索引（Prioritized DCI）的变体，用于 k 近邻搜索，并且相对于现有方法（如局部敏感哈希，LSH），优先 DCI 通过线性增加空间而不是查询时间的依赖来解决了维数灾难的问题，并在内在维数方面展现了显着的改进。

Mar, 2017

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

Jul, 2010

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

Apr, 2024

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

Jan, 2019

通过分析三种 k-d 树的变体，我们确定了一个简单的潜在函数，该函数能直接反映数据集和查询点难度，并在正增长测度和主题模型中限制了该潜在函数。

Feb, 2013

研究的主题是在多维单位盒子上基于样本的学习条件分布，采用聚类方法，在特征空间中的变化查询点附近聚类数据来创建目标空间的经验度量。聚类方案包括基于固定半径球和最近邻的方法，通过收敛速率的上界确定最佳的半径和邻居数量。通过在实践中进行经验分析，我们的建议是将最近邻方法结合到神经网络训练中，因为它在实践中的性能更好。训练过程利用随机二进制空间划分进行近似最近邻搜索以提高效率。另外，我们使用 Sinkhorn 算法和稀疏强制传输计划。经验研究结果表明，通过适当设计结构，神经网络能够在局部适应适当的 Lipschitz 连续性水平。用于可复现性的代码可在 https://github.com/zcheng-a/LCD_kNN 找到。

Jun, 2024

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

Dec, 2014

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

Oct, 2005

提出了一种名为密度敏感哈希（DSH）算法，它是局部敏感哈希（LSH）的扩展，利用数据的几何结构避免了纯随机投影的限制，并在大规模高维数据搜索中取得更好的性能。

May, 2012

本条研究提出了史上首个可查询到数据集中最近邻居的亚线性内存草图，并利用局部敏感哈希（LSH）估计器、在线核密度估计和压缩感知相结合来实现稳定查询的子线性内存性能，以取得内存 - 精度权衡的理论效果。

Feb, 2019