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

Feb, 2013

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

Dec, 2015

该论文提出了一种基于 Poincaré ball 模型的统一框架，用于构建可伸缩、简单的超几何线性分类器，并给出了凸优化的解决方案，该算法在合成数据集和真实数据集上的表现均有很高的准确率。

Sep, 2021

本文提出了针对内积最优匹配问题的新型分支边界算法，包括使用树形结构的一般分支边界算法、针对多个查询的双树算法以及新型数据结构等，实验结果表明与朴素搜索技术相比，该算法能使查询时间提升高达 5 个数量级。

Feb, 2012

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

Dec, 2014

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

Jul, 2010

本文提出了一种基于 vantage-point trees 的 t-SNE 实现算法，并使用 Barnes-Hut 算法来计算给出的高维数据点对之间的作用力，实验证明该算法相比于常规 t-SNE 具有更强的计算优势，且可以用于处理数据集建模任务。

Jan, 2013

本研究通过理论与实验结合的方法，探讨了更广泛的树类组合，以了解空间划分可以利用数据的内在低维结构的程度，对于回归、向量量化和最近邻搜索等标准统计任务的影响，并证实了随机投影树是适应数据固有维数的。

May, 2012

我们提出了一种新的 “双度量” 框架，用于设计最近邻数据结构。我们的框架基于两个不相似性函数：一个准确但计算代价高的基准度量，和一个廉价但不太准确的代理度量。我们在理论和实践中展示了如何仅使用代理度量构建数据结构，使查询过程达到基准度量的准确性，同时只使用有限次对两个度量的调用。我们的理论结果在两个最流行的最近邻搜索算法（DiskANN 和 Cover Tree）中实例化了该框架。对于任意一个这两个算法，只要用于构建数据结构的代理度量相对于基准度量有界因子的近似，我们的数据结构都能在基准度量方面获得任意好的近似保证。在实证方面，我们将该框架应用于具有计算代价差异的两个机器学习模型评估的文本检索问题。我们观察到，在 MTEB 基准测试中，对于几乎所有的数据集，我们的方法能够在准确度和效率之间获得相比其他方法（如重新排序）更好的平衡。

Jun, 2024

通过与两种替代分割方法的比较，通过 对数据结构的实证分析，分析了适用于近似最近邻搜索的数据结构。结果表明，对于聚类的数据点和查询集，这些算法可以相对于标准的 kd-tree 构造提供显着改进。

Jan, 1999