# 0127
https://docs.google.com/document/d/1nOUNee9v8Wt7AVz50SGxu1fIiHhpVsgXqjVxhVgHSAo/edit?usp=sharing
# 0120
https://docs.google.com/presentation/d/1qsTWXTzfT8NvkEJeyKI8gjU-Aooyu9UvFq2lQC6qMSc/edit?usp=sharing
# 0113

https://docs.google.com/document/d/1skRGRJF2pReWssrWNrKa00tmYXO6Lxllj5ntHjB2Q_E/edit?usp=sharing

# efnet
## summery

## 每個 query 的完整搜尋流程

## test
python NN_dynamic_efsearch.py --config ./config.json --threads 1 --reach_threshold 0.5

## budget

# Distribution-Aware Exploration for Adaptive HNSW Search

https://docs.google.com/presentation/d/1qsTWXTzfT8NvkEJeyKI8gjU-Aooyu9UvFq2lQC6qMSc/edit?usp=sharing

















# 1230
https://docs.google.com/document/d/13aS-QEgzCx8C2xiZpdKTSxbhZ7CXAfi6ihKhyQNpqwk/edit?usp=sharing
# HNSW 預測efsearch
必須讓「容易 query 的 ef 下降省下的成本」大於「probe + 模型」的額外成本。
## 為每個 query 做一次 probe-run 並抽特徵
### 特徵清單
::: warning
### faiss 文件內容

1. **nhops**：在圖上走了多少「步」
[nhops](https://faiss.ai/cpp_api/struct/structfaiss_1_1HNSWStats.html?utm_source=chatgpt.com)

2. ndis： 多少個 query「候選清單跑光」而結束
[ndis](https://faiss.ai/cpp_api/struct/structfaiss_1_1HNSWStats.html?utm_source=chatgpt.com)

3. n1 : ???
4. n2 : 搜尋過程中檢查過的向量數

:::
:::info
### 實際
1. n1：執行了多少次查詢（每個 query 加 1）

2. n2：多少次查詢在候選集合空掉時結束

3. ndis：整體搜尋過程中做了多少次距離計算（distance computations）

4. nhops：在 HNSW 圖上從一個節點走到另一個節點的總步數
:::
5. Index::search(...) 的輸出包含

    * n: query數 
    * k: 最近的k個
    * distances：輸出距離（大小 n*k） 
    * labels：輸出近鄰的 ID（大小 n*k）

1. d1 = D[:, 0] (取mean, std, min, max)
每個 query 與**第一名**鄰居距離(d1小 → 比較好找、密度高)(大 →可能落在稀疏區/離群)
2. dk = D[:, k-1] (取mean, std, min, max)
每個 query 與**最後一名**鄰居距離 (若 dk 和 d1 很接近，代表 top-10 都在一個很緊密的小半徑內；反之則表示鄰居分散。)
3. margin_k = dk - d1 (取mean, std, min, max)
第 1 名到第 10 名距離拉開多少 (小 margin：top-10 很集中，局部密度高，鄰居彼此距離差不多 大 margin：top-10 不集中)
4. ratio_k = dk / (d1 + eps) (取mean, std, min, max)
最後一名距離是第1名距離的幾倍(接近 1：第 10 名和第 1 名差不多近 → top-k 很緊密。很大：距離分布很不均)

### 只取
(A) Probe (delta over this single search)
exhausted (ndis delta) = 929
distcomp (nhops delta) = 37

(B) Distance-shape features (from top-k results)
d1 = 58281
dk(k) = 72315
margin_k = 14034
ratio_k = 1.2408
## 離線學 node embedding
1. 對整張圖做 node embedding（離線）

用 node2vec / DeepWalk / GraphSAGE 之類（或你自己定義 message passing），把每個資料點學成一個 embedding，代表它在 HNSW 圖中的位置與連結型態（可分 layer 做）。

2. query 怎麼用到這些 embedding

query 不是圖上的節點，所以不能直接 message pass。常見作法是：

用 efProbe 找到一小撮候選節點 S（例如 50 個）

把它們的 node embedding 聚合（mean/attention pooling）

再和 query 向量特徵一起丟進 predictor → 輸出 efSearch

這樣模型確實「吃到了圖拓撲」，但推論成本仍然可控，因為你只聚合 probe 命中的小子圖。
## Probe + 難度模型

訓練標籤怎麼定

對每個 query 定義一個目標，例如：

目標：recall@k ≥ 0.95（相對於 exact kNN 或很大的 efMax 當作近似 GT）

標籤：最小 efSearch* 使得 recall@k 達標

做法通常是：對每個 query 在 ef ∈ [ef_min, ef_max] 上 binary search 找到最小 ef*（或用階梯掃描也可以但比較慢）。

特徵怎麼抓（關鍵）

只看 query 向量本身通常不夠，因為「難度」強烈依賴圖與資料分佈。實務上很有效的一招是：

先用很小的 efProbe 跑一次 HNSW（例如 16 或 32），把這次走圖的早期訊號當特徵，再由模型輸出該 query 的 efSearch。

常見有效特徵（幾乎不需要全圖計算）：

Probe 過程的統計：

訪問節點數、距離計算數

best distance 的下降曲線斜率（前幾步改善速度）

候選隊列大小變化、pop 次數、top 候選的 distance margin（第1名 vs 第k名）

Probe 命中的節點的「局部圖特徵」：

平均 degree、layer 分佈（HNSW 多層）

probe 命中節點彼此距離的分散程度（代表局部是否混亂）

query 的幾何特徵：

norm、與資料中心/多個 centroid 的距離（粗略密度指標）

模型本體用 GBDT（LightGBM/XGBoost）或小 MLP 通常就很好；輸出可以是：

迴歸：predict log(ef*)

分類：把 ef 分桶（如 16/32/64/128/256），直接選桶

線上推論流程

先跑 efProbe 小搜尋拿特徵

模型輸出 efPred（可再做 clamp：efProbe,efMax）

用 efPred 跑正式搜尋回傳 top-k

# cv final



# data mining project 超高分觀察

Epoch 10 Train Loss: 0.0330, Train Acc: 0.9893
--> Epoch 10 Val Loss: 0.0909, Val Acc: 0.9333
Validation Confusion Matrix:
[[ 7 0]
[ 11 147]]

訓練完成，最佳驗證準確率: 0.9878787878787879

1. 指定lossfunction
比例並不是亂給


2. SqueezeNet
3. 標準化
transforms.Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225])

