hnsw

HNSW

حزمة hnsw تنفذ الرسوم البيانية العالمية الصغيرة الصالحة للملاحة في GO. يمكنك قراءة كيفية عملهم هنا. في جوهرها ، فإنها تسمح بإجراء عمليات بحث تقريبية تقريبية تقريبية مع بيانات متجه عالية الأبعاد.

يمكن اعتبار هذه الحزمة بديلاً في الذاكرة لقاعدة بيانات المتجه المفضلة لديك (مثل Pinecone ، Weaviate). ينفذ فقط العمليات الأساسية:

عملية	تعقيد	وصف
أدخل	$ o (log (n)) $	أدخل ناقل في الرسم البياني
يمسح	$ o (m^2 cdot log (n)) $	حذف ناقل من الرسم البياني
يبحث	$ o (log (n)) $	ابحث عن أقرب جيران المتجه
ابحث عن	$ o (1) $	استرداد ناقل بالمعرف

ملحوظة

التعقيدات تقريبية أين $ n $ هو عدد المتجهات في الرسم البياني و $ م $ هو الحد الأقصى لعدد الجيران يمكن أن يكون لكل عقدة. هذه الورقة مورد جيد لفهم تأثير معلمات البناء المختلفة.

الاستخدام

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

انظر المزيد:

• يصدّر
• يستورد
• Savedgraph

نستخدم ترميزًا ثنائيًا سريعًا للرسم البياني ، حتى تتوقع حفظ/تحميل تقريبًا بسرعة القرص. على جهاز 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 Default) ، يتم إنفاق 70 ٪ من عملية الاستعلام تحت المعلمات الافتراضية في وظيفة المسافة.

إذا كنت تكافح مع البطء / الكمون ، فكر في:

• تقليل الأبعاد
• زيادة $ م $

وإذا كنت تكافح مع استخدام الذاكرة الزائدة ، ففكر:

• تقليل $ م $ 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} = graph} + mem_}

أين:

• $ n $ هو عدد المتجهات في الرسم البياني
• $ text {size (key)} $ هو متوسط ​​حجم المفتاح في البايتات
• $ م $ هو الحد الأقصى لعدد الجيران يمكن لكل عقدة أن يكون
• $ d $ هو أبعاد المتجهات
• $ mem_ {graph} $ هي الذاكرة التي تستخدمها بنية الرسم البياني عبر جميع الطبقات
• $ mem_ {base} $ هل الذاكرة المستخدمة من قبل المتجهات نفسها في الطبقة القاعدة أو 0

يمكنك أن تستنتج ما يلي:

• الاتصال ( $ م $ ) مكلفة للغاية إذا كانت المفاتيح كبيرة
• لو $ 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 $ ميتادا بايت

ونمو الذاكرة خطي في الغالب.