查找相似向量

提高查找相似向量的速度

任何非暴力搜尋的搜尋方法，都會一定程度上的降低搜索品質。需要在搜索品質和速度進行 trade-off。

可用在將向量資料庫分群，以便縮小查找相似向量的範圍。

迭代計算群心，直到收斂

依據離群心的遠近分類

相近的向量有可能被分到不同群

可以透過「用更多類，並搜索多個最近群」來緩解問題

可以找其他 ANN (Approximate Nearest Neighbors) 演算法來面對該問題

讓越相似的向量越容易碰撞，找相似向量就在同個 bucket 找

此處挑一種方式舉例，此處用隨機超平面舉例。

可以在空間中隨機生成多個 (n-1) 維度的超平面，將兩邊分類為 0 和 1。距離較遠的點對被切割開的機率會比距離較近的點對還大。用這樣的方法，會讓相近的點對生出的 Hash 值較接近。

大量的高維向量會造成大量的記憶體開銷

把同一群的向量都用群心向量代替，是一種有損壓縮。

但這樣需要另外的空間來存取 codebook (向量對應表)，在某些情況不見得比原本的向量還省空間，甚至可能花更多。

n 維的向量可能需要 $2^{\frac{n}{2}}$ 的 class 才可以較好的分類 (來源未知)

可以透過把高維向量切割成多個低維子向量個別處理再合併來緩解該問題。

該方法稱為 Product Quntization (PQ)

對於世界上兩個互不相識的人，只需要六個中間人就可以建立起連結。

我們想找對於某個目標向量而言最相似的向量。

先隨機找一個點，找他的相鄰節點誰和目標向量最相近，並反覆此過程，直到所有相鄰節點都沒有自己離目標相近。

六度分隔理論讓我們推測這過程可能很快就會結束。

我們得幫這些向量建立圖關係。

但靠 Delaunay triangulation algorithm，有可能隨機的向量和目標向量距離很遠，查找很慢。

NSW 的實際做法是將所有向量隨機地放回圖中，並和最近的 k 個點連接。

只看較短的連接，會發現和 Delaunay triangulation algorithm 產的圖相近，可以進行細粒度的查找。只看較長的連接，則可達到快速導航的效果。

建立一個分層結構，越上層的點越稀疏、連線越長。

和 NSW 相比，讓粗粒度到細粒度的導航過程更加穩定。

但占用的記憶體空間更大。