這組數字是統計了 ImageNet 資料集（包含 100 萬張圖片、1000 個類別）中所有像素的結果：

Mean (平均值)： 代表 ImageNet 中所有圖片 R、G、B 三個通道的平均亮度。

Std (標準差)： 代表這些顏色數值的變動幅度。

因為大多數的自然照片（包括你的蝴蝶照片）顏色分佈都跟 ImageNet 類似，所以這組數字變成了電腦視覺界的「通用密碼」。
# 繪圖

https://excalidraw.com/

# cv論文報告

# 12/09
https://docs.google.com/document/d/1yXbVIJo30Eo6lUdHu4cude-6z6R-NJoTYi8938QWEDE/edit?usp=sharing

# line bot
https://hackmd.io/@flagmaker/S1VdzaGSye
https://hackmd.io/@flagmaker/S1VdzaGSye
# 12/2 報告
https://docs.google.com/presentation/d/1avMVb8QtPXAywe-aRfKUNP2mo8zqfddAbJGa3WCa768/edit?usp=sharing
## Secure Summation





## Secure Comparison

# 11/25

https://docs.google.com/presentation/d/1Q2biGWNwe3V-VI8CwKJ9JsY4zl2OXzqR67T2bdAYSkA/edit?usp=sharing

# Attention

1. Attention 是什麼？（一句話版本）
Attention = 找出「哪些部分比較重要」並給它們更高權重的機制。

在影像中 → 哪些區域重要
在文字中 → 哪些詞重要
在跨模態中 → 哪些文字片段和哪些影像片段互相關

2. 超白話比喻：自助餐找你最想吃的菜
你走進自助餐（一大堆食物 = 一大堆資訊），你會：
- 炸雞腿 → 注意力超高
- 燙青菜 → 注意力中等
- 胡蘿蔔 → 注意力低

你不會每道菜都平均拿，你會根據喜好「加權取樣」。
這就是 Attention 的核心：
→ 從海量資訊中挑出最相關的部分
→ 給不同資訊不同權重

3. Attention 的基本構成：Q、K、V
三大核心向量：
Q = Query → 你現在在找什麼
K = Key → 所有資料的「標籤」
V = Value → 真正的資料內容

流程：
拿 Q 去跟所有 K 比對相似度 → 轉成權重 → 加權所有 V

公式：
Attention(Q, K, V) = softmax( (Q·K^T) / √d ) × V

4. 超清楚例子
句子：「The man is riding a bicycle.」
想知道 “riding” 跟哪些詞最相關？

Q = embedding("riding")
K = 所有詞的 embedding
V = 所有詞的 embedding

結果：bicycle 和 man 權重最高 → riding 的語意會特別強調「人」和「腳踏車」

5. Attention 的兩大類型（超重要）
(1) Self-Attention
Q、K、V 都來自同一序列（純文字或純影像）
經典應用：Transformer 內部的注意力

(2) Cross-Attention
Q 來自一種模態，K/V 來自另一種模態
經典應用：影像-文字模型（如 CLIP、BLIP、Flamingo）
- 文字找圖：Q=text, K/V=image
- 圖找文字：Q=image, K/V=text

6. Attention 為什麼強大？
- 自動發現關鍵內容（「bicycle」直接找到圖中腳踏車）
- 輕鬆處理長距離依賴
- 並行計算，比 RNN 快很多
- 通用性極高：文字、影像、語音、蛋白質序列都行

7. 數學拆解（專業版）
Attention(Q, K, V) = softmax( (QK^T)/√d_k) ) V

步驟：
1. QK^T → 算相似度
2. /√d_k → 縮放防止梯度消失
3. softmax → 轉成權重（加總=1）
4. ×V → 加權後輸出

8. 影像–文字 Cross-Attention 範例
句子：「A man is riding a bicycle.」
影像區域：v1=man, v2=bike, v3=wheel, v4=tree, v5=sky

對 token「bicycle」做 attention：
相似度 → bike 0.60、wheel 0.30、man 0.05、tree 0.03、sky 0.02
softmax 後權重 ≈ bike 58%、wheel 29%、其他少少
最終輸出 = 0.58×v2 + 0.29×v3 + …

→ 這個 token 現在「知道」自己對應到圖中腳踏車

9. Attention 的缺點（為什麼後來有人用 OT）
- 每個 token 都會分到一點注意力 → 背景雜訊進來
- 計算量 O(N×M) 很大
- 只能壓低權重，無法真正丟掉不相關的 fragment

→ OMIT 等新方法用 Optimal Transport + Partial Matching，直接把不重要的影像 fragment 丟掉，乾淨又省算力

一句話總結
Attention 就是「用 Query 去問所有 Key，找出最相關的 Value 並加權」，是 Transformer 和所有現代多模態模型的靈魂。

*******
# 一張圖片和一段文字的語意是否一致。
## VSE：整體向量匹配方法（粗粒度）

VSE（Visual Semantic Embedding）把整張圖片 / 整段文字向量化成一個向量，再用 cosine similarity 來比較。

缺點：

把圖片或句子壓成一個向量，資訊損失嚴重

很難捕捉到「局部語意」(fine-grained semantics)

無法好好處理複雜圖片（例如多個物件）

VSE 最後只用兩個平均向量（黑色與灰色）比一次 cosine similarity

## PEM
Step 1：抽取影像與文字的局部特徵
Step 2：把局部特徵轉成 “高斯分布” 的參數
Step 3：比較二個分布間的距離（divergence）

PEM 把圖片與文字都變成「機率分布」，並用分布之間的 divergence 做相似度。比 VSE 更彈性，但仍無法做真正的細粒度對齊。

## CAM 可以用一句話總結為：

