Topik ini menjelaskan jenis-jenis indeks vektor yang didukung oleh OpenSearch Vector Search Edition.
Ikhtisar Pengambilan Vektor
Di era informasi, data tersedia dalam berbagai modalitas seperti teks, gambar, video, dan audio. Data multimodal ini dapat menyampaikan detail yang tidak bisa diwakili oleh teks saja, seperti warna, bentuk, gerakan, suara, dan hubungan spasial.
Modalitas informasi juga semakin beragam di berbagai bidang.
Dalam skenario multimodal, informasi diklasifikasikan menjadi dua kategori: data terstruktur dan tidak terstruktur.
Data tidak terstruktur sering kali sulit dipahami oleh komputer. Metode pengambilan tradisional yang mengandalkan tokenisasi teks tidak dapat memenuhi kebutuhan pencarian di berbagai bidang. Pencarian vektor adalah solusi ideal untuk masalah ini.
Apa itu vektor, dan bagaimana cara kerja pengambilan vektor?
Data tidak terstruktur dari dunia fisik diubah menjadi vektor multi-dimensi. Vektor-vektor ini merepresentasikan entitas dan hubungan di antara mereka.
Kemudian, jarak antara vektor dihitung. Biasanya, jarak yang lebih kecil menunjukkan kesamaan yang lebih tinggi. Sistem mengambil hasil yang paling mirip untuk menyelesaikan pencarian.
Algoritma
linier
Algoritma linier menghitung jarak secara linier untuk semua data vektor.
Skenario: Gunakan algoritma ini jika Anda memerlukan tingkat recall 100%.
Kelemahan: Algoritma ini tidak efisien dan mengonsumsi sumber daya yang signifikan, seperti CPU dan memori, saat memproses sejumlah besar data.
Pengelompokan
Pengelompokan Terkuantisasi
Ikhtisar:
Pengelompokan Terkuantisasi adalah algoritma pengambilan vektor yang dikembangkan oleh Alibaba berdasarkan pengelompokan K-means. Algoritma ini pertama-tama mengelompokkan dokumen vektor menjadi n pusat. Kemudian setiap dokumen ditetapkan ke pusat terdekatnya, membangun n daftar terbalik. N pusat ini dan daftar terbalik yang sesuai membentuk konten utama indeks Pengelompokan Terkuantisasi (QC). Selama pengambilan, kueri pertama kali menghitung jaraknya ke subset pusat dan memilih yang terdekat. Lalu, kueri menghitung jaraknya ke dokumen dalam daftar terbalik pusat yang dipilih. Akhirnya, ia mengembalikan top-k dokumen terdekat dengan kueri.
Perlu dicatat bahwa QC mendukung kuantisasi numerik fp16 dan int8, yang dapat mengurangi ukuran indeks dan meningkatkan kinerja pengambilan. Namun, ini mungkin sedikit mengurangi tingkat recall. Anda dapat mengonfigurasi fitur ini berdasarkan kebutuhan Anda.
Algoritma QC cocok untuk skenario data real-time atau skenario yang memiliki sumber daya GPU dan memerlukan latensi rendah.
Pengaturan Parameter:
Perbandingan Kinerja:
HNSW
Ikhtisar:
Hierarchical Navigable Small World (HNSW) adalah algoritma pengambilan vektor berbasis grafik kedekatan. Ini pertama-tama membangun grafik kedekatan di mana tepi dibuat antara vektor yang saling berdekatan. Vektor dan informasi kedekatannya membentuk konten utama indeks HNSW. Selama pengambilan, pencarian dimulai dari node entri. Ini menghitung jarak antara kueri dan semua tetangga node entri, lalu memilih tetangga terdekat sebagai node berikutnya untuk dilintasi. Proses ini diulang hingga pencarian konvergen. Konvergensi terjadi ketika tidak ada tetangga dari node saat ini yang lebih dekat ke kueri daripada node terdekat yang sudah ditemukan.
Untuk mempercepat konvergensi, HNSW membangun struktur grafik kedekatan berlapis, yang mirip dengan logika kueri daftar lompat. Proses pengambilan dimulai dari lapisan teratas dan bergerak ke bawah. Logika pengambilan serupa untuk setiap lapisan, dengan perbedaan kecil pada lapisan 0. Setelah traversal konvergen ke sebuah node di lapisan k, node tersebut menjadi titik masuk untuk lapisan k-1, dan traversal berlanjut. Lapisan k memiliki node yang lebih jarang dengan jarak yang lebih besar di antara mereka daripada lapisan k-1. Hal ini memungkinkan langkah yang lebih besar dan iterasi yang lebih cepat selama traversal di lapisan k.
Pengaturan Parameter:
QGraph
Ikhtisar:
Quantized Graph (QGraph) adalah algoritma yang ditingkatkan yang dikembangkan oleh OpenSearch berdasarkan HNSW. Selama pembuatan indeks, ia secara otomatis mengkuantisasi data mentah sebelum membangun indeks grafik. Dibandingkan dengan HNSW, QGraph dapat secara signifikan mengurangi ukuran indeks dan overhead memori, mengurangi indeks hingga seperdelapan dari ukuran aslinya. Selain itu, menggunakan optimasi instruksi CPU untuk perhitungan integer, kinerja QGraph beberapa kali lebih baik daripada HNSW. Setelah kuantisasi, keunikan vektor berkurang, yang menyebabkan tingkat recall QGraph lebih rendah daripada HNSW. Dalam skenario dunia nyata, efek ini dapat dikurangi dengan mengambil lebih banyak hasil.
QGraph mendukung kuantisasi int4, int8, dan int16 untuk data. Tingkat kuantisasi yang berbeda memengaruhi penggunaan memori indeks vektor, kinerja kueri, dan tingkat recall secara berbeda. Secara umum, lebar bit integer yang lebih kecil menghasilkan jejak memori yang lebih kecil untuk indeks vektor, kinerja yang lebih tinggi, dan tingkat recall yang lebih rendah. Karena sifat set instruksi CPU yang mendasarinya, kuantisasi int16 memiliki kinerja dan tingkat recall yang hampir sama dengan data yang tidak dikuantisasi.
Pengaturan Parameter:
CAGRA
Ikhtisar:
CUDA ANN GRAph-based (CAGRA) adalah algoritma pengambilan vektor berbasis grafik kedekatan. Ini dioptimalkan untuk GPU NVIDIA dan cocok untuk skenario dengan konkurensi tinggi dan permintaan batch.
Berbeda dengan HNSW, CAGRA hanya membangun grafik kedekatan satu lapisan untuk memfasilitasi komputasi paralel. Selama kueri, algoritma ini secara iteratif mempertahankan set kandidat yang terurut. Di setiap iterasi, ia memilih top-k node dari set kandidat sebagai titik awal pencarian dan mencoba memperbarui set dengan tetangga mereka. Proses ini berlanjut hingga semua top-k node dalam set kandidat telah digunakan sebagai titik awal pencarian, pada titik mana algoritma konvergen.
Algoritma CAGRA diimplementasikan dengan dua kebijakan: single-CTA dan multi-CTA. Kebijakan single-CTA memetakan kueri vektor tunggal ke blok thread tunggal dan efisien untuk ukuran batch besar. Kebijakan multi-CTA menggunakan beberapa blok thread untuk mengeksekusi kueri vektor tunggal. Kebijakan ini lebih baik memanfaatkan daya komputasi paralel GPU dan mencapai tingkat recall yang lebih tinggi ketika ukuran batch kecil. Namun, throughputnya lebih rendah daripada kebijakan single-CTA ketika ukuran batch besar. Sistem secara otomatis memilih kebijakan optimal berdasarkan beban kerja selama runtime.
Pengaturan Parameter:
DiskANN
Ikhtisar:
DiskANN adalah teknik pencarian tetangga terdekat perkiraan (ANN) berbasis disk yang dirancang untuk menangani dataset yang sangat besar. Ini menggunakan algoritma grafik Vamana untuk secara efisien menggunakan penyimpanan disk untuk dataset yang melebihi memori yang tersedia, sambil mempertahankan pengindeksan dan pengambilan vektor berkinerja tinggi.
Algoritma DiskANN hanya didukung ketika family node data adalah SSD.
Pengaturan Parameter:
CagraHnsw
Ikhtisar:
CagraHnsw adalah algoritma pengambilan vektor yang dikembangkan oleh OpenSearch. Ini menggabungkan keunggulan algoritma CAGRA dan HNSW dan cocok untuk skenario yang memerlukan pembuatan indeks cepat untuk dataset besar.
Algoritma CagraHnsw mirip dengan CAGRA selama fase pembuatan indeks. Ini menggunakan GPU untuk membangun indeks dan mengonversi file indeks ke format yang kompatibel dengan algoritma HNSW. Selama fase pengambilan, algoritma HNSW pada CPU melakukan pencarian. Strategi ini menggabungkan pembuatan indeks berbasis GPU yang efisien dari CAGRA dengan pengambilan berbasis CPU yang hemat biaya. Pendekatan ini menghindari kebutuhan akan instance GPU mahal selama pengambilan. Akibatnya, CagraHnsw lebih hemat biaya daripada CAGRA dalam skenario yang tidak memerlukan kueri konkurensi tinggi yang berkelanjutan.
Jenis jarak vektor
Pengambilan vektor bekerja dengan menghitung kesamaan antara vektor dan mengembalikan top-k vektor yang paling mirip. Dalam proses ini, kesamaan ditentukan dengan menghitung jarak. Biasanya, skor jarak yang lebih kecil menunjukkan bahwa vektor lebih dekat, dan skor yang lebih besar menunjukkan bahwa mereka lebih jauh.
Ruang vektor yang berbeda menggunakan metrik jarak yang berbeda untuk menghitung jarak antara vektor. OpenSearch Vector Search Edition mendukung metrik berikut: jarak Euclidean kuadrat, produk dalam, dan jarak kosinus.
Jarak Euclidean kuadrat (SquareEuclidean)
Jarak Euclidean, salah satu ukuran jarak yang paling umum, mewakili jarak garis lurus antara dua vektor. Ini dihitung dengan mengambil akar kuadrat dari jumlah perbedaan kuadrat antara koordinat mereka. Jarak Euclidean yang lebih kecil menunjukkan bahwa kedua vektor lebih mirip. Rumus untuk jarak Euclidean adalah sebagai berikut:
Jarak produk dalam (InnerProduct)
Produk dalam adalah produk titik atau produk skalar dari dua vektor. Hasil produk dalam yang lebih besar menunjukkan kesamaan yang lebih besar antara vektor. Ini dihitung dengan mengalikan elemen-elemen yang sesuai dari dua vektor dan kemudian menjumlahkan produk-produk tersebut. Metrik produk dalam umum dalam skenario pencarian dan rekomendasi. Pilihan untuk menggunakan metrik produk dalam biasanya bergantung pada apakah algoritma menggunakan model produk dalam. Rumus untuk produk dalam adalah sebagai berikut:
Jarak Kosinus
Jarak kosinus mengukur kesamaan antara dua vektor berdasarkan kosinus sudut di antara mereka. Nilai yang dihasilkan berkisar dari -1 hingga 1. Nilai 1 menunjukkan bahwa vektor menunjuk ke arah yang sama, mewakili kesamaan tertinggi. Nilai -1 menunjukkan bahwa mereka menunjuk ke arah yang berlawanan, mewakili kesamaan terendah. Nilai 0 menunjukkan bahwa vektor tegak lurus. Semakin dekat nilainya dengan 1, semakin mirip vektornya. Metrik ini sering digunakan dalam skenario pengambilan kesamaan teks. Rumusnya adalah sebagai berikut:
