摘要

本篇論文來自于 SIGMOD 2023，介紹了一種可靠和有效的距離比較操作的高維近似最近鄰搜索。主要工作1.提出一種隨機(jī)算法 ADSampling; 2.基于 ADSampling ，開發(fā)了兩種算法特定的技術(shù)作為插件來增強(qiáng)現(xiàn)有的 AKNN 算法。

論文背景

提出問題：

在高維空間中，幾乎所有 AKNN 算法的時(shí)間消耗都由距離比較操作（DCOs）所占據(jù)。對(duì)于每個(gè)操作，它掃描一個(gè)對(duì)象的全部維度，因此在維度上運(yùn)行的時(shí)間是線性的。

解決方法：

提出了一種隨機(jī)算法，名為 ADSampling，它在大多數(shù)距離比較操作（DCOs）中運(yùn)行時(shí)間是對(duì)數(shù)級(jí)別，并且具有高概率成功。特點(diǎn)概括起來便是1. 縮短比較時(shí)間；2. 成功率高。

論文主要工作：

（1）提出一種隨機(jī)算法 ADSampling;

（2）基于 ADSampling，我們開發(fā)了兩種算法特定的技術(shù)作為插件來增強(qiáng)現(xiàn)有的AKNN算法。

其中，兩種特定技術(shù)為：HNSW++和 IVF++。

??? HNSW++ 是基于 HNSW 算法的改進(jìn)，通過使用更好的近似距離和更高效的候選生成策略來提高搜索速度。

??? IVF++ 是基于 IVF 算法的改進(jìn)，通過重新組織數(shù)據(jù)布局和調(diào)整維度順序來提高緩存友好性，從而減少內(nèi)存訪問開銷，提高搜索速度。

傳統(tǒng)方法：

1、FDScanning：計(jì)算對(duì)象的距離（從查詢點(diǎn)），然后將計(jì)算的距離與閾值進(jìn)行比較。（需要掃描對(duì)象的全部維度來執(zhí)行操作）

2、PDScanning：增量掃描原始向量的維度，并在基于部分掃描的??維度的距離（如下圖公式）大于距離閾值??時(shí)終止該過程。

ADSampling 核心：

將對(duì)象投影到具有不同維度的空間中，并基于投影向量進(jìn)行比較操作（DCOs）以提高效率。

原理：對(duì)于遠(yuǎn)離查詢的負(fù)對(duì)象來說，將它們投影到維數(shù)更少的空間就足以進(jìn)行可靠的比較操作（DCOs）; 而對(duì)于靠近查詢的負(fù)對(duì)象，它們應(yīng)該被投影到具有更多維數(shù)的空間中以進(jìn)行可靠的比較操作（DCOs）。

實(shí)現(xiàn)步驟：

（1）通過隨機(jī)正交變換對(duì)對(duì)象進(jìn)行預(yù)處理。（注：這一步僅是隨機(jī)地旋轉(zhuǎn)對(duì)象而不扭曲它們的距離。）

（2）在查詢階段處理不同對(duì)象的比較操作（DCOs）時(shí)，它會(huì)對(duì)其轉(zhuǎn)換后的向量進(jìn)行不同維度的采樣。

注：ADSampling 根據(jù)查詢期間對(duì)象的 DCO 自適應(yīng)地決定每個(gè)對(duì)象要采樣的維度數(shù)量，而不是在索引階段預(yù)設(shè)一個(gè)確定的數(shù)量（這需要具有專業(yè)知識(shí)，實(shí)踐中難以設(shè)置）

ADSampling實(shí)現(xiàn)流程

隨機(jī)向量投影過程

給定一個(gè)對(duì)象 x，我們首先對(duì) x（向量） 應(yīng)用一個(gè)隨機(jī)正交矩陣 ??' ∈ R ??×??，然后對(duì)其上的??行進(jìn)行采樣(為簡單起見，使用前??行)。

