甘紅楠，張 凱

（1.復旦大學 軟件學院，上海 200438；2.復旦大學 計算機科學技術學院，上海 200438）

0 概述

最近鄰搜索（Nearest Neighbor Search，NNS）是指從被檢索對象集合中搜索出與給定目標最相似的一個或多個對象，其中相似程度由歐氏距離、余弦相似度等度量標準確定。在文檔檢索［1］、推薦系統(tǒng)［2］等應用程序中，圖像、文檔、商品等查詢和檢索對象被嵌入稠密連續(xù)向量，查詢對象間的相關性可以表示為嵌入向量間的距離。然而，隨著數(shù)據(jù)庫中檢索向量數(shù)量的增長和維度的增加，幾乎只有掃描所有數(shù)據(jù)，才能檢索到所需查詢的精確最近鄰［3-4］，該現(xiàn)象被稱為維度災難［5］。線性掃描會導致搜索效率低下，無法滿足大規(guī)模向量應用查詢的需求。近似最近鄰搜索（Approximate Nearest Neighbor Search，ANNS）通過犧牲較小的查詢精度提升查詢效率，并返回近似最近鄰（Approximate Nearest Neighbor，ANN）［6］。

ANNS 算法主要包括基于局部敏感性哈希［7-8］、基于樹結構［9-10］、基于量化［11-12］和基于近鄰圖［13-14］4 類算法。由于能夠高效地對稠密連續(xù)向量進行ANNS，基于近鄰圖的ANNS算法［15］被廣泛應用于人工智能相關領域，將數(shù)據(jù)庫中的向量視為點，向量間的距離表示點間的距離，根據(jù)距離將它們組織成近鄰圖。由于近鄰圖結構能夠靈活地表達點間的近鄰關系，基于近鄰圖的ANNS 算法只需搜索少量的點就可以達到給定的目標召回率［16］。DiskANN［17］、HNSW［18］、NSG［16］等是近年來提出的典型的基于近鄰圖的ANNS 算法，搜索過程采用貪心搜索［19］，從一個固定的入口點開始搜索并選擇與查詢向量最接近的鄰居進行迭代遍歷，每輪迭代中沿著近鄰圖遍歷距離查詢向量更近的點。所有遍歷過的點被放入一個固定大小的動態(tài)搜索列表（Dynamic Search List，DSL），如果超過DSL 大小，離查詢距離更遠的點將被移出。搜索過程直到某一輪迭代中沒有找到與查詢向量距離更近的點為止。DSL 越大，遍歷的點越多，召回率越大，但是吞吐量越小。由于不同應用程序對召回率的要求不同，用戶需要手動調節(jié)DSL 大小以達到目標召回率，然而處理不同查詢負載所需DSL 大小也不同，因此用戶通常通過設置足夠大的DSL 保證達到目標召回率，但是過大的DSL 使得基于近鄰圖的ANNS 算法搜索更多的點，從而大幅降低了吞吐量。

本文面向基于近鄰圖的ANNS 算法，提出一種參數(shù)自適應方法AdaptNNS。使用聚類方法生成分散在近鄰圖中不同位置的點，利用聚類中心點和最近鄰分類器提取查詢集合的特征，將其與不同的召回率相結合來訓練梯度提升決策樹（Gradient Boosting Decision Tree，GBDT）模型［20］。通過GBDT模型為查詢集合預測最優(yōu)DSL 大小，提升最近鄰搜索的吞吐量。

1 近似最近鄰搜索

1.1 相關定義

最近鄰搜索的目標是在給定集合中找到與給定查詢向量距離最近的向量。近似最近鄰搜索通過犧牲較小的查詢精度提升查詢效率，以獲取近似最近鄰［6］。給定查詢的最近鄰形式化定義［21］如下：

定義1（最近鄰）給定大小為N、維度為D的有限向量集合X={x1,x2,…,xN}?RD，表示被索引點的集合，給定查詢向量q∈RD，dist 表示兩個向量之間的距離，如歐式距離等。q在X中的最近鄰表示如下：

召回率是衡量ANNS 結果相關性的指標。最近鄰搜索通常要求返回K個最近鄰。Recall@K是搜索K個最近鄰時的召回率。召回率越高，返回結果與真實結果越接近。

定義2（召回率）假設集合C'包含q的K個近似最近鄰、C包含q的K個真實最近鄰，則Recall@K的計算公式如下：

