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

編者按：

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

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

導(dǎo)言

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

為了優(yōu)化算法設(shè)計(jì)、進(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í)驗(yàn)在豐富的真實(shí)世界數(shù)據(jù)集上執(zhí)行。我們的貢獻(xiàn)可總結(jié)如下：

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

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

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

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

研究動(dòng)機(jī)

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

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

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

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

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

近鄰圖算法“分子”級(jí)分析

在分析基于近鄰圖的 ANNS 算法之前，首先給大家介紹下 4 個(gè)經(jīng)典的圖結(jié)構(gòu)，即：德勞內(nèi)圖（DG）、相對(duì)領(lǐng)域圖（RNG）、K 近鄰圖（KNNG）、最小生成樹（MST）。如圖1所示，這四種圖結(jié)構(gòu)的差異主要體現(xiàn)在選邊過(guò)程，簡(jiǎn)單總結(jié)如下：DG 確保任意 3 個(gè)頂點(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 之間的距離為半徑的兩個(gè)圓的交集區(qū)域；KNNG 每個(gè)頂點(diǎn)連接 K 個(gè)最近的鄰居；MST 在保證聯(lián)通性的情況下所有邊的長(zhǎng)度（對(duì)應(yīng)兩個(gè)頂點(diǎn)的距離）之和最小。

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

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

算法1：NSW

NSW 是對(duì) DG 的近似，而 DG 能確保從任意一個(gè)頂點(diǎn)出發(fā)通過(guò)貪婪路由獲取精確的結(jié)果（即召回率為 1 ）。NSW 是一個(gè)類似于“交通樞紐”的無(wú)向圖，這會(huì)導(dǎo)致某些頂點(diǎn)的出度激增，從論文的表11 可知，NSW 在某些數(shù)據(jù)集上的最大出度可達(dá)幾十萬(wàn)。NSW 通過(guò)增量插入式的構(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ǔ)上有兩個(gè)優(yōu)化：“層次化”和“選邊策略”。層次化的實(shí)現(xiàn)較為直觀：不同距離范圍的邊通過(guò)層次呈現(xiàn)，這樣可以在搜索時(shí)形成類似于跳表結(jié)構(gòu)，效率更高。選邊策略的優(yōu)化原理是：如果要給某個(gè)頂點(diǎn)連接 K 個(gè)鄰居的話，NSW 選擇 K 個(gè)距離最近的，而 HNSW 從大于 K 個(gè)最近的頂點(diǎn)里面選出更離散分布的鄰居（見(jiàn)參考資料1）。因此，從選邊策略考慮，HNSW 是對(duì) DG 和 RNG 的近似。??

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

算法3：FANNG

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

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

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

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

算法4：NGT

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

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

算法5：SPTAG

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

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

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

算法6：KGraph

KGraph 是對(duì) KNNG 的近似，是一種面向一般度量空間的近鄰圖構(gòu)建方案。基于鄰居的鄰居更可能是鄰居的思想，KGraph 能夠快速構(gòu)建一個(gè)高精度的 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ī)初始化一個(gè)近鄰圖，而 EFANNA 是通過(guò) KD 樹初始化一個(gè)更精確的近鄰圖。此外，在搜索時(shí)，EFANNA 通過(guò) KD 樹獲取入口點(diǎn)，而 KGraph 隨機(jī)獲取入口點(diǎn)。?

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

算法8：IEH

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

算法9：DPG

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

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

算法10：NSG

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

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

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

算法11：NSSG

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

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

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

算法12：Vamana

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

算法13：HCNNG

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

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

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

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

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

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

HNSW 分解流程：

NSG 分解流程：

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

實(shí)驗(yàn)觀測(cè)和討論

具體的實(shí)驗(yàn)評(píng)估請(qǐng)參考論文第 5 章，接下來(lái)將概括介紹一下實(shí)驗(yàn)的觀測(cè)結(jié)果和討論：

不同場(chǎng)景下的算法推薦

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

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

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

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

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

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

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

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

優(yōu)化算法示例

基于上面的向?qū)В覀兘M裝了一個(gè)新的近鄰圖算法（圖3 中的 OA），該算法在圖2 中的 7 個(gè)組件中每個(gè)組件選中現(xiàn)存算法的一個(gè)具體實(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)的綜合性能，詳見(jiàn)論文原文。因此，我們甚至不用優(yōu)化當(dāng)前算法，僅僅把現(xiàn)存算法的不同部分組裝起來(lái)就可以形成一個(gè)新算法。

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

趨勢(shì)與挑戰(zhàn)

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

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

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

我們未來(lái)面對(duì)這三個(gè)挑戰(zhàn)：

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

關(guān)于作者：

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

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