Feb, 2024

带窗口过滤器的近似最近邻搜索

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

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

    Jun, 2018

  • 低维查询的近似最近邻搜索

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

    Jul, 2010

  • 使用松弛度的随机嵌入和高维近似最近邻

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

    Dec, 2014

  • 高维数据的近似最近邻搜索：实验、分析与改进（v1.0）

    本文详细评估了 16 种不同算法在 20 个不同数据集、多个评估指标和不同查询工作负载下的性能表现，并提出了一种新的方法以提高查询效率和召回率。

    Oct, 2016

  • 分类的自适应最近邻规则

    该论文提出了一种改进的 K 近邻分类器，它可以自适应地为每个查询选择 K，该选择取决于每个邻域的属性，因此可能在不同点之间显着变化，并且可以利用条件概率推导推导出一些收敛界限。

    May, 2019

  • 非参数时间序列分类的潜在源模型

    使用近邻法分类时间序列的理论依据是，许多应用场景下实际上原型时间序列相对于我们可以访问的时间序列数量非常少；作者提出了一种基于潜在源模型的分类规则，并在合成数据上验证了加权多数投票与近邻分类的同等正确分类率。通过这种方法，在 Twitter 上可以提前 1 小时 26 分钟实现 95% 的 “趋势话题” 检测。

    Feb, 2013

  • 聚类点集的近似最近邻搜索分析

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

    Jan, 1999

  • 基于神经相似性度量的大规模推荐系统近似最近邻搜索

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

    Feb, 2022

  • 精确且高效的范围近邻搜索的分组测试：自适应二分法

    提出一种自适应群体测试框架用于基于范围的高维近邻搜索问题，该方法通过余弦距离阈值快速标记图像描述符集合中的邻居和非邻居，并实现了超过 10 倍的速度提升，同时保持了与穷举搜索相同的准确性。

    Nov, 2023

  • 流行近似最近邻搜索实现的最坏情况性能：保证和限制

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

    Oct, 2023