定義3（搜索路徑）在給定的圖結構G上進行搜索，從點ps沿著G中的（有向）邊搜索到pe，中間依次經(jīng)過點p1、p2、…、pn，形成搜索路徑s1：ps→p1→p2→…→pn→pe。搜索路徑長度即為搜索路徑中經(jīng)過的邊的數(shù)目，單位為跳（hop）。s1的搜索路徑長度為n+1。在搜索過程中，搜索路徑越長，花費時間越久。

1.2 基于近鄰圖的ANNS 算法

現(xiàn)有基于近鄰圖的ANNS 算法主要分為如圖1所示的近鄰圖構建和搜索2 個階段［15］。在近鄰圖構建階段將數(shù)據(jù)庫中的點組織成近鄰圖結構，如DiskANN 采用近似的稀疏鄰域圖［22］組織被檢索向量、HNSW 采用近似的德勞內圖［18］構建近鄰圖。盡管不同算法采用的近鄰圖結構不相同，但是它們的搜索階段基本一致。貪心搜索廣泛用于基于近鄰圖的ANNS 算法的最近鄰搜索過程［19］，如算法1 所示。概括來說，搜索算法從一個固定入口點開始搜索近鄰圖，通過貪心搜索逐漸接近查詢向量的最近鄰。在搜索過程中，算法將已訪問的點存儲在DSL 中，隨后訪問它們的鄰居。當DSL 中點的數(shù)目超出指定大小時，只有與查詢向量距離較近的點才會保留在DSL 中。

圖1 基于近鄰圖的ANNS 算法流程Fig.1 Procedure of ANNS algorithm based on neighbor graph

算法1基于近鄰圖的ANNS 搜索過程

根據(jù)在多個數(shù)據(jù)集上的評測結果［23］，DiskANN和HNSW 算法在搜索時的性能表現(xiàn)優(yōu)異，并且綜述文獻［15］也將它們作為具有代表性的基于近鄰圖的ANNS 算法，因此本文以DiskANN、HNSW 算法為例，基于此實現(xiàn)AdaptNNS 方法，從而提高搜索性能。

2 參數(shù)自適應下基于近鄰圖的ANNS 算法

本節(jié)分析為基于近鄰圖的ANNS 算法設置過大DSL 所存在的問題，進而提出一種參數(shù)自適應方法并將其命名為AdaptNNS。AdaptNNS 方法主要包括2 個步驟：1）抽取查詢負載的特征；2）在給定召回率下為查詢集合預測DSL 大小。

2.1 參數(shù)設置問題分析

2.1.1 參數(shù)設置

給定一個查詢集合和目標召回率，用戶需要手動調節(jié)DSL 大小，使得查詢集合ANNS 達到目標召回率。如算法1 所示，在搜索時每輪迭代的中間結果被放入DSL，下一輪迭代從DSL 中未被訪問的點的鄰居開始，新訪問的點作為中間結果放入DSL。如果DSL 中點的數(shù)目超過了它的固定大小，將DSL中與查詢距離最遠的點刪去。DSL 越大，召回率越大，相應的吞吐量越低。

不同的查詢負載在不同的召回率要求下，存在一個最優(yōu)的DSL 大小，可使吞吐量最大化。然而，最優(yōu)的DSL 大小隨查詢負載和不同召回率要求而變化，用戶通常會設置足夠大的DSL 保證滿足召回率要求，這也導致了吞吐量的大幅降低。

以圖2 為例，分析DSL 過大導致的吞吐量性能低下問題。給定R2空間中的12 個向量a、b、c、d、e、f、h、i、k、m、n、o，根據(jù)它們之間的近鄰關系構建近鄰圖，圖中的邊都是雙向邊，每個點有兩條鄰邊，點a是搜索入口點。給定查詢Q1、Q2，它們與圖中所有點的距離如表1 所示。由表1 可知，當K=2 時，點n、d是查詢Q1的最近鄰，點c、b是查詢Q2的最近鄰。

圖2 近鄰圖實例Fig.2 Example of neighbor graph

表1 查詢點與被索引點之間的距離Table 1 Distance between query points and indexed points

2.1.2 相同負載和不同召回率下的搜索吞吐量變化

對于同一個查詢集合，為了達到不同的召回率目標需要設置不同大小的DSL。查詢的最近鄰答案有的與入口點之間的搜索路徑短、有的與入口點之間的搜索路徑長。因此，當要搜索更多最近鄰答案（更高的召回率要求）時，必須設置更大的DSL。