結(jié)果表示為(??' x)|[1,2，…，??]。

我們將轉(zhuǎn)換后的向量表示為 ?y := ??′x

基于采樣的維度，我們可以計(jì)算出 x 的近似距離，表示為 dist'

其中 d 是采樣的維度數(shù)量。值得注意的是，基于采樣維度計(jì)算近似距離的時(shí)間復(fù)雜度為 O(d)。

假設(shè)檢驗(yàn)尋找合適 d

待解決問題：如何確定需要采樣多少個(gè) y 的維度，才能對(duì)距離比較操作（DCOs）做出足夠自信的結(jié)論（即是否決定 ?????? ≤ ??）

假設(shè)檢驗(yàn)的步驟：

（1）定義一個(gè)零假設(shè) H0: dis ≤ r 和它的備擇假設(shè) H1: dis > r。

（2）使用 ??????′ 作為 ?????? 的估計(jì)器。

注意：??????′ 與 ?????? 之間的關(guān)系由引理 3.1（歐幾里得范數(shù)存在一個(gè)誤差概率） 提供（即：??????′ 與 ?????? 之間的差異受到 ??·?????? 的限制，且失敗概率最多為 2 exp(???0????^2))。

（3）設(shè)置顯著性水平 p（置信區(qū)間）

其中，c0 為常數(shù)，其中??是一個(gè)需要根據(jù)經(jīng)驗(yàn)調(diào)整的參數(shù)。

（4）我們檢查事件是否發(fā)生 （如下圖公式）。如果發(fā)生，我們可以拒絕??0并以足夠的置信度得出結(jié)論??1: ??????> ??；否則我們不能。

假設(shè)檢驗(yàn)的結(jié)果：

情況1：我們拒絕假設(shè)H0（即我們得出結(jié)論 ?????? > ??），且 ?? < ??。在這種情況下，時(shí)間成本（主要用于評(píng)估近似距離）為 ??(??)，小于計(jì)算真實(shí)距離的時(shí)間成本為 ??(??)。

情況2：我們無法拒絕假設(shè)且 ?? < ??。在這種情況下，我們將繼續(xù)逐步采樣y的一些更多的維度，并進(jìn)行另一次假設(shè)檢驗(yàn)。（增加d值）

情況3：?? = ??。在這種情況下，我們已經(jīng)對(duì) y 的所有維度進(jìn)行了采樣，基于采樣向量的近似距離等于真實(shí)距離。

因此，我們可以進(jìn)行精確的 DCOs。我們注意到，具有（可能是順序的）假設(shè)檢驗(yàn)的增量維度采樣過程的時(shí)間成本嚴(yán)格小于 ??（??）（當(dāng)它在 Case 1終止時(shí)），并且等于??（??）（當(dāng)它在 Case 3終止時(shí)）。

參數(shù)??0：

參數(shù)??0 是 ADSampling 算法的一個(gè)關(guān)鍵參數(shù)，因?yàn)樗苯涌刂屏藴?zhǔn)確性和效率之間的權(quán)衡(??0 越大意味著假設(shè)檢驗(yàn)的顯著性值越小，這進(jìn)一步意味著假設(shè)檢驗(yàn)的結(jié)果越準(zhǔn)確)。

下圖繪制了 HNSW++(左圖)和 IVF++(右圖)在不同 ??0 下的 QPS-recall 曲線?？偟膩碚f，我們從圖中觀察到，??0 越大，QPS -召回曲線就會(huì)向右下移動(dòng)。這是因?yàn)檩^大的 ??0 以效率為代價(jià)可以獲得更好的準(zhǔn)確性。

我們觀察到，當(dāng) ??0 = 2.1時(shí)，精度損失很小，而進(jìn)一步增加 ??0 則會(huì)降低效率。因此，為了提高效率而不損失太多的準(zhǔn)確性，我們建議將 ??0 設(shè)置在2.1左右。

參數(shù)Δ?? = 32：

在 ADSampling 中，它增量地對(duì)數(shù)據(jù)向量的一些維度進(jìn)行采樣，并在迭代中執(zhí)行假設(shè)測(cè)試。為了避免頻繁假設(shè)測(cè)試的開銷，我們?cè)诿看蔚袑?duì) Δ?? 維度進(jìn)行采樣。默認(rèn)情況下，我們?cè)O(shè)置 Δ??= 32。

