HNSW_SQ

HNSW_SQ menggabungkan grafik Hierarchical Navigable Small World (HNSW) dengan Scalar Quantization (SQ), menciptakan metode pengindeksan vektor tingkat lanjut yang menawarkan pertukaran ukuran versus akurasi yang dapat dikontrol. Dibandingkan dengan HNSW standar, jenis indeks ini mempertahankan kecepatan pemrosesan kueri yang tinggi sambil memperkenalkan sedikit peningkatan waktu konstruksi indeks.

Gambaran Umum

HNSW_SQ menggabungkan dua teknik pengindeksan: HNSW untuk navigasi berbasis grafik yang cepat dan SQ 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, sehingga secara signifikan mempercepat proses pencarian dalam ruang dimensi tinggi.

Untuk informasi lebih lanjut, lihat HNSW.

SQ

SQ adalah metode untuk mengompresi vektor dengan merepresentasikannya dengan bit yang lebih sedikit. Sebagai contoh:

• SQ8 menggunakan 8 bit, memetakan nilai ke dalam 256 level. Untuk informasi lebih lanjut, lihat IVF_SQ8.

• SQ6 menggunakan 6 bit untuk merepresentasikan setiap nilai floating-point, sehingga menghasilkan 64 level diskrit.

Hnsw Sq

Pengurangan presisi ini secara dramatis mengurangi jejak memori dan mempercepat komputasi sambil tetap mempertahankan struktur data yang penting.

SQ4UCompatible with Milvus 2.6.8+

Untuk skenario yang menuntut kecepatan kueri yang ekstrem dan penggunaan memori yang minimal, Milvus memperkenalkan SQ4U, sebuah Kuantisasi Skalar Seragam 4-bit. Ini adalah bentuk kuantisasi skalar yang agresif yang memampatkan nilai floating-point setiap dimensi menjadi bilangan bulat tak bertanda 4-bit.

"U" dalam SQ4U adalah singkatan dari Uniform. Tidak seperti Kuantisasi Skalar yang tidak seragam, yang biasanya menghitung nilai minimum dan maksimum secara independen untuk setiap dimensi (Kuantisasi Per-Dimensi), SQ4U menerapkan strategi Kuantisasi Seragam Global:

1. Statistik Global: Sistem menghitung satu nilai minimum vmin dan satu rentang nilai vdiff yang berlaku untuk semua dimensi vektor (atau seluruh segmen vektor).

2. Pemetaan Seragam: Rentang nilai global dibagi menjadi 16 interval yang sama. Setiap nilai floating-point dalam vektor, terlepas dari dimensi mana yang dimilikinya, dipetakan ke bilangan bulat 4-bit (0-15) menggunakan parameter bersama ini.

Keunggulan Kinerja:

• Rasio Kompresi 8x: Mengurangi ukuran sebesar 8x dibandingkan dengan FP32 dan 2x dibandingkan dengan SQ8, secara signifikan menurunkan tekanan bandwidth memori - yang sering kali menjadi hambatan dalam pencarian vektor.

• Optimalisasi SIMD: Struktur yang ringkas memungkinkan CPU modern (AVX2/AVX-512) untuk memproses lebih banyak dimensi per siklus. Yang terpenting, penggunaan parameter global menghilangkan kebutuhan untuk memuat nilai skala/offset yang berbeda-beda selama penghitungan jarak, sehingga menjaga pipeline instruksi tetap penuh.

• Efisiensi Cache: Ukuran vektor yang lebih kecil berarti lebih banyak data yang masuk ke dalam cache CPU, mengurangi latensi yang disebabkan oleh akses memori.

HNSW + SQ

HNSW_SQ menggabungkan kekuatan HNSW dan SQ untuk memungkinkan pencarian tetangga terdekat yang efisien. Berikut cara kerja prosesnya:

1. Kompresi Data: SQ mengompresi vektor menggunakan sq_type (misalnya, SQ6 atau SQ8), yang mengurangi penggunaan memori. Kompresi ini dapat menurunkan presisi, tetapi memungkinkan sistem untuk menangani kumpulan data yang lebih besar.

2. Konstruksi Grafik: Vektor-vektor yang dikompresi digunakan untuk membangun grafik HNSW. Karena data dikompresi, grafik yang dihasilkan lebih kecil dan lebih cepat untuk dicari.

3. Pengambilan Kandidat: Ketika vektor kueri disediakan, algoritma menggunakan data yang dikompresi untuk dengan cepat mengidentifikasi kumpulan kandidat tetangga dari graf HNSW.

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 akan 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_SQ 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_SQ", # 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": 64, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 100, # Number of candidate neighbors considered for connection during index construction
        "sq_type": "SQ6", # Scalar quantizer type
        "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_SQ.

• 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 oleh setiap simpul dalam graf, termasuk sisi keluar dan masuk. Parameter ini secara langsung mempengaruhi 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 pembuatan indeks dan pencarian. Pertimbangkan untuk meningkatkan M untuk dataset 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	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 penggunaan memori yang lebih besar 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].
SQ	sq_type	Menentukan metode kuantisasi skalar untuk mengompresi vektor. Setiap opsi menawarkan keseimbangan yang berbeda antara kompresi dan akurasi: SQ4U: Mengkodekan vektor menggunakan kuantisasi seragam 4-bit. Mode ini menawarkan kecepatan dan kompresi tertinggi. SQ6: Mengkodekan vektor menggunakan bilangan bulat 6-bit. SQ8: Mengkodekan vektor menggunakan bilangan bulat 8-bit. BF16: Menggunakan format Bfloat16. FP16: Menggunakan format floating-point 16-bit standar.	Jenis String Rentang: [ SQ4U, SQ6, SQ8, BF16, FP16 ] Nilai default: SQ8	Pilihan sq_type tergantung pada kebutuhan aplikasi tertentu. SQ4U dipilih untuk kecepatan maksimum dan efisiensi memori. SQ6 atau SQ8 mungkin cocok untuk kinerja yang seimbang. Di sisi lain, jika akurasi adalah yang terpenting, BF16 atau FP16 bisa lebih disukai.
	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.	Tipe Boolean Rentang: [true, false] Nilai default: false	Tetapkan 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 untuk penyempurnaan. Ketepatan ini harus lebih tinggi daripada vektor yang dikompresi (seperti yang ditetapkan oleh sq_type), yang memengaruhi akurasi vektor yang diperingkat ulang dan jejak memorinya.	Jenis String Rentang:[ 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. Akan tetapi, 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].
SQ	refine_k	Faktor pembesaran yang mengontrol berapa banyak kandidat tambahan yang diperiksa selama tahap penyempurnaan, relatif terhadap K hasil teratas yang diminta.	Tipe Mengambang Rentang: [1, float_max) Nilai default: 1	Nilai yang lebih tinggi dari refine_k dapat meningkatkan penarikan dan akurasi tetapi juga akan meningkatkan waktu pencarian dan penggunaan sumber daya. Nilai 1 berarti proses penyempurnaan hanya mempertimbangkan hasil K teratas awal.