以圖2 中的查詢Q1為例。當召回率的要求為Recall@2 不低于50%時，DSL 大小可以設為2。使用算法1 執(zhí)行搜索，DSL 中點的變化過程如表2 所示，其中，DSL 列表示DSL 緩沖區(qū)中的內容；visited 列表示對應點的鄰居是否被訪問過，其中，√表示被訪問過，×表示沒有被訪問過。算法1 中的循環(huán)體總共迭代了4 輪。在搜索過程中，算法總共訪問過a、b、c、d、f5 個點。因為在訪問f時DSL 中已經(jīng)有兩個元素并且f與查詢Q1距離最遠，所以f沒有被放入DSL。因為點d、b各自的鄰居到查詢點Q1的距離比d、b自身到查詢點的距離遠，所以第4 輪迭代之后循環(huán)終止。這種現(xiàn)象類似數(shù)學中的局部最優(yōu)。當DSL 大小為2 時，搜索算法找到了Q1的1 個最近鄰d（另一個是n），召回率滿足大于50%的要求。當召回率要求Recall@2 為100%時，DSL 大小則必須不小于6 才能搜索到Q1的所有最近鄰。仍用算法1 進行搜索，DSL 中點的變化過程如表3 所示，第11 輪遍歷點n的鄰居，點n的visited 標志位變?yōu)椤?。算? 中的循環(huán)體總共迭代了11 輪。在搜索過程中，算法將所有12 個點都訪問了一遍。

表2 搜索查詢Q1時DSL 大小為2 的搜索過程Table 2 Search process of DSL size equal to 2 when search query Q1

表3 搜索查詢Q1時DSL 大小為6 的搜索過程Table 3 Search process of DSL size equal to 6 when search query Q1

給定查詢負載q1，使用DiskANN 算法和Text-to-Image 10M 數(shù)據(jù)集（包含10 000 000 個被索引向量）進行實驗。如圖3 所示：當召回率目標為Recall@1不低于99%時，最優(yōu)DSL 大小為40；當召回率目標為Recall@1 等于100%時，最優(yōu)DSL 大小為80。由圖3 可以看出，在不同目標召回率下，最大吞吐量對應的DSL 大小（最優(yōu)DSL 大?。┎煌?。如果在召回率要求大于99%時若將DSL 大小設為80，則吞吐量將下降約35%。

圖3 相同查詢負載和不同目標召回率下的吞吐量變化情況Fig.3 Throughput variation under the same query loads and different target recall rates

2.1.3 不同負載和相同召回率下的搜索吞吐量變化

為達到同一個召回率目標，處理不同的查詢集合需要不同的DSL 大小。不同查詢集合中查詢的最近鄰答案與入口點之間的搜索路徑長度不同。因此，為搜索到相同比例的最近鄰答案，最近鄰答案與入口點之間距離遠的查詢集合在進行查詢時需要更大DSL。

以圖2中的查詢Q1、Q2為例，Q1、Q2代表不同的查詢負載。當召回率要求為Recall@2 等于100%時，處理Q1時的最優(yōu)DSL 大小為6，而處理Q2時的最優(yōu)DSL 大小為2。搜索查詢Q2時DSL 的變化如表4 所示，循環(huán)體總共迭代4 輪，遍歷a、b、c、d、e5 個點。相比于處理Q1時的11 輪循環(huán)、遍歷12 個點，搜索速度更快。Q1、Q2達到相同召回率時的最優(yōu)DSL 大小不同。

表4 搜索查詢Q2時DSL 大小為2 的搜索過程Table 4 Search process of DSL size equal to 2 when search query Q2

給定不同的查詢負載q11、q12、q13，使用DiskANN算法和Text-to-Image 10M 數(shù)據(jù)集（包含10 000 000 個被索引向量）進行實驗。如圖4 所示，當召回率要求為Recall@1 不小于94%時，q11、q12、q13的最優(yōu)DSL 大小各不相同，分別為10、70、110。如果將DSL 大小統(tǒng)一設置為110，則雖然處理3 個負載的召回率都能滿足條件，但是q11的吞吐量將下降超過50%、q12的吞吐量將下降超過20%。

圖4 不同查詢負載和相同目標召回率下的吞吐量變化情況Fig.4 Throughput variation under the different query loads and same target recall rates