CAM 用 cross-attention 計算每個文字片段與影像片段的對應，再用 cosine similarity 評估整體匹配度，是細粒度的方法，但容易受冗餘片段干擾且成本較高。
****
# 1119
[Link](https://docs.google.com/presentation/d/1-2JSpDa7PBbNKEqqhvyTK3hkqSmPi-E66WihqYXSbj0/edit?usp=sharing)

# faiss









# 資料探勘助教
## Scikit-learn

wine = load_wine()
X, y = wine.data, wine.target
print(f"features: {X.shape[1]}, samples: {X.shape[0]}, classes: {len(wine.target_names)}")
print(f"Class names: {wine.target_names}")

****
把 sklearn 載入的原始資料（numpy 格式）轉換成 pandas DataFrame，並把特徵和標籤整合在同一張表格裡，方便後續做探索性資料分析或模型訓練。

F = pd.DataFrame(wine.data, columns=wine.feature_names)
t = pd.Series(wine.target, name="target")

# 合併成一個 DataFrame
wine_df = pd.concat([F, t], axis=1)
wine_df.head()

****
類別分布檢查，確認資料是否平衡。如果類別數差異太大，訓練模型時可能會導致「偏向樣本多的類別」。

print(np.bincount(y)) # 查看三個classes的分布

（1）是否形成清楚群聚、（2）群聚間是否有橋接點/重疊、（3）明顯離群點。

****
決策樹就像一連串的 if-else 判斷，用特徵逐步把資料切分成不同群組，最後在葉節點輸出預測結果。

from sklearn.tree import DecisionTreeClassifier

tree_model = DecisionTreeClassifier(
    max_depth=5,         # 限制最大深度，避免過擬合
    min_samples_split=4,     # 至少4個樣本才能分裂
    min_samples_leaf=2,      # 葉子節點至少2個樣本
    random_state=42        # 設定隨機種子，確保每次運行的結果一致。
)
tree_model.fit(X_train, y_train)

****
條件（例：x[9] <= 3.82）
→ 代表用第 9 個特徵來分裂，閾值是 3.82。
→ 若條件為真，走左邊；為假，走右邊。

gini：基尼不純度 (Gini Impurity)
→ 測量這個節點的「混亂程度」。
→ 0 代表純粹（只有單一類別），越高代表類別混雜越多。

samples：這個節點包含多少筆樣本。

value：三個類別樣本數，例如 [41, 30, 33] 表示：

類別 0 有 41 筆

類別 1 有 30 筆

類別 2 有 33 筆

****
GaussianNB 假設每個特徵符合 高斯分布（常態分布）。適合連續型特徵的資料

from sklearn.naive_bayes import GaussianNB

NB_model = GaussianNB()
NB_model.fit(X_train, y_train)
NB_model.score(X_test, y_test)

****

列 (row) → 真實標籤 (True label)

欄 (column) → 模型預測 (Predicted label)

from sklearn.metrics import confusion_matrix

y_pred = NB_model.predict(X_test)
print(confusion_matrix(y_test, y_pred)) # 印出混淆矩陣
[[18  0  0]
 [ 0 20  1]
 [ 0  2 13]]

****

SVM 的目標是找出一條最佳「超平面 (hyperplane)」來分隔不同類別，同時最大化邊界 (margin)。

from sklearn.svm import SVC

SVC_model = SVC(
    C=1,           # 增加懲罰參數。值越大，越嚴格（容易過擬合）；值越小，允許更多錯誤（可能欠擬合）。
    kernel='linear',     # 核函數，決定如何將資料映射到高維空間。常用的有 'linear', 'poly', 'rbf', 'sigmoid'。
    gamma=0.01,        # 控制高斯核（RBF）、多項式核的影響範圍。值越大，影響範圍越小（容易過擬合）。如用linear則不需要gamma。
    random_state=42
)
SVC_model.fit(X_train, y_train)
SVC_model.score(X_test, y_test)

****

MLP（多層感知機, Multi-Layer Perceptron）

MLP 是一種前饋式神經網路 (Feedforward Neural Network)。

由 輸入層 → 一個或多個隱藏層 → 輸出層 組成。

每一層由多個「神經元 (neuron)」構成，神經元之間有權重 (weights) 連接。

from sklearn.ensemble import RandomForestClassifier

RF = RandomForestClassifier(
    n_estimators=20,       # 森林中樹的數量，設定20棵樹來增加穩定性
    max_depth=5,         # 每棵樹的最大深度限制為5，以避免過擬合
    min_samples_split=5,     # 若一個節點的樣本數少於5，則不再分裂
    min_samples_leaf=2,      # 每個葉節點至少保留2筆樣本，以避免過度分裂
    random_state=42
)

RF.fit(X_train, y_train)
RF.score(X_test, y_test)

****
它結合了多棵 決策樹 (Decision Tree)，利用 Bagging (Bootstrap Aggregating) 技術提升穩定性與準確度。

from sklearn.ensemble import RandomForestClassifier

RF = RandomForestClassifier(
    n_estimators=20,       # 森林中樹的數量，設定20棵樹來增加穩定性
    max_depth=5,         # 每棵樹的最大深度限制為5，以避免過擬合
    min_samples_split=5,     # 若一個節點的樣本數少於5，則不再分裂
    min_samples_leaf=2,      # 每個葉節點至少保留2筆樣本，以避免過度分裂
    random_state=42
)

RF.fit(X_train, y_train)
RF.score(X_test, y_test)

****


****
# Patience in Proximity A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search

https://docs.google.com/presentation/d/16PR0x36dapTWI7WV9xMDbw4oylv6mlBM0e067kO44tY/edit?usp=sharing

作者提出一個簡單的 saturation-based（飽和）早停策略，稱為 Patience in Proximity，在 HNSW 的圖遍歷/search 過程中動態判定何時停止擴展候選節點，以節省訪問次數和時間（QPS 提升），同時盡量不損失檢索效果。


現有 HNSW 優化方向

1. 圖建構改善

減少記憶體消耗、優化連結結構

2. 搜尋啟發式優化

距離門檻 (distance cutoff)：若最佳鄰居距離已足夠小，則提前停止。

固定訪問數 (visit budget per layer)：限制每層最多訪問節點數。

缺點：過於激進會 犧牲準確度 或 錯過遠端但相關的鄰居。

本研究定位

提出：將「候選飽和」概念改造，應用於 HNSW 的圖遍歷。

核心特色：

非固定門檻、非固定 budget，而是 依據候選品質改善率動態決定停止點。

減少冗餘計算，同時保持 HNSW 的高準確度。

以下整理「既有的 early-exit（早停）策略」在 HNSW／圖式 ANN 搜尋中的主要做法與技術要點，聚焦就事論事的技術面與取捨分析。

1) 基準：HNSW 的標準停止條件（Baseline）

內部機制：在最底層（layer 0）以最佳優先（best-first）彈出目前候選集中與查詢距離最近的點 c；若 dist(c, q) 已不優於當前結果集（如 top-k 或 efSearch 結果集）中的最差距離，則停止擴展。

含意：這是「必要不充分」的停止條件；後述 early-exit 策略都是在此基礎上「更早」終止以換取效率。

2) 距離門檻式（Distance-threshold Cutoff）

想法
當最佳已知鄰近距離足夠小時，繼續擴展的收益有限，可直接早停。

