參數(shù)自適應(yīng)下基于近鄰圖的近似最近鄰搜索

甘紅楠，張 凱

（1.復(fù)旦大學(xué) 軟件學(xué)院，上海 200438；2.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200438）

0 概述

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

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

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

1 近似最近鄰搜索

1.1 相關(guān)定義

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

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

召回率是衡量ANNS 結(jié)果相關(guān)性的指標(biāo)。最近鄰搜索通常要求返回K個(gè)最近鄰。Recall@K是搜索K個(gè)最近鄰時(shí)的召回率。召回率越高，返回結(jié)果與真實(shí)結(jié)果越接近。

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

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

1.2 基于近鄰圖的ANNS 算法

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

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

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

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

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

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

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

2.1.1 參數(shù)設(shè)置

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

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

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

圖2 近鄰圖實(shí)例Fig.2 Example of neighbor graph

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

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

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

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

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

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

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

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

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

為達(dá)到同一個(gè)召回率目標(biāo)，處理不同的查詢集合需要不同的DSL 大小。不同查詢集合中查詢的最近鄰答案與入口點(diǎn)之間的搜索路徑長度不同。因此，為搜索到相同比例的最近鄰答案，最近鄰答案與入口點(diǎn)之間距離遠(yuǎn)的查詢集合在進(jìn)行查詢時(shí)需要更大DSL。

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

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

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

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

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

2.2 AdaptNNS 方法

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

2.2.1 模型選擇

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

2.2.2 特征構(gòu)建

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

1）最近鄰分類器查詢

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

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

2）模型特征構(gòu)建

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

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

2.2.3 模型訓(xùn)練

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

表6 實(shí)驗(yàn)數(shù)據(jù)集Table 6 Experimental dataset

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

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

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

3.2 性能評(píng)估

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

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

表8 AdaptNNS 和Baseline 方法設(shè)置的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 方法的平均訪問點(diǎn)數(shù)對比Table 9 Comparison of the average number of points accessed by AdaptNNS and Baseline methods

根據(jù)文獻(xiàn)［16］，使用不同的K值（對應(yīng)召回率Recall@K中的K）大小來控制近似最近鄰與真實(shí)最近鄰的近似程度。若K值越小，則要求搜索結(jié)果的近似程度越大。本文使用DiskANN 算法并將K值分別設(shè)為1 和10 進(jìn)行實(shí)驗(yàn)，探究不同近似程度要求對AdaptNNS 性能的影響。K=10 時(shí)的實(shí)驗(yàn)結(jié)果如圖6 所示，在不同數(shù)據(jù)集上，AdaptNNS 對應(yīng)的吞吐量高于Baseline 方法，可高出1 倍多；在AdaptNNS與Optimal 情況下的吞吐量最少相差不到1%。結(jié)合圖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 可擴(kuò)展性分析

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

5 結(jié)束語

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