ADSampling算法流程：

Input : A transformed data vector o′, a transformed queryvector q′and a distance threshold ??

輸入：一個(gè)經(jīng)過變換的數(shù)據(jù)向量 o'，一個(gè)經(jīng)過變換的查詢向量 q'?和一個(gè)距離閾值 ??

Output : The result of DCO (i.e., whether ?????? ≤ ??): 1 meansyes and 0 means no; In case of the result of 1, anexact distance is also returned

輸出：DCOs 的結(jié)果（即是否 ??????≤??）：1表示是，0表示否；如果結(jié)果為1，則還返回一個(gè)確切的距離

Initialize the number of sampled dimensions ?? to be 0

將采樣維度的數(shù)量 ?? 初始化為 0

????while ?? < ?? do

????Sample some more dimensions ????incrementally with

????逐步采樣一些維度????

???????? = o??′ ? q??′

????Update ?? and the approximate distance ??????′accordingly

????相應(yīng)地更新????和近似距離 ??????′

????Conduct a hypothesis testing with the null hypothesis??0 as ?????? ≤ ?? based on the approximate distance ??????′

????進(jìn)行零假設(shè)檢驗(yàn)，零假設(shè)為 ?????? ≤ ??，檢驗(yàn)基于近似距離 ??????′。

????if ??0 is rejected and ?? < ?? then // Case 1

??????return 0

????else if ??0 is not rejected and ?? < ?? then // Case 2

??????Continue

????else // Case 3

??????return 1 (and ??????′) if ??????′ ≤ ?? and 0 otherwise

注意：當(dāng) ADSampling 在 Case 3（即?? = ??）終止時(shí)，將不會(huì)出現(xiàn)失敗，因?yàn)樵谶@種情況下，近似距離 ??????′ 等于真實(shí)距離 ??????，DCO結(jié)果是精確的。當(dāng)ADSampling在Case 1終止時(shí)，如果 ?????? ≤ ?? 成立，則會(huì)發(fā)生失敗，因?yàn)樵谶@種情況下，它得出了 ?????? > ??（通過拒絕零假設(shè)）。

ANN+

ANN+：在運(yùn)行 AKNN 算法的過程中，每當(dāng)它進(jìn)行距離比較操作（DCOs）時(shí)，我們使用 ADSampling 方法。

HNSW+：在將新訪問的對(duì)象的距離與結(jié)果集 R 中的最大值進(jìn)行比較時(shí)使用 ADSampling 方法。

IVF+：將候選對(duì)象的距離與當(dāng)前維護(hù)的 KNN 集合 K 中的最大值進(jìn)行比較，以選擇生成的候選對(duì)象中的最終 KNN 時(shí)應(yīng)用 ADSampling。

ANN++

HNSW++

1、HNSW+：

概念：維護(hù)了一個(gè) max-heap 大小為 ??（????）的結(jié)果集 R，并將距離作為鍵，其中 ??（????）>??。對(duì)于每個(gè)新生成的候選對(duì)象，它會(huì)檢查其距離是否不大于集合 R 中最大距離（的對(duì)象），如果是，則將對(duì)象插入集合 R。

具體操作：使用 ADSampling 對(duì)每個(gè)候選對(duì)象進(jìn)行 DCOs，其中 R 中距離最大的對(duì)象作為閾值距離。

R集的兩個(gè)作用：

1、維護(hù)了到目前為止生成的候選對(duì)象中距離最小的 KNN。這些 KNN 將在算法結(jié)束時(shí)作為輸出返回。

2、維護(hù)了到目前為止生成的候選對(duì)象中的前 ??^(th) ef 個(gè)最大距離。這個(gè)距離被用作 DCO 的閾值距離，影響候選對(duì)象的生成。

具體來說，如果由 HNSW+ 生成的候選對(duì)象的距離小于等于 R 中的第 Nef 大距離，則它將被添加到搜索集 S 中進(jìn)行進(jìn)一步的候選對(duì)象生成。對(duì)于每個(gè)新生成的候選對(duì)象，它會(huì)檢查其距離是否不大于集合R中最大距離（的對(duì)象），如果是，則將對(duì)象插入集合R。

