13 種高維向量檢索算法全解析！數(shù)據(jù)庫頂會 VLDB 2021 論文作者干貨分享
2021-09-30 10:36:11

編者按：

以圖搜圖、商品推薦、社交推薦等社會場景中潛藏了大量非結(jié)構(gòu)化數(shù)據(jù)，這些數(shù)據(jù)被工程師們表達(dá)為具有隱式語義的高維向量。為了更好應(yīng)對高維向量檢索這一關(guān)鍵問題，杭州電子科技大學(xué)計算機(jī)專業(yè)碩士王夢召等人探索并實(shí)現(xiàn)了「效率和精度最優(yōu)權(quán)衡的近鄰圖索引」，并在數(shù)據(jù)庫頂會 VLDB 2021 上發(fā)表成果。

作為連接生產(chǎn)和科研的橋梁，Zilliz 研究團(tuán)隊一直與學(xué)界保持交流、洞察領(lǐng)域前沿。此次，王夢召來到 Z 星，從研究動機(jī)、算法分析、實(shí)驗觀測和優(yōu)化討論等維度展開講講最新的科研成果。

導(dǎo)言

向量檢索是很多 AI 應(yīng)用必不可少的基礎(chǔ)模塊。近年來，學(xué)術(shù)界和工業(yè)界提出了很多優(yōu)秀的基于近鄰圖的ANNS 算法以及相關(guān)優(yōu)化，以應(yīng)對高維向量的檢索問題。但是針對這些算法，目前缺乏統(tǒng)一的實(shí)驗評估和比較分析。

為了優(yōu)化算法設(shè)計、進(jìn)一步落地工業(yè)應(yīng)用，我們完成了論文《A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search》。該論文聚焦實(shí)現(xiàn)了效率和精度最優(yōu)權(quán)衡的近鄰圖索引，綜述了 13 種具有代表性相關(guān)算法，實(shí)驗在豐富的真實(shí)世界數(shù)據(jù)集上執(zhí)行。我們的貢獻(xiàn)可總結(jié)如下：

根據(jù)圖索引的特征，我們將基于近鄰圖的 ANNS 算法劃分為四類，這給理解現(xiàn)存算法提供了一個新的視角。在此基礎(chǔ)上，我們闡述了算法間的繼承和發(fā)展關(guān)系，從而梳理出算法的發(fā)展脈絡(luò)；

我們分解所有算法為 7 個統(tǒng)一的細(xì)粒度組件，它們構(gòu)成一個完整的算法執(zhí)行流程，從而實(shí)現(xiàn)了算法的原子級分析。我們可以公平評估當(dāng)前工作在某一組件的優(yōu)化通過控制其它組件一致；

我們采用多樣的數(shù)據(jù)集（包括 8 個真實(shí)世界數(shù)據(jù)集，它們包括視頻、語音、文本和圖像生成的高維向量）和指標(biāo)評估當(dāng)前算法的全面性能；

我們提供了不同場景下最優(yōu)算法推薦、算法優(yōu)化指導(dǎo)、算法改進(jìn)示例、研究趨勢和挑戰(zhàn)的分析討論。

研究動機(jī)

根據(jù)以下觀測，我們對 13 種基于近鄰圖的 ANNS 算法進(jìn)行了比較分析和實(shí)驗綜述：

目前，學(xué)術(shù)界和工業(yè)界提出 10 余種常見的近鄰圖算法，但對于這些算法的合理分類和比較分析較為缺乏。根據(jù)我們的研究，這些算法的索引結(jié)構(gòu)可歸結(jié)為 4 種基礎(chǔ)的圖結(jié)構(gòu)，但這些圖存在著非常多的問題，如復(fù)雜度太高等。所以，在這 4 種圖結(jié)構(gòu)基礎(chǔ)上有多種優(yōu)化，如對相對鄰域圖（RNG）優(yōu)化就包含 HNSW、DPG、NGT、NSG、SPTAG 等算法。

很多現(xiàn)有的論文從“分子”角度評估基于近鄰圖的 ANNS 算法（宏觀角度）。然而，我們發(fā)現(xiàn)，這些算法有一個統(tǒng)一的“化學(xué)表達(dá)式”，它們還可再向下細(xì)分為“原子”（微觀角度），從“原子”角度分析可以產(chǎn)生一些新發(fā)現(xiàn)，比如很多算法都會用到某一“原子”（HNSW，NSG，KGraph，DPG的路由是相同的）。

