Nov, 2023

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

PDF
TL;DR提出一种自适应群体测试框架用于基于范围的高维近邻搜索问题，该方法通过余弦距离阈值快速标记图像描述符集合中的邻居和非邻居，并实现了超过 10 倍的速度提升，同时保持了与穷举搜索相同的准确性。
adaptive group testing frameworkrange-based high dimensional near neighbor search problemcosine distance thresholdlarge scale retrievalmulti-stage adaptive group testing algorithm
发现论文，激发创造
  • 聚类点集的近似最近邻搜索分析

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

    Jan, 1999

  • 基于动态连续索引的快速 K 最近邻搜索

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

    Dec, 2015

  • 噪声自适应群体测试：界限与算法

    本研究提出了一些信息理论上的可行性和对话界限，并为基于计算效率的变体提供了略微较弱的可行性界限，为噪声自适应设置提供了可能的最优算法，解决了组测试问题的有关缺陷项和噪声模型的问题。

    Mar, 2018

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

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

    Oct, 2016

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

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

    Feb, 2024

  • 基于 GPU 的十亿级相似度搜索

    本文提出了一种优化 k - 选择算法解决高维数据相似度搜索问题的方法，实现了快速且准确的 k - 最近邻图的构建，并在多个方面超越目前的最新 GPU 技术。

    Feb, 2017

  • 在 GPU 上高效地进行大规模近似最近邻搜索

    本研究提出基于 Product Quantization 的两层向量量化树的 ANN 搜索新方法，在 GPU 实现方面取得了比 CPU 更高的性能表现，适用于视频中循环关闭等对时间敏感的高维问题。

    Feb, 2017

  • 在十亿个向量中搜索：用源编码重新排序

    本文提出了一种在高维向量的压缩域内重新排列邻居猜想的方法，通过短量化码优化估算距离，以避免从磁盘中读取完整向量，实验证明该方法准确高效且占用较少内存。

    Feb, 2011

  • 基于图的近似最近邻搜索的综合调查和实验比较

    本文综述了 13 个代表性的基于图的近似最近邻搜索算法，通过新的分类和细粒度的流程进行了比较分析和实验评估。该研究提供了优化算法的原则并设计了一种优化方法，可以优于现有的基于图的近似最近邻算法。同时还提供了关于有前途的研究方向和适合不同领域从业者使用的算法的经验建议。

    Jan, 2021

  • 利用第一邻居关系实现高效无参数聚类

    提出了一种新的聚类方法，可以直接发现数据中的分组，不同于大多数现有的聚类算法，该方法不需要任何超参数、距离阈值和 / 或指定聚类数，该算法属于层次凝聚方法，在不同领域的公认数据集上评估表明性能大幅提高。

    Feb, 2019