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 $元数据字节

内存增长主要是线性的。