Faiss核心算法實現
Faiss是FAIR出品的一個用于向量k-NN搜索的計算庫，其作用主要在保證高準確度的前提下大幅提升搜索速度。
Faiss 對一些基礎的算法提供了非常高效的實現。
- 聚類Faiss提供了一個高效的k-means實現
- PCA降維算法
- PQ(ProductQuantizer)編碼/解碼：PQ優(yōu)化了向量距離計算的過程，但是假如庫里面的向量特別多，每一個查詢向量依舊要進行很多次距離計算，效率依舊還是不夠高
全量構建索引
- 原始向量文件
- Train
- Add
- Faiss索引文件
增量索引文件
- Faiss 索引文件
- Add
- Faiss 索引文件
Faiss本質上是一個向量（矢量）數據庫，對于數據庫來說，時空優(yōu)化是兩個永恒的主題，即在存儲上如何以更少的空間來存儲更多的信息，在搜索上如何以更快的速度來搜索出更準確的信息。
Faiss的核心原理
- Product Quantizer, 簡稱PQ.
- Inverted File System, 簡稱IVF.
IVF本身的原理比較簡單粗糙，其目的是想減少需要計算距離的目標向量的個數，做法就是直接對庫里所有向量做KMeans Clustering，假設簇心個數為1024，那么每來一個查詢向量，首先計算其與1024個粗聚類簇心的距離，然后選擇距離最近的top N個簇，只計算查詢向量與這幾個簇底下的向量的距離，計算距離的方法就是前面說的PQ，Faiss具體實現有一個小細節(jié)就是在計算查詢向量和一個簇底下的向量的距離的時候，所有向量都會被轉化成與簇心的殘差，這應該就是類似于歸一化的操作，使得后面用PQ計算距離更準確一點。使用了IVF過后，需要計算距離的向量個數就少了幾個數量級，最終向量檢索就變成一個很快的操作。
