基于k-means 特征的適應(yīng)性近似最近鄰搜索算法

胡文潔， 楊凱祥， 譚宗元

（東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 上海 201620）

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，文字、圖片和視頻等信息呈指數(shù)式增長(zhǎng)，給信息檢索帶來(lái)了巨大的挑戰(zhàn)。 最近鄰檢索問題最早采用暴力搜索的方式，而暴力搜索通常采用線性掃描的方式，即計(jì)算目標(biāo)點(diǎn)與每個(gè)數(shù)據(jù)點(diǎn)的相似性，從而返回與目標(biāo)點(diǎn)最相似的結(jié)果。 針對(duì)十億規(guī)模的高維數(shù)據(jù)，線性掃描效率過于低下的問題，研究者們開始研究海量數(shù)據(jù)中近似最近鄰搜索問題，力求在數(shù)據(jù)集龐大的條件下，返回與目標(biāo)最相似的K個(gè)鄰居。 近似最近鄰搜索在信息檢索、人臉識(shí)別、文件檢索、推薦系統(tǒng)等方面發(fā)揮著重要作用。

面對(duì)大規(guī)模的高維數(shù)據(jù)，近似最近鄰搜索算法主要解決兩個(gè)問題：降低內(nèi)存占用和加快搜索時(shí)間。在降低內(nèi)存占用方面，近似最近鄰采用量化技術(shù)，將原始數(shù)據(jù)壓縮為二進(jìn)制編碼進(jìn)行存儲(chǔ)，很大程度上降低了內(nèi)存開銷，其代表性算法包括乘積量化算法［1］、優(yōu)化的乘積量化算法［2］和加和量化算法［3］。在加快搜索時(shí)間方面，近似最近鄰搜索領(lǐng)域最常采用的解決措施是對(duì)數(shù)據(jù)構(gòu)建索引，使用不同的方法對(duì)數(shù)據(jù)進(jìn)行劃分，在查找目標(biāo)數(shù)據(jù)的最近鄰時(shí)，僅僅搜索與目標(biāo)數(shù)據(jù)最接近的一類數(shù)據(jù)，減少了數(shù)據(jù)的比對(duì)個(gè)數(shù)，降低了查詢時(shí)間。 其中，基于向量量化的近似最近鄰搜索算法［1-4］，根據(jù)數(shù)據(jù)構(gòu)建倒排索引；而基于近鄰圖的近似最近鄰搜索算法，是對(duì)數(shù)據(jù)構(gòu)建圖索引［5-6］。

目前，在根據(jù)索引搜索目標(biāo)數(shù)據(jù)的最近鄰算法中，通常只搜索固定的粗聚類或者固定的數(shù)據(jù)點(diǎn)，這會(huì)導(dǎo)致搜索訪問不必要的數(shù)據(jù)點(diǎn)。 因此，本文在IVF-HNSW 算法的基礎(chǔ)上，結(jié)合數(shù)據(jù)的k-means 特征，動(dòng)態(tài)預(yù)測(cè)每個(gè)查詢點(diǎn)需要搜索的粗聚類中心的個(gè)數(shù)，降低了查找次數(shù)以及查詢點(diǎn)平均的搜索時(shí)間。

1 相關(guān)工作

1.1 相關(guān)定義

最近鄰搜索將若干個(gè)數(shù)據(jù)點(diǎn)與給定目標(biāo)進(jìn)行匹配，并返回距離目標(biāo)最近的數(shù)據(jù)點(diǎn)。 當(dāng)計(jì)算目標(biāo)向量和數(shù)據(jù)集向量間的距離時(shí)，常用的指標(biāo)包括余弦相似度、漢明距離和歐式距離。 其中，歐式距離使用向量間的絕對(duì)距離表示兩者的遠(yuǎn)近程度。 本文研究中，采用歐式距離計(jì)算向量間的距離。 歐式距離定義為：在n維空間中，給定數(shù)據(jù)集中任意一條向量x＝（x1，x2，…，xn） 和目標(biāo)向量y＝（y1，y2，…，yn），向量x和向量y間的距離計(jì)算如式（1）：