除了搜索效率和精度的權(quán)衡之外，基于近鄰圖的 ANNS 算法的其它特征（包含在索引構(gòu)建和搜索中）也間接影響了最終的搜索性能。在搜索性能逐漸達(dá)到瓶頸的情況下，我們對于索引構(gòu)建效率、內(nèi)存消耗等指標(biāo)給予了重視。

一個算法的優(yōu)越性并不是一成不變的，數(shù)據(jù)集的特征在其中起著至關(guān)重要的作用。比如，在 Msong（語音生成的向量數(shù)據(jù)集）上NSG 的加速是 HNSW 的 125 倍；然而，在 Crawl（文本生成的向量數(shù)據(jù)集）上 HNSW 的加速是 NSG 的 80 倍。我們在多樣的數(shù)據(jù)集上執(zhí)行實(shí)驗評估，從而對算法形成更全面的認(rèn)識。

近鄰圖算法“分子”級分析

在分析基于近鄰圖的 ANNS 算法之前，首先給大家介紹下 4 個經(jīng)典的圖結(jié)構(gòu)，即：德勞內(nèi)圖（DG）、相對領(lǐng)域圖（RNG）、K 近鄰圖（KNNG）、最小生成樹（MST）。如圖1所示，這四種圖結(jié)構(gòu)的差異主要體現(xiàn)在選邊過程，簡單總結(jié)如下：DG 確保任意 3 個頂點(diǎn) x, y, z 形成的三角形 xyz 的外接圓內(nèi)部及圓上不能有除了 x, y, z 之外的其它頂點(diǎn)；RNG 要確保(b)中月牙形區(qū)域內(nèi)不能有其它點(diǎn)，這里的月牙形區(qū)域是分別以x和y為圓心，x 與 y 之間的距離為半徑的兩個圓的交集區(qū)域；KNNG 每個頂點(diǎn)連接 K 個最近的鄰居；MST 在保證聯(lián)通性的情況下所有邊的長度（對應(yīng)兩個頂點(diǎn)的距離）之和最小。

圖1 四種圖結(jié)構(gòu)在相同的數(shù)據(jù)集上的構(gòu)建結(jié)果

接下來，我將基于圖1 中的 4 個圖結(jié)構(gòu)來梳理 13 個基于近鄰圖的ANNS算法。為了避免翻譯造成了理解偏差，算法名使用英文簡稱，算法的原論文鏈接、部分高質(zhì)量的中文介紹、部分代碼請見參考資料。各算法之間更宏觀的聯(lián)系可參考論文中的表2 和圖3。

算法1：NSW

NSW 是對 DG 的近似，而 DG 能確保從任意一個頂點(diǎn)出發(fā)通過貪婪路由獲取精確的結(jié)果（即召回率為 1 ）。NSW 是一個類似于“交通樞紐”的無向圖，這會導(dǎo)致某些頂點(diǎn)的出度激增，從論文的表11 可知，NSW 在某些數(shù)據(jù)集上的最大出度可達(dá)幾十萬。NSW 通過增量插入式的構(gòu)建，這確保了全局連通性，論文表4 中可知，NSW的連通分量數(shù)均為1。NSW 具有小世界導(dǎo)航性質(zhì)：在構(gòu)建早期，形成的邊距離較遠(yuǎn)，像是一條“高速公路”，這將提升搜索的效率；在構(gòu)建后期，形成的邊距離較近，這將確保搜索的精度。??

代碼：??https://github.com/kakao/n2??

算法2：HNSW

HNSW 在 NSW 的基礎(chǔ)上有兩個優(yōu)化：“層次化”和“選邊策略”。層次化的實(shí)現(xiàn)較為直觀：不同距離范圍的邊通過層次呈現(xiàn)，這樣可以在搜索時形成類似于跳表結(jié)構(gòu)，效率更高。選邊策略的優(yōu)化原理是：如果要給某個頂點(diǎn)連接 K 個鄰居的話，NSW 選擇 K 個距離最近的，而 HNSW 從大于 K 個最近的頂點(diǎn)里面選出更離散分布的鄰居（見參考資料1）。因此，從選邊策略考慮，HNSW 是對 DG 和 RNG 的近似。??

代碼：??https://github.com/kakao/n2??

算法3：FANNG

