DiskANN Explorer: Pencarian Vektor Skala Miliar Dari SSD

DiskANN menyimpan salinan kecil yang dikompresi denganPQ dari setiap vektor di RAM serta vektor lengkap + grafik di SSD. Pencarian menjelajahi grafik dengan perbandingan RAM yang murah, kemudian menyusun ulang peringkat kandidat teratas dengan beberapa pembacaan disk yang mahal.

Alasan di balik adanya " DiskANN ": hambatan memori

RAMPQ kode (32 B/vec)3.2 GB

DiskVektor lengkap + grafik (3072 B/vec)307.2 GB

100M vektor × dimensi 768 Disk / RAM ≈ 96×

Satu komoditas SSD dapat dengan mudah menampung sisi disk. Sisi RAM dapat muat di laptop mana pun. Tanpa trik PQ, Anda memerlukan server dengan ratusan GB RAM hanya untuk memuat dataset tersebut.

Derajat graf

Kumpulan kandidat

Peringkat ulang5

Pembacaan disk

Kecepatan420ms

Per langkah

Perbandingan PQ (RAM) dalam kumpulan kandidat penyortiran ulang disk top-K hasil

Langkah Saat Ini

30 / 30

Pencarian selesai. Top-3: [1, 28, 27].

Biaya sejauh ini

RAM PQ membandingkan20≈ 20 µs

SSD membaca5≈ 500 µs

Latensi total0.52 ms

Dimodelkan dengan PQ ≈ 1 µs, SSD ≈ 100 µs. Angka riil bergantung pada perangkat keras.

Statistik Pencarian

Telah dikunjungi

20 / 36

Diurutkan ulang

Top-3

[1, 28, 27]

Cara kerj DiskANN

Bangun grafik " Vamana ": grafik kNN satu lapisan (derajat R) yang dioptimalkan untuk tata letak disk berurutan. Tanpa hierarki — hanya satu grafik besar.
Kuantisasi dan pemisahan penyimpanan: setiap vektor mendapatkan kode " PQ " yang sangat kecil (misalnya 32 byte). Kode " PQ " disimpan di RAM. Vektor lengkap + tepi graf disimpan di SSD.
Beam-walk dengan jarak " PQ ": dari titik masuk tetap (medoid), pertahankan kumpulan kandidat berukuran L. Pilih yang terbaik, perluas tetangganya, perkirakan jarak hanya menggunakan kode in-RAM PQ . Tidak ada I/O disk selama proses beam-walk.
Lakukan pemeringkatan ulang finalis dari disk: jarak entri teratas dalam kumpulan kandidat telah diperkirakan menggunakan PQ. Baca vektor lengkapnya dari disk dan hitung ulang jarak yang tepat untuk memperbaiki peringkat.
Kembalikan top-K. Total I/O disk = sejumlah kecil pembacaan acak, biasanya kurang dari 20.

Perdagangan

Alasan skalabilitasnya: RAM hanya menyimpan kode terkompresi. Kumpulan data 1 miliar vektor dengan ukuran PQ 32 byte membutuhkan ~32 GB RAM — yang dapat ditampung dalam satu workstation.
Mengapa ini lebih lambat daripada HNSW: SSD pembacaan acak ~100× lebih lambat daripada RAM. Bahkan dengan hanya ~10 pembacaan, latensi kueri didominasi oleh disk.
Mengapa metode ini masih lebih unggul daripada " IVF_PQ " dalam hal recall: langkah re-rank memperbaiki kesalahan kuantisasi yang tidak dapat diperbaiki oleh metode berbasis " PQ" murni.

Model mental: " PQ " adalah tes murah untuk menilai "apakah lingkungan ini menjanjikan?". Pembacaan disk adalah pemeriksaan mahal untuk "memverifikasi secara aktual". " DiskANN " menyelesaikan sebagian besar pekerjaannya dengan tes murah tersebut.

Apa itu " DiskANN"?

DiskANN adalah indeks tetangga terdekat aproksimatif berbasis graf yang dirancang untuk dataset yang tidak muat dalam RAM. Sistem ini membangun grafVamana berlapis tunggal yang disusun untuk akses disk yang efisien, menyimpan kode kuantisasi produk (PQ) berukuran kecil untuk setiap vektor di memori, dan menyimpan vektor presisi penuh serta tepi graf di SSD. Proses pencarian menelusuri graf menggunakan perbandingan in-RAM PQ yang efisien dan hanya mengakses disk untuk menyusun ulang peringkat beberapa finalis.