歐式距離的值越小，表示兩向量越近；反之，說明兩向量距離越遠(yuǎn)。

最近鄰搜索針對(duì)目標(biāo)數(shù)據(jù)返回精確的搜索結(jié)果。 但是當(dāng)數(shù)據(jù)量增加到百萬(wàn)甚至十億規(guī)模并且維度上升到成百上千，精確的最近鄰查找的代價(jià)非常高，于是在搜索時(shí)，犧牲可接受搜索精度范圍內(nèi)提高搜索的準(zhǔn)確率，返回與目標(biāo)數(shù)據(jù)最相似的K個(gè)最近鄰，即近似最近鄰搜索。 近似最近鄰搜索可定義為：

在D維空間中，給定包含N條向量的數(shù)據(jù)集合B＝｛b1，b2，…，bn｝ 和目標(biāo)數(shù)據(jù)t， 并確定返回最近鄰的個(gè)數(shù)（K值），則近似最近鄰搜索根據(jù)距離函數(shù)d（t，b），返回目標(biāo)數(shù)據(jù)t在數(shù)據(jù)集合B中的K個(gè)最近鄰，即：

適應(yīng)性搜索指給定一個(gè)查詢點(diǎn)，利用數(shù)據(jù)點(diǎn)的k-means 特征和回歸模型，預(yù)測(cè)其終止條件為τ，則此查詢點(diǎn)僅搜索τ個(gè)粗聚中心或者τ個(gè)候選節(jié)點(diǎn)。

1.2 近似最近鄰搜索

目前主流的近似最近鄰搜索方法包括基于哈希的近似最近鄰快速查找技術(shù)、基于樹的最近鄰搜索方法、基于向量量化的最近鄰搜索和基于圖的最近鄰搜索等。

基于樹的搜索方法以KD-樹［7］為代表。 KD-樹首先會(huì)選取數(shù)據(jù)各維度中方差最大的維度p； 其次以維度p為基準(zhǔn)對(duì)數(shù)據(jù)排序，選取位于中位數(shù)的數(shù)據(jù)點(diǎn)b；最后將數(shù)據(jù)點(diǎn)b作為閾值，則全部數(shù)據(jù)點(diǎn)被分為兩部分。 將數(shù)據(jù)點(diǎn)b作為根節(jié)點(diǎn)，兩部分?jǐn)?shù)據(jù)分別作為其左右子樹，并遞歸將其左右子樹展開，最終將全部數(shù)據(jù)構(gòu)建為一顆索引樹。 在查詢目標(biāo)數(shù)據(jù)的最近鄰時(shí)，根據(jù)二分搜索，查找左子樹或右子樹，直到搜索到葉子節(jié)點(diǎn)，返回目標(biāo)數(shù)據(jù)的最近鄰。

基于哈希的近似最近鄰查找算法中，局部敏感哈希（LSH）［8］占據(jù)重要地位，其主要思想是利用哈希函數(shù)簇，將原始數(shù)據(jù)映射到低維空間，經(jīng)過哈希函數(shù)簇之后，原始空間中相似的兩條數(shù)據(jù)以更大的概率被分配在同一個(gè)桶中；反之，不相似的兩條數(shù)據(jù)被分配在不同的桶中，并建立桶編號(hào)和數(shù)據(jù)點(diǎn)的索引關(guān)系。 在查找目標(biāo)數(shù)據(jù)的最近鄰時(shí)，利用哈希函數(shù)簇對(duì)目標(biāo)數(shù)據(jù)進(jìn)行哈希，并計(jì)算目標(biāo)數(shù)據(jù)和其對(duì)應(yīng)的桶中的全部數(shù)據(jù)的距離，返回最近鄰。