FANNG 的選邊策略與 HNSW 是一樣的，都是對RNG近似。FANNG 比 HNSW 更早提出，不過當(dāng)前 HNSW 得到更普遍的應(yīng)用，可能的原因是：

（1）FANNG 的選邊策略是在暴力構(gòu)建的近鄰圖的基礎(chǔ)上實(shí)現(xiàn)的，構(gòu)建效率很低；

（2）HNSW 通過增量式構(gòu)建且引入分層策略，構(gòu)建和搜索效率都很高；

（3）HNSW 開源了代碼，F(xiàn)ANNG 則沒有。?

算法4：NGT

NGT 是雅虎日本開源的向量檢索庫，核心算法基于近鄰圖索引。NGT 在構(gòu)建近鄰圖時類似于 NSW，也是對 DG 的近似，后續(xù)有一些度調(diào)整優(yōu)化，其中最有效的路徑優(yōu)化也是對 RNG 的近似（論文的附件B 也給出了證明）。?

代碼：??https://github.com/yahoojapan/NGT??

算法5：SPTAG

SPTAG 是微軟發(fā)布的向量檢索庫，它的構(gòu)建過程基于分治策略，即迭代地劃分?jǐn)?shù)據(jù)集，然后在每個子集上構(gòu)建近鄰圖，接著歸并子圖，最后通過鄰域傳播策略進(jìn)一步優(yōu)化近鄰圖。上述過程旨在構(gòu)建一個盡可能精確的 KNNG。在搜索時，SPTAG 采用樹索引和圖索引交替執(zhí)行的方案，即先從樹上獲取距查詢較近的點(diǎn)作為在圖上搜索的起始點(diǎn)執(zhí)行路由，當(dāng)陷入局部最優(yōu)時繼續(xù)從樹索引上獲取入口點(diǎn)，重復(fù)上述操作直至滿足終止條件。?

中文介紹2：??https://cloud.tencent.com/developer/article/1429751??

代碼：??https://github.com/microsoft/SPTAG???

算法6：KGraph

KGraph 是對 KNNG 的近似，是一種面向一般度量空間的近鄰圖構(gòu)建方案?；卩従拥泥従痈赡苁青従拥乃枷?，KGraph 能夠快速構(gòu)建一個高精度的 KNNG。后續(xù)的很多算法（比如 EFANNA、DPG、NSG、NSSG）都是在該算法的基礎(chǔ)上的進(jìn)一步優(yōu)化。?

代碼：??https://github.com/aaalgo/kgraph??

算法7：EFANNA

EFANNA 是基于 KGraph 的優(yōu)化。兩者的差別主要體現(xiàn)在近鄰圖的初始化：KGraph 是隨機(jī)初始化一個近鄰圖，而 EFANNA 是通過 KD 樹初始化一個更精確的近鄰圖。此外，在搜索時，EFANNA 通過 KD 樹獲取入口點(diǎn)，而 KGraph 隨機(jī)獲取入口點(diǎn)。?

代碼：??https://github.com/ZJULearning/ssg??

算法8：IEH

類比 EFANNA，IEH 暴力構(gòu)建了一個精確的近鄰圖。在搜索時，它通過哈希表獲取入口點(diǎn)。?

算法9：DPG

在 KGraph 的基礎(chǔ)上，DPG 考慮頂點(diǎn)的鄰居分布多樣性，避免彼此之間非常接近的鄰居重復(fù)與目標(biāo)頂點(diǎn)連邊，最大化鄰居之間的夾角，論文的附件4 證明了 DPG 的選邊策略也是對 RNG 的近似。此外，DPG 最終添加了反向邊，是無向圖，因此它的最大出度也是非常高的（見論文附件表11）。?

代碼：??https://github.com/DBW??

算法10：NSG

NSG 的設(shè)計思路與 DPG 幾乎是一樣的。在 KGraph 的基礎(chǔ)上，NSG 通過 MRNG 的選邊策略考慮鄰居分布的均勻性。NSG 的論文中將 MRNG 的選邊策略與 HNSW 的選邊策略做了對比，例證了 MRNG 的優(yōu)越性。論文中的附件1 證明了NSG的這種選邊策略與 HNSW 選邊策略的等價性。NSG 的入口點(diǎn)是固定的，是與全局質(zhì)心最近的頂點(diǎn)。此外，NSG 通過 DFS 的方式強(qiáng)制從入口點(diǎn)至其它所有點(diǎn)都是可達(dá)的。?

