HNSW Explorer: Dunia Kecil Hierarkis yang Dapat Dinavigasi, Divisualisasikan

Amati perjalanan pencarian melalui grafik berlapis — dari lapisan atas yang jarang (jalan raya) hingga lapisan bawah yang padat (jalan lokal). Seret titik kueri pada Lapisan 0 dan sesuaikan M / ef untuk melihat bagaimana grafik tersebut berubah.

Jumlah tetangga maksimum per simpul

ef8

Kumpulan kandidat Lapisan-0

Kecepatan450ms

Per langkah

Langkah Saat Ini

14 / 14

Pencarian selesai. Top-3: [3, 10, 4].

Statistik Pencarian

Telah dikunjungi

17 / 30

Lapisan

Entri

Simpul 0

Top-3

[3, 10, 4]

Distribusi Lapisan

Cara kerj HNSW

Grafik berlapis: setiap simpul secara acak diberi lapisan maksimum menggunakan distribusi eksponensial. Sebagian besar simpul hanya berada di Lapisan 0; sangat sedikit yang mencapai lapisan teratas.
Di dalam setiap lapisan: setiap simpul terhubung ke tetangga terdekatnya yang memiliki jarak terpendek ( M ). Lapisan yang lebih tinggi bersifat jarang (sedikit simpul, tepi panjang = "jalan raya"). Lapisan 0 bersifat padat (semua simpul, tepi pendek = "jalan lokal").
Pencarian dimulai dari atas: dari titik masuk tetap, bergerak secara rakus ke tetangga terdekat dengan kueri, ulangi hingga tidak ada peningkatan.
Turunkan satu lapisan dan ulangi: posisi dari lapisan sebelumnya menjadi titik awal pergerakan lapisan berikutnya. Setiap penurunan akan menyempurnakan hasil dengan tepi yang lebih halus.
Layer 0 dengan " ef": pada lapisan terbawah, alih-alih berhenti di minimum lokal pertama, " HNSW " mempertahankan kumpulan ef kandidat terbaik dan memperluas lingkungan sekitarnya. Lebih besar ef → semakin akurat namun semakin lambat.

Mengapa ini cepat: lapisan teratas bertindak seperti indeks di atas indeks — Anda menempuh jarak yang sangat jauh hanya dalam beberapa lompatan, lalu memperbesar. Untuk N titik, pencarian mengunjungi sekitar O(log N) node, bukan N.

Apa itu " HNSW"?

HNSW (Hierarchical Navigable Small World) adalah algoritma tetangga terdekat aproksimatif berbasis graf. Algoritma ini mengatur vektor ke dalam tumpukan graf "small-world" yang dapat dinavigasi: lapisan atas yang jarang dengan tepi jangkauan panjang untuk rute kasar, dan lapisan bawah yang padat dengan tepi pendek untuk perjalanan akhir yang lebih detail. Pencarian secara rakus melompat menuju kueri pada setiap lapisan, lalu turun ke lapisan berikutnya — mengunjungi kira-kira O(log N) node alih-alih memindai seluruh N.

HNSW adalah indeks vektor dalam memori yang paling banyak digunakan, dan indeks graf default di Milvus. Milvus juga menawarkan HNSW_SQ dan HNSW_PQ varian yang mengkuantisasi vektor yang disimpan untuk mengurangi penggunaan memori dengan sedikit pengorbanan pada recall.

HNSW parameter dalam Milvus

M (waktu pembangunan): jumlah tepi maksimum per simpul, pengaturan yang sama dengan penggeser di atas. Nilai tipikal adalah 8–64. Nilai M yang lebih tinggi meningkatkan recall dan konektivitas graf, tetapi meningkatkan penggunaan memori secara linier dan memperlambat proses pembangunan.
efConstruction (waktu pembuatan): ukuran kumpulan kandidat yang digunakan saat menyisipkan simpul. Nilai yang lebih tinggi menghasilkan grafik berkualitas lebih baik (recall yang lebih tinggi) dengan mengorbankan waktu pembuatan indeks yang lebih lambat. Nilai umumnya berkisar antara 100–500.
ef / ef_search (waktu kueri): kumpulan kandidat yang disimpan selama proses Layer-0 walk — pengatur utama recall/latensi pada saat pencarian. Nilainya harus setidaknya sebesar top-K. Tingkatkan nilainya hingga recall mencapai titik jenuh; latensi akan meningkat secara linier seiring dengan peningkatan tersebut.

HNSW vs IVF vs DiskANN

HNSW biasanya memberikan latensi kueri terbaik dengan recall tinggi untuk pencarian dalam memori — itulah mengapa ini menjadi pilihan default ketika dataset (ditambah overhead graf) muat dalam RAM. Biayanya adalah memori dan waktu pembangunan: graf menambah overhead yang terasa per vektor, dan penyisipan lebih lambat daripada penugasan k-means di IVF. Pilih IVF saat Anda membutuhkan pembuatan indeks yang cepat atau kuantisasi agresif, dan DiskANN saat dataset terlalu besar untuk RAM tetapi Anda tetap membutuhkan tingkat recall yang tinggi.

Pertanyaan yang Sering Diajukan

Apa yang dikendalikan oleh parameter M dalam HNSW?

M membatasi jumlah tepi yang disimpan setiap simpul per lapisan. Nilai M yang lebih besar membuat grafik lebih terhubung — recall lebih tinggi dan perutean lebih kuat — tetapi memori bertambah secara linier seiring dengan M dan pembuatan indeks menjadi lebih lambat. Nilai antara 8 dan 64 mencakup sebagian besar beban kerja; 16–32 adalah titik optimal yang umum.

Apa perbedaan antara ef dan efConstruction?

Keduanya merupakan ukuran kumpulan kandidat, yang diterapkan pada waktu yang berbeda. " efConstruction " digunakan saat membangun indeks: ini menentukan seberapa teliti setiap simpul yang dimasukkan mencari tetangganya, sehingga mengontrol kualitas graf. " ef " (ef_search) digunakan saat melakukan kueri: ini mengontrol seberapa luas pencarian Layer-0, menukar latensi dengan recall pada setiap kueri.

Berapa banyak memori yang dibutuhkan oleh indeks " HNSW "?

Secara kasar, vektor mentah ditambah grafik: sekitar d × 4 byte per vektor untuk data float32, ditambah sekitar M × 2 × 8 byte tepi per simpul. Untuk penerapan dengan keterbatasan memori, Milvus menawarkan HNSW_SQ dan HNSW_PQ, yang mengkuantisasi vektor yang disimpan, atau DiskANN, yang memindahkan vektor lengkap ke SSD.

Kapan saya harus menggunakan " HNSW " daripada " IVF"?

Gunakan " HNSW " ketika latensi kueri pada tingkat recall tinggi menjadi prioritas dan indeks muat dalam memori — biasanya metode ini yang paling unggul. Pilih " IVF " ketika Anda sering membangun ulang indeks (proses pembangunannya jauh lebih cepat), atau ketika dikombinasikan dengan kuantisasi " SQ8" / "PQ " untuk menyesuaikan dengan anggaran memori yang ketat.

Pelajari lebih lanjut: baca dokumentasi "HNSW " untuk parameter indeks yang tepat, atau lihat "Index Explained " untuk panduan pengambilan keputusan lengkap.