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

保存/加載具有256個維的100個向量的圖時。

表現

總的來說，您可以對圖表的性能產生最大的效果是降低數據的維度。在1536個維度（OpenAI默認值）處，默認參數下的查詢過程的70％用於距離函數。

如果您在緩慢 /潛伏期中掙扎，請考慮：

• 降低維度
• 增加 $ m $

而且，如果您在過多的內存使用方面苦苦掙扎，請考慮：

• 減少 $ m $ aka Graph.M （每個節點可以擁有的最大鄰居數）
• 減少 $ m_l $ aka Graph.Ml （級別生成參數）

內存開銷

圖表的內存開銷看起來像：

$$ displayLines {mem_ {graph} = n cdot log（n） cdot cdot text {size（id）} cdot m \ mem_ {base} = n cdot d cdot d cdot 4 cdot 4 cd mem_ {tater}

在哪裡：

• $ n $是圖中的向量數
• $ text {size（key）} $是字節中的鍵的平均大小
• $ m $是每個節點可以擁有的最大鄰居數
• $ D $是向量的維度
• $ mem_ {Graph} $圖形結構在所有圖層中使用的內存
• $ 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 $元數據字節

內存增長主要是線性的。