向量檢索

ANN(Approximate Nearest Neighbor)搜索的方法分為三大類：基于樹的方法、哈希方法、矢量量化方法。

基于樹的方法

基于樹的方法采用樹這種數據結構的方法來表達對全空間的劃分，其中KD樹和Annoy是兩種經典的方法。

哈希方法

·???????? Local Sensitive Hashing

LSH開源工具包

·???????? LSHash

·???????? FALCONN

FALCONN是經過了極致優化的LSH，其對應的論文為NIPS 2015 Practical and Optimal LSH for Angular Distance，FALCONN的索引構建過程非常快，百萬量級的數據，維度如果是128維，其構建索引時間大概2-3min，實時搜索可以做到幾毫秒的響應時間。另外談一下數據規模問題。對于小數據集和中型規模的數據集(幾個million-幾十個million)， FALCONN和NMSLIB是一個非常不錯的選擇，如果對于大型規模數據集(幾百個million以上)，基于矢量量化的Faiss是一個明智的選擇。

當然，FALCONN還不是很完善，比如對于數據的動態增刪目前還不支持，具體的討論可以參見Add a dynamic LSH table。其實這不是FALCONN獨有的問題，NMSLIB目前也不支持。一般而言，動態的增刪在實際應用場合是一個基本的要求，但是我們應注意到，增刪并不是毫無限制的，在增刪頻繁且持續了一段時間后，這是的數據分布已經不是我們原來建索引的數據分布形式了，我們應該重新構建索引。在這一點上，Faiss支持數據的動態增刪。

矢量量化方法

矢量量化方法，即vector quantization，其具體定義為：將一個向量空間中的點用其中的一個有限子集來進行編碼的過程。在矢量量化編碼中，關鍵是碼本的建立和碼字搜索算法。比如常見的聚類算法，就是一種矢量量化方法。而在ANN近似最近鄰搜索中，向量量化方法又以乘積量化(PQ, Product Quantization)最為典型。在之前的博文基于內容的圖像檢索技術的最后，對PQ乘積量化的方法做過簡單的概要。在這一小節里，小白菜結合自己閱讀的論文和代碼對PQ乘積量化、倒排乘積量化(IVFPQ)做一種更加直觀的解釋。

·???????? PQ乘積量化

·???????? 倒排乘積量化

高維空間最近鄰逼近搜索算法評測

關于索引結構，有千千萬萬，而在圖像檢索領域，索引主要是為特征索引而設計的一種數據結構。關于ANN搜索領域的學術研究，Rasmus Pagh發起的大規模相似搜索項目ANN-Benchmarks、Faiss以及ann-benchmarks都有對一些主流的方法做過對比。雖然三個對比的框架對不同方法的性能均有出入，但一些主流方法的性能差異是可以達成共識的，比如基于圖方法的ANN其召回率均要優于其他方法。在工業上，常用的索引方法主要以倒排、PQ及其變種、基于樹的方法（比如KD樹）和哈希（典型代表LSH和ITQ）為主流。

FAISS

faiss庫包含線性檢索方法（BLAS庫優化）、哈希方法的實現（LSH）及矢量量化方法的實現（PQ、IVFPQ）。faiss庫的一大優勢是支持索引的動態增刪。

faiss是為稠密向量提供高效相似度搜索和聚類的框架。由Facebook AI Research研發。 具有以下特性。

1、提供多種檢索方法

2、速度快

3、可存在內存和磁盤中

4、C++實現，提供Python封裝調用。

5、大部分算法支持GPU實現

Faiss具有以下特點：

1，支持兩種相似性計算方法：L2距離（即歐式距離）和點乘（歸一化的向量點乘即cosine相似度）。

2，按照是否編碼壓縮數據可以分為兩類算法，使用壓縮的算法可以在單臺機器上處理十億級別的向量規模。

3，并非線程安全的——不支持并行添加向量或搜索與添加的并行；僅在CPU模式下支持并行搜索。

4，只有繼承了IndexIVF 的算法才支持向量的 remove() 操作，但由于是連續存儲，remove的時間復雜度是 O(n)，建議另外維護一個列表記錄被刪除的或尚存的向量。

5，faiss 針對批量搜索做了優化。

6，IndexPQ, IndexIVFFlat, IndexIVFPQ, IndexIVFPQR?需要訓練。

7，不支持重新訓練，建議新建一個索引。

8，只接受 32-bit 浮點類型的輸入數據。

挑一個合適的 Index

Faiss 提供了很多 Index，那么如何根據實際情況選擇 Index 呢？

可以以下根據幾個必要的問題，來找到自己合適的 Index 類型。

需要注意：

以下都通過 index_factory 字符串來表示不同 Index，如果需要參數，使用相應的 ParameterSpace 參數

1. 是否需要精確的結果？

使用 “Flat”

可以保證精確結果的唯一索引是 IndexFlatL2。

它為其他索引的結果提供基線。

它不壓縮向量，但不會在它們之上增加開銷。 它不支持添加id（add_with_ids），只支持順序添加，因此如果需要 add_with_ids，請使用“IDMap,Flat”。

是否支持 GPU： yes

2. 是否關心內存？

請記住，所有Faiss索引都存儲在RAM中。 以下的這些考慮是，如果我們不需要精確的結果而 RAM 又是限制因素，那么，我們就需要在內存的限制下，來優化精確-速度比（precision-speed tradeoff）。

如果不需要關心內存：“HNSWx”

