Hierarchical Navigable Small World GraphsSmall world是一種圖：大多數(shù)節(jié)點(diǎn)并不互相連接，但又總能通過(guò)某個(gè)路徑搜索到彼此，且搜索的

Hierarchical Navigable Small World Graphs

Small world是一種圖：大多數(shù)節(jié)點(diǎn)并不互相連接，但又總能通過(guò)某個(gè)路徑搜索到彼此，且搜索的成本相對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)是log復(fù)雜度增長(zhǎng)的。很多現(xiàn)實(shí)世界的圖都表現(xiàn)出small world現(xiàn)象，比如社交網(wǎng)絡(luò)，wiki，Internet，基因，深度特征。世界的本質(zhì)是小圈子。

就KNN搜索而言，暴力算法復(fù)雜度隨數(shù)據(jù)集大小線性增長(zhǎng)，毫無(wú)疑問(wèn)不適合大數(shù)據(jù)集。完全匹配的搜索方法在應(yīng)用于低維數(shù)據(jù)時(shí)效果理想，高維則遠(yuǎn)不如近似搜索。

近似方法的召回率即為所找到的真正k近鄰數(shù)與k的比值。常用近似方法包括近似版本的樹(shù)算法、局部性敏感的哈希（LSH）、乘積量化（PQ）、臨近圖。圖方法在高維數(shù)據(jù)上表現(xiàn)很好，但圖的本質(zhì)決定了它的路由復(fù)雜度是冪律增長(zhǎng)的，這意味著它在低維數(shù)據(jù)上表現(xiàn)不好。

HNSW是一個(gè)比較新的求k近似近鄰的純粹圖數(shù)據(jù)結(jié)構(gòu)。它能提供log復(fù)雜度的增長(zhǎng)。主要貢獻(xiàn)包括：顯式選擇圖的入口節(jié)點(diǎn)，根據(jù)不同尺度分離連接、用高級(jí)的啟發(fā)式方法。HNSW可視為一種skip list的擴(kuò)展——只不過(guò)把鏈表?yè)Q成了臨近圖。

KNN臨近圖

所謂臨近圖，就是一種對(duì)圖進(jìn)行KNN搜索，并采樣貪婪路由的方法：從某個(gè)起點(diǎn)開(kāi)始，遍歷圖，每到一處就檢驗(yàn)鄰居到目標(biāo)的距離，選擇距離最小的作為下一站。

