IVF_RABITQCompatible with Milvus 2.6.x

Indeks IVF_RABITQ adalah algoritme pengindeksan berbasis kuantisasi biner yang mengkuantisasi vektor FP32 ke dalam representasi biner. Indeks ini menawarkan efisiensi penyimpanan yang luar biasa dengan rasio kompresi 1 banding 32 dengan tetap mempertahankan tingkat pemanggilan yang relatif baik. Indeks ini mendukung penyempurnaan opsional untuk mencapai pemanggilan yang lebih tinggi dengan biaya penyimpanan tambahan, menjadikannya pengganti serbaguna untuk IVF_SQ8 dan IVF_FLAT dalam skenario dengan memori terbatas.

Gambaran Umum

IVF_RABITQ adalah singkatan dari Inverted File dengan kuantisasi RaBitQ, yang menggabungkan dua teknik canggih untuk pencarian dan penyimpanan vektor yang efisien.

IVF

Inverted File (IVF) mengatur ruang vektor ke dalam wilayah yang dapat dikelola menggunakan pengelompokan k-means. Setiap klaster diwakili oleh sebuah pusat, yang berfungsi sebagai titik referensi untuk vektor-vektor di dalam klaster tersebut. Pendekatan pengelompokan ini mengurangi ruang pencarian dengan memungkinkan algoritme untuk fokus hanya pada cluster yang paling relevan selama pemrosesan kueri.

Untuk mempelajari lebih lanjut tentang detail teknis IVF, lihat IVF_FLAT.

RaBitQ

RaBitQ adalah metode kuantisasi biner mutakhir dengan jaminan teoretis, yang diperkenalkan dalam makalah penelitian "RaBitQ: Mengukur Vektor Dimensi Tinggi dengan Batas Kesalahan Teoretis untuk Perkiraan Pencarian Tetangga Terdekat" oleh Jianyang Gao dan Cheng Long.

RaBitQ memperkenalkan beberapa konsep inovatif:

Pengkodean Informasi Sudut: Tidak seperti pengkodean spasial tradisional, RaBitQ mengkodekan informasi sudut melalui normalisasi vektor. Dalam IVF_RABITQ, vektor data dinormalisasi terhadap centroid IVF terdekat, sehingga meningkatkan ketepatan proses kuantisasi.

Landasan Teori: Rumus perkiraan jarak inti adalah:

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Dimana

• $or\mathbf{o_r}$ or adalah vektor data dari kumpulan data
• $qr\mathbf{q_r}$ qr adalah vektor kueri
• $co\mathbf{c_o}$ co adalah vektor centroid IVF terdekat untuk $or\mathbf{o_r}$ o r
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) dan $C_1(\mathbf{o_r}, \mathbf{c_o})$ C ${}_{}(o$ r, c o ) adalah konstanta-konstanta yang telah dihitung sebelumnya
• $o~\tilde{\mathbf{o}}$ ~ adalah vektor biner terkuantisasi yang disimpan dalam indeks
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩$ mewakili operasi dot-product

Efisiensi Komputasi: Sifat biner dari $o~\tilde{\mathbf{o}}$ ~ membuat perhitungan jarak menjadi sangat cepat, terutama diuntungkan oleh arsitektur CPU modern dengan instruksi AVX-512 VPOPCNTDQ khusus pada prosesor Intel Ice Lake+ atau AMD Zen 4+.

Peningkatan Algoritmik: RaBitQ terintegrasi secara efektif dengan teknik-teknik yang sudah ada seperti pendekatanFastScan dan rotasi acak untuk meningkatkan kinerja.

IVF + RaBitQ

Indeks IVF_RABITQ menggabungkan pengelompokan IVF yang efisien dengan kuantisasi biner tingkat lanjut RaBitQ:

1. Pemfilteran Kasar: IVF mempartisi ruang vektor menjadi beberapa klaster, secara signifikan mengurangi cakupan pencarian dengan berfokus pada wilayah klaster yang paling relevan.

2. Kuantisasi Biner: Di dalam setiap klaster, RaBitQ memampatkan vektor ke dalam representasi biner sambil mempertahankan hubungan jarak yang penting melalui jaminan teoritis.

3. Penyempurnaan Opsional: Ketika diaktifkan, indeks menyimpan data tambahan yang disempurnakan menggunakan format presisi yang lebih tinggi (SQ6, SQ8, FP16, BF16, atau FP32) untuk meningkatkan tingkat penarikan dengan biaya penyimpanan yang lebih besar.

