🟣FAISS

Facebook AI Similarity Search

FAISS (Facebook AI Similarity Search) adalah sebuah pustaka open-source yang dikembangkan oleh tim AI Research di Meta (dulu Facebook) untuk melakukan pencarian nearest neighbor secara cepat pada data berukuran sangat besar dan berdimensi tinggi. FAISS dirilis sekitar tahun 2017 dan segera populer karena bisa mengatasi pencarian di dataset dengan jutaan hingga miliaran vektor, misalnya untuk rekomendasi musik, gambar, atau sistem pencarian berbasis embedding. Berbeda dengan Annoy yang berbasis pohon acak, FAISS lebih menekankan efisiensi matematis dengan optimasi berbasis vector quantization dan GPU acceleration, sehingga cocok untuk big data.

Secara matematis, FAISS tetap berangkat dari konsep mencari vektor xqx_qxq​ (query) yang paling dekat dengan vektor lain xix_ixi​ dalam himpunan data, menggunakan metrik jarak, biasanya Euclidean distance atau cosine similarity.

FAISS tidak menghitung jarak ke semua vektor secara langsung (yang memakan waktu). FAISS menggunakan teknik seperti IndexFlat (brute-force tapi dioptimasi), IVF (Inverted File Index), dan PQ (Product Quantization). Dalam PQ, vektor berdimensi besar dipecah menjadi sub-vektor, lalu tiap sub-vektor dikodekan ke centroid terdekat hasil K-Means. Dengan begitu, perhitungan jarak bisa diganti dengan perhitungan pada centroid yang jumlahnya jauh lebih sedikit. Hal ini mempercepat pencarian tanpa terlalu banyak mengorbankan akurasi.

Annoy dapat diibaratkan membuat “pohon acak” untuk memotong ruang pencarian, FAISS lebih seperti “mengompresi” ruang vektor menjadi representasi yang lebih sederhana, lalu melakukan pencarian cepat di ruang terkompresi itu. Karena bisa dijalankan di GPU, FAISS sangat unggul untuk dataset raksasa, misalnya embedding gambar dari model deep learning dengan dimensi 512 atau 1024.

IndexFlat disebut juga metode brute force optimized, karena prinsipnya menghitung jarak antara query dengan seluruh vektor dalam dataset tanpa ada kompresi atau clustering. Berbeda dengan IVF atau PQ, IndexFlat tidak melakukan pengelompokan data maupun pengurangan dimensi, sehingga hasil pencariannya selalu exact nearest neighbor (akurasi 100%).

Inverted File Index (IVF). IVF bekerja dengan cara membagi seluruh ruang vektor ke dalam beberapa cluster menggunakan algoritma seperti k-means. Setelah ruang dibagi, setiap data vektor hanya disimpan pada cluster terdekatnya. Ketika ada query, FAISS tidak perlu mencari tetangga terdekat di seluruh dataset, melainkan cukup pada beberapa cluster yang paling dekat dengan query tersebut. Dengan cara ini, pencarian bisa menjadi jauh lebih cepat karena jumlah perhitungan jarak yang dilakukan lebih sedikit dibandingkan pencarian brute force.

dimana $x_q$ query, $c_j$ centroid cluster ke-j

Selain IVF, FAISS juga menggunakan metode kompresi agar dataset yang besar bisa disimpan dengan efisien dan pencarian tetap cepat. Salah satunya adalah Product Quantization (PQ). Ide dari PQ adalah memecah vektor berdimensi tinggi menjadi beberapa sub-vektor berdimensi lebih kecil. Setiap sub-vektor kemudian dikuantisasi, yaitu diganti dengan indeks dari centroid terdekat pada kamus kecil (codebook). Dengan demikian, setiap vektor asli tidak lagi disimpan dalam bentuk angka floating-point penuh, melainkan sebagai kombinasi kode diskrit dari sub-vektornya. Teknik ini sangat efektif karena mampu mengurangi kebutuhan memori secara drastis sambil tetap menjaga akurasi pencarian.

IVF + PQ adalah kombinasi dari dua konsep yang digunakan FAISS. Pertama, ruang vektor dibagi menjadi cluster dengan IVF. Lalu, setiap vektor yang masuk ke cluster disimpan dalam bentuk terkompresi menggunakan PQ. Pada saat pencarian, FAISS hanya akan membuka beberapa cluster terdekat query (bukan semua cluster), kemudian menghitung jarak antara query dan vektor di dalam cluster tersebut dengan memanfaatkan representasi terkompresi dari PQ. Kombinasi ini membuat FAISS sangat efisien: pencarian cepat karena hanya fokus pada sebagian kecil data, dan penggunaan memori lebih hemat karena data disimpan dalam bentuk terkuantisasi.