hnsw

HNSW

O pacote hnsw implementa os gráficos mundiais pequenos navegáveis ​​hierárquicos em Go. Você pode ler sobre como eles funcionam aqui. Em essência, eles permitem pesquisas de vizinhas mais próximas mais próximas com dados vetoriais de alta dimensão.

Este pacote pode ser pensado como uma alternativa na memória ao seu banco de dados vetorial favorito (por exemplo, Pinecone, Weaviate). Ele implementa apenas as operações essenciais:

Operação	Complexidade	Descrição
Inserir	$ O (log (n)) $	Insira um vetor no gráfico
Excluir	$ O (M^2 CDOT LOG (N)) $	Exclua um vetor do gráfico
Procurar	$ O (log (n)) $	Procure os vizinhos mais próximos de um vetor
Pesquisa	$ O (1) $	Recuperar um vetor por id

Observação

Complexidades são aproximadas onde $ n $ é o número de vetores no gráfico e $ M $ é o número máximo de vizinhos que cada nó pode ter. Este artigo é um bom recurso para entender o efeito dos vários parâmetros de construção.

Uso

 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] 

Persistência

Embora todas as operações gráficas estejam na memória, hnsw fornece instalações para carregar/salvar a partir de armazenamento persistente.

Para uma interface io.Reader / io.Writer , use Graph.Export e Graph.Import .

Se você estiver usando um único arquivo como back -end, o HNSW fornece um tipo de SavedGraph conveniente:

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

Veja mais:

• Exportar
• Importar
• SAVEDGRAPH

Usamos uma codificação binária rápida para o gráfico, para que você possa salvar/carregar quase na velocidade do disco. No meu M3 MacBook, recebo esses resultados de referência:

 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

Ao salvar/carregar um gráfico de 100 vetores com 256 dimensões.

Desempenho

Em geral, o maior efeito que você pode ter no desempenho do gráfico está reduzindo a dimensionalidade dos seus dados. Nas dimensões de 1536 (inadimplência do OpenAI), 70% do processo de consulta sob parâmetros padrão é gasto na função de distância.

Se você está lutando com a lentidão / latência, considere:

• Reduzindo a dimensionalidade
• Aumentando $ M $

E, se você está lutando com o excesso de uso da memória, considere:

• Reduzindo $ M $ aka Graph.M (o número máximo de vizinhos que cada nó pode ter)
• Reduzindo $ m_l $ aka Graph.Ml (o parâmetro de geração de nível)

Sobrecarga de memória

A sobrecarga de memória de um gráfico parece:

$$ DisplayLines {mem_ {Graph} = n cdot log (n) cdot text {size (id)} cdot m \ mem_ {base} = n cdot d cdot 4 \ Memor

onde:

• $ n $ é o número de vetores no gráfico
• $ text {size (key)} $ é o tamanho médio da chave em bytes
• $ M $ é o número máximo de vizinhos que cada nó pode ter
• $ d $ é a dimensionalidade dos vetores
• $ mem_ {gráfico} $ é a memória usada pela estrutura do gráfico em todas as camadas
• $ mem_ {base} $ é a memória usada pelos próprios vetores na base ou 0ª camada

Você pode deduzir isso:

• Conectividade ( $ M $ ) é muito caro se as chaves forem grandes
• Se $ d cdot 4 $ é muito maior do que $ M cdot text {size (key)} $ , você deve esperar o uso linear de memória gasto na representação de dados vetoriais
• Se $ d cdot 4 $ é muito menor que $ M cdot text {size (key)} $ , você deveria esperar $ n cdot log (n) $ Uso de memória gasto na representação da estrutura do gráfico

No exemplo de um gráfico com 256 dimensões e $ M = 16 $ , com 8 teclas de byte, você veria que cada vetor leva:

• $ 256 CDOT 4 = 1024 $ bytes de dados
• $ 16 CDOT 8 = 128 $ Bytes de metadados

e o crescimento da memória é principalmente linear.