常見形式

絕對門檻：若 best_dist ≤ τ 則停止（需對資料尺度有先驗或離線估計 τ）。

相對改進率：最近幾次彈出／擴展帶來的 best_dist 改善量低於 ε（如 Δbest / best ≤ ε）持續 M 次，則停止。

邊界比較：若候選佇列最小距離 min_candidate_dist ≥ current_worst_in_topk（較嚴格版本會再加上 margin）。

優缺點

優：簡單、開銷低。

缺：門檻設置錯誤在非均勻分佈時易造成召回掉點；需要資料/任務特定調參。

3) 訪問次數／層級配額（Visit-Budget / Per-Layer Cap）

想法
事先設定彈出（pop）或實際訪問（expand）的上限來控制延遲。

變體

全域訪問上限：總擴展節點數達上限 B 即停。

逐層配額：每一層最多訪問 B_l 個節點後，下切至下一層或直接終止。

時間上限：以牆鐘時間（wall time）或 CPU 配額作為停止條件。

優缺點

優：延遲可預測、易於服務層面的 SLO 控制。

缺：召回受資料難度波動影響大；需要離線選 B/B_l 以平衡效能。

4) 飽和／停滯檢測（Saturation / Patience）

想法
當「結果集幾乎不再改變」時，視為品質飽和並早停。

典型實作（含本文脈絡）

記錄第 h 次訪問後的鄰居集合 N_{h,l}(q) 與前一次 N_{h-1,l}(q) 的重疊率
φ_{h,l}(q) = 100 · |N_{h-1,l} ∩ N_{h,l}| / k。

若連續 Δ 次滿足 φ_{h,l}(q) ≥ γ（如 90–99%），則停止當前層的擴展或整體搜尋。

優缺點

優：自適應於查詢與資料難度；在維持效果下顯著減少訪問次數。

缺：需維護結果集重疊統計；γ, Δ 需以驗證集調參。

5) 候選品質斜率／推進率（Improvement-Slope / Promotion-Rate）

想法
監控「每 N 次訪問帶來的有效提拔（promotion）數」或「top-k 惡化／改善速度」。

指標例子

Promotion rate：在視窗 W 內，進入 top-k 的新節點比例 p = (#promotions)/W；若 p < p_min 持續 M 個視窗則早停。

Frontier quality slope：觀察候選佇列最小距離的移動平均改善率，低於門檻即停。

優缺點

優：能細緻反映「探索前沿」是否仍有收益。

缺：需額外統計／平滑；參數較多。

6) 分支限界／上界裁剪（Branch-and-Bound with Bounds）

想法
利用度量空間的性質（如三角不等式）或外部下界／上界（如量化預估距離）做更強的剪枝與早停。

範式

若對所有待展開候選皆有下界 LB(x, q) ≥ current_worst_in_topk，則可終止（因不可能產生更佳結果）。

與多索引或量化（PQ/OPQ、HNSW-PQ 等）結合時，用粗距離的下界快速判斷無望候選，當剩餘候選皆為無望者即可早停。

優缺點

優：理論上更保守、錯殺少。

缺：需要額外的下界估計機制（量化碼本或索引結構），工程複雜度較高。

7) 層間早停（Inter-Level Early Exit）

想法
在高層就評估是否有必要下行到底層，或在底層限制擴展深度。

做法

若 entry point 與查詢距離已遠低於某臨界，直接以較小 efSearch 進入底層或縮短底層搜尋。

對密集資料集，允許在底層僅做有限次的鄰接展開後停止。

優缺點

優：減少到底層的「長尾」開銷。

缺：對不同資料分佈的魯棒性需驗證。

8) 叢集／區域感知的早退（Cluster-Aware / Region-Aware）

想法
以叢集或區域為單位追蹤改善情況；當某些叢集的質心或代表點對查詢已無改進潛力時，整塊跳過。

適用情境

多段式索引（如 coarse quantizer + HNSW 的混合）

圖與叢集的混成搜尋器（先路由到幾個候選叢集，再在叢集內圖搜尋）

優缺點

優：能「批量」刪除無望區域，速度收益可觀。

缺：需額外叢集結構與路由品質；叢集邊界誤差會影響召回。

9) 服務面導向的策略（Latency-First Heuristics）

想法
以線上延遲為首要目標的混合策略：

動態調整 efSearch／訪問上限，根據目前系統負載或查詢時間進度收斂到一個目標延遲。

針對「簡單查詢」（很快出現高重疊率或高 promotion rate 下降）提早結束；「困難查詢」允許多花些預算。

優缺點

優：在流量高峰時維持整體 SLO。

缺：效果（召回）在壓力情況下會有可預期的退化，需要離線/線上監控對策。

參數調整與實作建議

門檻選擇：先以驗證集畫出「訪問數 ↔ NDCG/Recall ↔ QPS」曲線，確定在可接受的效果損失（如 NDCG@10 ≤ 0.5–1.0pt 掉點）下的參數範圍。

視窗平滑：對「改進率／重疊率」以移動平均或指數平滑，降低單一步驟抖動。

分層搭配：在高層採較嚴格早停（因為本就粗略），底層採較保守早停（以守住召回）。

指標監控：線上追蹤 promotion rate、重疊率 φ、每查詢訪問數分佈與 P95/P99 延遲，必要時動態放寬/收緊。

與「Patience in Proximity」的關係

屬於第 4 類（飽和／停滯檢測） 的具體化：以 top-k 重疊率 φ 與 連續次數 Δ 作為停止條件，γ 設為 90–99% 常見。

可用於只在搜尋時（HNSWP(S)）或索引＋搜尋（HNSWP(IS)）；後者可能讓圖更稀疏、進一步省時，但對效果更敏感。

工程成本低、可與其他策略（如全域訪問上限）組合以同時保障延遲與效果下限。

小結

現有 early-exit 策略可概括為：（距離／品質）門檻、訪問/時間預算、飽和/停滯檢測、上界裁剪、層間早停、與叢集感知等路線。實務上常採「一個保守的基準 + 一個自適應的飽和檢測 + 一個延遲上限」的多重保險，以在召回與延遲之間取得可控的權衡。

****
# 9/16

1. 比較 faiss hnswlib nmslib

看看有沒有其他參數能改但都只有efsearch、efconstruction、M

| hnswlib | faiss| nmslib |
| -------- | -------- | -------- |
| 最快的索引構建和最高的recall | 最均衡的整體效能 | 在小規模設定下表現出色 |

