hnsw

HNSW

Paket hnsw mengimplementasikan grafik dunia kecil yang dapat dilayari secara hierarkis di Go. Anda dapat membaca tentang cara kerja mereka di sini. Intinya, mereka memungkinkan untuk mendekati pencarian tetangga terdekat dengan data vektor dimensi tinggi.

Paket ini dapat dianggap sebagai alternatif dalam memori untuk database vektor favorit Anda (misalnya Pinecone, Weaviate). Ini menerapkan hanya operasi penting:

Operasi	Kompleksitas	Keterangan
Menyisipkan	$ O (log (n)) $	Masukkan vektor ke dalam grafik
Menghapus	$ O (m^2 cdot log (n)) $	Hapus vektor dari grafik
Mencari	$ O (log (n)) $	Cari tetangga terdekat dari sebuah vektor
Pencarian	$ O (1) $	Mengambil vektor dengan id

Catatan

Kompleksitas perkiraan dimana $ n $ adalah jumlah vektor dalam grafik dan $ M $ adalah jumlah maksimum tetangga yang dapat dimiliki setiap node. Makalah ini adalah sumber yang baik untuk memahami efek dari berbagai parameter konstruksi.

Penggunaan

 go get github.com/coder/hnsw@main

 g := hnsw . NewGraph [ int ]()
g . Add (
    hnsw . MakeNode ( 1 , [] float32 { 1 , 1 , 1 }),
    hnsw . MakeNode ( 2 , [] float32 { 1 , - 1 , 0.999 }),
    hnsw . MakeNode ( 3 , [] float32 { 1 , 0 , - 0.5 }),
)

neighbors := g . Search (
    [] float32 { 0.5 , 0.5 , 0.5 },
    1 ,
)
fmt . Printf ( "best friend: %v n " , neighbors [ 0 ]. Vec )
// Output: best friend: [1 1 1] 

Kegigihan

Sementara semua operasi grafik dalam memori, hnsw menyediakan fasilitas untuk memuat/menghemat dari penyimpanan persisten.

Untuk antarmuka io.Reader / io.Writer , gunakan Graph.Export dan Graph.Import .

Jika Anda menggunakan satu file sebagai backend, HNSW menyediakan jenis SavedGraph yang nyaman sebagai gantinya:

 path := "some.graph"
g1 , err := LoadSavedGraph [ int ]( path )
if err != nil {
    panic ( err )
}
// Insert some vectors
for i := 0 ; i < 128 ; i ++ {
    g1 . Add ( hnsw . MakeNode ( i , [] float32 { float32 ( i )}))
}

// Save to disk
err = g1 . Save ()
if err != nil {
    panic ( err )
}

// Later...
// g2 is a copy of g1
g2 , err := LoadSavedGraph [ int ]( path )
if err != nil {
    panic ( err )
}

Lihat lebih lanjut:

• Ekspor
• Impor
• SavedGraph

Kami menggunakan penyandian biner cepat untuk grafik, sehingga Anda dapat menghemat/memuat hampir pada kecepatan disk. Pada M3 MacBook saya, saya mendapatkan hasil tolok ukur ini:

 goos: darwin
goarch: arm64
pkg: github.com/coder/hnsw
BenchmarkGraph_Import-16            4029            259927 ns/op         796.85 MB/s      496022 B/op       3212 allocs/op
BenchmarkGraph_Export-16            7042            168028 ns/op        1232.49 MB/s      239886 B/op       2388 allocs/op
PASS
ok      github.com/coder/hnsw   2.624s

Saat menyimpan/memuat grafik 100 vektor dengan 256 dimensi.

Pertunjukan

Pada umumnya efek terbesar yang dapat Anda miliki pada kinerja grafik adalah mengurangi dimensi data Anda. Pada 1536 dimensi (default OpenAI), 70% dari proses kueri di bawah parameter default dihabiskan dalam fungsi jarak.

Jika Anda berjuang dengan kelambatan / latensi, pertimbangkan:

• Mengurangi dimensi
• Meningkat $ M $

Dan, jika Anda berjuang dengan penggunaan memori berlebih, pertimbangkan:

• Mengurangi $ M $ alias Graph.M (jumlah maksimum tetangga yang dapat dimiliki setiap node)
• Mengurangi $ m_l $ alias Graph.Ml (parameter generasi level)

Overhead memori

Overhead memori grafik terlihat seperti:

$$ DisplayLines {mem_ {grafik} = n cdot log (n) cdot text {size (id)} cdot m \ mem_ {base} = n cdot d cdot 4 mem_ {total} = mem_ {grafik {mems_ {mems_ {mems {mems {mems {mems {mems.

Di mana:

• $ n $ adalah jumlah vektor dalam grafik
• $ text {size (key)} $ adalah ukuran rata -rata kunci dalam byte
• $ M $ adalah jumlah maksimum tetangga yang dapat dimiliki setiap node
• $ d $ adalah dimensi vektor
• $ mem_ {grafik} $ adalah memori yang digunakan oleh struktur grafik di semua lapisan
• $ mem_ {base} $ adalah memori yang digunakan oleh vektor itu sendiri di lapisan pangkalan atau ke -0

Anda dapat menyimpulkan itu:

• Konektivitas ( $ M $ ) sangat mahal jika kunci besar
• Jika $ d cdot 4 $ jauh lebih besar dari $ M cdot text {size (key)} $ , Anda harus mengharapkan penggunaan memori linier yang dihabiskan untuk mewakili data vektor
• Jika $ d cdot 4 $ jauh lebih kecil dari $ M cdot text {size (key)} $ , Anda harus berharap $ n cdot log (n) $ Penggunaan memori yang dihabiskan untuk mewakili struktur grafik

Dalam contoh grafik dengan 256 dimensi, dan $ M = 16 $ , dengan kunci 8 byte, Anda akan melihat bahwa setiap vektor mengambil:

• $ 256 CDOT 4 = 1024 $ byte data
• $ 16 CDOT 8 = 128 $ metadata byte

Dan pertumbuhan memori sebagian besar linier.