由上述分析可知：對于相同查詢負載，達到不同目標召回率時的最優(yōu)DSL 大小不同；對于不同查詢負載，達到相同目標召回率時的最優(yōu)DSL 大小也不同。如果將DSL 設置過大，則ANNS 算法將在達到召回率要求后繼續(xù)搜索，增加額外的搜索開銷，導致搜索吞吐量降低。

2.2 AdaptNNS 方法

針對基于近鄰圖的ANNS 算法，本文提出參數(shù)自適應方法AdaptNNS。AdaptNNS 方法利用采樣、聚類得到最近鄰分類器，并利用其抽取查詢負載的特征，同時結合查詢負載的特征與不同的目標召回率訓練機器學習模型，使得模型能夠預測給定查詢負載和目標召回率下的最優(yōu)DSL 大小。AdaptNNS方法相比于人工調節(jié)參數(shù)的方法，能夠在搜索效率與召回率之間達到更好的平衡。

2.2.1 模型選擇

選擇GBDT 作為AdaptNNS 方法中預測搜索參數(shù)的模型。GBDT 是一個基于決策樹的集成模型，將上一輪迭代產(chǎn)生的殘差作為下一輪訓練的目標，通過不斷減小殘差實現(xiàn)梯度的下降，從而最小化預測誤差，被認為是泛化能力較強的模型。GBDT 主要具有以下3 個優(yōu)點［20］：1）能夠在短時間內做出預測；2）占用內存少；3）是可解釋的，可以計算每個特征的重要性，有助于特征搜索。

2.2.2 特征構建

根據(jù)上文分析可知，最優(yōu)DSL 大小隨著查詢負載、目標召回率的不同而變化。因此，綜合考慮兩者構建模型特征。通過采樣、聚類獲取最近鄰分類器，將查詢負載中的不同查詢進行分類。由于每種類別與入口點之間的搜索路徑長度不同，影響DSL 大小設置，因此利用最近鄰分類器抽取查詢負載特征，再結合召回率構建模型所需特征。

1）最近鄰分類器查詢

首先對近鄰圖中的點以采樣率r進行隨機抽樣（算法2 中的第1 行），使得采樣得到的點分布在近鄰圖的不同位置。當總的時間開銷在可接受范圍內時，采樣率可以設置的盡可能大（但不超過1），有利于更加準確地進行分類查詢。然后將采樣出的點聚類成大小相同的類簇，并選出所有類簇的中心點作為區(qū)分查詢的最近鄰分類器，具體為：首先用k-means++算法［24］初始化類簇中心點（算法2 中的第2 行），然后利用均衡化kmeans［25］思想（算法2 中的第3 行）保證聚類結果中每個類簇的大小近似相等（最大相差1），從而使得各個類簇的中心點不受離群點影響。

算法2查詢的最近鄰分類器獲取

2）模型特征構建

由算法2 得到查詢的最近鄰分類器，即T個向量，它們分別對應T個類別。利用最近鄰分類器將查詢集合中每個查詢向量進行分類。每個查詢集合對應的特征用一個T維向量表示，每一維對應一個類別；向量表示查詢集合中不同類別查詢的數(shù)量。模型特征F 由表5 中的F0、F1、F2 連接而成，是一個T+2 維向量。

表5 模型特征描述Table 5 Model feature description

2.2.3 模型訓練

獲取不同工作負載在不同目標召回率下的最優(yōu)DSL 大小，結合工作負載和召回率要求抽取特征F。特征F 和最優(yōu)DSL 大小構成GBDT 模型的訓練數(shù)據(jù)，然后用模型為給定查詢預測在給定召回率下的最優(yōu)DSL 大小。這是一個回歸任務，確定DSL 大小的公式如下：

其中：Fm(x)表示最終預測DSL 大小的GBDT 模型，由m個決策樹組成。當i＞0 時，i表示第i棵決策樹的下標，Ti(x,θi)表示第i棵決策樹，x表示決策樹的輸入數(shù)據(jù)，θi表示第i棵決策樹的參數(shù)值，λi表示第i棵決策樹的權重值；當i=0 時，T0(x,θ0)與F0(x)相等（表示Fm(x)初始值）并且λ0=1。給定訓練數(shù)據(jù){(xj,yj)}，xj屬于特征集合F，yj表示最優(yōu)DSL 大小，則訓練過程如下：

其中：Fi(x)、Ti(x,θi)均為分段函數(shù)。訓練數(shù)據(jù)(xj,yj)在第i輪的殘差為yj-Fi-1(xj)，即決策樹Ti(x,θi)需要擬合的目標值。GBDT 的訓練過程是通過決策樹擬合殘差以及選擇權重λi從而最小化損失函數(shù)的過程。本文使用平方差損失函數(shù)，其公式如下：