如果你有大量的RAM或數據集很小，HNSW 是最好的選擇，它是一個非常快速和準確的索引。 x 的范圍是[4, 64]，它表示了每個向量的鏈接數量，越大越精確，但是會使用越多的內存。

速度-精確比（speed-accuracy tradeoff）可以通過 efSearch 參數來設置。 每個向量的內存使用是情況是（d * 4 + x * 2 * 4 ）。

HNSW 只支持順序添加（不是add_with_ids），所以在這里再次使用 IDMap 作為前綴（如果需要）。 HNSW 不需要訓練，也不支持從索引中刪除矢量。

是否支持 GPU： no

如果有些擔心內存：“…,Flat”

“…” 表示必須事先執行數據集的聚類。 在聚類之后，“Flat”只是將向量組織到不同桶中，因此它不會壓縮它們，存儲大小與原始數據集的大小相同。 速度和精度之間的權衡是通過 nprobe 參數設置的。

是否支持 GPU： yes（但是聚類方法也需要支持GPU）

如果相當關心內存：“PCARx,…,SQ8”

如果存儲整個向量太昂貴，則執行兩個操作：

使用尺寸為x的PCA以減小尺寸

每個矢量分量的標量量化為1個字節。

因此，總存儲量是每個向量 x 個字節。

是否支持 GPU： no

如果非常關心內存：“OPQx_y,…,PQx”

PQx 代表了通過一個product quantizer壓縮向量為 x 字節。 x 一般 <= 64，對于較大的值，SQ 通常是準確和快速的。

OPQ 是向量的線性變換，使其更容易壓縮。 y是一個維度：

y是x的倍數（必需）

y <= d，d為輸入向量的維度（最好）

y <= 4*x（最好）

是否支持 GPU： yes（注意：OPQ轉換是在軟件中完成的，但它不是性能關鍵）

3. 數據集有多大

這個問題用于選擇聚類選項（就是上面的那些”…“）。 數據集聚集到存儲桶中，在搜索時，只訪問了一小部分存儲桶（nprobe 個存儲桶）。 聚類是在數據集矢量的代表性樣本上執行的，通常是數據集的樣本。 我們指出該樣本的最佳大小。

如果向量數量低于1百萬：”…,IVFx,…”

當數據集的數量為 N 時，那么 x 應該處于 4 * sqrt(N) 和 16 * sqrt(N) 之間。 這只是用k-means聚類向量。 你需要 30 * x 到 256 * x 的矢量進行訓練（越多越好）。

是否支持 GPU： yes

如果向量數量位于1百萬-1千萬之間：”…,IMI2x10,…”

（這里x是文字x，而不是數字）

IMI在訓練向量上執行具有2^10個質心的 k-means，但它在向量的前半部分和后半部分獨立地執行。 這將簇的數量增加到 2^(2 * 10)。您將需要大約64 * 2 ^ 10個向量進行訓練。

是否支持 GPU： no

如果向量數量位于1千萬-1億之間：”…,IMI2x12,…”

與上面相同，將10替換為12。

是否支持 GPU： no

如果向量數量位于1億-10億之間：”…,IMI2x14,…”

與上面相同，將10替換為14。

是否支持 GPU： no

索引方法匯總：

Faiss CPU的代碼規范

沒有public/private

Faiss中所有的C++對象結構，沒有public/private概念，所有的字段都可以直接訪問。

對象所有權

大部分情況下，Faiss對象都是可拷貝的。有一些例外的地方，對象A包含一個對象B的指針，在這種情況下，在A中有一個boolean類型的標志own_fields，這個標識用于指明當對象A被刪除時對象B是否要被刪除，構造時通常我們將該變量值設為false，即不是B的擁有者，當然如果在調用代碼中失去了對B的引用，這可能會導致內存泄漏，所以如果我們想A在銷毀時B跟著銷毀，需要將其設為True，對于以下類的構造我們要注意：

Class? ? ? ? ? ? ? ? ? ? ? ?????????????????field

IndexIVF? ? ? ? ? ?????????????????????quantizer

IndexPreTransform? ???????????????chain

IndexIDMap??? ????????????????????????index

IndexRefineFlat??????? ????????????base_index

線程和異步調用

線程安全

Faiss CPU對于并發檢索和其它不更改index的操作都是線程安全的，多線程改變index的函數需要實現互斥。

內部線程

Faiss本身有多種不同的內部線程，對于CPU的Faiss，index上3中基本操作（train，add，search）都是多線程的。線程是通過OpenMP，以及多線程的BLAS實現。我們可以通過環境變量OMP_NUM_THREADS或者調用omp_set_num_threads(10)方法。

如果查詢或添加單個向量，Faiss是不會使用多線程的。

查詢的性能

最好的提升查詢QPS是進行批量提交。如果只是一個向量查詢，那將只會在調用線程中執行。

內部線程的性能（OpenML）

調整OpenML線程數量對性能提升有時候并不是特別顯著，在一些機器架構中，將線程數量設置的比內核數量稍微小點，有時候執行效率會更高。例如在Intel E5-2680 v2中，將線程數設置為20而不是默認的40，效果會更好。

如果使用OpenBLAS、BLAS實現，將線程策略設置為PASSIVE會更好：

export OMP_WAIT_POLICY=PASSIVE

異步搜索

對于包含以下一些計算的search操作，并行計算會更好：

·???????? 單線程計算

·???????? 等IO

·???????? GPU計算

對于Faiss CPU，和其他多線程計算（如其它searcher）并行化并沒有什么幫助，因為這樣反而會導致太多的線程從而降低正題性能。

3D+ARVR EI企業智能 EI創新孵化Lab

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。