中文介紹：??https://zhuanlan.zhihu.com/p/50143204??

代碼：??https://github.com/ZJULearning/nsg??

算法11：NSSG

NSSG 的設(shè)計思路與 NSG、DPG 幾乎是一樣的。在 KGraph 的基礎(chǔ)上，NSSG 通過 SSG 選邊策略考慮鄰居分布的多樣性。NSSG 認(rèn)為，NSG 過度裁邊了（見論文表4），相比之下 SSG 的裁邊要松弛一些。NSG 與 NSSG 另一個重要的差異是，NSG 通過貪婪路由獲取候選鄰居，而 NSSG 通過鄰居的一階擴(kuò)展獲取候選鄰居，因此，NSSG 的構(gòu)建效率更高。?

中文介紹：??https://zhuanlan.zhihu.com/p/100716181??

代碼：??https://github.com/ZJULearning/ssg??

算法12：Vamana

簡單來說，Vamana 是 KGraph、HNSW 和 NSG 三者的結(jié)合優(yōu)化。在選邊策略上，Vamana 在 HNSW （或 NSG）的基礎(chǔ)上增加了一個調(diào)節(jié)參數(shù)，選邊策略為 HNSW 的啟發(fā)式選邊，取不同的值執(zhí)行了兩遍選邊。?

算法13：HCNNG

HCNNG 是目前為止唯一一個以 MST 為基本構(gòu)圖策略的向量檢索算法。類似SPTAG，HCNNG 的構(gòu)建過程基于分治策略，在搜索時通過 KD 樹獲取入口點(diǎn)。

中文介紹：??https://whenever5225.github.io/2019/08/17/HCNNG/??

近鄰圖算法“原子”級分析 我們發(fā)現(xiàn)所有的基于近鄰圖的 ANNS 算法都遵循統(tǒng)一的處理流程框架，該流程里面有多個公共模塊（如圖2 的 C1->C7）。當(dāng)一個近鄰圖算法按照該流程被解構(gòu)后，我們可以很容易了解該算法是如何設(shè)計組裝的，這將給后續(xù)近鄰圖向量檢索算法的設(shè)計帶來很大的便利性。此外，我們也可固定其它模塊，保持其他模塊完全相同，從而更公平地評估不同算法在某一模塊實(shí)現(xiàn)上的性能差異。

圖2 近鄰圖向量檢索算法遵循的統(tǒng)一流程框架圖

接下來，我們以 HNSW 和 NSG 為例，說明如何實(shí)現(xiàn)圖2 的流程框架分析算法。在此之前，我們要先熟悉這兩個算法的索引構(gòu)建和搜索過程。

首先是 HNSW 分解，HNSW 的構(gòu)建策略是增量式的。因此，每插入一個數(shù)據(jù)點(diǎn)都要執(zhí)行一遍 C1->C3 過程。

HNSW 分解流程：

NSG 分解流程：

由于 HNSW 的 C3 與 NSG 的 C3 是等價的，因此，從上面兩個表格可知，HNSW 與 NSG 這兩個算法差別并不大。其實(shí)，論文涉及到的 13 種算法中很多算法之間都是很相似的，詳見論文第 4 章。

實(shí)驗觀測和討論

具體的實(shí)驗評估請參考論文第 5 章，接下來將概括介紹一下實(shí)驗的觀測結(jié)果和討論：

不同場景下的算法推薦

NSG 和 NSSG 普遍有最小的索引構(gòu)建時間和索引尺寸，因此，它們適用于有大量數(shù)據(jù)頻繁更新的場景；如果我們想要快速構(gòu)建一個精確的 KNNG（不僅用于向量檢索），KGraph、EFANNA 和 DPG 更適合；DPG 和 HCNNG 有最小的平均搜索路徑長度，因此，它們適合需要 I/O 的場景；對于 LID 值高的較難數(shù)據(jù)集，HNSW、NSG、HCNNG 比較適合；對于 LID 值低的簡單數(shù)據(jù)集，DPG、NSG、HCNNG 和 NSSG 較為適合；NGT 有更小的候選集尺寸，因此適用于 GPU 加速（考慮到 GPU 的內(nèi)存限制）；當(dāng)對內(nèi)存消耗要求較高時，NSG 和 NSSG 適合，因為它們內(nèi)存占用更小。

