Indeks dalam memori

Indeks untuk penyematan titik mengambang

Untuk penyematan floating-point 128 dimensi (vektor), penyimpanan yang digunakan adalah 128 * ukuran float = 512 byte. Dan metrik jarak yang digunakan untuk penyematan float-point adalah jarak Euclidean (L2) dan Inner product (IP).

Jenis-jenis indeks ini termasuk FLAT, IVF_FLAT, IVF_PQ, IVF_SQ8, HNSW, HNSW_SQ, HNSW_PQ, HNSW_PRQ, dan SCANN untuk pencarian ANN berbasis CPU.

FLAT

Untuk aplikasi pencarian kemiripan vektor yang membutuhkan akurasi sempurna dan bergantung pada set data yang relatif kecil (skala jutaan), indeks FLAT adalah pilihan yang baik. FLAT tidak memampatkan vektor, dan merupakan satu-satunya indeks yang dapat menjamin hasil pencarian yang tepat. Hasil dari FLAT juga dapat digunakan sebagai titik perbandingan untuk hasil yang dihasilkan oleh indeks lain yang memiliki recall kurang dari 100%.

FLAT akurat karena menggunakan pendekatan yang menyeluruh dalam melakukan pencarian, yang berarti untuk setiap kueri, input target dibandingkan dengan setiap kumpulan vektor dalam kumpulan data. Hal ini membuat FLAT menjadi indeks paling lambat dalam daftar kami, dan tidak cocok untuk melakukan kueri data vektor yang sangat besar. Tidak ada parameter yang diperlukan untuk indeks FLAT di Milvus, dan untuk menggunakannya tidak memerlukan pelatihan data.

• Parameter pencarian

  Parameter	Deskripsi	Range
  metric_type	[Opsional] Metrik jarak yang dipilih.	Lihat Metrik yang Didukung.

IVF_FLAT

IVF_FLAT membagi data vektor ke dalam unit klaster nlist, lalu membandingkan jarak antara vektor input target dan pusat setiap klaster. Bergantung pada jumlah klaster yang diatur oleh sistem untuk melakukan kueri (nprobe), hasil pencarian kemiripan dikembalikan berdasarkan perbandingan antara input target dan vektor dalam klaster yang paling mirip saja - secara drastis mengurangi waktu kueri.

Dengan menyesuaikan nprobe, keseimbangan ideal antara akurasi dan kecepatan dapat ditemukan untuk skenario tertentu. Hasil dari uji kinerja IVF_FLAT menunjukkan bahwa waktu kueri meningkat tajam seiring dengan bertambahnya jumlah vektor input target (nq), dan jumlah cluster yang dicari (nprobe).

IVF_FLAT adalah indeks IVF yang paling dasar, dan data yang disandikan yang disimpan di setiap unit konsisten dengan data aslinya.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang	Nilai Default
  nlist	Jumlah unit cluster	[1, 65536]	128

• Parameter pencarian

  • Pencarian umum

    Parameter	Deskripsi	Rentang	Nilai Default
    nprobe	Jumlah unit yang akan ditanyakan	[1, nlist]	8

  • Pencarian rentang

    Parameter	Deskripsi	Rentang	Nilai Default
    max_empty_result_buckets	Jumlah maksimum bucket yang tidak mengembalikan hasil pencarian. Ini adalah parameter pencarian rentang dan menghentikan proses pencarian ketika jumlah bucket kosong secara berurutan mencapai nilai yang ditentukan. Meningkatkan nilai ini dapat meningkatkan tingkat penarikan dengan mengorbankan waktu pencarian yang lebih lama.	[1, 65535]	2

IVF_SQ8

IVF_FLAT tidak melakukan kompresi apa pun, sehingga file indeks yang dihasilkannya memiliki ukuran yang kurang lebih sama dengan data vektor mentah yang tidak diindeks. Sebagai contoh, jika set data SIFT 1B asli berukuran 476 GB, file indeks IVF_FLAT akan sedikit lebih kecil (~470 GB). Memuat semua file indeks ke dalam memori akan menghabiskan 470 GB penyimpanan.

Ketika sumber daya memori disk, CPU, atau GPU terbatas, IVF_SQ8 adalah pilihan yang lebih baik daripada IVF_FLAT. Jenis indeks ini dapat mengubah setiap FLOAT (4 byte) menjadi UINT8 (1 byte) dengan melakukan Kuantisasi Skalar (SQ). Hal ini mengurangi konsumsi memori disk, CPU, dan GPU sebesar 70-75%. Untuk kumpulan data SIFT 1B, file indeks IVF_SQ8 hanya membutuhkan penyimpanan 140 GB.