基于向量量化的方法，以乘積量化（PQ）［1］為代表。 乘積量化的思想是對(duì)高維數(shù)據(jù)進(jìn)行正交分解，將高維特征空間劃分為M個(gè)低維子空間，在每一個(gè)低維子空間中運(yùn)用k-means 方法對(duì)所有的數(shù)據(jù)進(jìn)行聚類，并對(duì)聚類中心進(jìn)行編碼，每個(gè)數(shù)據(jù)用其對(duì)應(yīng)聚類中心的編碼表示。 在查詢過程中，使用ADC 方法計(jì)算目標(biāo)向量與數(shù)據(jù)庫(kù)向量間的距離，并利用lookups 表存儲(chǔ)查詢向量的每一段子向量到各編碼的距離，通過lookups 表查詢M段距離并進(jìn)行加和，最終將距離排序，返回目標(biāo)向量的最近鄰。

在十億規(guī)模的數(shù)據(jù)集上，原有的ADC 方式雖然加快了查詢時(shí)間，但仍然是線性掃描，耗時(shí)較多，因此Jegou 等人提出結(jié)合倒排索引系統(tǒng)［4］進(jìn)行搜索。倒排索引首先使用k-means 方法對(duì)所有的數(shù)據(jù)進(jìn)行粗聚類，并計(jì)算每個(gè)數(shù)據(jù)的殘差，即原始數(shù)據(jù)和對(duì)應(yīng)粗聚類中心的差值，之后再使用乘積量化算法對(duì)所有殘差進(jìn)行量化。 最終每一類建立一個(gè)倒排列表，倒排列表中存儲(chǔ)該類中所有數(shù)據(jù)的id 和PQ 量化的結(jié)果。 在查詢向量搜索最近鄰的過程中與所有的粗聚類中心計(jì)算距離，并選取w個(gè)距離最近的粗聚類中心，從w個(gè)類中包含的所有數(shù)據(jù)點(diǎn)中選取最近鄰。

基于圖的方法，代表性的方法為分層可導(dǎo)航小世界（HNSW）［7］，其做法如下：在構(gòu)建圖索引的過程中，當(dāng)插入一個(gè)新數(shù)據(jù)點(diǎn)時(shí)，計(jì)算新數(shù)據(jù)點(diǎn)插入的層數(shù)l，將其插入到0-l層，并在每一層選取新數(shù)據(jù)點(diǎn)的m個(gè)最近鄰并連接，直到數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)全部插入圖索引，則多層索引構(gòu)建完成。 查詢向量搜索最近鄰時(shí)，從最上層的入口點(diǎn)開始，計(jì)算其在當(dāng)前層最近的鄰居，并將其作為下層搜索的起始點(diǎn)。 當(dāng)搜索到最底層時(shí)，構(gòu)建長(zhǎng)度為w的優(yōu)先隊(duì)列，用于存儲(chǔ)候選節(jié)點(diǎn)。 查詢向量在優(yōu)先隊(duì)列中進(jìn)行精確的查找，返回其最近鄰。

1.3 IVF-HNSW 算法

IVF-HNSW 算法針對(duì)十億規(guī)模數(shù)據(jù)集，結(jié)合倒排索引和圖索引，實(shí)現(xiàn)了更細(xì)粒度的劃分。 一方面，IVF-HNSW 算法將聚類得到的區(qū)域劃分為更小的區(qū)域；另一方面，在查找最近鄰時(shí)，利用剪枝策略過濾部分?jǐn)?shù)據(jù)點(diǎn)，加快了檢索速度。 具體實(shí)現(xiàn)過程如下：

在構(gòu)建倒排索引的過程中，首先將整個(gè)空間劃分為若干個(gè)區(qū)域，并計(jì)算每個(gè)區(qū)域的粗聚類中心（質(zhì)心）。 在每個(gè)區(qū)域中再次進(jìn)行劃分，與普通的劃分方式不同的是，IVF-HNSW 算法采用凸組合的形式表示子質(zhì)心，即每個(gè)區(qū)域的子質(zhì)心由質(zhì)心和此質(zhì)心相鄰的L個(gè)最近質(zhì)心的凸組合表示。 凸組合形式的優(yōu)勢(shì)在于不需要存儲(chǔ)碼本，節(jié)省了內(nèi)存空間的占用。 其次每條數(shù)據(jù)庫(kù)向量被量化到最近的子質(zhì)心后，計(jì)算其殘差，即原始向量和其對(duì)應(yīng)子質(zhì)心的差值，并利用乘積量化算法對(duì)殘差進(jìn)行編碼。 最后建立倒排索引，鍵為質(zhì)心，值為質(zhì)心對(duì)應(yīng)區(qū)域中包含的數(shù)據(jù)點(diǎn)，并且同一個(gè)子區(qū)域中的數(shù)據(jù)排列在一起。