[A Comparative Study of HNSW Implementations for Scalable Approximate Nearest Neighbor Search](https://www.techrxiv.org/users/922842/articles/1311476-a-comparative-study-of-hnsw-implementations-for-scalable-approximate-nearest-neighbor-search)
****
2. 把用python做的hnsw檢索參數改成query與資料點的距離計算次數


****


****

# PQ

https://docs.google.com/presentation/d/1VaXNH7P2xxy25U75JSA_J8_pVq_zrFfMxBniX_OhfgA/edit?usp=sharing

* 分段：

把一個高維向量（例如 64 維）分成幾個小段（例如 8 段，每段 8 維）。
****
* 聚類：

對每一小段的數據（8 維小向量）進行 K-means 聚類，生成一組代表性的「中心點」。

假設 K=256

****

* 編碼：

用每個小段的「中心點編號」來表示原始向量，這樣就把高維向量壓縮成一個短向量。

例如:
假設一個原始向量，我們將它平均分成 8 段

每段都會有自己的一組聚類器（k-means），產生 256 個中心（k*=256）

找出該段向量 yᵢ 所屬的中心，得到中心編號 qᵢ(yᵢ)

用 8 bits 表示（因為 2⁸ = 256）

最後得到一組 8 × 8 = 64 bits 的 PQ 編碼（Quantization Index）

例如 [18, 130, 241, 3, 90, 45, 32, 9]


****


* Y軸：平方失真 D(q)（square distortion） ， 失真越小，代表壓縮後越接近原始向量

* X軸：編碼長度（code length），即整體 PQ 向量的長度

* 圖中不同線條代表不同的 m 值（分段數）：

m=1、m=2、m=4、m=8、m=16

* 每條曲線上的點對應於不同的 k* 值（每段聚類中心數目，例如 16, 64, 256, 1024）
****

* Code length = m × log2(k)

例如 m=8, k=256 時，code length = 8 × 8 = 64 bits

* 失真隨著 code length 增加而下降

越長的編碼越精細，誤差小

* 失真也隨 m 增加而下降

分更多段，更細的局部壓縮，更準確

* 固定碼長時， m 小的曲線比 m 大的曲線誤差小。

例如 64 bits 時，m=8, k=256 比 m=16, k=16 精度高

分太多段會讓每段維度變太小，每段資訊太少，聚類效果下降

****
## 查詢 (SDC ADC)


### SDC（Symmetric Distance Computation）

指查詢向量和數據庫中的向量都經過 PQ 量化

直接比較查詢向量和數據庫中向量的「短向量」（例如 [18, 130, ...]）

* 距離表

計算每段中 256 個聚類中心之間的距離

8 段，每段有 256×256 個距離值，組成一個距離表。
****
1. 壓縮查詢向量：

將查詢向量（64 維）按相同方式分成 8 段。

每段找到最近的聚類中心，得到一個 8 維短向量，例如 q(x) = [5, 200, 15, 100, 80, 60, 40, 20]。

1. 計算短向量距離：

對於數據庫中的每個短向量（例如 q(y) = [18, 130, 241, 3, 90, 45, 32, 9]），計算 q(x) 和 q(y) 之間的距離。

查詢時，只需根據 q(x) 和 q(y) 的編號，從距離表中查出每段的距離，然後加總。

距離 = 距離表[段1][5][18] + 距離表[段2][200][130] + ... + 距離表[段8][20][9]。
****
* 優點: 簡單、速度快

* 缺點 : 誤差較大

因為查詢向量和數據庫向量都經過量化，丟失了原始向量的細節，導致計算的距離與真實距離偏差較大。
****
### ADC（Asymmetric Distance Computation）

查詢向量保持原始向量，數據庫中的向量使用 PQ 量化後的短向量

1. 查詢向量分段：

將查詢向量（64 維）按相同方式分成 8 段，每段 8 維，但不進行量化，保留原始數據

2. 生成距離表：

對查詢向量的每段（8 維子向量），計算它與該段 256 個聚類中心的距離

生成一個距離表，包含 8 列 （對應 8 段），每列 256 個距離值

例如:

距離表[1][0] 表示查詢向量第 1 段與第 1 段聚類中心 0 的距離。
距離表[2][100] 表示查詢向量第 2 段與第 2 段聚類中心 100 的距離。

3. 計算距離：

對於數據庫中的短向量（例如 doc_i = [18, 130, 241, 3, 90, 45, 32, 9]），從距離表中查出每段的距離，然後加總：

距離 = 距離表[段1][18] + 距離表[段2][130] + 距離表[段3][241] + ... + 距離表[段8][9]。

****

* 優點: 精度更高

* 缺點 : 計算量稍大、距離表生成成本

因為查詢向量不同，每次查詢都需要生成一個新的距離表，這增加了少量計算負擔

****

### IVFADC

ADC/SDC還是窮舉（掃全部資料）。太慢。

用k-means，把向量分到不同 cell。
查詢時，找到最近的幾個 cell（比如 top-N cell）。
在這些 cell 內，用 ADC 計算距離。


1. 粗粒度量化（Coarse Quantization）
對數據集做 k-means，減少推理過程的搜索範圍，聚類計算殘差向量

* 對數據集做 k-means 聚類，生成 nlist 個中心
* 每個向量 x 根據歐氏距離分配到最近的中心 c_i

2. 計算殘差
* 計算殘差向量： x - c_i ，表示向量相對於其中心的偏移
* 可以讓所有分區的向量之間更加接近，因為它們分佈集中於原點附近，殘差向量使量化更精確

2. IVF

為每個中心 c_i 創建一個倒排鏈，記錄每個簇的向量資訊，儲存該簇內殘差的 PQ 編碼

3. PQ

* 收集所有簇的殘差向量，統一形成殘差數據集。
* 乘積量化不是針對每個分區單獨執行，是同時對所有分區的殘差做乘積量化

4. 查詢 (根據查詢向量 q 找到 top-k 最近鄰)

1. 粗搜索
計算 q 與所有簇中心的距離，選出最近的 nprobe 個簇
3. 精搜索
* 對選中的 nprobe 個簇，計算查詢殘差：q - c_i
* 每個分區的q殘差向量都不相同. 需要為每個q的殘差向量單獨計算距離表
* 用ADC， 算 q - c_i 與倒排鏈中殘差向量的 PQ 碼距離

****
* 為甚麼IVFADC 在 PQ 階段對所有簇的殞差向量進行統一處理，而不是分開處理每個簇

已處理全局分區，專注於殞差的局部偏移

****
### SDC ADC IVFADC 比較

* recall隨著碼長增加而上升。
* 固定碼長時(256)，m 小的曲線（如 m=8 ）比 m 大的曲線（如 m=16 ）recall更高。
****
* recall隨碼長增加上升，類似SDC，但整體值更高。
* 固定碼長時，ADC表現優於SDC
****
* recall隨碼長增加上升
* 粗量化參數 k （中心數），分配到最近的w個區域 ，w 不足時，可能漏掉真鄰居
* 固定碼長時， k 和 w 越大，recall越高
****

# 偵測晶體長晶過程中的斷線問題
## 資料集介紹
* 二層子目錄的資料夾名稱前半段記錄拍攝的時間與給定的序號
* images為一連串連續拍攝影像，以日期時間命名，例如20240602_093811_CCD .jpg
* 影像有發生斷線，即會有對應的20240602_093811_CCD.txt
## 資料集統計表
## 晶向斷線範例
## 座標框的標記格式
**class x_center y_center width height**

* class: 只有斷線，class都是設成0
* x_center: x_center為方框中心點x座標/圖片寬度
* y_center: y_center 為方框中心點y座標/圖片高度
* width: width為方框寬度/圖片寬度
* height: height為方框高度/圖片高度

剛好是YOLO的標註格式
## 模型評估方式
* 當 IoU ≥ 0.3 時視為命中。以此計算 F1-score作為主要判斷依據。
* 模型能夠在斷線首次出現的圖片或其鄰近幀中正確偵測，即視為及時命中。反之若偵測時間落後越多，分數將相應降低。
* 

## 訓練模型
### 模型選擇YOLOV8
* 因為題目給的label格式剛好是yolo的標註格式可以直接用不需額外轉換
* 推論速度極快
* YOLOv8 有 ultralytics 套件 ，不用下載其他東西
* 每張影像可能存在多個斷線區域，YOLO 能同時預測多個邊框

### 前處理
1. 建立資料夾結構

* 晶向分類：

classification/
├── train/
│ ├── 100/
│ ├── 111/
│ └── 776/
├── val/
└── test/

* 斷線偵測:

detection/
├── 100/
│ ├── train/images + labels/
│ ├── val/images + labels/
│ └── test/images + labels/
├── 111/
└── 776/
2. 資料分割
* 訓練集0.8、驗證集0.1、測試集0.1

3. 圖片前處理
* 縮放到640x640
* **提升對比度1.2 倍**

### 訓練模型
1. 訓練分類模型
2. 訓練偵測模型

## 結果
1. 使用 classification_model 分類晶向

Accuracy: 0.7067

2. 使用 detection_models 偵測斷裂

- 100 晶向：210 張圖像，318 個實例
- Precision: 0.8484（84.84%）
- Recall: 0.6509（65.09%）
- 111 晶向：212 張圖像，326 個實例
- Precision: 0.7708（77.08%）
- Recall: 0.5675（56.75%）
- 776 晶向：134 張圖像，195 個實例
- Precision: 0.7941（79.41%）
- Recall: 0.2769（27.69%）

3. 使用 classification_model + detection_models

- TP（有標註、有預測）: 593
- FP（無標註、有預測）: 23
- FN（有標註、無預測）: 123
- TN（無標註、無預測）: 0

===== 綜合評估結果 =====
- Precision: 0.963
- Recall: 0.828
- F1 Score: 0.890

# NSW
## Small world
* 同質性：點與點之間基於相似性連接。
* 弱連接：點與點之間通過隨機長距離邊實現快速導航。
* 導航性：是否能從任意節點，用局部資訊，有效率地「導航」到目標節點的能力。


## 在NSW中K近鄰檢索的過程
通過黑色鄰邊來找最近鄰節點， 通過紅色長邊來實現不同類節點之間的快速檢索。

q：查詢點。
m：隨機重啟的次數（重覆搜索的輪數）。
k：要返回的最近鄰數量。
輸出：
result：包含與 q 最接近的 k 個節點的集合。
數據結構：
tempRes：臨時存儲每次搜索的候選結果（TreeSet，按距離排序）。
candidates：存儲當前待檢查的候選節點（priority queue，按距離排序）。
visitedSet：記錄已訪問的節點，避免重覆訪問。
result：存儲最終的 k 個最近鄰結果。

K-NNSearch(object q,integer:m,k)

1 TreeSet[object]tempRes, candidates, visitedSet, result

   # NSW 的單次貪婪搜索可能陷入局部最優，
   # 因此做 m 次（每次從不同的隨機入口點開始），增加找到全局最近鄰的機會，提高準確性
2  for(i<-0; i<m; i++) do:
    
    # 1.
    #  隨機選擇1個元素，放入到candidates當中
3   put random entry point in candidates
    # 臨時存儲設為空
4   tempRes<-null

5   repeat:
     
     # 2.
     #  candidates選與查詢點最近的c，把c移出candidates
6    get element c closest from candidates to q
7    remove c from candidates

    # 3.
    # 如果目前 candidate 的「最近元素」都已經比 result 裡第最後一名還遠，就視為可以終止擴散了
    # 效率與精度之間的 trade-off，
    # 有一定機率會錯過最佳解，做 m 次可能能夠彌補單次錯過的情況
9   if c is further than k-th element from result
10   than break repeat
     
     # 4.
11   # 找出與c連結的所有點，如果不再visited Set 把她加入visited Set, candidates, tempRes
12   for every element e from friends of c do:
13    if e is not in visited Set than
14     add e to visited Set, candidates, tempRes

     # candidates 變空（無更多節點可檢查）。
     # 滿足停止條件（步驟 9：c 的距離大於 result 中第 k 個節點的距離）。
16   end repeat 

17   # 把臨時結果存入 result 
18   add objects from tempRes to result
19  end for
    
20  return best k elements from result

* 隨機選擇一個點作為查詢起始點entry_point，把該點加入candidates中，同時加入visitedset
* 從candidates中刪除點c。
* 從candidates中選擇距離查詢點最近的點c，和results中距離查詢點最遠的點d進行比較，如果c和查詢點q的距離大於d和查詢點q的距離，則結束查詢

* 查詢c的所有鄰居e，如果e已經在visitedset中存在則跳過，不存在則加入visited Set, candidates, tempRes

## Delaunay 三角剖分
德勞內

* 唯一性：無論從點集的任何位置開始建網，Delaunay三角剖分是唯一的

**目標是讓相鄰的點在空間距離上盡可能“近”，並且生成的三角形盡可能“規整”**（避免過於尖銳或扁平的三角形）。這種方法在 NSW 和 HNSW 算法中常用於構建圖的鄰居連接，因為它**能確保節點之間的邊（連接）具有良好的空間接近性**。

* 空圓特性

Delaunay三角剖分是唯一的（任意四點不能共圓），在Delaunay三角剖分中任一三角形的外接圓內不會存在其它點。即滿足Delaunay邊的定義。

* 最大化最小角特性

在所有可能的三角剖分中，Delaunay三角剖分所形成的三角形最小的角度會是最大的。

## NSW 網絡構建

* 理想情況：

用 Delaunay 三角剖分把它們連成三角形，然後再加一些“跳躍邊”（隨機長邊），讓圖可以快速從一個點跳到遠處的點。這就形成了一個小世界網絡，適合快速搜索。

* 實際挑戰：

Delaunay 三角剖分在高維空間計算量太大，不適合實時構建。因此，NSW 采用了一種近似方法：**隨機插入節點，利用插入的隨機性引入全局跳躍邊並通過最近鄰搜索模擬 Delaunay 邊的局部連通性**。

**透過節點隨機插入來引入隨機性**

建立 NSW 圖時，是一個一個地把資料點加進圖裡(順序是隨機的)，
而這些點的加入不是照距離、也不是照ID或排序。
這樣就有機會產生一些非預期、遠距離的連結（第一個加入的節點可能會在圖的一角，結果第 100 個加入的點卻在很遠的地方，因為圖還很稀疏，這兩個就有可能直接連起來）。**幫助搜尋時快速跳躍遠區域**。

**利用已有節點模擬建構 Delaunay 邊來引入同質性**

每插入一個新點，NSW 會找出目前圖中「跟它最接近的幾個點」來連線。彼此距離近、特徵相似。**保證局部的連接精準性**。

* 把一個新的節點（new_object）插入到圖中

# new_object：你要插進圖的那個新節點
# f：想要連接的「最近的 f 個鄰居」數量（連幾條邊）
Nearest_Neighbor_Insert(object: new_object, integer: f, integer: w)

# 幫這個新節點 new_object 找出圖中距離它最近的 f 個點。
1 SET[object]: neighbors <- k-NNSearch(new_object, w, f);

# 把新節點和剛剛找到的 f 個近鄰節點建立「雙向連線」
2 for(i <- 0; i < f; i++) do
3   neighbors[i].connect(new_object);
4   new_object.connect(neighbors[i]);

# HNSW

## HNSW 中的 Beam Search

搜索過程：HNSW 使用一種變體的 Beam Search，具體取決於層級：

在高層（除了基層外），Beam Search 的寬度（beam width）為 1。這意味著在每個層級，算法只選擇與查詢向量距離最近的單個節點作為下一個層級的起點。
在基層（Base layer），Beam Search 的寬度為 p （在 Faiss 中對應參數 $ efSearch ），表示在候選優先級隊列中，每次從隊列頂部彈出一個節點，評估其相鄰節點，並將距離查詢向量最近的 p 個節點的相鄰節點加入隊列進行進一步搜索。

工作原理：搜索從頂層的單個節點開始，通過 1 跳 Beam Search 收斂到基層的一個相對接近真實最近鄰的起點。隨後在基層使用寬度為 $ p $ 的 Beam Search，逐步擴展搜索範圍，直到滿足終止條件（例如找到頂部 p 個最佳候選節點）。

## 基本特性

1. 在 Layer = 0 層中，包含了連通圖中所有的點。
2. 隨著層數的增加，每一層的點數逐漸減少並且遵循指數衰減。
3. 從某個點所在的最高層往下的所有層中均存在該節點。
4. 在對 HNSW 進行查詢的時候，從最高層開始檢索。

* INSERT(): 將新資料點 q 插入 HNSW 圖中
* SEARCH-LAYER(): 在指定層 lc 中，從入口點 ep 開始，找出最多 ef 個離查詢點 q 最近的節點
* SELECT-NEIGHBORS-SIMPLE(): 從候選集合中挑選距離查詢點 q 最近的 M 個節點。
* SELECT-NEIGHBORS-HEURISTIC(): 從候選集合中挑選最多 M 個對後續搜尋最有效率的鄰居點
* K-NN-SEARCH(): 從圖中找出與查詢點 q 最接近的 K 個鄰居

## Algorithm 1: INSERT()
把新的資料點 q 插入到 HNSW 多層圖中，並建立與其他點的連結，使得整個圖仍然保持「小世界圖」的特性

# M: 節點可以與最多幾個節點相連

INSERT(hnsw, q, M, Mmax, efConstruction, mL)

1 W ← ∅ # 存放目前找到的最近的點
2 ep ← get enter point for hnsw # 進入點
3 L ← level of ep # 進入點的層數

  # 1.
  # 為新的節點 q 隨機產生一個層數 l，決定它會出現在第幾層。
4 l ← ⌊-ln(unif(0..1))∙mL⌋ 

  # 2.
  # 從最高層 L 一直往下走到 l+1 層
  # 每一層選出「離 q 最近的那個」，當作下一層搜尋的起點
5 for lc ← L … l+1
6     W ← SEARCH-LAYER(q, ep, ef=1, lc)
7     ep ← get the nearest element from W to q


8 for lc ← min(L, l) … 0

      # 3.
      # 從 ep（入口點）開始找出最多 ef 個與 q 距離最近的節點當候選人
9     W ← SEARCH-LAYER(q, ep, efConstruction, lc)

      # 4.
    　#  以W為候選人選出最多 M 個「對目標點 q 最有幫助」的鄰居點
      #  能選alg. 3 or alg. 4 
10    neighbors ← SELECT-NEIGHBORS(q, W, M, lc) 
      
      # 5.
      # 建立q和neighbors的雙向連接
11    add bidirectionall connectionts from neighbors to q at layer lc
      
      # 6.
      # 確保每個鄰居的連線數不超過 Mmax
12    for each e ∈ neighbors 
13         eConn ← neighbourhood(e) at layer lc
14         if │eConn│ > Mmax 
15             eNewConn ← SELECT-NEIGHBORS(e, eConn, Mmax, lc)
16             set neighbourhood(e) at layer lc to eNewConn
      
      # 入口點從單一節點擴展成多個節點
17    ep ← W

   # 如果新節點 q 的層數比原本的最高層 L 還高，把整個圖的進入點更新為 q。
   # 下次要進圖查詢，就從 q 開始走
18 if l > L
19    set enter point for hnsw to q

## Algorithm 2: SEARCH-LAYER()
在 HNSW 某一層進行「近似鄰居搜尋」
查詢元素 q，從 ep（入口點）開始，在第 lc 層中，找出最多 ef 個與 q 距離最近的節點。

SEARCH-LAYER(q, ep, ef, lc)
   
1  v ← ep # 已拜訪過的節點，初始只有入口點 ep
2  C ← ep # 候選節點集合（等著被處理的），初始只有入口點。
3  W ← ep # 動態儲存找到的最近鄰居，初始只有入口點。

   # 只要候選集合 C 不為空，就持續搜尋。每次挑出目前看起來最接近q的點來探索它的鄰居。
4  while │C│ > 0

       # 1.
       # 從候選集合 C 中取出並移除距離查詢點 q 最近的元素 c，初始只有入口點
5      c ← extract nearest element from C to q
       
       # 2. 
       # f 是目前「已經找到的最近鄰」中最遠離 q 的節點。
6      f ← get furthest element from W to q
       
       # 3.
       # 效率關鍵
       # C 是按照距離 q 從近到遠排序的，所以接下來從 C 拿出來的點，一定只會比 c 更遠
       # 如果 c 比 f 還遠，就能停止了
       # 雖然有可能「c 的鄰居更近」，但可能信不高為了效率犧牲他
7      if distance(c, q) > distance(f, q)
8          break 

       # 4.
       # 探索節點 c 在第 lc 層的所有鄰居 e。
9      for each e ∈ neighbourhood(c) at layer lc 

           # e沒被拜訪過
10         if e ∉ v
11             v ← v ⋃ e

               # 取得目前最近鄰集合 W 中最遠的節點 f。
12             f ← get furthest element from W to q
               
               # 5.
               # 若 鄰居 比 f 更近，或 W 中元素還沒到要找的目標個數，把鄰居加進W
13             if distance(e, q) < distance(f, q) or │W│ < ef
14                 C ← C ⋃ e
15                 W ← W ⋃ e
                   # W 的大小不超過 ef
16                 if │W│ > ef
17                     remove furthest element from W to q
18 return W

## Algorithm 3: SELECT-NEIGHBORS-SIMPLE()
**從候選節點中**挑選 M 個最近鄰

# q: 查詢點
#　C: 候選集合
#　M: 要選出幾個鄰居

SELECT-NEIGHBORS-SIMPLE(q, C, M)

Input: base element q, candidate elements C, number of neighbors to return M
Output: M nearest elements to q

return M nearest elements from C to q

## Algorithm 4: SELECT-NEIGHBORS-HEURISTIC()
在第 lc 層從**候選集合 C 裡**，選出最多 M 個「對目標點 q 最有幫助」的鄰居點（不只是最近的）

SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keep-
PrunedConnections)
   
