提出SHEAF方法,用答案集变化预测图搜索查询难度,提升精度。
SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search
- 通过查询自身答案集在浅层探测中的变化量衡量难度
- 在四个数据集上比基线方法相关性提升最多1.55倍
- 仅需两次浅层搜索,无需查询时真值,适合实时系统部署
基于图的近似最近邻(ANN)搜索通常由一个固定的束宽参数控制,该参数在工作负载中保持不变,以召回率为代价换取吞吐量。然而,不同查询的难度并不相同:例如在广泛使用的SIFT1M数据集上,达到95%召回率所需的束宽差异超过32倍。若系统能廉价且提前判断每个查询的难度,并为其分配合适的束宽,则可显著提升效率。目前主流的难度假设是局部内在维度(LID),但其静态且几何特性使其对最小束宽的预测能力较弱。本文提出一种新度量——从答案集流变中自适应估计查询硬度(SHEAF),将查询的硬度定义为自身前k个答案集在两个浅层探测束宽之间的变化程度。我们设计了一个自校准估计算法,将这种流变转化为可部署的每查询束宽预测器;同时提出一种固定探测评估协议,在所有查询上以实际所需最小束宽为基准进行评分。在CAGRA和HNSW等主流索引结构下,针对四个多样化数据集的实验表明,SHEAF在GPU与CPU上均优于五种基线方法,最大持有外相关性提升达1.55倍,且仅需两次浅层探测,无需查询时真值信息。
原文摘要 · Abstract (English)
Graph-based approximate nearest neighbor (ANN) search is usually governed by a beam-width parameter that trades recall for throughput and is fixed for the whole workload. Yet, queries may not be equally hard: for example, on the widely used data set SIFT1M, the beam that a query needs to reach 95\% recall varies by more than $32\times$. Therefore, serving each query at its own width would help if the system could tell, cheaply and in advance, how hard it is. The prevailing proxy for this difficulty is called local intrinsic dimensionality (LID); however, LID is static and geometric, which makes it only weakly predict the minimum beam. This paper presents a new measure, namely Self-profiled Hardness Estimation from Answer-set Flux (SHEAF), which represents a query's hardness as how much its own top-$k$ answer set changes between two shallow probe widths. We design a self-profiling estimator that turns this flux into a deployable per-query beam predictor; furthermore, we develop a fixed-probe evaluation protocol that scores each measure over all queries with an observed minimum sufficient beam. On popular ANN indexes such as CAGRA and HNSW across four diverse data sets, SHEAF predicts the per-query beam better than five baseline measures on both GPU and CPU by up to $1.55\times$ in held-out correlation, using only two shallow probe searches and no query-time ground truth.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。