NSW是一種相對(duì)數(shù)據(jù)大小以polylog復(fù)雜度增長(zhǎng)的臨近圖，是以謂之navigable。NSW在構(gòu)建時(shí)通過(guò)連續(xù)以隨機(jī)順序插入元素，并雙向連接到M個(gè)近鄰(用一種從多個(gè)隨機(jī)起點(diǎn)開(kāi)始的貪婪搜索找到這M個(gè)近鄰）。這一過(guò)程可以非常高效地并行化，且不需要全局鎖，因此很適合分布式搜索系統(tǒng)。NSW在某些數(shù)據(jù)集上表現(xiàn)sota，但總體來(lái)說(shuō)由于polylog復(fù)雜度，仍會(huì)在低維度數(shù)據(jù)上出現(xiàn)嚴(yán)重地性能下降（相對(duì)樹(shù)方法）。

最早的NSW模型是克萊恩伯格發(fā)明，并用于著名的Milgram社會(huì)心理學(xué)實(shí)驗(yàn)（權(quán)威服從性測(cè)試）給社交網(wǎng)絡(luò)進(jìn)行建模的工具。Watts–Strogatz模型是生成隨機(jī)small world圖的模型，克萊恩伯格研究這個(gè)模型生成的網(wǎng)絡(luò)，用一個(gè)d-維向量空間內(nèi)的常規(guī)的柵格網(wǎng)絡(luò)（lattice graph），外加長(zhǎng)程連接的增強(qiáng)——這種長(zhǎng)程連接的長(zhǎng)度是符合(r^-d)分布的。這種方法雖然將路由復(fù)雜度降到了polylog（相對(duì)原來(lái)的power law），卻必須事先知道數(shù)據(jù)的分布。此外polylog也不算特別好。

另一種著名的NSW模型是scale-free models，可復(fù)現(xiàn)現(xiàn)實(shí)世界網(wǎng)絡(luò)的多種特征，但這種模型生成的網(wǎng)絡(luò)搜索起來(lái)甚至比貪婪搜索的power law還慢，且與克萊恩伯格模型一樣，scale-free模型需要知道數(shù)據(jù)分布知識(shí)——這也意味著不適合搜索應(yīng)用。

HNSW：按粒度分層搜索

NSW路由可分為zoom-out和zoom-in兩個(gè)階段，貪婪算法起始于zoom-out階段，從一個(gè)低degree點(diǎn)開(kāi)始遍歷圖，同時(shí)增加節(jié)點(diǎn)的degree，直到該節(jié)點(diǎn)連接長(zhǎng)度的特征半徑落到到query距離的尺度內(nèi)。在此之前，節(jié)點(diǎn)的平均degree往往維持在非常小的階段，所以需要zoom-out。

想要跳過(guò)zoom-out，可以選一個(gè)最高degree的點(diǎn)開(kāi)始，也就是要找個(gè)good candidate——hubs，可直接進(jìn)入zoom-in階段，大大提升路由成功率與低維數(shù)據(jù)上的效率。但這種NSW路由仍然只有最多polylog復(fù)雜度。在高維上還不如HNSW。

HNSW的思路是將link根據(jù)其長(zhǎng)度尺度分離到不同的layer，然后在分層的圖里進(jìn)行搜素。在這種結(jié)構(gòu)中，搜索從最上層開(kāi)始，最上層只包含最長(zhǎng)的links，這就相當(dāng)于之前NSW路由中的zoom-in階段。HNSW貪婪遍歷上層，直到達(dá)到一個(gè)局部最小——之后切換到下層，從這個(gè)局部最小再開(kāi)始遍歷，只不過(guò)用的是更短的link，更細(xì)致地搜索這一層的局部最小，以此類(lèi)推，總體復(fù)雜度降到log級(jí)別。這從本質(zhì)上來(lái)說(shuō)，就是skiplist在圖上的推廣，將鏈表改成臨近圖而已，運(yùn)用簡(jiǎn)單有效的分層搜索的理念。因此skiplist可以做的分布式方法，同樣適用于HNSW。

每次插入都會(huì)隨機(jī)選擇一個(gè)最大layer數(shù)。插入時(shí)也進(jìn)行自頂層開(kāi)始的搜索，找到每層的鄰居，再進(jìn)入下一層。

HNSW還有個(gè)優(yōu)點(diǎn)：構(gòu)造分層的隨機(jī)化本質(zhì)實(shí)際上已經(jīng)讓HNSW引入了隨機(jī)性（stochasticity），因此不像NSW構(gòu)造那樣需要在插入前shuffle元素。這意味著即使數(shù)據(jù)分布臨時(shí)改變，也能增量地對(duì)數(shù)據(jù)進(jìn)行索引。

元素插入階段的臨近圖連接選取，是基于一種啟發(fā)式方法的：考慮候選元素間距離的多樣性，而不簡(jiǎn)單地選取最近鄰居。這算是政治正確在算法中的合理使用。該啟發(fā)式方法從離插入元素最近的候選開(kāi)始，只有檢驗(yàn)出該候選離插入元素比其他所有已連接候選都近才會(huì)再建立連接。

當(dāng)候選數(shù)目足夠大，以至于啟發(fā)式方法能夠獲得準(zhǔn)確的相對(duì)鄰域圖作為Delaunay圖（德勞內(nèi)圖）的最小子圖，且只用兩點(diǎn)間距離就可以進(jìn)行推理——這在針對(duì)1D數(shù)據(jù)時(shí)直接讓NSW轉(zhuǎn)化成skip list。

一個(gè)圖如果是平面內(nèi)一些點(diǎn)集的德勞內(nèi)三角剖分，則稱(chēng)為德勞內(nèi)圖；德勞內(nèi)三角剖分是一種沒(méi)有任意點(diǎn)位于歐氏空間三角形（完全可以從歐氏空間推廣到度量空間）外接圓內(nèi)部的三角剖分；三角剖分是覆蓋點(diǎn)集凸包的simplicial complex；某個(gè)形狀的凸包(convex hull/envelope/closure)是包含它的最小凸集(convex region/set)；凸集是與任意線段相交部分都是單個(gè)線段的歐氏空間子集。

NGT-ONNG

background

有兩種類(lèi)型的knn近似搜索方法：一類(lèi)是用hash、quantization、permutation-based methods，在搜索過(guò)程中無(wú)需任何object來(lái)計(jì)算距離。另一類(lèi)是基于樹(shù)或者圖的方法，需要object——也就需要更多的內(nèi)存。前一類(lèi)方法的準(zhǔn)確度不如后一類(lèi)。如果內(nèi)存足夠大或用高速SSD代替內(nèi)存，那么用后一種方法會(huì)更好。

樹(shù)類(lèi)方法包括kd-tree、vp-tree，將整個(gè)搜索空間分層次且遞歸地分成子空間再搜，可提供準(zhǔn)確的搜索結(jié)果，但效率很低，甚至可能不如bruteforce加并行優(yōu)化。也有一些基于樹(shù)的近似方法，ANN就是將近似施加于kd-tree。

基于graph的方法用鄰接圖做輔助索引。Arya用隨機(jī)化的鄰接圖做搜索索引。Sebastian用knn graph(KNNG)作為搜索索引，KNNG中每個(gè)節(jié)點(diǎn)都有一個(gè)有向邊到k個(gè)最近的節(jié)點(diǎn)。KNNG雖然簡(jiǎn)單，但準(zhǔn)確率不錯(cuò)——事實(shí)上可以比LSH和kd-tree好。

DRNG將KNNG的degree降低，從而縮短查詢(xún)時(shí)間。

KNNG的缺點(diǎn)是構(gòu)建速度會(huì)隨著數(shù)據(jù)增多而指數(shù)性地慢。SW-graph、KGraph和ANNG用approximagte neighborhood graphs解決這個(gè)問(wèn)題。HNSW用多層approximate neighborhood，用長(zhǎng)edge達(dá)到遠(yuǎn)處的節(jié)點(diǎn)。

PANNG又對(duì)ANNG優(yōu)化，修剪每個(gè)節(jié)點(diǎn)的edge，從而縮短查詢(xún)時(shí)間，效果擊敗了量化方法。

proposed methods

1. 使用adjustment方法：
1. 靜態(tài)degree調(diào)整，用于管理自KNNG派生出的degree
2. 帶約束的靜態(tài)degree調(diào)整，更精確地管理自KNNG派生出的degree
3. 動(dòng)態(tài)degree調(diào)整，依賴(lài)搜索過(guò)程中的搜索準(zhǔn)確率
4. 路徑調(diào)整，考慮圖中的其他可行路徑

1. 提升對(duì)在搜索過(guò)程中已遍歷的節(jié)點(diǎn)的管理，以縮短查詢(xún)時(shí)間。

KNNG

KNNG里每個(gè)數(shù)據(jù)庫(kù)元素是一個(gè)節(jié)點(diǎn)，連接到k個(gè)最近鄰居。在KNNG上搜索是基于啟發(fā)式方法的，先選擇幾個(gè)分離度高的元素作為種子，用作搜索起點(diǎn)，每個(gè)種子代表一個(gè)數(shù)據(jù)庫(kù)粗采樣。從這些種子開(kāi)始，近鄰搜索不斷移動(dòng)到鄰居處，以best-first原則選擇下一個(gè)目標(biāo)。