• Parameter pembuatan indeks

  Parameter	Deskripsi	Rentang
  nlist	Jumlah unit cluster	[1, 65536]

• Parameter pencarian

  • Pencarian umum

    Parameter	Deskripsi	Rentang	Nilai Default
    nprobe	Jumlah unit yang akan ditanyakan	[1, nlist]	8

  • Pencarian rentang

    Parameter	Deskripsi	Rentang	Nilai Default
    max_empty_result_buckets	Jumlah maksimum bucket yang tidak mengembalikan hasil pencarian. Ini adalah parameter pencarian rentang dan menghentikan proses pencarian ketika jumlah bucket kosong secara berurutan mencapai nilai yang ditentukan. Meningkatkan nilai ini dapat meningkatkan tingkat penarikan dengan mengorbankan waktu pencarian yang lebih lama.	[1, 65535]	2

IVF_PQ

PQ (Kuantisasi Produk) secara seragam menguraikan ruang vektor dimensi tinggi asli menjadi produk Cartesian dari ruang vektor dimensi rendah m, dan kemudian mengkuantisasi ruang vektor dimensi rendah yang terurai. Alih-alih menghitung jarak antara vektor target dan pusat semua unit, kuantisasi produk memungkinkan perhitungan jarak antara vektor target dan pusat pengelompokan setiap ruang dimensi rendah dan sangat mengurangi kompleksitas waktu dan kompleksitas ruang algoritma.

IVF_PQ melakukan pengelompokan indeks IVF sebelum mengkuantisasi produk vektor. File indeksnya bahkan lebih kecil daripada IVF_SQ8, tetapi juga menyebabkan hilangnya akurasi selama pencarian vektor.

• Parameter pembuatan indeks

  Parameter	Deskripsi	Rentang
  nlist	Jumlah unit cluster	[1, 65536]
  m	Jumlah faktor kuantisasi produk	dim mod m == 0
  nbits	[Opsional] Jumlah bit tempat penyimpanan setiap vektor dimensi rendah.	[1, 64] (8 secara default)

• Parameter pencarian

  • Pencarian umum

    Parameter	Deskripsi	Rentang	Nilai Default
    nprobe	Jumlah unit yang akan ditanyakan	[1, nlist]	8

  • Pencarian rentang

    Parameter	Deskripsi	Rentang	Nilai Default
    max_empty_result_buckets	Jumlah maksimum bucket yang tidak mengembalikan hasil pencarian. Ini adalah parameter pencarian rentang dan menghentikan proses pencarian ketika jumlah bucket kosong secara berurutan mencapai nilai yang ditentukan. Meningkatkan nilai ini dapat meningkatkan tingkat penarikan dengan mengorbankan waktu pencarian yang lebih lama.	[1, 65535]	2

SCANN

ScaNN (Scalable Nearest Neighbors) mirip dengan IVF_PQ dalam hal pengelompokan vektor dan kuantisasi produk. Apa yang membuat mereka berbeda terletak pada detail implementasi kuantisasi produk dan penggunaan SIMD (Single-Instruction/Multi-data) untuk penghitungan yang efisien.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang
  nlist	Jumlah unit cluster	[1, 65536]
  with_raw_data	Apakah akan menyertakan data mentah dalam indeks	True atau False. Nilai default untuk True.

  Tidak seperti IVF_PQ, nilai default berlaku untuk m dan nbits untuk kinerja yang dioptimalkan.

• Parameter pencarian

  • Pencarian umum

    Parameter	Deskripsi	Rentang	Nilai default
    nprobe	Jumlah unit yang akan ditanyakan	[1, nlist]
    reorder_k	Jumlah unit kandidat yang akan ditanyakan	[top_k, ∞]	top_k

  • Pencarian rentang

    Parameter	Deskripsi	Rentang	Nilai Default
    max_empty_result_buckets	Jumlah maksimum bucket yang tidak mengembalikan hasil pencarian. Ini adalah parameter pencarian rentang dan menghentikan proses pencarian ketika jumlah bucket kosong secara berurutan mencapai nilai yang ditentukan. Meningkatkan nilai ini dapat meningkatkan tingkat penarikan dengan mengorbankan waktu pencarian yang lebih lama.	[1, 65535]	2

HNSW

