原文連結: https://blog.csdn.net/u011233351/article/details/85116719
一.背景介紹
在浩渺的資料長河中做高效率相似性查找一直以來都是讓人頭疼的問題。比如，我在搜狗app上閱讀了一篇文章，推薦系統就應當為我推送與這篇文章最相近的文章，資料庫中所有文章是用向量表示的，是以我們要解決的問題就是“找到與這篇文章的向量最相近的幾個向量”，然後把這些向量對應的文章推送出去。資料庫中的文章千千萬，所有使用者每秒的請求也是千千萬，我們需要又快又準又相對節約資源的辦法來解決這個問題。
解決這個問題的方法有很多，PQ，Annoy，HNSW等等。篇幅有限，這篇文章隻介紹HNSW算法。
二.樸素想法
樸素想法圖
請大家把目光投向上面這張圖。假設我們現在有13個2維資料向量，我們把這些向量放在了一個平面直角坐标系内，隐去坐标系刻度，它們的位置關系如上圖所示。
樸素查找法：不少人腦子裡都冒出過這樣的樸素想法，把某些點和點之間連上線，構成一個查找圖，存下來備用；當我想查找與粉色點最近的一點時，我從任意一個黑色點出發，計算它和粉色點的距離，與這個任意黑色點有連接配接關系的點我們稱之為“友點”（直譯），然後我要計算這個黑色點的所有“友點”與粉色點的距離，從所有“友點”中選出與粉色點最近的一個點，把這個點作為下一個進入點，繼續按照上面的步驟查找下去。如果目前黑色點對粉色點的距離比所有“友點”都近，終止查找，這個黑色點就是我們要找的離粉色點最近的點。
如果你沒看懂上面的文字描述，我們來舉個例子。目标：我們要查找與粉色點最近的點。步驟：從任意一個黑色點出發，這裡我們随便選個C點吧，計算一下C點和粉色點的距離，存下來備用，再計算C點的所有友點（A，I，B）與粉色點的距離（計算距離和度量的方式有多種，這裡我們采用歐氏距離，就是二維實體空間上的“近和遠”），我們計算得出B與粉色點的距離最近，而且B點距離粉色點的距離比C點距離粉色點的距離（前面算過）更近，是以我們下面用B點繼續查找。B點距離粉色點的距離儲存下來，B點的友點是E，A，C，I，H，分别計算它們與粉色點的距離，得到E點與粉色點距離最近，且E點比B點距離粉色點還要近，是以我們選擇E點作為下一個查找點。E點的友點是J，B，D，G，這時我們發現J點的與粉色點的距離最近，但是，but，however，J點的距離粉色點的距離比E點還要遠，是以滿足了終止查找的條件，是以我們傳回E點。
樸素想法之是以叫樸素想法就是因為它的缺點非常多。首先，我們發現圖中的K點是無法被查詢到的，因為K點沒有友點，怎麼辦？。其次，如果我們要查找距離粉色點最近的兩個點，而這兩個近點之間如果沒有連線，那麼将大大影響效率（比如L和E點，如果L和E有連線，那麼我們可以輕易用上述方法查出距離粉色點最近的兩個點），怎麼辦？。最後一個大問題，D點真的需要這麼多“友點”嗎？誰是誰的友點應該怎麼确定呢？
關于K點的問題，我們規定在構圖時所有資料向量節點都必須有友點。關于L和E的問題，我們規定在構圖時所有距離相近（相似）到一定程度的向量必須互為友點。關于D點問題，權衡構造這張圖的時間複雜度，我們規定盡量減少每個節點的“友點”數量。帶着這三條規定，我們進入下一章節。
三.NSW算法
在圖論中有一個很好的剖分法則專門解決上一節中提到的樸素想法的缺陷問題------德勞内（Delaunay）三角剖分算法，這個算法可以達成如下要求：1，圖中每個點都有“友點”。2，相近的點都互為“友點”。3，圖中所有連接配接（線段）的數量最少。效果如下圖。
但NSW沒有采用德勞内三角剖分法來構成德勞内三角網圖，原因之一是德勞内三角剖分構圖算法時間複雜度太高，換句話說，構圖太耗時。原因之二是德勞内三角形的查找效率并不一定最高，如果初始點和查找點距離很遠的話我們需要進行多次跳轉才能查到其臨近點，需要“高速公路”機制（Expressway mechanism, 這裡指部分遠點之間擁有線段連接配接，以便于快速查找）。在理想狀态下，我們的算法不僅要滿足上面三條需求，還要算法複雜度低，同時配有高速公路機制的構圖法。
NSW論文中配了這樣一張圖，黑色是近鄰點的連線，紅色線就是“高速公路機制”了。我們從enter point點進入查找，查找綠色點臨近節點的時候，就可以用過紅色連線“高速公路機制”快速查找到結果。
NSW樸素構圖算法在這裡：向圖中逐個插入點，插圖一個全新點時，通過樸素想法中的樸素查找法（通過計算“友點”和待插入點的距離來判斷下一個進入點是哪個點）查找到與這個全新點最近的m個點（m由使用者設定），連接配接全新點到m個點的連線。完了。
在上面這個戛然而止的算法描述中有些讀者肯定會問，就這麼簡單？對，就這麼簡單。我們來理智地分析一下這個算法。首先，我們的構圖算法是逐點随機插入的，這就意味着在圖建構的早期，很有可能建構出“高速公路”。假設我們現在要構成10000個點組成的圖，設定m=4（每個點至少有4個“友點”），這10000個點中有兩個點，p和q，他們倆坐标完全一樣。假設在插入過程中我們分别在第10次插入p，在第9999次插入q，請問p和q誰更容易具有“高速公路”？答：因為在第10次插入時，隻見過前9個點，故隻能在前9個點中選出距離最近的4個點（m=4）作為“友點”，而q的選擇就多了，前9998個點都能選，是以q的“友點”更接近q，p的早期“友點”不一定接近p，是以p更容易具有“高速公路”。結論：一個點，越早插入就越容易形成與之相關的“高速公路”連接配接，越晚插入就越難形成與之相關的“高速公路”連接配接。是以這個算法設計的妙處就在于扔掉德勞内三角構圖法，改用“無腦添加”（NSW樸素插入算法），降低了構圖算法時間複雜度的同時還帶來了數量有限的“高速公路”，加速了查找。
下面對NSM樸素構圖算法的過程舉例，已經看懂上面文字描述的讀者可以跳過下一段。
我們對7個二維點進行構圖，使用者設定m=3（每個點在插入時找3個緊鄰友點）。首先初始點是A點（随機出來的），A點插入圖中隻有它自己，是以無法挑選“友點”。然後是B點，B點隻有A點可選，是以連接配接BA，此為第1次構造。然後插入F點，F隻有A和B可以選，是以連接配接FA，FB，此為第2此構造。然後插入了C點，同樣地，C點隻有A，B，F可選，連接配接CA，CB，CF，此為第3次構造。重點來了，然後插入了E點，E點在A，B，F，C中隻能選擇3個點（m=3）作為“友點”，根據我們前面講規則，要選最近的三個，怎麼确定最近呢？樸素查找！從A，B，C，F任意一點出發，計算出發點與E的距離和出發點的所有“友點”和E的距離，選出最近的一點作為新的出發點，如果選出的點就是出發點本身，那麼看我們的m等于幾，如果不夠數，就繼續找第二近的點或者第三近的點，本着不找重複點的原則，直到找到3個近點為止。由此，我們找到了E的三個近點，連接配接EA，EC，EF，此為第四次構造。第5次構造和第6次與E點的插入一模一樣，都是在“現成”的圖中查找到3個最近的節點作為“友點”，并做連接配接。
圖畫完了，請關注E點和A點的連線，如果我再這個圖的基礎上再插入6個點，這6個點有3個和E很近，有3個和A很近，那麼距離E最近的3個點中沒有A，距離A最近的3個點中也沒有E，但因為A和E是構圖早期添加的點，A和E有了連線，我們管這種連線叫“高速公路”，在查找時可以提高查找效率（當進入點為E，待查找距離A很近時，我們可以通過AE連線從E直接到達A，而不是一小步一小步分多次跳轉到A）。
關于NSW算法的樸素構思就講到這裡了，下面我們來說說優化。
一.在查找的過程中，為了提高效率，我們可以建立一個廢棄清單，在一次查找任務中周遊過的點不再周遊。在一次查找中，已經計算過這個點的所有友點距離查找點的距離，并且已經知道正确的跳轉方向了，這些結果是唯一的，沒有必要再去做走這個路徑，因為這個路徑會帶給我們同樣的重複結果，沒有意義。
二.在查找過程中，為了提高準确度，我們可以建立一個動态清單，把距離查找點最近的n個點存儲在表中，并行地對這n個點進行同時計算“友點”和待查找點的距離，在這些“友點”中選擇n個點與動态列中的n個點進行并集操作，在并集中選出n個最近的友點，更新動态清單。
注意，插入過程之前會先進行查找，是以優化查找過程就是在優化插入過程。以下給出NSW查找步驟。設待查找q點的m個近鄰點。
1.随機選一個點作為初始進入點，建立空廢棄表g和動态清單c，g是變長的清單，c是定長為s的清單（s>m）,将初始點放入動态清單c（附上初始點和待查找q的距離資訊），制作動态清單的影子清單c'。
2.對動态清單c中的所有點并行找出其“友點”，檢視這些“友點”是否存儲在廢棄表g中，如果存在，則丢棄，如不存在，将這些 剩餘“友點”記錄在廢棄清單g中（以免後續重複查找，走冤枉路）。
3.并行計算這些剩餘“友點”距離待查找點q的距離，将這些點及其各自的距離資訊放入c。
4.對動态清單c去重，然後按距離排序（升序），儲存前s個點及其距離資訊。
5.檢視動态清單c和c'是否一樣，如果一樣，結束本次查找，傳回動态清單中前m個結果。如果不一樣，将c'的内容更新為c的 内容，執行第2步。
插入算法更簡單了，插入算法就是先用查找算法查找到m個（使用者設定）與待插入點最近的點，連接配接它們，完了。
以上就是NSW算法的全部内容，HNSW就是NSW再優化版本。如果你需要消化一下上面的内容，我建議你明天再看下面， 因為筆者也不是一天就撸懂了他的論文。為了搞懂這個算法，筆者總共撸了三篇論文，NSW是其中一本，另一本是HNSW，不 看NSW就看不懂HNSW，另外還撸了維羅諾伊多邊形和德勞内三角剖分的化石級論文，然後Malkov先生在NSW論文某段中告訴我，它構造的“僞德勞内三角剖分圖”和真德勞内三角剖分圖沒有任何關系，隻是随便取了這個名罷了，我喝着水差點把我嗆死。
四.跳表結構
設有有序連結清單，名叫sorted_link，裡面有n個節點，每個節點是一個整數。我們從表頭開始查找，查找第t（0<t<n）個節點 需要跳轉幾次？答：t-1次（沒錯，我是從1開始數的）。把n個節點分成n次查找的需求，都查找一遍，需要跳轉幾次？答： （0+1+2+3+.....+（n-1））次。
如果我這連結清單長成下圖這樣呢？
這已經不是一個有序連結清單了，這是三個有序連結清單+分層連接配接指針構成的跳表了。看這張示意圖就能明白它的查找過程，先查第一層，然後查第二層，然後查第三層，然後找到結果。如果把上段所描述的名字叫sorted_link的連結清單建立成這樣的跳表，那麼把sorted_link中的所有元素都查一遍還需要花費（0+1+2+3+.....+（n-1））次嗎？當然不需要。那麼具體是多少次呢？如果你真的關心，請搜狗搜尋關鍵詞“跳表”。
跳表怎麼建構呢？三個字，抛硬币。對于sorted_link連結清單中的每個節點進行抛硬币，如抛正，則該節點進入上一層有序鍊 表，每個sorted_link中的節點有50%的機率進入上一層有序連結清單。将上一層有序連結清單中和sorted_link連結清單中相同的元素做一一對應的指針連結。再從sorted_link上一層連結清單中再抛硬币，sorted_link上一層連結清單中的節點有50%的可能進入最表層，相當于sorted_link中的每個節點有25%的機率進入最表層。以此類推。
這樣就保證了表層是“高速通道”，底層是精細查找，這個思想被應用到了NSW算法中，變成了其更新版-----HNSW。
五.HNSW算法
論文中的一張示意圖即可看懂作者malkov的意思。
第0層中，是資料集中的所有點，你需要設定一個常數ml，通過公式floor(-ln(uniform(0,1)) x ml)來計算這個點可以深入到第幾層。公式中x是乘号，floor（）的含義是向下取整，uniform（0,1）的含義是在均勻分布中随機取出一個值，ln（）表示取對數。對于上述三個函數有任何疑問的同學請下載下傳搜狗搜尋app，搜一下，什麼都有。沒事看看資訊流，罵罵小編，蘇福。
到此，關于HNSW算法的描述就基本結束了。我們來大緻梳理一下它的查找過程，從表層（上圖中編号為Layer=2）任意點開始查找，選擇進入點最鄰近的一些友點，把它們存儲在定長的動态清單中，别忘了把它們也同樣在廢棄表中存一份，以防後面走冤枉路。一般地，在第x次查找時，先計算動态清單中所有點的友點距離待查找點（上圖綠色點）的距離，在廢棄清單中記錄過的友點不要計算，計算完後更新廢棄清單，不走冤枉路，再把這些計算完的友點存入動态清單，去重排序，保留前k個點，看看這k個點和更新前的k個點是不是一樣的，如果不是一樣的，繼續查找，如果是一樣的，傳回前m個結果。
插入構圖的時候，先計算這個點可以深入到第幾層，在每層的NSW圖中查找t個最緊鄰點，分别連接配接它們，對每層圖都進行如此操作，描述完畢。
我們需要控制一大堆參數，首先，插入時的動态清單c的大小，它的大小直接影響了插入效率，和構圖的品質，size越大，圖的品質越高，構圖和查找效率就越低。其次，一個節點至少有幾個“友點”，“友點”越多，圖的品質越高，查找效率越低。作者在論文中還提到了“max友點連接配接數”這個參數，設定一個節點至多有多少友點，來提高查找效率，但是設的太小又會影響圖的品質，權衡着來。上一段中的ml也是你來控制的，設定的大了，層數就少，記憶體消耗少，但嚴重影響效率，太大了會嚴重消耗記憶體和構圖時間。在論文中，作者将查找狀态下的動态清單長度和插入狀态下的動态清單長度做了區分，你可以通過調整他們來實作“精構粗找”或者“精找粗構”。
文中或有疏漏，歡迎指正批評。如果各位讀者對我的文章還滿意的話，一聽可樂的錢就可以支援我繼續寫作，歡迎打賞。