Dalam Milvus, DiskANN mendukung opsi indeks pada disk: koleksi berskala miliaran dapat dicari pada mesin dengan puluhan — bukan ratusan — gigabyte RAM, sementara langkah pemeringkatan ulang pada disk menjaga recall mendekati indeks grafik dalam memori.

Apa yang dikendalikan oleh kenop-kenop tersebut

R (derajat graf, waktu pembuatan): jumlah maksimum tepi per simpul dalam graf " Vamana ". Nilai R yang lebih tinggi memberikan konektivitas dan recall yang lebih baik, dengan konsekuensi graf yang lebih besar di disk dan proses pembuatan yang lebih lambat.
L / search_list (waktu kueri): kumpulan kandidat yang dipertahankan selama pencarian beam — pengatur utama recall/latensi, setara dengan ef di HNSW. Nilainya harus setidaknya sebesar top-K.
Anggaran pemeringkatan ulang: berapa banyak finalis yang vektor lengkapnya diambil dari SSD untuk penilaian yang tepat. Masing-masing merupakan pembacaan disk acak, sehingga di sinilah letak latensi kueri — dan juga tempat di mana kesalahan aproksimasi " PQ " diperbaiki.

DiskANN vs HNSW vs IVF

Pilih " DiskANN " ketika dataset (atau penggunaan memori) melebihi kapasitas " RAM": opsi ini melayani kueri dengan akurasi tinggi menggunakan sebagian kecil memori, dengan imbalan latensi tingkat milidetik yang didominasi oleh pembacaan " SSD ". Jika semuanya muat dengan nyaman di memori, " HNSW " memberikan respons lebih cepat. Jika Anda membutuhkan pembentukan indeks yang cepat atau penghematan memori sedang tanpa melibatkan disk, varian " IVF " berada di antara keduanya.

Pertanyaan yang Sering Diajukan

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

Ketika vektor Anda tidak lagi muat di RAM — atau RAM untuk menyimpannya membutuhkan biaya lebih dari yang ingin Anda bayar. Satu miliar vektor float 768-dimensi membutuhkan ~3 TB memori untuk HNSW, tetapi hanya puluhan GB RAM ditambah SSD dengan DiskANN. Jika dataset muat dengan nyaman di memori, HNSW tetap menjadi pilihan dengan latensi lebih rendah.

Perangkat keras apa yang dibutuhkan oleh DiskANN?

Kecepatan " NVMe " ( SSD ) merupakan persyaratan utama, karena latensi kueri didominasi oleh beberapa pembacaan disk acak (masing-masing ~100 µs). Kebutuhan " RAM " relatif sederhana: kira-kira kode " PQ " (misalnya 32–64 byte per vektor) ditambah buffer kerja.

Apakah " DiskANN " lebih lambat daripada indeks dalam memori seperti " HNSW"?

Per kueri, ya — biasanya dalam milidetik satu digit rendah dibandingkan sub-milidetik untuk " HNSW" dalam memori, karena setiap "disk re-rank" ~100× lebih lambat daripada akses " RAM ". Komprominya adalah biaya: " DiskANN " melayani dataset yang sama dengan " RAM " yang lebih rendah satu orde besar sambil mempertahankan recall di atas 90–95%.

Bagaimana cara " DiskANN " mempertahankan tingkat recall yang tinggi meskipun menggunakan kompresi " PQ "?

PQ Kode hanya digunakan untuk mengarahkan penelusuran graf, bukan untuk menghasilkan skor akhir. Sebelum mengembalikan hasil, ` DiskANN ` membaca vektor presisi penuh dari kandidat teratas dari ` SSD ` dan menyusun ulang peringkatnya secara tepat, memperbaiki kesalahan kuantisasi yang tidak dapat diperbaiki oleh indeks berbasis ` PQ` murni seperti ` IVF_PQ `.

Pelajari lebih lanjut: baca dokumentasi "DiskANN " untuk persyaratan pengaturan, atau lihat "Index Explained " untuk panduan pengambilan keputusan lengkap.