HNSW_PQ

HNSW_PQ memanfaatkan grafik Hierarchical Navigable Small World (HNSW) dengan Product Quantization (PQ), menciptakan metode pengindeksan vektor tingkat lanjut yang menawarkan pertukaran ukuran versus akurasi yang dapat dikontrol. Dibandingkan dengan HNSW_SQ, jenis indeks ini memberikan tingkat penarikan yang lebih tinggi pada tingkat kompresi yang sama, meskipun dengan kecepatan pemrosesan kueri yang lebih rendah dan waktu konstruksi indeks yang lebih lama.

Gambaran Umum

HNSW_PQ menggabungkan dua teknik pengindeksan: HNSW untuk navigasi berbasis grafik yang cepat dan PQ untuk kompresi vektor yang efisien.

HNSW

HNSW membangun grafik multi-layer di mana setiap node berhubungan dengan 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, sehingga secara signifikan mempercepat proses pencarian dalam ruang dimensi tinggi.

Untuk informasi lebih lanjut, lihat HNSW.

PQ

PQ adalah teknik kompresi vektor yang memecah vektor berdimensi tinggi menjadi sub-vektor yang lebih kecil, yang kemudian dikuantisasi dan dikompresi. Kompresi ini secara dramatis mengurangi kebutuhan memori dan mempercepat perhitungan jarak.

Untuk informasi lebih lanjut, lihat IVF_PQ.

HNSW + PQ

HNSW_PQ menggabungkan kekuatan HNSW dan PQ untuk memungkinkan pencarian tetangga terdekat yang efisien. Algoritma ini menggunakan PQ untuk mengompresi data (sehingga mengurangi penggunaan memori), dan kemudian membuat grafik HNSW pada vektor-vektor yang telah dikompresi untuk memungkinkan pengambilan kandidat dengan cepat. Selama pencarian, algoritme ini secara opsional dapat menyempurnakan hasil kandidat menggunakan data dengan presisi lebih tinggi untuk meningkatkan akurasi. Berikut cara kerja prosesnya:

1. Kompresi Data: PQ membagi setiap vektor menjadi beberapa sub-vektor dan mengkuantisasi mereka menggunakan buku kode centroid, yang dikontrol oleh parameter seperti m (jumlah sub-vektor) dan nbits (bit per sub-vektor).

2. Konstruksi Grafik: Vektor-vektor yang telah dikompresi kemudian digunakan untuk membangun grafik HNSW. Karena vektor-vektor disimpan dalam bentuk terkompresi, grafik yang dihasilkan biasanya lebih kecil, membutuhkan lebih sedikit memori, dan dapat dilalui dengan lebih cepat-secara signifikan mempercepat langkah pengambilan kandidat.

3. Pengambilan Kandidat: Ketika sebuah kueri dijalankan, algoritme menggunakan data terkompresi dalam grafik HNSW untuk mengidentifikasi kumpulan kandidat tetangga secara efisien. Pencarian berbasis grafik ini secara drastis mengurangi jumlah vektor yang harus dipertimbangkan, sehingga meningkatkan latensi kueri dibandingkan dengan pencarian brute force.

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

   • refine: Mengontrol apakah langkah penyempurnaan ini diaktifkan. Jika 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_PQ 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_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": 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,
        "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].
PQ	m	Jumlah sub-vektor (digunakan untuk kuantisasi) untuk membagi setiap vektor dimensi 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].
	refine	Bendera boolean yang mengontrol apakah langkah perbaikan 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].
PQ	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.