1  R ← ∅ # 用來存放最後選中的鄰居
2  W ← C # working queue for the candidates
   
   # 1. 
   # 如果 extendCandidates 設成 true
   # 擴大候選人選，把候選節點的鄰居加入候選集
3  if extendCandidates 
4      for each e ∈ C
5          for each eadj ∈ neighbourhood(e) at layer lc
6              if eadj ∉ W
7                  W ← W ⋃ eadj

8  Wd ← ∅ # 用來放被丟棄的

   # 當還有候選人且選進來的鄰居還沒滿 M 個
9  while │W│ > 0 and │R│< M
       
       # 2.
       # 從 W 裡拿出一個最接近 q 的節點 e
10     e ← extract nearest element from W to q

       # 3.
       # 不要 e 太接近某個已經被選進來的鄰居
       # 如果e 和 q 的距離小於 e 和 R 中任何一個節點的距離
       # 就要把它加入 R。
       # 有助於找到「分布均勻的鄰居集合」，讓未來查詢能更有效率地跳躍整個圖
11     if e is closer to q compared to any element from R
12         R ← R ⋃ e

       # 先放進丟棄隊列 Wd，之後也許會再考慮。
13     else
14         Wd ← Wd ⋃ e
   
   # 4.
   # 設 keepPrunedConnections = true
   # 從 Wd 裡按照距離 q 的遠近排序補進 R，直到補滿 M 個為止。