HNSW (Hierarchical Navigable Small World Graph) adalah algoritma pengindeksan berbasis grafik. Algoritma ini membangun struktur navigasi multi-lapisan untuk sebuah gambar menurut aturan tertentu. Dalam struktur ini, lapisan atas lebih jarang dan jarak antar node lebih jauh; lapisan bawah lebih padat dan jarak antar node lebih dekat. Pencarian dimulai dari lapisan paling atas, menemukan node yang paling dekat dengan target di lapisan ini, dan kemudian memasuki lapisan berikutnya untuk memulai pencarian lain. Setelah beberapa kali iterasi, ia dapat dengan cepat mendekati posisi target.

Untuk meningkatkan kinerja, HNSW membatasi tingkat maksimum node pada setiap lapisan grafik ke M. Selain itu, Anda dapat menggunakan efConstruction (saat membangun indeks) atau ef (saat mencari target) untuk menentukan rentang pencarian.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang	Nilai Default
  M	M mendefinisikan jumlah maksimum koneksi keluar dalam grafik. M yang lebih tinggi akan menghasilkan akurasi/waktu_jalan yang lebih tinggi pada ef/efKonstruksi yang tetap.	[2, 2048]	Tidak ada
  efConstruction	ef_construction mengontrol kecepatan pencarian indeks/pertukaran kecepatan pembangunan. Meningkatkan parameter efConstruction dapat meningkatkan kualitas indeks, tetapi juga cenderung memperpanjang waktu pengindeksan.	[1, int_max]	Tidak ada

• Parameter pencarian

  Parameter	Deskripsi	Rentang	Nilai Default
  ef	Parameter yang mengendalikan pertukaran waktu kueri/akurasi. ef yang lebih tinggi akan menghasilkan pencarian yang lebih akurat namun lebih lambat.	[top_k, int_max]	Tidak ada

HNSW_SQ

Kuantisasi Skalar (SQ) adalah teknik yang digunakan untuk mendiskritkan data floating-point menjadi sekumpulan nilai yang terbatas berdasarkan besarnya. Sebagai contoh, SQ6 merepresentasikan kuantisasi ke dalam (2^6 = 64) nilai diskrit, di mana setiap angka floating-point dikodekan menggunakan 6 bit. Demikian pula, SQ8 mengkuantisasi data menjadi (2^8 = 256) nilai diskrit, dengan setiap angka floating-point diwakili oleh 8 bit. Kuantisasi ini mengurangi jejak memori sekaligus mempertahankan struktur data yang penting untuk pemrosesan yang efisien.

Dikombinasikan dengan SQ, HNSW_SQ menawarkan pertukaran yang dapat dikontrol antara ukuran indeks dan akurasi, sambil mempertahankan kinerja query-per-detik (QPS) yang tinggi. Dibandingkan dengan HNSW standar, ini menghasilkan peningkatan yang tidak terlalu besar dalam waktu pembangunan indeks.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang	Nilai Default
  M	M mendefinisikan jumlah maksimum koneksi keluar dalam grafik. M yang lebih tinggi akan menghasilkan akurasi/waktu_jalan yang lebih tinggi pada ef/efKonstruksi yang tetap.	[2, 2048]	Tidak ada
  efConstruction	ef_construction mengontrol kecepatan pencarian indeks/pertukaran kecepatan pembangunan. Meningkatkan parameter efConstruction dapat meningkatkan kualitas indeks, tetapi juga cenderung memperpanjang waktu pengindeksan.	[1, int_max]	Tidak ada
  sq_type	Jenis kuantizer skalar.	SQ6,SQ8, BF16, FP16	SQ8
  refine	Apakah data yang disempurnakan dicadangkan selama pembangunan indeks.	true, false	false
  refine_type	Tipe data dari indeks yang disempurnakan.	SQ6, SQ8, BF16, FP16, FP32	Tidak ada

• Parameter pencarian

  Parameter	Deskripsi	Rentang	Nilai Default
  ef	Parameter yang mengendalikan pertukaran waktu kueri/akurasi. ef yang lebih tinggi akan menghasilkan pencarian yang lebih akurat namun lebih lambat.	[top_k, int_max]	Tidak ada
  refine_k	Faktor pembesaran dari refine dibandingkan dengan k.	[1, float_max] (1, float_max)	1

HNSW_PQ

Ide dasar dari PQ adalah untuk membagi vektor menjadi sub-vektor m, yang masing-masing akan menemukan 2^{nbits} centroid berdasarkan kmeans, dan setiap sub-vektor akan memilih centroid terdekat sebagai perkiraan sub-vektor. Kemudian kita mencatat semua centroid, sehingga setiap subvektor dapat dikodekan sebagai nbits, dan vektor mengambang dengan panjang dim dapat dikodekan sebagai m ⋅ n bit.

