Feb, 2017

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

PDF
TL;DR本研究提出基于 Product Quantization 的两层向量量化树的 ANN 搜索新方法，在 GPU 实现方面取得了比 CPU 更高的性能表现，适用于视频中循环关闭等对时间敏感的高维问题。
approximate nearest neighbor searchproduct quantization treegpu implementationhigh dimensional spacesvector quantization
发现论文，激发创造
  • 提升双层产品量化在高维度亿级近似最近邻搜索中的效率

    本研究针对高维数据，提出了两种基于产品量化方法的最近邻搜索系统，并通过实验证明这些系统在检索效率与精度方面优于现有的系统。

    Apr, 2014

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

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

    Oct, 2016

  • AiSAQ：全存储 ANNS 与产品量化用于无 DRAM 信息检索

    本文提出了一种名为 All-in-Storage ANNS with Product Quantization (AiSAQ) 的方法，通过将压缩向量转移到存储器中，可以在十亿级别的数据集中实现约 10MB 的内存使用，同时还能减少查询之前的索引加载时间，增强检索辅助生成（RAG）的灵活性。该方法适用于所有基于图的近似最近邻搜索算法，未来还可以与更高规格的近似最近邻搜索方法相结合。

    Apr, 2024

  • 使用 Quick ADC 加速最近邻搜索

    本文提出了一种名为 Quick ADC 的新技术，通过利用当前 CPU 中可用的单指令多数据 (SIMD) 单元，实现了对 ADC 的 3-6 倍加速，并提出了两个关键算法修改，将 8 位子量化器替换为 4 位子量化器和定量化浮点距离。

    Apr, 2017

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

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

    Feb, 2022

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

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

    Feb, 2017

  • 面向半监督图像检索的广义产品量化网络

    本研究提出了基于泛化乘积量化网络的半监督图像检索方案，通过设计新颖的度量学习策略提高量化网络的泛化能力，实现了对标记和未标记数据的充分利用，并在大规模图像基准数据集上展示了最先进的性能。

    Feb, 2020

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

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

    Dec, 2014

  • 使用 GPU 进行快速 k 近邻搜索

    该研究评估了使用 NVIDIA CUDA API 加速 K - 最近邻搜索在计算机视觉中的应用，最多可缩短搜索时间 120 倍。

    Apr, 2008

  • CAGRA: 高并行图构建和 GPU 上的近似最近邻搜索

    通过使用现代硬件的高性能能力，我们的方法在构建接近图时，构建时间比 HNSW 快 2.2~27 倍；在大批量查询吞吐量方面，在 90% 至 95% 召回范围内，我们的方法比 HNSW 快 33~77 倍，并且比 GPU 的最新实现快 3.8~8.8 倍；对于单个查询，在 95% 召回率时我们的方法比 HNSW 快 3.4~53 倍。

    Aug, 2023