CAGRA：一种高性能、GPU加速的ANN向量索引算法

本文连接： https://wanger-sjtu.github.io/CARGA/

CAGRA是N社在RAFT项目中最新的ANN（近似最近邻）向量索引算法。它是一种高性能的、GPU加速的、基于图的方法，特别针对小批量情况进行了优化，其中每次查找只包含一个或几个查询向量。与其他基于图的方法（如HNSW、SONG等）类似，CAGRA在索引训练阶段构建了一个经过优化的k-最近邻（k-NN）图。这个图具备多种优良特性，能够在保持合理召回率的同时实现高效的搜索。与NSW、HNSW算法不同的是，CARGA算法是单层的图，在构建和查询阶段做了特殊的优化以适应GPU计算加速。

代码示例：

using namespace raft::neighbors;
// use default index parameters based on shape of the dataset
ivf_pq::index_params build_params =   ivf_pq::index_params::from_dataset(dataset);
ivf_pq::search_params search_params;
auto knn_graph      = raft::make_host_matrix(dataset.extent(0), 128);

// create knn graph
cagra::build_knn_graph(res, dataset, knn_graph.view(), 2, build_params, search_params);
auto optimized_gaph = raft::make_host_matrix(dataset.extent(0), 64);
cagra::optimize(res, dataset, knn_graph.view(), optimized_graph.view());
// Construct an index from dataset and optimized knn_graph

auto index = cagra::index(res, build_params.metric(), dataset,
                                   optimized_graph.view());

CAGRA构建的图有几个不同之处：

• 每个节点有固定的出度
• 构建的图是一个有向图
• 不同于HNSW，CAGRA构建的图是单层的