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

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

CAGRA是N社在RAFT項(xiàng)目中最新的ANN（近似最近鄰）向量索引算法。它是一種高性能的、GPU加速的、基于圖的方法，特別針對小批量情況進(jìn)行了優(yōu)化，其中每次查找只包含一個(gè)或幾個(gè)查詢向量。與其他基于圖的方法（如HNSW、SONG等）類似，CAGRA在索引訓(xùn)練階段構(gòu)建了一個(gè)經(jīng)過優(yōu)化的k-最近鄰（k-NN）圖。這個(gè)圖具備多種優(yōu)良特性，能夠在保持合理召回率的同時(shí)實(shí)現(xiàn)高效的搜索。與NSW、HNSW算法不同的是，CARGA算法是單層的圖，在構(gòu)建和查詢階段做了特殊的優(yōu)化以適應(yīng)GPU計(jì)算加速。

代碼示例：

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構(gòu)建的圖有幾個(gè)不同之處：

• 每個(gè)節(jié)點(diǎn)有固定的出度
• 構(gòu)建的圖是一個(gè)有向圖
• 不同于HNSW，CAGRA構(gòu)建的圖是單層的

• 《暗喻幻想：ReFantazio》尤法社群等級提升作用介紹
• 【長城守望】新服開啟！沖榜就送非遺城磚
• 《寶可夢大集結(jié)》路卡利歐技能圖鑒
• 《塞爾達(dá)傳說 智慧的再現(xiàn)》螺旋甜味冰沙怎么制作
• 《仙劍世界》黑蜘蛛森林寶箱開啟方法