基于提前終止的近似最近鄰搜索算法

王執政，楊凱祥，譚宗元

（東華大學 計算機科學與技術學院，上海 201620）

0 引 言

隨著計算機技術的飛速發展，當今社會已經進入互聯網大數據時代。當前的數據量巨大、數據維度之高，給信息檢索帶來極大挑戰。最近鄰搜索是信息檢索的重要技術，已經在數據庫、人工智能、圖像搜索等領域廣泛應用，其最原始的方法是對數據庫中的所有點進行一一比對，找到最近的鄰居，然而這種方法只適應于數據量非常小的情況，對于大數據集查詢時間較長，無法滿足應用需求。近似最近鄰搜索成為主流，其主要思想在犧牲較小的查詢精度情況下，減少查詢時間、提高查詢效率?；趫D的搜索算法是當前近鄰搜索算法中最受關注的，已經被很多大型商業公司廣泛應用。

基于圖的近似最近鄰搜索算法使用的是近似k近鄰圖，其主要思想是將數據集的每個向量通過計算歐氏距離得到k個鄰居，通過鄰居關系建立圖索引結構，并在建立的索引的基礎上進行查詢［1］。該算法一方面使每個點只連接幾個鄰居，極大的減少了索引的內存；另一方面，通過此圖索引可以很快定位到查詢點的鄰居附近，實現快速查詢。近年來，基于圖的算法取得了很大的進步，該算法是目前查詢速度最快，查詢精度最高的近似最近鄰搜索算法。

本文通過對基于圖的搜索算法查詢階段的分析，將自適應的提前終止算法與Link and Code（L＆C）算法進行結合，對L＆C 算法的查詢階段進行改進。實驗結果表明，與原始L＆C 結果相比，在GIST 數據集上平均查詢時間最大減少76%。

1 相關工作

1.1 相關定義

最近鄰搜索離不開距離的計算，距離越小的兩個向量越相似。目前常用的度量標準有余弦距離、歐幾里得距離（歐氏距離）和漢明距離等，本文采用歐氏距離作為標準，衡量兩個向量之間的遠近關系。

定義1（歐氏距離）在n維歐式空間Rn中，向量a＝(a1，a2，…，an) 是其中的一個點，ai（i＝1，2，…，n）為a的第i個坐標值，則歐式空間中向量a＝(a1，a2，…，an)、向量b＝(b1，b2，…，bn)的距離d(a，b) 定義為式（1）：

定義2（K－最近鄰搜索）Y＝｛y1，y2，…，yN｝∈Rd表示d維歐式空間中的一個集合（包含N個向量），該空間中的一個查詢向量q（q∈Rd），對于一個整數值K，滿足K≤N，通過近似最近鄰搜索算法在Y中搜索到q的K個鄰居，根據定義1 的距離函數d(q，y)，得到K個最近鄰的公式（2），返回大小為＝K的向量集合TopK?Y，同時對?yq∈TopK和yi∈Y－ TopK，總 有d(q，yq) ≤d(q，yi) 。

定義2 是目前基于圖索引的搜索算法常用的結果表示，查詢點q經過搜索返回的K個最近鄰居的結果示意，如圖1 所示。

圖1 K－最近鄰搜索結果示意Fig.1 K－nearest neighbor search result show

1.2 近似最近鄰搜索算法

近似最近鄰搜索算法主要分為以下幾類：基于空間劃分的算法、基于哈希的算法、基于量化的算法和基于圖的算法。

基于空間劃分的方法主要是指基于樹的方法，是最近鄰搜索的一類經典算法。主要思想：在高維數據的某一維度上，選擇該維度的中位數進行劃分，數據集上的其他向量在該維度上與此中位數進行比較，這樣就可以把數據集劃分為左子樹和右子樹，每次選擇一個維度迭代遞歸多次進行劃分，最終生成一個樹索引［2］。查找時對于給定查詢點，從根節點開始，最終定位到葉子節點，返回查詢點的最近鄰居。

基于哈希的方法的主要思想：原始空間距離較近的兩個點，映射到另一個空間很可能仍然相鄰［3］。該類算法將數據集通過哈希函數映射，得到多個桶，每個桶中有若干個數據點，此時建立哈希索引，查詢時同樣對查詢點進行映射，得到映射后所在的桶，在該桶中進行歐氏距離比較，得到最近鄰。

