按年被提到
20172017 · 2 次2026
系统、数据库与网络›数据库与向量检索·arXiv:1702.08734 · cs.CV

Billion-scale similarity search with GPUs

基于 GPU 的十亿级相似性搜索
Jeff Johnson, Matthijs Douze, Hervé Jégou · 2017

GPU 上的 k-选择与乘积量化设计,近邻搜索快 8.5 倍

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2017-03-04 · 最近 2024-01-12
6不同的人
5活跃月份
6讨论串
4,465被引(OpenAlex)

论文针对 GPU 上近邻搜索的瓶颈(k-min 选择并行度低、内存层次利用差),提出峰值利用率可达约 55% 的 k-选择设计,并据此实现比此前 GPU 最优快 8.5 倍的最近邻搜索,覆盖暴力、近似和基于乘积量化的压缩域搜索。这套实现支持在 4 块 GPU 上不到 12 小时构建 10 亿向量的 k-NN 图,代码已开源(即 Faiss)。

HN 为什么提它

评论者在讨论向量近邻搜索选型时引用它,其中还有 Faiss 作者本人说明 Faiss 的实现细节(包括 IVFPQ 索引)都写在这篇论文里。

方法难度 4 / 5约 50 分钟经得起时间
读之前最好知道
1最近邻搜索(k-NN)
2乘积量化(product quantization)
3GPU 并行编程与内存层次
4倒排索引(IVF)

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先了解被检索的向量从哪里来(词向量等嵌入),再对比另一类近似最近邻方法(图索引),然后读 GPU 上的乘积量化与 k-选择设计。

  1. 1
    Efficient Estimation of Word Representations in Vector Space向量空间中词表示的高效估计 · 2013

    词向量是十亿级相似性搜索典型处理的高维稠密向量之一,帮助理解应用场景。

    读只需理解词被映射为稠密向量、相似度由向量距离表示。

  2. 2
    Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs基于分层可导航小世界图的高效、鲁棒近似最近邻搜索 · 2016

    HNSW 是与乘积量化不同路线的近似最近邻索引,用来对比 GPU 暴力与压缩方案的取舍。

    读抓住多层邻近图和贪心搜索的基本思路,不用看参数细节。

  3. 3
    Billion-scale similarity search with GPUs基于 GPU 的十亿级相似性搜索 · 2017 · 就是这篇

    目标论文:GPU 上的 k-选择、IVF 与乘积量化设计,支持十亿级向量搜索。

    读看 GPU 内存层次下的 k-选择设计、倒排索引加乘积量化的流程,以及十亿级实验。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用PaulHoule · 2023-03

“Depends on what you want to optimize for. See this paper”

回答优化取舍问题时,指向这篇 GPU 近邻搜索论文
Ask HN: What’s the optimal approach for KNN (K- Nearest Neighbor)?原评论 ↗
引用jhj · 2024-01

“including the one in Faiss which I wrote (described in detail in Billion-scale similarity search with GPUs)”

作者说明自己写的 Faiss 实现细节见这篇论文
Vector Databases: A Technical Primer [pdf]原评论 ↗
被提交为 story · 4 次