在查詢向量搜索最近鄰的過程中，數(shù)據(jù)集的規(guī)模導(dǎo)致查詢向量搜索質(zhì)心的效率低下，因此IVFHNSW 算法選擇對(duì)質(zhì)心構(gòu)建HNSW 索引，用于快速查找最近的質(zhì)心。 搜索到最近的質(zhì)心S后，查詢向量和質(zhì)心S中包含的子質(zhì)心計(jì)算距離，并計(jì)算距離的均值E，當(dāng)查詢向量和子質(zhì)心的距離大于距離E時(shí)，則跳過對(duì)應(yīng)的子區(qū)域，過濾不可能成為最近鄰的數(shù)據(jù)點(diǎn)；當(dāng)查詢向量和子質(zhì)心的距離小于或等于距離E時(shí)，則在對(duì)應(yīng)的子區(qū)域中進(jìn)行搜索，即計(jì)算查詢向量的殘差，并利用ADC 的方式計(jì)算查詢向量和已壓縮向量的距離，將距離排序，最終返回查詢向量的最近鄰。

2 自適應(yīng)的提前終止查詢算法

本文通過分析固定的終止條件對(duì)近似最近鄰搜索算法產(chǎn)生的影響，在查詢階段將原始的IVFHNSW 算法和基于k-means 特征的提前終止算法相結(jié)合，使得每個(gè)查詢點(diǎn)進(jìn)行適應(yīng)性搜索，優(yōu)化了查詢過程，并在sift 和deep 數(shù)據(jù)集上通過實(shí)驗(yàn)進(jìn)行證明。

2.1 問題分析

基于倒排索引結(jié)構(gòu)的近似最近鄰搜索算法（如IVFADC 算法等），通常使用固定的搜索終止條件（如Nprobe），Nprobe 指每個(gè)查詢點(diǎn)所需要搜索的粗聚類中心的數(shù)量。 基于圖索引的搜索算法（如HNSW 算法），通常也使用固定的搜索終止條件（如Efsearch）。 Efsearch 參數(shù)指圖索引的0 層使用長(zhǎng)度為efsearch 的優(yōu)先隊(duì)列，用于存儲(chǔ)候選節(jié)點(diǎn)，每個(gè)查詢點(diǎn)在優(yōu)先隊(duì)列中進(jìn)行精確的搜索。 因此終止條件（即nprobe 和efsearch）的設(shè)置，是影響搜索準(zhǔn)確度的關(guān)鍵指標(biāo)。 隨著終止條件的增大，查詢點(diǎn)需要搜索數(shù)據(jù)點(diǎn)的個(gè)數(shù)增多，則搜索準(zhǔn)確度越高，花費(fèi)的搜索時(shí)間也越長(zhǎng)；反之，雖然搜索時(shí)間較少，但搜索準(zhǔn)確度會(huì)逐漸降低。

在實(shí)際搜索過程中，存在每個(gè)查詢點(diǎn)終止條件不同的情況，即有些查詢點(diǎn)只需要很小的終止條件α1就可以檢索到最近鄰，而一些查詢點(diǎn)需要更大的終止條件α2才能搜索到最近鄰，其中α2＞α1。 對(duì)于這種情況，為了滿足搜索精度的要求，終止條件的設(shè)置需要保證絕大部分查詢點(diǎn)搜索到最近鄰，即終止條件大于α2。 由于所有的查詢點(diǎn)使用相同的終止條件，則導(dǎo)致“容易”搜索到最近鄰的查詢點(diǎn)花費(fèi)時(shí)間搜索不必要的數(shù)據(jù)點(diǎn)，造成了平均搜索時(shí)間升高的問題。

