🚀 Coba Zilliz Cloud, Milvus yang sepenuhnya terkelola, secara gratis—rasakan performa 10x lebih cepat! Coba Sekarang>>

Mulai

Home BlogsMempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor

Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor

Engineering

December 05, 2019

milvus

Mulai dari visi komputer hingga penemuan obat baru, mesin pencari kemiripan vektor mendukung banyak aplikasi kecerdasan buatan (AI) yang populer. Komponen besar yang memungkinkan untuk melakukan kueri secara efisien terhadap jutaan, miliaran, atau bahkan triliunan set data vektor yang menjadi andalan mesin pencari kemiripan adalah pengindeksan, sebuah proses pengorganisasian data yang secara drastis mempercepat pencarian data besar. Artikel ini membahas peran pengindeksan dalam membuat pencarian kemiripan vektor menjadi efisien, berbagai jenis indeks vector inverted file (IVF), dan saran mengenai indeks mana yang akan digunakan dalam berbagai skenario.

Langsung ke:

Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor

Bagaimana pengindeksan vektor mempercepat pencarian kemiripan dan pembelajaran mesin?

Mesin pencari kemiripan bekerja dengan membandingkan input ke database untuk menemukan objek yang paling mirip dengan input. Pengindeksan adalah proses pengorganisasian data secara efisien, dan ini memainkan peran utama dalam membuat pencarian kemiripan menjadi berguna dengan mempercepat kueri yang memakan waktu secara dramatis pada kumpulan data yang besar. Setelah kumpulan data vektor yang sangat besar diindeks, kueri dapat dialihkan ke cluster, atau subset data, yang kemungkinan besar berisi vektor yang mirip dengan kueri masukan. Dalam praktiknya, ini berarti tingkat akurasi tertentu dikorbankan untuk mempercepat kueri pada data vektor yang sangat besar.

Sebuah analogi dapat diambil dari sebuah kamus, di mana kata-kata diurutkan menurut abjad. Ketika mencari sebuah kata, Anda dapat dengan cepat menavigasi ke bagian yang hanya berisi kata-kata dengan huruf awal yang sama - secara drastis mempercepat pencarian definisi kata yang dimasukkan.

Apa saja jenis indeks IVF yang berbeda dan skenario mana yang paling cocok untuknya?

Ada banyak indeks yang dirancang untuk pencarian kemiripan vektor berdimensi tinggi, dan masing-masing indeks memiliki kekurangan dan kelebihan dalam hal kinerja, akurasi, dan kebutuhan penyimpanan. Artikel ini membahas beberapa jenis indeks IVF yang umum, kekuatan dan kelemahannya, serta hasil pengujian kinerja untuk setiap jenis indeks. Pengujian kinerja mengukur waktu kueri dan tingkat penarikan untuk setiap jenis indeks di Milvus, sebuah platform manajemen data vektor sumber terbuka. Untuk informasi tambahan tentang lingkungan pengujian, lihat bagian metodologi di bagian bawah artikel ini.

DATAR: Baik untuk mencari set data yang relatif kecil (skala jutaan) ketika diperlukan 100% recall.