算法設(shè)計向?qū)?/h3>

一個實(shí)用的近鄰圖向量檢索算法一般滿足以下四個方面：

• 
  
• 高構(gòu)建效率
• 高路由效率
• 高搜索精度
• 低內(nèi)存負(fù)載
• 
  

針對第一方面，我們不要在提升近鄰圖索引質(zhì)量（即一個頂點(diǎn)的鄰居中真實(shí)的最近鄰居所占的比例）上花費(fèi)太多的時間。因為最好的圖質(zhì)量（可通過圖中與距它最近的頂點(diǎn)有邊相連的頂點(diǎn)所占比例度量）不一定實(shí)現(xiàn)最佳搜索性能（結(jié)合論文中表4 和圖7、8）。

針對第二方面，我們應(yīng)當(dāng)控制適當(dāng)?shù)钠骄龆?，多樣化鄰居的分布，減少獲取入口點(diǎn)的花費(fèi)，優(yōu)化路由策略，從而減少收斂到查詢點(diǎn)的鄰域所需的距離計算次數(shù)。

針對第三方面，我們應(yīng)當(dāng)合理設(shè)計鄰居的分布，確保連通性，從而提升對陷入局部最優(yōu)的"抵抗力"。

針對第四方面，我們應(yīng)當(dāng)優(yōu)化鄰居選擇策略和路由策略，從而減小出度和候選集尺寸。

優(yōu)化算法示例

基于上面的向?qū)В覀兘M裝了一個新的近鄰圖算法（圖3 中的 OA），該算法在圖2 中的 7 個組件中每個組件選中現(xiàn)存算法的一個具體實(shí)現(xiàn)，即 C1 采用 KGraph 算法的實(shí)現(xiàn)；C2 采用 NSSG 算法的實(shí)現(xiàn)；C3 采用 NSG 算法的實(shí)現(xiàn)；C4 采用 DPG 算法的實(shí)現(xiàn)；C5 采用 NSSG 算法的實(shí)現(xiàn)；C6 采用 DPG 算法的實(shí)現(xiàn)；C7 采用 HCNNG 和 NSW 算法的實(shí)現(xiàn)。

OA 算法實(shí)現(xiàn)了當(dāng)前最優(yōu)的綜合性能，詳見論文原文。因此，我們甚至不用優(yōu)化當(dāng)前算法，僅僅把現(xiàn)存算法的不同部分組裝起來就可以形成一個新算法。

圖3 OA 算法與當(dāng)前最優(yōu)的近鄰圖算法的搜索性能對比

趨勢與挑戰(zhàn)

基于 RNG 的選邊策略設(shè)計在當(dāng)前近鄰圖向量檢索算法的效率提升中起到了關(guān)鍵作用。在論文的評估中，唯一一個基于 MST 的算法 HCNNG 也表現(xiàn)出來很好的綜合性能。

在上述純近鄰圖算法基礎(chǔ)上，后續(xù)發(fā)展有三個主要方向：

• 
  
• 硬件優(yōu)化；
• 機(jī)器學(xué)習(xí)優(yōu)化；
• 更高級的查詢需求，比如結(jié)構(gòu)化和非結(jié)構(gòu)化混合查詢。
• 
  

我們未來面對這三個挑戰(zhàn)：

• 
  
• 數(shù)據(jù)編碼技術(shù)與圖索引如何有機(jī)結(jié)合以解決近鄰圖向量檢索算法高內(nèi)存消耗問題；
• 硬件加速近鄰圖索引構(gòu)建減少近鄰圖索引構(gòu)建時間；
• 根據(jù)不同場景的特征自適應(yīng)選擇最優(yōu)的近鄰圖算法。
• ?

關(guān)于作者：

王夢召，杭州電子科技大學(xué)計算機(jī)專業(yè)碩士。主要關(guān)注基于近鄰圖的向量相似性檢索、多模態(tài)檢索等研究內(nèi)容，并在相關(guān)方向申請發(fā)明專利三項，在數(shù)據(jù)庫頂會 VLDB 和 SCI 一區(qū) top 期刊 KBS 等發(fā)表論文兩篇。

日常愛好彈吉他、打乒乓球、跑步、看書，他的個人網(wǎng)站是 http://mzwang.top，Github主頁是 http://github.com/whenever5225