HNSW

HNSW adalah salah satu algoritma approximate nearest neighbor search yang berbasis graf. Algoritma ini dikembangkan oleh Malkov dan Yashunin pada tahun 2016 dengan tujuan untuk mempercepat pencarian tetangga terdekat pada dataset besar, sekaligus memberikan akurasi yang sangat tinggi (mendekati exact search) namun tetap efisien dalam penggunaan memori. HNSW merupakan pengembangan dari konsep Small World Graphs, yaitu graf yang setiap simpulnya (node) bisa terhubung dengan node lain dalam jarak relatif pendek melalui lintasan tertentu, sehingga memungkinkan navigasi cepat di dalam graf. Dalam konteks ANN, data vektor direpresentasikan sebagai node, dan hubungan antar node ditentukan oleh kedekatan jaraknya.

HNSW membangun struktur graf bertingkat (hierarchical). Pada level teratas, hanya ada sedikit node dengan koneksi yang jarang, sementara pada level terbawah, terdapat semua node dengan koneksi yang lebih rapat. Proses pencarian dilakukan secara hierarkis: pencarian dimulai dari level atas dengan graf yang lebih jarang untuk menemukan area umum di mana query berada, lalu turun ke level yang lebih rendah untuk memperbaiki pencarian hingga akhirnya menemukan tetangga terdekat di level dasar. Struktur bertingkat ini memungkinkan algoritma menemukan approximate nearest neighbors dengan sangat cepat, karena setiap langkah navigasi hanya melibatkan sebagian kecil node.

Alih-alih menghitung jarak ke semua titik, HNSW menggunakan strategi greedy search di dalam graf: dari satu node, query berpindah ke node tetangga yang jaraknya lebih dekat, sampai tidak ada tetangga yang lebih dekat lagi. Dengan struktur hierarki, langkah-langkah ini lebih efisien karena pada level tinggi, jumlah node yang harus diperiksa sedikit, dan di level rendah pencarian lebih detail.

Kesimpulan: Annoy memakai random projection tree, FAISS memakai quantization & clustering, sedangkan HNSW memakai navigasi graf hierarkis. HNSW sering dianggap state-of-the-art untuk ANN karena kombinasi akurasi tinggi, kecepatan, dan efisiensi memori.