2、HNSW++：

概念：通過維護(hù)兩個(gè)集合 R1 和 R2 來解耦 R 的兩個(gè)作用，即為每個(gè)作用維護(hù)一個(gè)集合。

集合 R 的分解：

集合 R1 的大小為 K，基于精確距離（深綠色）。

集合 R2 具有大小 ??????，并基于距離，這些距離可以是精確的或近似的。

具體來說，對(duì)于每個(gè)新生成的候選對(duì)象，他都會(huì)檢查它的距離是否小于或等于集合R1中最大距離，并在滿足條件時(shí)將該候選對(duì)象插入到集合 R1 中。

注：這個(gè) DCO 會(huì)產(chǎn)生一個(gè)副產(chǎn)品，即觀察到的距離 ??????'（淺綠色），當(dāng) ADSampling 終止時(shí)，它可以是精確的（如果所有的 D 個(gè)維度都被采樣），或者是近似的（如果它以 ??<?? 的方式終止）。然后，它根據(jù)觀察到的距離類似于 HNSW+ 維護(hù)集合 R2 和集合 S。

總結(jié)：HNSW++ 使用的是K作為尋找候選值；HNSW+ 使用 ?????? 尋找候選值。其中 ?????? > K。

IVF++

1、IVF：

在原始的 IVF 算法中，同一簇中的向量按順序存儲(chǔ)。在評(píng)估它們的距離時(shí)，算法按順序掃描所有這些向量的維度，這展現(xiàn)出強(qiáng)烈的局部性，并因此使其具有良好的緩存性能。

2、IVF+：

它掃描的維度比 IVF 少，但如果使用相同的數(shù)據(jù)布局，它就無法具有良好的緩存性能。具體來說，當(dāng) IVF+ 為數(shù)據(jù)向量終止維度采樣過程時(shí)，隨后的維度可能已經(jīng)從主存儲(chǔ)器加載到緩存中，盡管它們不是必需的。

3、IVF++：

ADSampling 一定會(huì)先采樣一些維度（如 ??1 個(gè)），然后根據(jù)假設(shè)檢驗(yàn)結(jié)果逐漸采樣更多維度。也就是說，每個(gè)候選向量的前 ??1 個(gè)維度一定會(huì)被訪問。出于這個(gè)原因，我們將所有候選向量的前 ??1 個(gè)維度順序存儲(chǔ)在一個(gè)數(shù)組 ??1 中，將所有候選向量的其余 ?????1 個(gè)維度順序存儲(chǔ)在另一個(gè)數(shù)組 ??2 中。

性能分析（6個(gè)數(shù)據(jù)集）

召回率：成功檢索到的真實(shí) knn 的數(shù)量與 ?? 之間的比率。

平均距離比：檢索到的 ?? 對(duì)象與真實(shí) knn 的距離比。

結(jié)論總結(jié)：

結(jié)論 1（結(jié)果圖）：

我們可以清楚地觀察到 AKNN+ 和 AKNN++ 在達(dá)到幾乎相同的召回率的情況下，評(píng)估的維度比 AKNN 少得多。

具體而言，在 GIST 上，對(duì)于 ?????? 的所有測(cè)試值，HNSW+ 和 HNSW++(相對(duì)于 HNSW)的精度損失不超過0.14%，IVF+ 和 IVF++ 的精度損失不超過0.1%。

與此同時(shí)，HNSW++ 組在總維度上從39.4%節(jié)省到75.3%，HNSW+ 組從34.5%節(jié)省到39.4%，IVF+/IVF++ 組從76.5%節(jié)省到89.2%。

基線法 HNSW* 從10.9%節(jié)省到15.7%，這解釋了它在 HNSW 上的改善很小。IVF*/IVF** 可節(jié)省28.9%至40.4%。

結(jié)論 2：

技術(shù)在 IVF 上比 HNSW 帶來了更多的改進(jìn)(即使 IVF 比 HNSW 表現(xiàn)更好，例如在 Word2Vec 上)。

