IVF_PQ

IVF_PQ索引是一種基於量化的索引演算法，用於高維空間中的近似近鄰搜尋。雖然速度不如某些基於圖的方法，但IVF_PQ通常需要較少的記憶體，因此是大型資料集的實用選擇。

概述

IVF_PQ是Inverted File with Product Quantization 的縮寫，是一種結合索引與壓縮的混合方法，用於有效率的向量搜尋與檢索。它利用兩個核心元件：倒轉檔案 (IVF)與乘積量化 (PQ )。

IVF

IVF 就像是在書本中建立索引。您不需要掃描每一頁 (或在我們的情況下，掃描每一個向量)，而是在索引中查找特定的關鍵字（群組），以快速找到相關的頁面 (向量)。在我們的情況中，向量會被歸類為叢集，演算法會在幾個與查詢向量接近的叢集內進行搜尋。

以下是其運作方式：

1. 聚類：使用 k-means 之類的聚類演算法，將向量資料集分為指定數量的叢集。每個叢集都有一個中心點（叢集的代表向量）。
2. 分派：每個向量會被分派到其中心點最接近的叢集。
3. 反向索引：建立一個索引，將每個群集的中心點對應到分配給該群集的向量清單。
4. 搜尋：搜尋最近鄰居時，搜尋演算法會比較您的查詢向量與群集中心點，並選擇最有希望的群集。然後將搜尋範圍縮小到這些選定叢集中的向量。

要瞭解更多技術細節，請參閱IVF_FLAT。

PQ

Product Quantization (PQ)是一種高維向量的壓縮方法，可大幅降低儲存需求，同時實現快速的相似性搜尋作業。

PQ 過程包含以下關鍵階段：

PQ-Process-1

1. 尺寸分解：該演算法首先將每個高維向量分解為m 大小相等的子向量。此分解將原始的 D 維空間轉換為m 不相交的子空間，其中每個子空間包含D/m維。參數m 控制分解的粒度，並直接影響壓縮比。
2. 子空間編碼本製作：在每個子空間中，演算法應用k-means 聚類來學習一組代表性向量 (中心點)。這些中心點共同形成該子空間的編碼簿。每個編碼本的中心點數量由參數nbits 決定，其中每個編碼本包含 2^nbits 的中心點。例如，如果nbits = 8 ，每個編碼本將包含 256 個中心點。每個中心點都會被指派一個唯一的nbits 位元索引。
3. 向量 量化：對於原始向量中的每個子向量，PQ 會使用特定的度量類型在對應的子空間中找出其最近的中心點。此過程能有效地將每個子向量映射到編碼簿中最接近的代表向量。與其儲存完整的子向量座標，不如只保留匹配中心點的索引。
4. 壓縮表示：最後的壓縮表示由m 索引組成，每個子空間一個，統稱為PQ 編碼。此編碼可將儲存需求從D × 32位元 (假設為 32 位元浮點數) 減少到m×nbits位元，在保留近似向量距離能力的同時，達到大幅壓縮的效果。

有關參數調整與最佳化的詳細資訊，請參閱索引參數。

使用 PQ 計算距離

當使用查詢向量執行相似性搜尋時，PQ 可透過下列步驟有效率地計算距離：

1. 查詢預處理

   1. 將查詢向量分解為m 子向量，以符合原始 PQ 分解結構。
   2. 對於每個查詢子向量及其對應的編碼簿 (包含 2^nbits 中心點)，計算並儲存與所有中心點的距離。
   3. 這會產生m 查詢表，其中每個表格包含 2^nbits 距離。

2. 距離近似

   對於任何以 PQ 代碼表示的資料庫向量，其與查詢向量的近似距離計算如下：

   1. 對於每個m 子向量，使用儲存的中心點索引從對應的查詢表中擷取預先計算的距離。
   2. 將這些m 距離相加，得到基於特定度量類型 (例如歐氏距離) 的近似距離。

pq-process-1

IVF + PQ

IVF_PQ索引結合了IVF和PQ的優點來加速搜尋。此程序分兩個步驟運作：

1. 使用 IVF 進行粗過濾：IVF 將向量空間分割成群組，縮小搜尋範圍。該演算法不評估整個資料集，而只專注於最接近查詢向量的叢集。
2. 與 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]。