hnsw

HNSW

แพ็คเกจ hnsw ใช้กราฟโลกขนาดเล็กที่นำทางได้ตามลำดับชั้นใน GO คุณสามารถอ่านเกี่ยวกับวิธีการทำงานที่นี่ ในสาระสำคัญพวกเขาอนุญาตให้มีการค้นหาเพื่อนบ้านที่ใกล้ที่สุดโดยประมาณด้วยข้อมูลเวกเตอร์มิติสูง

แพ็คเกจนี้สามารถคิดว่าเป็นทางเลือกในหน่วยความจำสำหรับฐานข้อมูลเวกเตอร์ที่คุณชื่นชอบ (เช่น pinecone, weaviate) มันใช้เพียงการดำเนินการที่สำคัญ:

การดำเนินการ	ความซับซ้อน	คำอธิบาย
แทรก	$ o (log (n)) $	ใส่เวกเตอร์ลงในกราฟ
ลบ	$ o (m^2 cdot log (n)) $	ลบเวกเตอร์จากกราฟ
ค้นหา	$ o (log (n)) $	ค้นหาเพื่อนบ้านที่ใกล้ที่สุดของเวกเตอร์
การค้นหา	$ o (1) $	ดึงเวกเตอร์ด้วย ID

บันทึก

ความซับซ้อนโดยประมาณที่ $ n $ จำนวนเวกเตอร์ในกราฟและ $ m $ เป็นจำนวนสูงสุดของเพื่อนบ้านที่แต่ละโหนดสามารถมีได้ บทความนี้เป็นทรัพยากรที่ดีสำหรับการทำความเข้าใจผลกระทบของพารามิเตอร์การก่อสร้างต่างๆ

การใช้งาน

 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] 

ความเพียร

ในขณะที่การดำเนินการกราฟทั้งหมดเป็นหน่วยความจำ hnsw ให้บริการสิ่งอำนวยความสะดวกสำหรับการโหลด/บันทึกจากที่เก็บข้อมูลถาวร

สำหรับอินเทอร์เฟซ io.Reader / io.Writer ให้ใช้ Graph.Export และ Graph.Import

หากคุณใช้ไฟล์เดียวเป็นแบ็กเอนด์ HNSW จะให้ประเภท SavedGraph ที่สะดวกสบายแทน:

 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 )
}

ดูเพิ่มเติม:

• ส่งออก
• นำเข้า
• บันทึกกราฟ

เราใช้การเข้ารหัสแบบไบนารีอย่างรวดเร็วสำหรับกราฟดังนั้นคุณสามารถคาดหวังว่าจะประหยัด/โหลดได้เกือบที่ความเร็วของดิสก์ ใน M3 MacBook ของฉันฉันได้รับผลลัพธ์มาตรฐานเหล่านี้:

 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

เมื่อบันทึก/โหลดกราฟ 100 เวกเตอร์ที่มี 256 มิติ

ผลงาน

เอฟเฟกต์ที่ยิ่งใหญ่ที่สุดที่คุณสามารถมีต่อประสิทธิภาพของกราฟคือการลดขนาดของข้อมูลของคุณ ที่ 1536 มิติ (openai ค่าเริ่มต้น) 70% ของกระบวนการสืบค้นภายใต้พารามิเตอร์เริ่มต้นจะถูกใช้ในฟังก์ชันระยะทาง

หากคุณกำลังดิ้นรนกับความช้า / แฝงให้พิจารณา:

• ลดขนาด
• ที่เพิ่มขึ้น $ m $

และหากคุณกำลังดิ้นรนกับการใช้หน่วยความจำส่วนเกินให้พิจารณา:

• การลดลง $ m $ aka Graph.M (จำนวนสูงสุดของเพื่อนบ้านแต่ละโหนดสามารถมีได้)
• การลดลง $ m_l $ aka Graph.Ml (พารามิเตอร์การสร้างระดับ)

หน่วยความจำค่าใช้จ่าย

หน่วยความจำเหนือศีรษะของกราฟดูเหมือนว่า:

$$ displayLines {mem_ {graph} = n cdot log (n) cdot text {size (id)} cdot m \ mem_ {base} = n cdot d cdot 4 \ mem_ {total} = mem_ {กราฟ}

ที่ไหน:

• $ n $ คือจำนวนเวกเตอร์ในกราฟ
• $ text {size (key)} $ คือขนาดเฉลี่ยของคีย์ในไบต์
• $ m $ จำนวนเพื่อนบ้านสูงสุดแต่ละโหนดสามารถมีได้หรือไม่
• $ D $ เป็นมิติของเวกเตอร์
• $ mem_ {กราฟ} $ เป็นหน่วยความจำที่ใช้โดยโครงสร้างกราฟในทุกเลเยอร์
• $ mem_ {base} $ หน่วยความจำที่ใช้โดยเวกเตอร์เองในฐานหรือชั้น 0

คุณสามารถอนุมานได้ว่า:

• การเชื่อมต่อ ( $ m $ ) มีราคาแพงมากถ้าคีย์มีขนาดใหญ่
• ถ้า $ D CDOT 4 $ มีขนาดใหญ่กว่า $ m cdot text {size (key)} $ คุณควรคาดหวังว่าการใช้หน่วยความจำเชิงเส้นที่ใช้ไปกับข้อมูลเวกเตอร์
• ถ้า $ D CDOT 4 $ เล็กกว่า $ m cdot text {size (key)} $ คุณควรคาดหวัง $ n cdot log (n) $ การใช้หน่วยความจำที่ใช้ในการแสดงโครงสร้างกราฟ

ในตัวอย่างของกราฟที่มี 256 มิติและ $ m = 16 $ ด้วยปุ่ม 8 ไบต์คุณจะเห็นว่าแต่ละเวกเตอร์ใช้:

• $ 256 CDOT 4 = 1024 $ ไบต์ข้อมูล
• $ 16 CDOT 8 = 128 $ เมตาดาต้าไบต์

และการเติบโตของหน่วยความจำส่วนใหญ่เป็นเส้นตรง