HNSW_PRQ

HNSW_PRQ memanfaatkan grafik Hierarchical Navigable Small World (HNSW) dengan Product Residual Quantization (PRQ), menawarkan metode pengindeksan vektor tingkat lanjut yang memungkinkan Anda untuk menyelaraskan antara ukuran indeks dan akurasi. PRQ melampaui Kuantisasi Produk (PQ) tradisional dengan memperkenalkan langkah kuantisasi residu (RQ) untuk menangkap informasi tambahan, sehingga menghasilkan akurasi yang lebih tinggi atau indeks yang lebih ringkas dibandingkan dengan metode berbasis PQ murni. Namun, langkah tambahan ini dapat menyebabkan overhead komputasi yang lebih tinggi selama pembuatan dan pencarian indeks.

Gambaran Umum

HNSW_PRQ menggabungkan dua teknik pengindeksan: HSNW untuk navigasi berbasis grafik yang cepat dan PRQ untuk kompresi vektor yang efisien.

HNSW

HNSW membangun grafik multi-layer di mana setiap node berhubungan dengan sebuah vektor dalam kumpulan data. Dalam grafik ini, node terhubung berdasarkan kesamaan mereka, memungkinkan penjelajahan yang cepat melalui ruang data. Struktur hirarkis memungkinkan algoritme pencarian untuk mempersempit kandidat tetangga, yang secara signifikan mempercepat proses pencarian dalam ruang dimensi tinggi.

Untuk informasi lebih lanjut, lihat HNSW.

PRQ

PRQ adalah pendekatan kompresi vektor multi-tahap yang menggabungkan dua teknik yang saling melengkapi: PQ dan RQ. Dengan terlebih dahulu membagi vektor dimensi tinggi menjadi sub-vektor yang lebih kecil (melalui PQ) dan kemudian mengkuantifikasi perbedaan yang tersisa (melalui RQ), PRQ mencapai representasi yang ringkas namun akurat dari data asli.

Gambar berikut menunjukkan cara kerjanya.

Hnsw Prq

1. Kuantisasi Produk (PQ)

   Pada fase ini, vektor asli dibagi menjadi sub-vektor yang lebih kecil, dan setiap sub-vektor dipetakan ke centroid terdekat dalam codebook yang dipelajari. Pemetaan ini secara signifikan mengurangi ukuran data, namun menimbulkan beberapa kesalahan pembulatan karena setiap sub-vektor didekati oleh satu centroid. Untuk lebih jelasnya, lihat IVF_PQ.

2. Kuantisasi Sisa (RQ)

   Setelah tahap PQ, RQ mengkuantisasi residual-selisih antara vektor asli dan perkiraan berbasis PQ-menggunakan buku kode tambahan. Karena residual ini biasanya jauh lebih kecil, maka dapat dikodekan dengan lebih tepat tanpa peningkatan penyimpanan yang besar.

   Parameter nrq menentukan berapa kali residual ini dikuantisasi secara iteratif, sehingga Anda dapat menyempurnakan keseimbangan antara efisiensi dan akurasi kompresi.

3. Representasi Kompresi Akhir

   Setelah RQ selesai mengkuantifikasi residual, kode integer dari PQ dan RQ digabungkan menjadi satu indeks terkompresi. Dengan menangkap detail halus yang mungkin terlewatkan oleh PQ, RQ meningkatkan akurasi tanpa menyebabkan peningkatan penyimpanan yang signifikan. Sinergi antara PQ dan RQ inilah yang mendefinisikan PRQ.

HNSW + PRQ

Dengan menggabungkan HNSW dengan PRQ, HNSW_PRQ mempertahankan pencarian berbasis grafik yang cepat dari HNSW sambil memanfaatkan kompresi multi-tahap dari PRQ. Alur kerjanya terlihat seperti ini:

1. Kompresi Data: Setiap vektor pertama-tama ditransformasikan melalui PQ ke representasi kasar, dan kemudian residu dikuantisasi melalui RQ untuk penyempurnaan lebih lanjut. Hasilnya adalah sekumpulan kode ringkas yang mewakili setiap vektor.

2. Konstruksi Graf: Vektor-vektor yang dikompresi (termasuk kode PQ dan RQ) menjadi dasar untuk membangun grafik HNSW. Karena data disimpan dalam bentuk yang ringkas, grafik membutuhkan lebih sedikit memori, dan navigasi melaluinya dipercepat.

3. Pengambilan Kandidat: Selama pencarian, HNSW menggunakan representasi terkompresi untuk menelusuri graf dan mengambil sekumpulan kandidat. Hal ini secara dramatis mengurangi jumlah vektor yang perlu dipertimbangkan.