原因：HNSW 的 DCOs 以外的其他計(jì)算比IVF的計(jì)算更重(如下圖所示)

結(jié)論 3：

該技術(shù)總體上在高精度區(qū)域比低精度區(qū)域帶來了更多的改進(jìn)(例如，GIST 95% vs . 85%)

原因：當(dāng) AKNN 算法以更高的精度為目標(biāo)時(shí)，它不可避免地會(huì)生成更多低質(zhì)量的候選對(duì)象，并且距離差距更大 ??，因此它需要更少的維度來獲得可靠的 DCOs。

結(jié)論 4：

數(shù)據(jù)布局優(yōu)化對(duì) IVF+(即 IVF++ vs . IVF+)的改進(jìn)大于對(duì) IVF*(即 IVF** vs . IVF*)的改進(jìn)。

原因：ADSampling 具有對(duì)數(shù)復(fù)雜度，而基線 PDScanning 具有線性復(fù)雜度。具體來說，在使用 ADSampling 時(shí)，第一個(gè) Δ?? 維度對(duì)于許多 dco 已經(jīng)足夠，因此可以避免對(duì)圖4c 中第二個(gè)數(shù)組 ??2 的多次訪問。當(dāng)對(duì) DCOs 使用 PDScanning 時(shí)，它仍然會(huì)頻繁地訪問第二個(gè)數(shù)組，因?yàn)樗枰木S度超過 Δ??。

補(bǔ)充

索引階段：

我們首先用 NumPy 庫生成一個(gè)隨機(jī)正交變換矩陣，存儲(chǔ)它并將變換應(yīng)用到所有數(shù)據(jù)向量。然后我們將轉(zhuǎn)換后的向量(AKNN, AKNN* 和 AKNN** 的原始向量)輸入到現(xiàn)有的 AKNN 算法中。

對(duì)于 HNSW、HNSW+、HNSW++ 和 HNSW*(注意它們具有相同的圖結(jié)構(gòu))，我們的實(shí)現(xiàn)基于 hnswlib

對(duì)于 IVF、IVF+、IVF++、IVF* 和 IVF**(注意它們具有相同的聚類結(jié)構(gòu))，我們的 K-means 聚類實(shí)現(xiàn)基于 Faiss 庫

查詢階段：

所有算法都是用 c++ 實(shí)現(xiàn)的。

對(duì)于一個(gè)新的查詢，我們首先使用特征庫[25]轉(zhuǎn)換查詢向量，以便在運(yùn)行 AKNN+ 和 AKNN++ 算法時(shí)進(jìn)行快速矩陣乘法(對(duì)于 AKNN, AKNN* 和 AKNN**，它們不涉及轉(zhuǎn)換)。

然后我們將向量輸入 AKNN, AKNN+， AKNN++， AKNN* 和 AKNN** 算法。

時(shí)間成分分析：

應(yīng)用 ADSampling 需要隨機(jī)轉(zhuǎn)換數(shù)據(jù)和查詢向量的額外成本。具體來說，轉(zhuǎn)換數(shù)據(jù)向量的成本位于索引階段，并且可以由同一數(shù)據(jù)庫上的所有后續(xù)查詢攤銷。查詢向量的轉(zhuǎn)換在查詢階段進(jìn)行，當(dāng)出現(xiàn)查詢時(shí)，查詢的代價(jià)可以由回答相同查詢所涉及的所有 dco 分?jǐn)偂?/p>

為了簡單起見，我們將這一步(又稱為 Johnson-Lindenstrauss 變換)實(shí)現(xiàn)為矩陣乘法運(yùn)算，它需要 ??(??^2) 時(shí)間。我們注意到，使用高級(jí)算法[19]可以在更短的時(shí)間內(nèi)執(zhí)行這一步，例如，使用 Kac 's Walk 需要 ??(??log??) 時(shí)間。

—? ??參考文獻(xiàn)????—

[1]Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824-836. https://doi.org/10.1109/TPAMI.2018.2889473

[2]Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128.

向量檢索實(shí)驗(yàn)室地球號(hào)：VectorSearch，關(guān)注了解更多