15 if keepPrunedConnections 
16     while │Wd│> 0 and │R│< M
17         R ← R ⋃ extract nearest element from Wd to q

18 return R

1. 如果extendCandidates被設置把候選節點的鄰居加入候選集
2. W的大小大於0,R的大小小於M:
3. 從W中提取離q最近的元素e。
4. 如果e 和 q 的距離小於 e 和 R 中任何一個節點的距離，就要把它加入 R
5. 否則，將e加到Wd。
6. 如果設置了keepPrunedConnections(即true):
7. 而Wd的大小大於0,R的大小小於M:
8. 從Wd中提取到q最近的元素e，加到R中。
9. 返回R。

## Algorithm 5: K-NN-SEARCH()
找q 的 K 個最近鄰

# K：真正想要的最近鄰個數
# ef：搜尋時保留的候選節點數量
# 通常設得比 K 大很多如：ef = 50，K = 10
# ef 越大，準確率越高，但速度越慢
K-NN-SEARCH(hnsw, q, K, ef)

1 W ← ∅ # 目前找到的最近鄰集合
2 ep ← get enter point for hnsw # 選擇一個進入點
3 L ← level of ep # 取得 ep 所在的最上層
   
  # 1.
  # 從頂層一直往底層走。找到一個比較好的初始點
  # 不好的起點可能會導致找不到真正的最近鄰、搜尋時間變長
4 for lc ← L … 1

      # 從 ep（入口點）開始，在第 lc 層中，找出最多 ef=1 個與 q 距離最近的節點。
5     W ← SEARCH-LAYER(q, ep, ef=1, lc)

      # 取得目前找到的最接近查詢點 q 的節點，這個作為下一層搜尋的起點。
6     ep ← get nearest element from W to q

  # 2.
  # 用找到的比較好的初始點ep，進入底層開始認真做 ef 次數的鄰居搜尋
7 W ← SEARCH-LAYER(q, ep, ef, lc =0)

8 return K nearest elements from W to q

1. 對於每一層lc，從L到1
2. 取得目前找到的最接近查詢點 q 的節點，這個作為下一層搜尋的起點。
3. 用找到的比較好的初始點ep，進入底層開始認真做 ef 次數的鄰居搜尋
4. 返回W中最接近的K個元素作為輸出。