4. (Opsional) Penyempurnaan Hasil: Hasil kandidat awal dapat disempurnakan untuk akurasi yang lebih baik, berdasarkan parameter berikut:

   • refine: Mengontrol apakah langkah penyempurnaan ini diaktifkan. Ketika diatur ke true, sistem menghitung ulang jarak menggunakan representasi yang lebih presisi atau tidak terkompresi.

   • refine_type: Menentukan tingkat presisi data yang digunakan selama penghalusan (misalnya, SQ6, SQ8, BF16). Pilihan presisi yang lebih tinggi seperti FP32 dapat memberikan hasil yang lebih akurat tetapi membutuhkan lebih banyak memori. Ini harus melebihi ketepatan data terkompresi asli yang ditetapkan oleh sq_type.

   • refine_k: Bertindak sebagai faktor pembesaran. Misalnya, jika k teratas Anda adalah 100 dan refine_k adalah 2, sistem akan mengurutkan ulang 200 kandidat teratas dan mengembalikan 100 terbaik, sehingga meningkatkan akurasi secara keseluruhan.

Untuk daftar lengkap parameter dan nilai yang valid, lihat Parameter indeks.

Membangun indeks

Untuk membangun indeks HNSW_PRQ pada bidang vektor di Milvus, gunakan metode add_index(), tentukan index_type, metric_type, dan parameter tambahan untuk indeks.

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="HNSW_PRQ", # 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": 30, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 360, # Number of candidate neighbors considered for connection during index construction
        "m": 384, 
        "nbits": 8,
        "nrq": 1,
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

Dalam konfigurasi ini:

• index_type: Jenis indeks yang akan dibangun. Dalam contoh ini, tetapkan nilainya ke HNSW_PQ.

• metric_type: Metode yang digunakan untuk menghitung jarak antara vektor. Nilai yang didukung termasuk COSINE, L2, dan IP. Untuk detailnya, lihat Jenis Metrik.

• params: Opsi konfigurasi tambahan untuk membangun indeks. Untuk detailnya, lihat Parameter pembuatan indeks.

Setelah parameter indeks dikonfigurasi, Anda dapat membuat indeks dengan menggunakan metode create_index() secara langsung atau mengoper parameter indeks dalam metode create_collection. Untuk detailnya, lihat Membuat Koleksi.

Mencari di indeks

Setelah indeks dibuat dan entitas dimasukkan, Anda dapat melakukan pencarian kemiripan pada indeks.