Untuk aplikasi pencarian kemiripan vektor yang membutuhkan akurasi sempurna dan bergantung pada set data yang relatif kecil (berskala 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 vektor dalam kumpulan data. Hal ini membuat FLAT menjadi indeks paling lambat dalam daftar kami, dan tidak cocok untuk mencari data vektor yang sangat besar. Tidak ada parameter untuk indeks FLAT di Milvus, dan menggunakannya tidak memerlukan pelatihan data atau penyimpanan tambahan.

Hasil pengujian kinerja FLAT:

Pengujian kinerja waktu kueri FLAT dilakukan di Milvus menggunakan dataset yang terdiri dari 2 juta vektor 128 dimensi.

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_2.png

Hal-hal penting yang dapat diambil:

Ketika nq (jumlah vektor target untuk sebuah kueri) meningkat, waktu kueri juga meningkat.
Dengan menggunakan indeks FLAT di Milvus, kita dapat melihat bahwa waktu kueri meningkat tajam setelah nq melebihi 200.
Secara umum, indeks FLAT lebih cepat dan lebih konsisten ketika menjalankan Milvus pada GPU vs CPU. Namun, kueri FLAT pada CPU lebih cepat ketika nq di bawah 20.

IVF_FLAT: Meningkatkan kecepatan dengan mengorbankan akurasi (dan sebaliknya).

Cara umum untuk mempercepat proses pencarian kesamaan dengan mengorbankan akurasi adalah dengan melakukan pencarian tetangga terdekat (ANN). Algoritma ANN mengurangi kebutuhan penyimpanan dan beban komputasi dengan mengelompokkan vektor-vektor yang mirip, sehingga menghasilkan pencarian vektor yang lebih cepat. IVF_FLAT adalah jenis indeks file terbalik yang paling dasar dan bergantung pada bentuk pencarian ANN.

IVF_FLAT membagi data vektor ke dalam sejumlah unit klaster (nlist), dan kemudian membandingkan jarak antara vektor input target dan pusat setiap klaster. Bergantung pada jumlah klaster yang diatur oleh sistem untuk 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 kami menunjukkan bahwa waktu kueri meningkat tajam seiring dengan bertambahnya jumlah vektor input target (nq), dan jumlah klaster yang dicari (nprobe). IVF_FLAT tidak memampatkan data vektor, namun, file indeks menyertakan metadata yang sedikit meningkatkan kebutuhan penyimpanan dibandingkan dengan set data vektor mentah yang tidak diindeks.

Hasil uji kinerja IVF_FLAT:

Pengujian kinerja waktu kueri IVF_FLAT dilakukan di Milvus menggunakan dataset SIFT 1B publik, yang berisi 1 miliar vektor 128 dimensi.

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_3.png

Kesimpulan utama:

Ketika berjalan di CPU, waktu kueri untuk indeks IVF_FLAT di Milvus meningkat dengan nprobe dan nq. Ini berarti semakin banyak vektor input yang dikandung kueri, atau semakin banyak cluster yang dicari kueri, maka waktu kueri akan semakin lama.
Pada GPU, indeks menunjukkan lebih sedikit varians waktu terhadap perubahan nq dan nprobe. Hal ini dikarenakan data indeks berukuran besar, dan menyalin data dari memori CPU ke memori GPU menyumbang sebagian besar dari total waktu kueri.
Pada semua skenario, kecuali saat nq = 1.000 dan nprobe = 32, indeks IVF_FLAT lebih efisien saat berjalan di CPU.

Pengujian kinerja penarikan IVF_FLAT dilakukan di Milvus dengan menggunakan dataset SIFT 1M publik, yang berisi 1 juta vektor 128 dimensi, dan dataset sarung tangan-200-sudut, yang berisi lebih dari 1 juta vektor 200 dimensi, untuk membangun indeks (nlist = 16.384).

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_4.png

Hal-hal penting yang dapat diambil:

Indeks IVF_FLAT dapat dioptimalkan untuk akurasi, mencapai tingkat recall di atas 0,99 pada dataset SIFT 1M ketika nprobe = 256.

IVF_SQ8: Lebih cepat dan tidak terlalu membutuhkan sumber daya dibandingkan IVF_FLAT, tetapi juga kurang akurat.

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 besar (~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 mengonversi setiap FLOAT (4 byte) menjadi UINT8 (1 byte) dengan melakukan kuantisasi skalar. Hal ini mengurangi konsumsi memori disk, CPU, dan GPU sebesar 70-75%. Untuk kumpulan data SIFT 1B, file indeks IVF_SQ8 hanya membutuhkan penyimpanan sebesar 140 GB.

Hasil pengujian kinerja IVF_SQ8:

Pengujian waktu kueri IVF_SQ8 dilakukan di Milvus dengan menggunakan dataset SIFT 1B publik, yang berisi 1 miliar vektor 128 dimensi, untuk membangun indeks.

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_5.png

Kesimpulan utama:

Dengan mengurangi ukuran file indeks, IVF_SQ8 menawarkan peningkatan kinerja yang nyata dibandingkan IVF_FLAT. IVF_SQ8 mengikuti kurva performa yang mirip dengan IVF_FLAT, dengan waktu kueri yang meningkat dengan nq dan nprobe.
Serupa dengan IVF_FLAT, IVF_SQ8 menunjukkan performa yang lebih cepat ketika berjalan pada CPU dan ketika nq dan nprobe lebih kecil.

Pengujian performa recall IVF_SQ8 dilakukan di Milvus dengan menggunakan dataset SIFT 1M publik, yang berisi 1 juta vektor 128 dimensi, dan dataset sarung tangan-200-sudut, yang berisi lebih dari 1 juta vektor 200 dimensi, untuk membangun indeks (nlist = 16.384).

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_6.png

Kesimpulan utama:

Meskipun mengompresi data asli, IVF_SQ8 tidak mengalami penurunan yang signifikan dalam akurasi kueri. Di berbagai pengaturan nprobe, IVF_SQ8 memiliki tingkat penarikan paling banyak 1% lebih rendah daripada IVF_FLAT.

IVF_SQ8H: Pendekatan hybrid GPU/CPU baru yang bahkan lebih cepat dari IVF_SQ8.

IVF_SQ8H adalah jenis indeks baru yang meningkatkan kinerja kueri dibandingkan dengan IVF_SQ8. Ketika indeks IVF_SQ8 yang berjalan di CPU di-query, sebagian besar waktu query dihabiskan untuk menemukan cluster nprobe yang paling dekat dengan vektor input target. Untuk mengurangi waktu kueri, IVF_SQ8 menyalin data untuk operasi kuantisasi kasar, yang lebih kecil daripada file indeks, ke memori GPU - sangat mempercepat operasi kuantisasi kasar. Kemudian gpu_search_threshold menentukan perangkat mana yang menjalankan kueri. Ketika nq >= gpu_search_threshold, GPU menjalankan kueri; jika tidak, CPU menjalankan kueri.

IVF_SQ8H adalah jenis indeks hibrida yang membutuhkan CPU dan GPU untuk bekerja sama. Ini hanya dapat digunakan dengan Milvus yang mendukung GPU.

Hasil uji kinerja IVF_SQ8H:

Pengujian kinerja waktu kueri IVF_SQ8H dilakukan di Milvus menggunakan dataset SIFT 1B publik, yang berisi 1 miliar vektor 128 dimensi, untuk membangun indeks.

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_7.png

Poin-poin penting:

Ketika nq kurang dari atau sama dengan 1.000, IVF_SQ8H melihat waktu kueri hampir dua kali lebih cepat dari IVFSQ8.
Ketika nq = 2000, waktu kueri untuk IVFSQ8H dan IVF_SQ8 adalah sama. Namun, jika parameter gpu_search_threshold lebih rendah dari 2000, IVF_SQ8H akan mengungguli IVF_SQ8.
Tingkat penarikan kueri IVF_SQ8H identik dengan IVF_SQ8, yang berarti lebih sedikit waktu kueri yang dicapai tanpa kehilangan akurasi pencarian.

Pelajari lebih lanjut tentang Milvus, platform manajemen data vektor berskala besar.

Milvus adalah platform manajemen data vektor yang dapat mendukung aplikasi pencarian kemiripan di berbagai bidang yang mencakup kecerdasan buatan, pembelajaran mendalam, perhitungan vektor tradisional, dan banyak lagi. Untuk informasi tambahan tentang Milvus, lihat sumber-sumber berikut:

Milvus tersedia di bawah lisensi sumber terbuka di GitHub.
Jenis indeks tambahan, termasuk indeks berbasis grafik dan pohon, didukung di Milvus. Untuk daftar lengkap jenis indeks yang didukung, lihat dokumentasi untuk indeks vektor di Milvus.
Untuk mempelajari lebih lanjut tentang perusahaan yang meluncurkan Milvus, kunjungi Zilliz.com.
Mengobrol dengan komunitas Milvus atau dapatkan bantuan untuk masalah di Slack.

Metodologi

Lingkungan pengujian kinerja

Konfigurasi server yang digunakan di seluruh pengujian performa yang dirujuk dalam artikel ini adalah sebagai berikut:

Intel ® Xeon ® Platinum 8163 @ 2.50GHz, 24 core
GeForce GTX 2080Ti x 4
Memori 768 GB

Konsep teknis yang relevan

Meskipun tidak diperlukan untuk memahami artikel ini, berikut adalah beberapa konsep teknis yang berguna untuk menginterpretasikan hasil dari pengujian performa indeks kami:

Blog_Mempercepat Pencarian Kemiripan pada Data yang Sangat Besar dengan Pengindeksan Vektor_8.png