Apa itu Approximate Nearest Neighbor (ANN)

Approximate Nearest Neighbor (ANN) adalah teknik yang digunakan untuk dengan perkiraan menemukan tetangga terdekat dari data vektor berdimensi tinggi, seperti vektor hasil embedding teks atau gambar, tanpa melakukan perhitungan yang tepat.

Dalam data vektor berdimensi tinggi, menghitung jarak ke setiap titik data untuk menemukan yang terdekat dapat menjadi mahal secara komputasi. Terutama dalam dataset besar atau aplikasi real-time, biaya komputasi ini dapat menjadi tantangan. ANN menggunakan algoritma yang cepat dan efisien untuk dengan cepat menemukan tetangga terdekat, memungkinkan pencarian tetangga dengan kecepatan praktis. Algoritma-algoritma seperti ini digunakan dalam berbagai bidang, termasuk pengambilan gambar serupa dan sistem rekomendasi.

Artikel ini memperkenalkan algoritma-algoritma ANN berikut:

• LSH (Locality-Sensitive Hashing)
• HNSW (Hierarchical Navigable Small World)
• IVF (Inverted File)

LSH (Locality-Sensitive Hashing)

LSH menggunakan fungsi hash khusus yang memastikan item-item serupa di-hash ke dalam "ember" yang sama dengan probabilitas tinggi.

Algoritma LSH

Algoritma LSH terdiri dari langkah-langkah kunci berikut:

1. Pemilihan Fungsi Hash: Pilih fungsi hash yang memaksimalkan probabilitas item-item serupa ditempatkan dalam ember yang sama.
2. Peng-hash-an Data: Berikan setiap titik data ke dalam ember menggunakan fungsi-fungsi hash.
3. Pencarian dalam Ember: Cari titik-titik data yang diberikan ke ember yang sama dengan titik kueri.
4. Pemurnian Kandidat: Pilih titik data yang paling dekat dari kandidat yang diperoleh melalui pencarian berbasis ember dengan perhitungan lebih lanjut.

HNSW (Hierarchical Navigable Small World)

HNSW menggambarkan data menggunakan struktur grafik multi-lapis untuk mencari dengan efisien titik-titik data dekat dari titik kueri.

Algoritma HNSW

Algoritma HNSW terdiri dari langkah-langkah utama berikut:

1. Konstruksi Grafik: Bangun struktur grafik multi-lapis dengan titik-titik data sebagai simpul.
2. Penugasan Tautan: Berikan tautan antara titik-titik data yang dekat untuk memungkinkan eksplorasi yang efisien pada grafik.
3. Pencarian Hierarkis: Mulai pencarian dari lapisan atas grafik, secara bertahap bergerak ke bawah untuk menemukan titik data terdekat dengan titik kueri.

IVF (Inverted File)

Inverted File (IVF) adalah metode efisien untuk mencari data berdimensi tinggi melalui pengelompokan.

Algoritma IVF

Algoritma IVF dasar terstruktur sebagai berikut:

1. Pengelompokan: Bagi titik-titik data menjadi beberapa kelompok dan berikan ID ke setiap kelompok.
2. Pengindeksan: Simpan hubungan antara ID kelompok dan titik-titik data individu dalam indeks (file terbalik).
3. Pencarian: Ketika kueri diberikan, identifikasi kelompok terdekat dan lakukan perhitungan jarak terperinci dalam kelompok tersebut untuk menemukan tetangga terdekat.

Perbandingan Setiap Metode

Kecepatan dan Akurasi

• LSH: Menawarkan pencarian cepat, tetapi sering memiliki akurasi yang lebih rendah dibandingkan metode lain.
• HNSW: Menyeimbangkan akurasi tinggi dengan efisiensi, tetapi mungkin memerlukan penggunaan memori yang lebih tinggi.
• IVF: Memungkinkan pencarian cepat melalui pengindeksan, tetapi akurasi dapat tidak stabil karena kualitas pengelompokan.

Penggunaan Memori

• LSH: Secara umum memiliki efisiensi memori yang baik karena menggunakan tabel hash.
• HNSW: Struktur grafik canggih dapat menyebabkan penggunaan memori yang lebih tinggi.
• IVF: Penggunaan memori meningkat dengan volume data karena perlu menyimpan informasi indeks.

Kompleksitas Implementasi

• LSH: Algoritma sederhana dan dapat diimplementasikan dengan mudah dalam banyak bahasa pemrograman.
• HNSW: Implementasi agak menantang karena struktur grafik yang kompleks.
• IVF: Struktur data relatif sederhana, tetapi pengelompokan dan pengindeksan efisien diperlukan.

Referensi

https://archive.pinecone.io/learn/vector-indexes/