IVF_PQ
IVF_PQ索引是一種基於量化的索引演算法,用於高維空間中的近似近鄰搜尋。雖然速度不如某些基於圖的方法,但IVF_PQ通常需要較少的記憶體,因此是大型資料集的實用選擇。
概述
IVF_PQ是Inverted File with Product Quantization 的縮寫,是一種結合索引與壓縮的混合方法,用於有效率的向量搜尋與檢索。它利用兩個核心元件:倒轉檔案 (IVF)與乘積量化 (PQ )。
IVF
IVF 就像是在書本中建立索引。您不需要掃描每一頁 (或在我們的情況下,掃描每一個向量),而是在索引中查找特定的關鍵字(群組),以快速找到相關的頁面 (向量)。在我們的情況中,向量會被歸類為叢集,演算法會在幾個與查詢向量接近的叢集內進行搜尋。
以下是其運作方式:
- 聚類:使用 k-means 之類的聚類演算法,將向量資料集分為指定數量的叢集。每個叢集都有一個中心點(叢集的代表向量)。
- 分派:每個向量會被分派到其中心點最接近的叢集。
- 反向索引:建立一個索引,將每個群集的中心點對應到分配給該群集的向量清單。
- 搜尋:搜尋最近鄰居時,搜尋演算法會比較您的查詢向量與群集中心點,並選擇最有希望的群集。然後將搜尋範圍縮小到這些選定叢集中的向量。
要瞭解更多技術細節,請參閱IVF_FLAT。
PQ
Product Quantization (PQ)是一種高維向量的壓縮方法,可大幅降低儲存需求,同時實現快速的相似性搜尋作業。
PQ 過程包含以下關鍵階段:
PQ-Process-1
- 尺寸分解:該演算法首先將每個高維向量分解為
m
大小相等的子向量。此分解將原始的 D 維空間轉換為m
不相交的子空間,其中每個子空間包含D/m維。參數m
控制分解的粒度,並直接影響壓縮比。 - 子空間編碼本製作:在每個子空間中,演算法應用k-means 聚類來學習一組代表性向量 (中心點)。這些中心點共同形成該子空間的編碼簿。每個編碼本的中心點數量由參數
nbits
決定,其中每個編碼本包含 2^nbits 的中心點。例如,如果nbits = 8
,每個編碼本將包含 256 個中心點。每個中心點都會被指派一個唯一的nbits
位元索引。 - 向量 量化:對於原始向量中的每個子向量,PQ 會使用特定的度量類型在對應的子空間中找出其最近的中心點。此過程能有效地將每個子向量映射到編碼簿中最接近的代表向量。與其儲存完整的子向量座標,不如只保留匹配中心點的索引。
- 壓縮表示:最後的壓縮表示由
m
索引組成,每個子空間一個,統稱為PQ 編碼。此編碼可將儲存需求從D × 32位元 (假設為 32 位元浮點數) 減少到m×nbits位元,在保留近似向量距離能力的同時,達到大幅壓縮的效果。
有關參數調整與最佳化的詳細資訊,請參閱索引參數。
壓縮範例
考慮一個使用 32 位元浮點數的D = 128維向量。使用 PQ 參數m = 64(子向量) 和nbits = 8(因此每個子空間的中心點數為k =2^8= 256),我們可以比較儲存需求:
- 原始向量:128 維 × 32 位元 = 4,096 位元
- PQ 壓縮向量:64 個子向量 × 8 位元 = 512 位元
這表示儲存需求減少了 8 倍。
使用 PQ 計算距離
當使用查詢向量執行相似性搜尋時,PQ 可透過下列步驟有效率地計算距離:
查詢預處理
- 將查詢向量分解為
m
子向量,以符合原始 PQ 分解結構。 - 對於每個查詢子向量及其對應的編碼簿 (包含 2^nbits 中心點),計算並儲存與所有中心點的距離。
- 這會產生
m
查詢表,其中每個表格包含 2^nbits 距離。
- 將查詢向量分解為
距離近似
對於任何以 PQ 代碼表示的資料庫向量,其與查詢向量的近似距離計算如下:
- 對於每個
m
子向量,使用儲存的中心點索引從對應的查詢表中擷取預先計算的距離。 - 將這些
m
距離相加,得到基於特定度量類型 (例如歐氏距離) 的近似距離。
- 對於每個
pq-process-1
IVF + PQ
IVF_PQ索引結合了IVF和PQ的優點來加速搜尋。此程序分兩個步驟運作:
- 使用 IVF 進行粗過濾:IVF 將向量空間分割成群組,縮小搜尋範圍。該演算法不評估整個資料集,而只專注於最接近查詢向量的叢集。
- 與 PQ 進行精細比較:在選定的叢集內,PQ 使用壓縮與量化的向量表示來快速計算近似距離。
IVF_PQ索引的效能會受到控制 IVF 和 PQ 演算法的參數的顯著影響。要針對特定的資料集和應用程式達到最佳結果,調整這些參數至關重要。有關這些參數以及如何調整參數的詳細資訊,請參閱Index params。
建立索引
要在 Milvus 的向量場上建立IVF_PQ
索引,請使用add_index()
方法,指定index_type
,metric_type
, 以及索引的附加參數。
from pymilvus import MilvusClient
# Prepare index building params
index_params = MilvusClient.prepare_index_params()
index_params.add_index(
field_name="your_vector_field_name", # Name of the vector field to be indexed
index_type="IVF_PQ", # Type of the index to create
index_name="vector_index", # Name of the index to create
metric_type="L2", # Metric type used to measure similarity
params={
"m": 4, # Number of sub-vectors to split eahc vector into
} # Index building params
)
在此設定中
index_type
:要建立的索引類型。在本範例中,設定值為IVF_PQ
。metric_type
:用來計算向量間距離的方法。支援的值包括COSINE
,L2
, 和IP
。如需詳細資訊,請參閱公制類型。params
:建立索引的附加設定選項。m
:將向量分割成的子向量數量。
要瞭解
IVF_PQ
索引可用的更多建立參數,請參閱索引建立參數。
索引參數設定完成後,您可以直接使用create_index()
方法或在create_collection
方法中傳入索引參數來建立索引。如需詳細資訊,請參閱建立集合。
在索引上搜尋
索引建立且實體插入後,您就可以在索引上執行相似性搜尋。
search_params = {
"params": {
"nprobe": 10, # Number of clusters to search
}
}
res = MilvusClient.search(
collection_name="your_collection_name", # Collection name
data=[[0.1, 0.2, 0.3, 0.4, 0.5]], # Query vector
limit=3, # TopK results to return
search_params=search_params
)
在此配置中
params
:在索引上搜尋的其他設定選項。nprobe
:要搜尋的群集數量。
要瞭解
IVF_PQ
索引可用的更多搜尋參數,請參閱特定於索引的搜尋參數。
索引參數
本節概述用於建立索引和在索引上執行搜尋的參數。
索引建立參數
下表列出了建立索引時可在params
中設定的參數。
參數 | 說明 | 值範圍 | 調整建議 | |
---|---|---|---|---|
IVF | nlist | 在建立索引時使用 k-means 演算法建立的叢集數。 | 類型:整數 範圍:[1, 65536] 預設值: 128 | 較大的nlist 值會透過建立更精細的叢集來改善召回率,但會增加索引建立時間。根據資料集大小和可用資源進行最佳化。在大多數情況下,我們建議您設定此範圍內的值:[32, 4096]. |
PQ | m | 在量化過程中,將每個高維向量分割成的子向量(用於量化)數量。 | 類型:整數 範圍:[1, 65536] 預設值:無 | 較高的m 值可以提高精確度,但也會增加計算複雜度和記憶體使用量。m 必須是向量維度(D) 的除數,以確保正確的分解。一般建議的值是m = D/2。在大多數情況下,我們建議您設定此範圍內的值:[D/8, D]。 |
nbits | 用來以壓縮形式表示每個子向量中心點索引的位元數。它直接決定每個編碼本的大小。每個編碼本將包含 2^nbits 的中心點。例如,如果nbits 設定為 8,每個子向量將以 8 位元的中心點索引來表示。這樣,該子向量的編碼簿中就有 2^8 (256) 個可能的中心點。 | 類型:整數 範圍:[1, 64] 預設值: 8 | nbits 較高的值允許較大的編碼本,可能導致原始向量的表示更精確。不過,這也意味著要使用更多位元來儲存每個索引,導致較少的壓縮。在大多數情況下,我們建議您設定此範圍內的值:[1, 16]. |
特定於索引的搜尋參數
下表列出在索引上搜尋時,可在search_params.params
中設定的參數。
參數 | 說明 | 值範圍 | 調整建議 | |
---|---|---|---|---|
IVF | nprobe | 搜尋候選人的叢集數。 | 類型:整數 範圍:[1、nlist] 預設值: 8 | 較高的值允許搜尋更多的叢集,藉由擴大搜尋範圍來改善召回率,但代價是增加查詢延遲。 請依 nlist 的比例設定nprobe ,以平衡速度與精確度。在大多數情況下,我們建議您設定此範圍內的值:[1, nlist]。 |