建構:逐點插入,先依 LCG(線性同餘產生器,burn-in 3 步)抽層數(幾何分佈,u<0.5 升層,本頁 cap=2,共
0/1/2 三層);若圖為空,該點直接成為 entry point。否則從目前 entry point 出發,先在高於自己層數的各層只
找路不連邊(新點尚不存在於這些層),再從自己層數往下逐層插入自己、貪婪精煉目前位置,並與候選中離自己最近的
M 個點互連——新增邊後若既有點鄰居數超過 M,立刻剪到最近的 M 個(雙向剪除,鄰接恆對稱,本頁 M=2)。
查詢:從 entry point 於高層貪婪下降,到層 0 切換 ef 搜尋,並與獨立全掃的暴力最近鄰同幀對照。
累計距離計算次數(全域 visits,含建構+全部查詢):0
階段:declare-level
多層帶狀圖:由上而下依序為層 2(頂層,最少點)→ 層 1 → 層 0(底層,含全部 10 個點)——
上面的帶就是高層;同一點跨層 x 座標不變,跨層之間的垂直邊代表「這個點同時存在於相鄰兩層」,
層內邊代表該層的近鄰連結。橘色(current)=當下處理/走訪節點;綠色(finalized)=連邊完成/entry
point 建立/查詢終幀的 HNSW 結果;藍色外框(frontier)=新連上的鄰居,或查詢終幀漏標時另外標出的
「暴力真最近鄰」;紫色(visited)=本次查詢累積走訪過的節點。節點上方數字為其所在層數(L0/L1/L2)。
誠實揭露——近似可能漏掉真最近鄰:Q2([6,0])在 ef=1(純貪婪,等同只信任目前最近候選)時會
卡在局部最優、回傳的並非全域真正最近鄰;把 ef 提高到 2(保留較多候選繼續擴展)才找回真正最近鄰——
ef 越大越接近精確解,代價是多訪問幾個點,下方查詢對照表會逐列列出兩者差異,漏標列會醒目標紅。
教學縮尺:本頁僅 10 個點、M=2,暴力全掃只需 10 次距離計算,HNSW 反而不見得更快——
HNSW 的優勢要在十億級向量、M/ef 遠大於本例的生產設定下才會顯現,這裡看不出速度優勢,只能看出
「近似 vs 精確」的取捨長什麼樣子。
簡化裁剪策略:本頁連邊採簡化版「取離插入點最近的 M 個候選」啟發式(候選池只看目前搜尋到
的點與其直接鄰居),並非 HNSW 論文完整的 heuristic selection(論文版本會額外考慮候選之間的相對距離,
避免同側過度密集連邊),教學上足以展示多層 + 貪婪的核心機制,但非論文完整實作。
建構進度(insertProgress)
(尚未開始)
查詢對照表(HNSW 結果 vs 暴力全掃真值)
| 查詢 | ef | HNSW 結果 | 暴力 NN | HNSW visits | 暴力 visits | 漏標 |