由于IVF-HNSW 算法在查詢階段使用固定的終止條件進(jìn)行搜索，因此本文采用k-means 特征，動(dòng)態(tài)預(yù)測(cè)每個(gè)查詢點(diǎn)的終止條件，并使得每個(gè)查詢點(diǎn)在對(duì)應(yīng)的終止條件下停止搜索，實(shí)現(xiàn)了適應(yīng)性搜索，降低了平均查詢時(shí)間。

2.2 算法實(shí)現(xiàn)

本文在IVF-HNSW 算法上的優(yōu)化包括以下步驟：收集數(shù)據(jù)集的特征、訓(xùn)練模型、預(yù)測(cè)查詢點(diǎn)的停止條件、建立IVF-HNSW 索引并整合模型。

2.2.1 收集數(shù)據(jù)集的特征

數(shù)據(jù)集特征包括訓(xùn)練集的輸入特征和輸出特征兩部分。 輸入特征表示訓(xùn)練集中每個(gè)數(shù)據(jù)點(diǎn)的kmeans 特征，輸出特征指訓(xùn)練集中每個(gè)數(shù)據(jù)點(diǎn)在IVF-HNSW 算法中真實(shí)的停止條件。 收集k-means特征首先利用k-means 方法，將訓(xùn)練集聚到一萬(wàn)個(gè)類聚類中心，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)最近的50 個(gè)聚類中心。 選取特征見表1。

其中，t表示訓(xùn)練集中任一數(shù)據(jù)點(diǎn)，dist（t，ith nearest coarse cluster centroid）表示數(shù)據(jù)點(diǎn)和其第i個(gè)聚類中心的距離，因此選取的特征共10 個(gè)，包括數(shù)據(jù)點(diǎn)到其第5、10、15 等聚類中心與數(shù)據(jù)點(diǎn)到最近的聚類中心的距離的比值。

收集輸出特征是在查找過程中，判斷每個(gè)數(shù)據(jù)點(diǎn)是否搜索到其真實(shí)最近鄰，如果搜索到真實(shí)最近鄰，則記錄搜索的倒排列表的個(gè)數(shù)。 由于數(shù)據(jù)庫(kù)向量中存在重復(fù)的向量，因此每個(gè)數(shù)據(jù)點(diǎn)可能會(huì)有多個(gè)距離相同的真實(shí)最近鄰，于是在收集輸出特征的過程中，只要數(shù)據(jù)點(diǎn)搜索到其真實(shí)最近鄰中的一個(gè)，則認(rèn)為此數(shù)據(jù)點(diǎn)搜索到真實(shí)最近鄰并記錄下最小訪問點(diǎn)的個(gè)數(shù)。

2.2.2 訓(xùn)練模型

將每個(gè)數(shù)據(jù)點(diǎn)的k-means 特征作為輸入，對(duì)應(yīng)的真實(shí)停止條件作為輸出，選擇神經(jīng)網(wǎng)絡(luò)模型對(duì)數(shù)據(jù)進(jìn)行回歸擬合。 神經(jīng)網(wǎng)絡(luò)回歸模型的輸入層為數(shù)據(jù)的10 個(gè)k-means 特征；隱藏層的個(gè)數(shù)為2，其神經(jīng)元個(gè)數(shù)設(shè)置為100；輸出層個(gè)數(shù)為1，即神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)的數(shù)據(jù)點(diǎn)的終止條件。 當(dāng)訓(xùn)練次數(shù)為50 次時(shí)，模型訓(xùn)練完成。

2.2.3 預(yù)測(cè)查詢點(diǎn)的停止條件