2.2.4 參數(shù)自適應的在線應用

當用戶給定查詢負載集合Q、目標召回率R后，將AdaptNNS 的最近鄰分類器M1 和GBDT 模型M2加載到內存中，后續(xù)搜索過程如算法3 所示。首先，由最近鄰分類器抽取查詢負載的特征（算法3 中的第1 行）。然后，結合目標召回率和K值構建模型特征（算法3 中的第2 行）。接著，利用GBDT 模型預測最優(yōu)DSL 大小（算法3 中的第3 行）。最后，使用預測的DSL 大小并行處理查詢負載（算法3 中的第4～6 行）并返回結果（算法3 中的第7 行）。

算法3面向近鄰圖的參數(shù)自適應ANNS 算法

3 實驗與結果分析

3.1 實驗環(huán)境與參數(shù)設置

實驗所用服務器的CPU 型號為Intel?Xeon?Gold 5218 CPU @ 2.30 GHz。使用AdaptNNS 方法優(yōu)化DiskANN、HNSW 算法。DiskANN 算法常用于內存有限的場景，因此為DiskANN 分配8 個線程、4 GB 內存、1 TB 固態(tài)硬盤；HNSW 算法常用于內存充足的場景，為其分配8 個線程以及充足的內存資源。

使用Text-to-Image、DEEP、Turing-ANNS 這3 個真實世界中的數(shù)據(jù)集來分析AdaptNNS 的各項性能，數(shù)據(jù)集具體信息見表6。由于訓練和測試AdaptNNS 中的模型時需要設置不同的查詢負載，而這3 個數(shù)據(jù)集分別提供了真實應用中的查詢集合，因此使用它們構建不同的查詢負載。首先對查詢進行聚類，然后隨機選擇不同的類簇合并為查詢集合，從而得到不同工作負載的查詢集合。針對每個數(shù)據(jù)集，生成1 000 個查詢負載訓練AdaptNNS 中的模型，利用同樣的方法生成用于測試算法性能的查詢負載。在訓練時，目標召回率的取值范圍為0.7～1.0，步長為0.02。

表6 實驗數(shù)據(jù)集Table 6 Experimental dataset

AdaptNNS 方法能優(yōu)化搜索參數(shù)，但不改變近鄰圖的構建。構建近鄰圖時有2 個重要參數(shù)，其中，r是近鄰圖中點的出度，l用于控制所構建近鄰圖的質量。DiskANN 和HNSW 算法需要先構建近鄰圖，構建近鄰圖的參數(shù)設置如表7 所示。由于使用不同圖結構，因此它們的構圖參數(shù)也不同。

表7 構建近鄰圖的參數(shù)設置Table 7 Parameter setting for building neighbor graphs

將對比方法記為Baseline，具體步驟為：基于近鄰圖的ANNS 算法人為設置DSL 大??；用戶使用歷史查詢集合，獲取達到不同召回率時的DSL 值；對于新來的查詢集合，根據(jù)目標召回率選擇相應的DSL值。在本文的對比實驗中，將數(shù)據(jù)集提供的查詢集合作為歷史查詢集合，將其達到指定召回率的DSL大小用于測試查詢負載。

3.2 性能評估

本節(jié)對AdaptNNS 方法的性能進行端到端的評估。首先，使用DiskANN、HNSW 算法為3 個數(shù)據(jù)集構建近鄰圖。其次，分別使用AdaptNNS、Baseline 方法設置DSL 大小，得到各自在指定召回率要求下的吞吐量。然后，針對每個召回率，使用最優(yōu)DSL 大小的方法記為Optimal，并得到對應的吞吐量。計算AdaptNNS 方法對應的吞吐量相對于Baseline 方法的提升、相對于Optimal 情況的差距，如圖5 所示。從圖5 可以看出：當達到相同的召回率時，相比于Baseline 方法，使用AdaptNNS 方法為DiskANN、HNSW 算法設置DSL 大小使得吞吐量有不同程度的提升，其中在HNSW 算法和Turing-ANNS 數(shù)據(jù)集上，相比于Baseline 方法，AdaptNNS 方法將相同召回率下的吞吐量提升了1.3 倍；AdaptNNS 方法相比于Optimal 情況有一定的差距，AdaptNNS 方法得到的吞吐量與Optimal 情況對應的吞吐量最大相差不超過50%（圖5（f）中召回率為95%），最小相差約1%（圖5（d）中召回率為94%）。