Dikombinasikan dengan PQ, HNSW_PQ menawarkan pertukaran yang dapat dikontrol antara ukuran indeks dan akurasi, tetapi memiliki nilai QPS yang lebih rendah dan tingkat penarikan yang lebih tinggi daripada HNSW_SQ untuk tingkat kompresi yang sama. Dibandingkan dengan HNSW_SQ, dibutuhkan waktu lebih lama untuk membangun indeks.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang	Nilai Default
  M	M mendefinisikan jumlah maksimum koneksi keluar dalam grafik. M yang lebih tinggi akan menghasilkan akurasi/waktu_jalan yang lebih tinggi pada ef/efKonstruksi yang tetap.	[2, 2048]	Tidak ada
  efConstruction	ef_construction mengontrol kecepatan pencarian indeks/pertukaran kecepatan pembangunan. Meningkatkan parameter efConstruction dapat meningkatkan kualitas indeks, tetapi juga cenderung memperpanjang waktu pengindeksan.	[1, int_max]	Tidak ada
  m	Jumlah kelompok sub-vektor untuk membagi vektor.	[1, 65536]	32
  nbits	Jumlah bit yang dikuantisasi ke dalam setiap kelompok sub-vektor.	[1, 24]	8
  refine	Apakah data yang disempurnakan dicadangkan selama pembangunan indeks.	true, false	false
  refine_type	Tipe data dari indeks penghalusan.	SQ6, SQ8, BF16, FP16, FP32	Tidak ada

• Parameter pencarian

  Parameter	Deskripsi	Rentang	Nilai Default
  ef	Parameter yang mengendalikan pertukaran waktu kueri/akurasi. ef yang lebih tinggi akan menghasilkan pencarian yang lebih akurat namun lebih lambat.	[top_k, int_max]	Tidak ada
  refine_k	Faktor pembesaran dari refine dibandingkan dengan k.	[1, float_max] (1, float_max)	1

HNSW_PRQ

PRQ mirip dengan PQ, dan juga membagi vektor ke dalam kelompok-kelompok m. Setiap sub-vektor akan dikodekan sebagai nbits. Setelah menyelesaikan kuantisasi pq, ia akan menghitung sisa antara vektor dan vektor terkuantisasi pq, dan menerapkan kuantisasi pq ke vektor sisa. Sebanyak nrq kuantisasi pq lengkap akan dilakukan, sehingga vektor mengambang dengan panjang dim akan dikodekan sebagai m ⋅ nbit ⋅ nrq bit.

Dikombinasikan dengan Product Residual Quantizer (PRQ), HNSW_PRQ menawarkan pertukaran yang dapat dikontrol lebih tinggi antara ukuran indeks dan akurasi. Memiliki nilai QPS yang hampir setara dan tingkat recall yang lebih tinggi daripada HNSW_PQ untuk tingkat kompresi yang sama. Dibandingkan dengan HNSW_PQ, waktu untuk membangun indeks dapat meningkat beberapa kali lipat.

• Parameter pembangunan indeks

  Parameter	Deskripsi	Rentang	Nilai Default
  M	M mendefinisikan jumlah maksimum koneksi keluar dalam grafik. M yang lebih tinggi akan menghasilkan akurasi/waktu_jalan yang lebih tinggi pada ef/efKonstruksi yang tetap.	[2, 2048]	Tidak ada
  efConstruction	ef_construction mengontrol kecepatan pencarian indeks/pertukaran kecepatan pembangunan. Meningkatkan parameter efConstruction dapat meningkatkan kualitas indeks, tetapi juga cenderung memperpanjang waktu pengindeksan.	[1, int_max]	Tidak ada
  m	Jumlah kelompok sub-vektor untuk membagi vektor.	[1, 65536]	32
  nbits	Jumlah bit yang dikuantisasi ke dalam setiap kelompok sub-vektor.	[1, 24]	8
  nrq	Jumlah subkuantisasi sisa.	[1, 16]	2
  refine	Apakah data yang disempurnakan dicadangkan selama pembangunan indeks.	true, false	false
  refine_type	Tipe data dari indeks penghalusan.	SQ6, SQ8, BF16, FP16, FP32	Tidak ada

• Parameter pencarian

  Parameter	Deskripsi	Rentang	Nilai Default
  ef	Parameter yang mengendalikan pertukaran waktu kueri/akurasi. ef yang lebih tinggi akan menghasilkan pencarian yang lebih akurat namun lebih lambat.	[top_k, int_max]	Tidak ada
  refine_k	Faktor pembesaran dari refine dibandingkan dengan k.	[1, float_max] (1, float_max)	1