引用PaulHoule · 2023-03
“Depends on what you want to optimize for. See this paper”
回答优化取舍问题时,指向这篇 GPU 近邻搜索论文
GPU 上的 k-选择与乘积量化设计,近邻搜索快 8.5 倍
论文针对 GPU 上近邻搜索的瓶颈(k-min 选择并行度低、内存层次利用差),提出峰值利用率可达约 55% 的 k-选择设计,并据此实现比此前 GPU 最优快 8.5 倍的最近邻搜索,覆盖暴力、近似和基于乘积量化的压缩域搜索。这套实现支持在 4 块 GPU 上不到 12 小时构建 10 亿向量的 k-NN 图,代码已开源(即 Faiss)。
评论者在讨论向量近邻搜索选型时引用它,其中还有 Faiss 作者本人说明 Faiss 的实现细节(包括 IVFPQ 索引)都写在这篇论文里。
先了解被检索的向量从哪里来(词向量等嵌入),再对比另一类近似最近邻方法(图索引),然后读 GPU 上的乘积量化与 k-选择设计。
词向量是十亿级相似性搜索典型处理的高维稠密向量之一,帮助理解应用场景。
读只需理解词被映射为稠密向量、相似度由向量距离表示。
HNSW 是与乘积量化不同路线的近似最近邻索引,用来对比 GPU 暴力与压缩方案的取舍。
读抓住多层邻近图和贪心搜索的基本思路,不用看参数细节。
目标论文:GPU 上的 k-选择、IVF 与乘积量化设计,支持十亿级向量搜索。
读看 GPU 内存层次下的 k-选择设计、倒排索引加乘积量化的流程,以及十亿级实验。
“Depends on what you want to optimize for. See this paper”
“including the one in Faiss which I wrote (described in detail in Billion-scale similarity search with GPUs)”