AdaptNNS、Baseline、Optimal 對應吞吐量的差別源于它們設置的DSL 大小不同。以DiskANN 算法和3 個數(shù)據(jù)集為例，進一步探究它們設置的DSL大小的差異。表8 分別給出了Baseline 和AdaptNNS方法設置的DSL 大小與最優(yōu)DSL 大小（Optimal 情況）之間相差的比率。由表8 可以看出，在給定目標召回率下，AdaptNNS 方法設置的DSL 大小與最優(yōu)DSL 大小的誤差比Baseline 方法的更小。表9 分別給出了AdaptNNS 方法和Baseline 方法在不同召回率下平均訪問的點的數(shù)目，前者相對于后者訪問的點更少，最多可少訪問62%的點。

表8 AdaptNNS 和Baseline 方法設置的DSL 大小與最優(yōu)DSL 大小的差距對比Table 8 Comparison of difference between the DSL size set by AdaptNNS or Baseline methods and the optimal DSL size

表9 AdaptNNS 和Baseline 方法的平均訪問點數(shù)對比Table 9 Comparison of the average number of points accessed by AdaptNNS and Baseline methods

根據(jù)文獻［16］，使用不同的K值（對應召回率Recall@K中的K）大小來控制近似最近鄰與真實最近鄰的近似程度。若K值越小，則要求搜索結果的近似程度越大。本文使用DiskANN 算法并將K值分別設為1 和10 進行實驗，探究不同近似程度要求對AdaptNNS 性能的影響。K=10 時的實驗結果如圖6 所示，在不同數(shù)據(jù)集上，AdaptNNS 對應的吞吐量高于Baseline 方法，可高出1 倍多；在AdaptNNS與Optimal 情況下的吞吐量最少相差不到1%。結合圖5（a）、圖5（b）、圖5（c）可知，在不同近似程度下（K為1 或10），AdaptNNS 方法的吞吐量均比Baseline 方法高。

圖6 AdaptNNS 方法對吞吐量的影響（K=10）Fig.6 Effect of AdaptNNS method on throughput（K=10）

4 可擴展性分析

AdaptNNS 方法針對4 類ANNS 算法中的基于近鄰圖的ANNS 算法（以DiskANN 和HNSW 為例）而設計，基本原理為：給定目標召回率，結合查詢特征，通過機器學習算法調節(jié)平衡召回率和搜索開銷的相關參數(shù)，使得ANNS 的召回率達到指定目標的前提下提升搜索速度。如1.2 節(jié)所述，基于近鄰圖的ANNS 算法中都需要將DSL 大小作為參數(shù)，該參數(shù)平衡搜索召回率和開銷，由機器學習算法調節(jié)。AdaptNNS 方法框架同樣適用于其他3 類ANNS 算法，具體如下：基于量化的ANNS 算法將向量進行壓縮編碼，編碼長度越短搜索越快，但是精度越低；基于局部敏感性哈希的ANNS 算法將被檢索向量進行分桶，分桶粒度越大搜索越快，但精度越低；基于樹的ANNS 算法在搜索時允許回溯、遍歷樹的不同分支，最大回溯次數(shù)越少搜索越快，但精度越低。因此，可以利用機器學習算法動態(tài)設置相關參數(shù)（如編碼長度、分桶粒度、最大回溯次數(shù)），使得ANNS 達到指定召回率的同時提升搜索速度。

5 結束語

為優(yōu)化現(xiàn)有基于近鄰圖的ANNS 算法的參數(shù)設置，本文提出一種搜索參數(shù)自適應的方法AdaptNNS，根據(jù)查詢負載的特征以及目標召回率自適應調整DSL 大小。使用DiskANN 和HNSW 算法在3 個數(shù)據(jù)集上進行實驗，結果表明在相同目標召回率下，AdaptNNS 方法的吞吐量比Baseline 方法的吞吐量最高提升了1.3 倍，與Optimal 情況下的吞吐量最少相差不到1%。下一步擬將AdaptNNS 方法應用于更多的基于近鄰圖的ANNS 算法，以驗證AdaptNNS 方法的通用性，并嘗試使用模型預測基于近鄰圖的ANNS 算法的搜索入口點、最大搜索深度等參數(shù)，進一步提升ANNS 算法的搜索效率。