search_params = {
    "params": {
        "ef": 10, # Parameter controlling query time/accuracy trade-off
        "refine_k": 1 # The magnification factor
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field",  # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=3,  # TopK results to return
    search_params=search_params
)

Dalam konfigurasi ini:

• params: Opsi konfigurasi tambahan untuk pencarian pada indeks. Untuk detailnya, lihat Parameter pencarian khusus indeks.

Parameter indeks

Bagian ini memberikan gambaran umum tentang parameter yang digunakan untuk membangun indeks dan melakukan pencarian pada indeks.

Parameter pembuatan indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di params saat membangun indeks.

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
HNSW	M	Jumlah maksimum koneksi (atau sisi) yang dapat dimiliki setiap simpul dalam graf, termasuk sisi keluar dan masuk. Parameter ini secara langsung memengaruhi konstruksi indeks dan pencarian.	Tipe: Bilangan bulat Rentang: [2, 2048] Nilai default: 30 (hingga 30 sisi keluar dan 30 sisi masuk per simpul)	M yang lebih besar umumnya menghasilkan akurasi yang lebih tinggi tetapi meningkatkan overhead memori dan memperlambat pembangunan indeks dan pencarian. Pertimbangkan untuk meningkatkan M untuk set data dengan dimensi tinggi atau ketika pemanggilan yang tinggi sangat penting. Pertimbangkan untuk mengurangi M ketika penggunaan memori dan kecepatan pencarian menjadi perhatian utama. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [5, 100].
	efConstruction	Jumlah kandidat tetangga yang dipertimbangkan untuk koneksi selama konstruksi indeks. Kumpulan kandidat yang lebih besar dievaluasi untuk setiap elemen baru, tetapi jumlah maksimum koneksi yang benar-benar dibuat masih dibatasi oleh M.	Tipe: Bilangan bulat Rentang: [1, int_max] Nilai default: 360	Nilai efConstruction yang lebih tinggi biasanya menghasilkan indeks yang lebih akurat, karena lebih banyak koneksi potensial yang dieksplorasi. Namun, hal ini juga menyebabkan waktu pengindeksan yang lebih lama dan peningkatan penggunaan memori selama konstruksi. Pertimbangkan untuk meningkatkan efConstruction untuk meningkatkan akurasi, terutama dalam skenario di mana waktu pengindeksan tidak terlalu penting. Pertimbangkan untuk mengurangi efConstruction untuk mempercepat konstruksi indeks ketika keterbatasan sumber daya menjadi perhatian. Dalam kebanyakan kasus, kami menyarankan Anda menetapkan nilai dalam kisaran ini: [50, 500].
PRQ	m	Jumlah sub-vektor (digunakan untuk kuantisasi) untuk membagi setiap vektor berdimensi tinggi selama proses kuantisasi.	Jenis: Bilangan bulat Rentang: [1, 65536] Nilai default: Tidak ada	Nilai m yang lebih tinggi dapat meningkatkan akurasi, tetapi juga meningkatkan kompleksitas komputasi dan penggunaan memori. m harus merupakan pembagi dimensi vektor(D) untuk memastikan penguraian yang tepat. Nilai yang umumnya direkomendasikan adalah m = D/2. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [D/8, D].
	nbits	Jumlah bit yang digunakan untuk merepresentasikan indeks centroid setiap sub-vektor dalam bentuk terkompresi. Ini secara langsung menentukan ukuran setiap codebook. Setiap codebook akan berisi centroid 2nbit. Sebagai contoh, jika nbits diatur ke 8, setiap sub-vektor akan diwakili oleh indeks centroid 8-bit. Hal ini memungkinkan28 (256) kemungkinan centroid dalam codebook untuk sub-vektor tersebut.	Jenis: Rentang Bilangan Bulat: [1, 24] Nilai default: 8	Nilai nbits yang lebih tinggi memungkinkan codebook yang lebih besar, yang berpotensi menghasilkan representasi yang lebih akurat dari vektor asli. Namun, ini juga berarti menggunakan lebih banyak bit untuk menyimpan setiap indeks, yang menghasilkan kompresi yang lebih sedikit. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [1, 16].
	nrq	Mengontrol berapa banyak subkuantisasi sisa yang digunakan dalam tahap RQ. Lebih banyak subkuantisasi berpotensi mencapai kompresi yang lebih besar, tetapi dapat menyebabkan lebih banyak kehilangan informasi.	Tipe: Rentang Bilangan Bulat: [1, 16] Nilai default: 2	Nilai nrq yang lebih tinggi memungkinkan langkah subkuantisasi sisa tambahan, yang berpotensi menghasilkan rekonstruksi yang lebih tepat dari vektor asli. Namun, hal ini juga berarti menyimpan dan menghitung lebih banyak subkuantisasi, sehingga menghasilkan ukuran indeks yang lebih besar dan overhead komputasi yang lebih besar.
	refine	Bendera boolean yang mengontrol apakah langkah penyempurnaan diterapkan selama pencarian. Refinement melibatkan pemeringkatan ulang hasil awal dengan menghitung jarak yang tepat antara vektor kueri dan kandidat.	Jenis: Rentang Boolean: [true, false] Nilai default: false	Setel ke true jika akurasi tinggi sangat penting dan Anda dapat mentolerir waktu pencarian yang sedikit lebih lambat. Gunakan false jika kecepatan adalah prioritas dan kompromi kecil dalam akurasi dapat diterima.
	refine_type	Menentukan ketepatan data yang digunakan selama proses penghalusan. Ketepatan ini harus lebih tinggi daripada vektor yang dikompresi (seperti yang ditetapkan oleh parameter m dan nbits ).	Jenis: Rentang String:[ SQ6, SQ8, BF16, FP16, FP32 ] Nilai default: Tidak ada	Gunakan FP32 untuk presisi maksimum dengan biaya memori yang lebih tinggi, atau SQ6/SQ8 untuk kompresi yang lebih baik. BF16 dan FP16 menawarkan alternatif yang seimbang.

Parameter pencarian khusus indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di search_params.params saat mencari di indeks.

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
HNSW	ef	Mengontrol luasnya pencarian selama pencarian tetangga terdekat. Parameter ini menentukan berapa banyak node yang dikunjungi dan dievaluasi sebagai tetangga terdekat yang potensial. Parameter ini hanya memengaruhi proses pencarian dan berlaku secara eksklusif pada lapisan bawah grafik.	Tipe: Bilangan bulat Rentang: [1, int_max] Nilai default: batas (tetangga terdekat TopK yang akan dikembalikan)	ef yang lebih besar umumnya menghasilkan akurasi pencarian yang lebih tinggi karena lebih banyak tetangga potensial yang dipertimbangkan. Namun, hal ini juga meningkatkan waktu pencarian. Pertimbangkan untuk meningkatkan ef ketika mencapai recall yang tinggi sangat penting dan kecepatan pencarian tidak terlalu menjadi perhatian. Pertimbangkan untuk mengurangi ef untuk memprioritaskan pencarian yang lebih cepat, terutama dalam skenario di mana sedikit penurunan akurasi dapat diterima. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [K, 10K].
PRQ	refine_k	Faktor pembesaran yang mengontrol berapa banyak kandidat tambahan yang diperiksa selama tahap penyempurnaan (pemeringkatan ulang), relatif terhadap hasil K teratas yang diminta.	Tipe Rentang Float: [1, float_max) Nilai default: 1	Nilai yang lebih tinggi dari refine_k dapat meningkatkan recall dan akurasi tetapi juga akan meningkatkan waktu pencarian dan penggunaan sumber daya. Nilai 1 berarti proses penyempurnaan hanya mempertimbangkan hasil K teratas awal.