基于量化的方法最開始是信號論領域的方法，對信號進行量化處理。目前計算機領域使用較多的是乘積量化的方法，可以有效減少內存占用。乘積量化的思想主要是將高維向量進行分段，在每一段所在的子空間中聚類，在同一子空間中的向量都可以使用聚類后的質心代替，同時對質心編碼，這樣所有的向量都可以使用編碼的質心組合表示，極大的減少了占用內存［4］。查詢之前，會預先計算一個預計算表，查詢點到來時，直接查表可快速得到結果，但由于量化誤差，查詢精度會降低。

基于圖的近似最近鄰搜索，使用近似k近鄰圖表示圖之間的一種近鄰關系，這種關系通過歐式距離確定，該算法目標是建立一個圖索引結構，通過該索引結構可以很快地定位到查詢點的鄰居附近，從而實現快速搜索。

近年來，比較高效的算法有HNSW 算法和NSG算法等，目標是建立占用內存較小、同時搜索時間較短且查詢準確度較高的索引。HNSW 算法是分層可導航小世界算法，該算法采用分層的方式，每一層是一個索引圖，分層結構提供了出色的性能，復雜度為對數級別［5］。查詢過程從頂層開始，依次向下查找，可以快速準確定位到查詢點的最近鄰附近；NSG是查詢導向拓展圖算法，算法從圖構建的連通性、平均出度、路徑長度等幾個方面入手，通過綜合考慮這些因素，得出一種高效的圖剪枝策略，索引的復雜度大大降低，同時該算法使用數據集的近似中心作為導航節點，對于搜索帶有導向作用，同時搜索從該節點開始，可實現快速查詢［6］。

盡管以上兩種算法查詢時間快且精度高，但對于大數據集，其索引結構占用內存較大，一臺內存有限的服務器無法滿足實驗。Link and Code（L＆C）算法結合基于圖的算法和量化編碼兩種算法的優勢，在HNSW 算法的基礎上，對原始的數據庫向量編碼存儲，極大減少了索引內存［7］。同時，該算法為了減少編碼量化誤差，使用一組量化回歸系數改進向量近似表示的方法，并且對查詢向量的候選列表重新排序，可以提高查詢精度。該算法可以在一臺內存有限制的服務器上實現億級別數據集的實驗。

2 自適應的提前終止查詢算法

基于圖索引結構的搜索算法，工作重點在于構建高質量的圖索引結構進行搜索，如HNSW、NSG 算法構建的索引，查詢速度快、精度高?；趫D的搜索算法有兩個階段：構建索引和查詢。高質量的索引可以提高查詢效率，但查詢方法同樣可以影響查詢效率。本文結合自適應的提前終止查詢與L＆C 算法，對L＆C 索引結構進行分析，對查詢階段進行改進并通過實驗驗證。

2.1 問題分析

很多基于圖的搜索算法在查詢階段使用固定的查詢終止條件進行查詢，當查詢達到這個條件時查詢終止。例如：HNSW 算法會設置固定的查詢輪次（efSearch），該查詢輪次可以認為查詢走過的跳數；在倒排索引算法中，只搜索查詢點的前幾個聚類中心（nprobe），該做法可以減少搜索時間，同時精度損失較小，這些終止條件的大小可以根據精度的要求設置，查詢終止條件越大，搜索時間越長，同時搜索精度也會越高。

但所有的查詢點使用固定的查詢終止條件，會出現這個固定的終止條件對于一些查詢點來說過大的問題，可能較小的終止條件就能滿足查詢精度的需求，這就會產生很多額外的查詢時間，導致最終的查詢時間變長。原因在于設置的查詢終止條件必須滿足絕大部分查詢點在查詢結束時能夠得到對應的精度，才能保證在最終的平均查詢精度達到對應的精度值。這就需要將終止條件變大，此時一些查詢點本來可以很快結束搜索，但最終還是多花費了過多的時間。

通過分析可以看出不同查詢點存在不同的查詢終止條件。由于L＆C 算法與HNSW 算法有類似的索引結構，故本文對L＆C 算法的查詢階段使用提前終止算法進行改進，通過預測得到不同查詢點的終止條件，提高查詢的效率。

2.2 算法實現

本文在L＆C 算法索引上使用自適應的提前終止查詢算法對查詢階段進行改進，通過預測提前終止查詢［8］。該算法主要分為：

（1）特征的選擇：本文對L＆C 圖索引結構進行分析，結合索引的特點，選擇一些特征。選擇查詢點作為一類特征，查詢點的每一維都作為一個特征，查詢過程中的中間搜索結果是一個重要指標，因此選擇中間結果作為另一類特征。

