Langsung ke konten

Apa itu HNSW (Hierarchical Navigable Small World)?

HNSW adalah struktur indeks berbasis graf berlapis untuk pencarian vektor terdekat secara cepat, dipakai banyak vector database sebagai metode pencarian default.

Apa itu HNSW?

HNSW (Hierarchical Navigable Small World) adalah metode indeks untuk approximate nearest neighbor (pencarian tetangga terdekat secara perkiraan) pada data vektor berdimensi tinggi. Strukturnya berupa graf berlapis: lapisan atas sangat jarang dan berfungsi seperti rute tol antarwilayah, lapisan bawah sangat padat dan berfungsi seperti jalan lingkungan. Pencarian dimulai dari atas, melompat jauh, lalu turun perlahan untuk menemukan titik paling dekat.

Algoritmanya diperkenalkan Malkov dan Yashunin dalam makalah Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv:1603.09320, pertama terbit 2016, versi final 2018). HNSW menjadi tulang punggung pencarian di Elasticsearch, Qdrant, Weaviate, Milvus, pgvector, dan Chroma.

Cara kerja HNSW

  1. Pembangunan graf bertingkat: Setiap vektor jadi simpul. Vektor diberi level acak dengan distribusi eksponensial, sehingga hanya sebagian kecil simpul yang masuk ke lapisan atas.
  2. Koneksi tetangga: Tiap simpul dihubungkan ke M simpul terdekat di lapisannya sendiri (parameter M). Di lapisan atas koneksinya lebih sedikit dan jarak jangkauannya lebih panjang.
  3. Pencarian masuk dari puncak: Kueri dimulai di simpul masuk lapisan teratas, lalu greedy search bergerak ke tetangga yang paling dekat sampai tidak ada yang lebih dekat lagi.
  4. Turun bertahap: Posisi terbaik di lapisan atas dipakai sebagai titik awal lapisan di bawahnya, diulang sampai lapisan dasar.
  5. Pengambilan tetangga terdekat: Di lapisan dasar, algoritma menelusuri kandidat tambahan (ef atau efSearch) untuk memastikan hasilnya akurat, lalu mengembalikan K tetangga teratas.

Contoh pemakaian

Bayangkan kamu membangun chatbot pencarian dokumen internal dengan 2 juta potongan teks, masing-masing dinyatakan sebagai vektor 1.536 dimensi. Pencarian brute force harus menghitung kemiripan ke seluruh 2 juta vektor di setiap kueri, terlalu lambat untuk dipakai chat. Dengan indeks HNSW, waktu pencarian turun ke hitungan milidetik karena sistem hanya menyentuh sebagian kecil simpul.

Kamu bisa membuat indeks ini langsung di PostgreSQL lewat pgvector:

CREATE INDEX ON dokumen USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

Batasan dan salah paham umum

  • Hasilnya aproksimasi, bukan pasti. HNSW bisa melewatkan tetangga yang sebenarnya paling dekat. Presisi ditukar dengan kecepatan lewat parameter efSearch.
  • Butuh memori besar. Seluruh graf plus vektor biasanya disimpan di RAM. Jutaan vektor bisa menuntut puluhan gigabyte memori.
  • Mahal untuk data yang sering berubah. Insert menghabiskan lebih banyak komputasi dibanding insert indeks B-tree biasa, dan penghapusan lazimnya ditandai dulu lalu dibersihkan belakangan.
  • Bukan satu-satunya pilihan. IVFFlat lebih hemat memori tetapi kurang akurat, sedangkan Product Quantization (PQ) menekan ukuran vektor dengan kompresi. Pilih sesuai skala dan anggaran.
  • Parameter bukan angka sakti. M tinggi menaikkan recall tetapi memperberat memori dan pembangunan indeks. Uji dengan dataset sendiri sebelum mengunci nilai.

Rujukan resmi

Dicek 11 November 2026.

Istilah Terkait

Vector DatabaseEmbedding AISemantic Search (Pencarian Semantik AI)Cosine Similarity (Kemiripan Kosinus Vektor AI)RAG (Retrieval-Augmented Generation)