首先收集查詢集中每個(gè)查詢點(diǎn)的k-means 特征，計(jì)算每個(gè)查詢點(diǎn)的110 個(gè)聚類中心，選取查詢點(diǎn)到其最近的聚類中心的距離和查詢點(diǎn)到其第5、10、15 等聚類中心的距離的比值，作為10 個(gè)k-means特征。 查詢點(diǎn)的k-means 特征作為神經(jīng)網(wǎng)絡(luò)回歸模型的輸入，預(yù)測(cè)其終止條件，即需要搜索的倒排列表的個(gè)數(shù)和候選節(jié)點(diǎn)的個(gè)數(shù)。

2.2.4 建立IVF-HNSW 索引并進(jìn)行適應(yīng)性搜索

將訓(xùn)練集聚類到一百萬(wàn)個(gè)粗聚類中心后，建立相應(yīng)的倒排索引并根據(jù)粗聚類中心建立HNSW 索引。 在IVF-HNSW 索引的基礎(chǔ)上，加載每個(gè)查詢點(diǎn)的停止條件，并將nprobe 和efsearch 參數(shù)設(shè)置為對(duì)應(yīng)的終止條件，保證每個(gè)查詢點(diǎn)進(jìn)行適應(yīng)性搜索。

3 實(shí)驗(yàn)

本文采用sift1B、deep1B 以及spacev1B 3 個(gè)公開的數(shù)據(jù)集。 每個(gè)數(shù)據(jù)集包括3 部分：數(shù)據(jù)集、訓(xùn)練集和查詢集。 訓(xùn)練集用于訓(xùn)練回歸模型，數(shù)據(jù)集和查詢集用于評(píng)估最近鄰搜索的準(zhǔn)確度。 spacev1B 數(shù)據(jù)集包含的訓(xùn)練集是從數(shù)據(jù)庫(kù)集中切分的一千萬(wàn)條向量，所以數(shù)據(jù)庫(kù)集僅包含九億九千萬(wàn)條向量。 有關(guān)數(shù)據(jù)集的詳情見表2。

表2 數(shù)據(jù)集Tab. 2 Datasets

SIFT 數(shù)據(jù)集是從圖像中提取的局部特征描述符，每張圖片的描述符組成128 維的特征向量，其中每個(gè)坐標(biāo)為0 ～128 的整數(shù)；DEEP 數(shù)據(jù)集是由自然圖像經(jīng)過CNN 后生成的96 維特征向量，其中每個(gè)坐標(biāo)的取值范圍為-1 ～1 的浮點(diǎn)數(shù)；SPACEV 數(shù)據(jù)集是微軟必應(yīng)最先發(fā)布的數(shù)據(jù)集，由Microsoft SpaceV 模型生成的數(shù)據(jù)庫(kù)向量和查詢向量，其中每條向量的維度為100 維，每個(gè)坐標(biāo)的取值范圍為-128～128 的整數(shù)。

本文采用召回率recall1＠100 衡量搜索最近鄰的準(zhǔn)確度，即搜索結(jié)果的第1 最近鄰在其前100 個(gè)真實(shí)最近鄰中的查詢點(diǎn)個(gè)數(shù)占所有查詢點(diǎn)個(gè)數(shù)的比例。 召回率越高，表示搜索的準(zhǔn)確度越高。 在比較原始的IVF-HNSW 算法和本文優(yōu)化的算法時(shí)，采用控制變量法，即達(dá)到相同的召回率時(shí)，對(duì)比兩種算法的平均查詢時(shí)間。 在相同的召回率下，平均查詢時(shí)間越短，證明算法的性能越好。

原始的IVF-HNSW 算法和本文優(yōu)化的自適應(yīng)搜索算法在sift1B、deep1B 和spacev1B 3 個(gè)數(shù)據(jù)集上得到的實(shí)驗(yàn)結(jié)果如圖1 ～圖3 所示。 其中縱軸表示算法達(dá)到的召回率recall1＠100，橫軸表示在對(duì)應(yīng)的召回率下，算法對(duì)于所有查詢點(diǎn)的平均查詢時(shí)間（以ms 為單位）。 藍(lán)色的實(shí)線表示基準(zhǔn)的IVFHNSW 算法，紅色的實(shí)線表示基于IVF-HNSW 算法的自適應(yīng)搜索算法。

