参数自适应下基于近邻图的近似最近邻搜索 甘红楠.pdf

: .
计算机工程 S。AdaptNNS 首先采样
数据库中的被检索向量，并对采样结果进行聚类。AdaptNNS 随后将聚类中心向量作为最近邻分类器，并用其抽取查询负载
的特征，来表征搜索查询最近邻的难易程度。最后，AdaptNNS 使用不同的召回率与查询负载的特征结合，将其作为完整的
输入特征来训练梯度提升决策树（GBDT）模型。在处理查询时，AdaptNNS 结合应用程序指定的召回率获取完整的特征，并
利用训练好的模型预测最优搜索参数，从而提升 ANNS 的吞吐量。使用 DiskANN 算法和 HNSW 算法在三个千万级别数据集
上进行实验。结果表明，在达到相同召回率时，AdaptNNS 方法相较于对比方法最大能够将吞吐量提升 倍，与最优情况下
的吞吐量最少相差不到 1%。
关键词：近似最近邻搜索；近邻图结构；参数自适应；聚类；GBDT

开放科学（资源服务）标志码（OSID）:
Graph-based Approximate Nearest Neighbor Search under Parameter
Dynamic Adjustment
GAN Hongnan1, ZHANG Kai2
(1. School of Software Engineering, Fudan University, Shanghai 200438, China;
2. School of Computer Science, Fudan University, Shanghai 200438, China)
【Abstract】The graph-based approximate nearest neighbor search (ANNS) algorithms organize vectors in the database into a
proximity graph structure, and get the approximate nearest neighbor of the query vector leveraging user-specified search parameter
configurations. The search parameter is configured large enough to meet different recall targets required by various applications, which
results in a sharp drop in throughput. To address this issue, this paper proposes an approach for the graph-based ANNS algorithms to
adjust the parameter adaptively and names it AdaptNNS. Firstly, AdaptNNS samples vectors in database and clusters sampling result.
Secondly, AdaptNNS uses c