Milvus mengimplementasikan IVF_RABITQ menggunakan string pabrik FAISS berikut ini:

• Dengan penyempurnaan: "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• Tanpa penyempurnaan: "RR({dim}),IVF{nlist},RaBitQ"

Membangun indeks

Untuk membangun indeks IVF_RABITQ pada bidang vektor di Milvus, gunakan metode add_index(), dengan menetapkan 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="IVF_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

Dalam konfigurasi ini:

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

• 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": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement 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 pembangunan indeks

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

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
IVF	nlist	Jumlah klaster yang dibuat menggunakan algoritme k-means selama pembuatan indeks. Setiap klaster, yang diwakili oleh centroid, menyimpan daftar vektor. Meningkatkan parameter ini akan mengurangi jumlah vektor di setiap klaster, menciptakan partisi yang lebih kecil dan lebih terfokus.	Tipe Bilangan bulat Rentang: [1, 65536] Nilai default: 128	Nilai nlist yang lebih besar meningkatkan daya ingat dengan membuat klaster yang lebih halus, tetapi meningkatkan waktu pembuatan indeks. Optimalkan berdasarkan ukuran set data dan sumber daya yang tersedia. Dalam kebanyakan kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [32, 4096].
RaBitQ	refine	Mengaktifkan proses refine dan menyimpan data yang telah disempurnakan.	Tipe Boolean Rentang: [true, false] Nilai default: false	Setel ke true jika diperlukan tingkat penarikan 0,9+. Mengaktifkan pemurnian akan meningkatkan akurasi, tetapi meningkatkan kebutuhan penyimpanan dan waktu pembuatan indeks.
	refine_type	Menentukan representasi data yang digunakan untuk pemurnian ketika refine diaktifkan.	Tipe: String Rentang: [SQ6, SQ8, FP16, BF16, FP32] Nilai default: Tidak ada	Nilai yang tercantum disajikan dalam urutan peningkatan tingkat pemanggilan, penurunan QPS, dan peningkatan ukuran penyimpanan. SQ8 direkomendasikan sebagai titik awal, menawarkan keseimbangan yang baik antara akurasi dan penggunaan sumber daya.

Parameter pencarian khusus indeks

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

	Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
IVF	nprobe	Jumlah cluster untuk mencari kandidat. Nilai yang lebih tinggi memungkinkan lebih banyak klaster untuk dicari, meningkatkan daya ingat dengan memperluas cakupan pencarian, tetapi dengan biaya peningkatan latensi kueri.	Jenis Bilangan bulat Rentang: [1, nlist] Nilai default: 8	Meningkatkan nilai ini akan meningkatkan daya ingat tetapi dapat memperlambat pencarian. Tetapkan nprobe secara proporsional dengan nlist untuk menyeimbangkan kecepatan dan akurasi. Pada sebagian besar kasus, kami sarankan Anda menetapkan nilai dalam kisaran ini: [1, nlist].
RaBitQ	rbq_query_bits	Mengatur apakah kuantisasi skalar tambahan dari vektor kueri diterapkan. Jika diatur ke 0, kueri digunakan tanpa kuantisasi. Jika diatur ke nilai dalam [1, 8], kueri akan diproses sebelumnya menggunakan kuantisasi skalar n-bit.	Tipe Bilangan bulat Rentang: [0, 8] Nilai default: 0	Nilai default 0 memberikan tingkat pemanggilan maksimum tetapi kinerja paling lambat. Kami merekomendasikan nilai pengujian 0, 8, dan 6, karena mereka memberikan tingkat penarikan yang serupa dengan 6 sebagai yang tercepat. Gunakan nilai yang lebih kecil untuk persyaratan penarikan yang lebih tinggi.
	refine_k	Proses pemurnian menggunakan kuantisasi kualitas yang lebih tinggi untuk memilih jumlah tetangga terdekat yang dibutuhkan dari kumpulan kandidat yang dipilih menggunakan IVF_RABITQ sebanyak refine_k kali lebih besar.	Tipe Mengambang Rentang: [1, float_max) Nilai default: 1	Nilai refine_k yang lebih tinggi akan menurunkan QPS tetapi meningkatkan tingkat penarikan. Mulailah dengan 1 dan nilai pengujian 2, 3, 4, dan 5 untuk menemukan trade-off optimal antara QPS dan recall untuk set data Anda.