圖1 平均查詢時(shí)間-召回率（SIFT1B）Fig. 1 Average query time-Recall （SIFT1B）

圖2 平均查詢時(shí)間-召回率（DEEP1B）Fig. 2 Average query time-Recall （DEEP1B）

圖3 平均查詢時(shí)間-召回率（SPACEV1B）Fig. 3 Average query time-Recall （SPACEV1B）

從中可以看出，自適應(yīng)搜索算法在低召回率和高召回率下的平均查詢時(shí)間均低于IVF-HNSW 算法，并且隨著召回率的升高，減少的查詢時(shí)間越多。在SIFT1B 數(shù)據(jù)集上，當(dāng)兩種算法的搜索準(zhǔn)確度都達(dá)到最高召回率0.958 6 時(shí)，IVF-HNSW 算法的平均查詢時(shí)間為6.03 ms，而自適應(yīng)搜索算法的平均查詢時(shí)間為5.15 ms，在原始算法的基礎(chǔ)上降低了14.6%；當(dāng)兩種算法的召回率為0.95 時(shí)，基準(zhǔn)算法的平均查詢時(shí)間為3.78 ms，而自適應(yīng)搜索算法的平均查詢時(shí)間為2.52 ms，下降了33%。 結(jié)果表明，在SIFT 數(shù)據(jù)集上，高召回率下的時(shí)間下降更多。

然而在DEEP1B 數(shù)據(jù)集上，兩種算法達(dá)到最高召回率0.948 9 時(shí)，IVF-HNSW 算法的平均查詢時(shí)間為5.13 ms，而自適應(yīng)優(yōu)化算法的平均查詢時(shí)間為3.75 ms，降低了27%；在召回率0.90 下，IVF-HNSW算法的平均查詢時(shí)間為1.94 ms；而自適應(yīng)優(yōu)化算法的平均查詢時(shí)間為1.52 ms，降低了21%。 說明隨著召回率的升高，平均查詢時(shí)間在原始IVF-HNSW 算法的基礎(chǔ)上下降的幅度更大。

對(duì)于SPACEV1B 數(shù)據(jù)集，在低召回率下兩者沒有區(qū)別，但是在最高召回率0.956 6的情況下，平均查詢時(shí)間從17.42 ms 降低到15.25 ms，降低了12.5%，說明自適應(yīng)算法在高召回率下具有更高的優(yōu)勢(shì)。

從實(shí)驗(yàn)結(jié)果分析可以看出，本文優(yōu)化后的自適應(yīng)搜索算法的性能全面高于原始的IVF-HNSW 算法，在相同的召回率下，進(jìn)一步降低了平均查詢時(shí)間。 由于不同數(shù)據(jù)集生成特征向量的方式不同，所以同一種算法在不同的數(shù)據(jù)集上表現(xiàn)不同。 在sift數(shù)據(jù)集上，自適應(yīng)搜索算法在低召回率上更有優(yōu)勢(shì)；在deep 數(shù)據(jù)集的高召回率下，查詢時(shí)間下降的百分比更多；在spacev 數(shù)據(jù)集上，自適應(yīng)算法在低召回率下的表現(xiàn)幾乎和原始的IVF-HNSW 算法重合，但是在高召回率下的查詢時(shí)間有很大程度的降低。

4 結(jié)束語(yǔ)

本文在IVF-HNSW 算法的基礎(chǔ)上，建立并訓(xùn)練神經(jīng)網(wǎng)絡(luò)回歸模型，利用數(shù)據(jù)的k-means 特征預(yù)測(cè)每個(gè)查詢點(diǎn)的終止條件，進(jìn)而實(shí)現(xiàn)適應(yīng)性搜索。 實(shí)驗(yàn)結(jié)果表明本文優(yōu)化后的算法進(jìn)一步降低了近似最近鄰搜索算法在十億規(guī)模上的搜索時(shí)間，使得近似最近鄰搜索算法以更低的平均查詢時(shí)間達(dá)到了相同的準(zhǔn)確度。