見表1，F1 是特征查詢向量q；F2 表示q與索引結構第0 層的查詢起始點之間的歐氏距離；F3 代表q與經過查詢后得到的最近鄰之間的距離；F4 表示q與經過查詢后得到的第10 個最近鄰居之間的距離；F5是F3與F2 的距離比值；F6 是F4與F2 的比值，其中F3，F4，F5 和F6 中間結果特征。

表1 特征Tab.1 Feature

（2）模型的選擇與訓練：該算法選擇梯度提升決策樹（GBDT）作為訓練和預測的模型。選擇該模型有以下幾點原因：首先，訓練時間短，同時在訓練過程中上一次迭代產生的殘差數據作為特征可以在下一次迭代中繼續使用，使得模型具有一定的反饋調節能力，并且最終的模型所占空間較??；其次，該算法在訓練時，對于小數據集使用該數據集的10%進行訓練，對于上億級別的大數據集使用100 萬大小進行訓練，訓練集超過100 萬訓練時間變長且效果相差不大。訓練的輸入是上述提到的特征，輸出是在L＆C 索引上查詢過程中的最小搜索量，查詢終止條件與該值高度相關。

（3）L＆C 索引上模型的整合與預測：查詢的過程在L＆C 索引結構上，將訓練得到的預測模型加載到該索引上，進行L＆C 索引和預測模型銜接，在搜索過程直接預測，實現查詢點的提前終止查詢。

3 實驗

本文使用4 個公開的數據集進行實驗，分別是ImageNet、SIFT10M、GIST 和DEEP100M 數據集，見表2。

表2 數據集Tab.2 Datasets

搜索算法得到的最近鄰越準確，表明算法越好，衡量標準為召回率，其含義是查找到的精確近鄰個數與實際精確近鄰個數的比值，式（3）：

其中，S是查詢點的精確近鄰集合，S'是算法搜索得到的近鄰集合。

比較不同算法時不僅要求搜索準確，同時要求時間花費較少，可以采用固定召回率比較時間或者固定時間比較召回率兩種方法。

ImageNet、SIFT10M、GIST 和DEEP100M 4 個數據集對應的平均查詢時間和召回率的實驗結果如圖2～5 所示，基準算法對應的是L＆C 算法（圖2～5 中的紫色曲線，baseline），淺藍色曲線（adaptive）是本文在L＆C 算法上使用的自適應提前終止算法的實驗結果。

圖2 平均時間－召回率（ImageNet）Fig.2 Average time－recall（ImageNet）

圖3 平均時間－召回率（SIFT10M）Fig.3 Average time－recall（SIFT10M）

圖4 平均時間－召回率（GIST）Fig.4 Average time－recall（GIST）

圖5 平均時間－召回率（DEEP100M）Fig.5 Average time－recall（DEEP100M）

在ImageNet 數據集上，召回率為0.73 時，基準算法查詢花費時間為3.295 ms，本文在L＆C 上的提前終止查詢花費時間為1.901ms，減少了42%；而當召回率為0.7786時，基準算法花費時間為14.226ms，本文在L＆C 上提前終止查詢時間為6.155 ms，減少了57%，在召回率不斷變大的過程中，減少的時間百分比也在不斷變大。在SIFT10M數據集上，召回率為0.86 和0.87 時，兩種算法的差距不大，但隨著召回率的變大，本文在L＆C 上提前終止查詢的算法優勢越來越明顯，最大減少56%。在GIST 數據集上，本文的實驗效果較好，在召回率較低為0.79 時，減少63%，在召回率為0.84 時，減少百分比最大為76%，在每一個召回率上平均時間減少百分比都比較大，整體效果比較好。在DEEP100M 數據集上，0.92 和0.93 的召回率時，本文的實驗結果優勢不大，但隨著召回率的變大，優勢越來越明顯，召回率為0.968 9 時，平均時間減少71%。

從上述實驗結果分析中，可以看出本文在L＆C索引上的提前終止查詢算法優于原始的L＆C 算法。本文在L＆C 索引上實驗的優勢在高召回率上，召回率越高實驗效果提升越大，隨著召回率升高，兩種算法平均查詢時間的差距越來越大，提升效果越來越好。

4 結束語

目前基于圖的最近鄰搜索算法均使用固定的終止條件，但對于一些查詢點來說，小于這個固定的終止條件就能滿足查詢精度的需求，此時使用這個固定的終止條件會產生很多額外的查詢時間。為了減少額外的查詢時間，本文在L＆C 索引結構上使用了自適應的提前終止查詢算法，對查詢階段的查詢方法進行改進，同時在ImageNet、SIFT10M、GIST 和DEEP100M 4 個數據集上實驗驗證。實驗結果表明，改進后的效果明顯優于L＆C 算法。