hnsw

HNSW

Package hnsw implémente les graphiques hiérarchiques de petit monde navigable dans Go. Vous pouvez lire comment ils fonctionnent ici. Essentiellement, ils permettent des recherches de voisins les plus proches plus rapides avec des données vectorielles à haute dimension.

Ce package peut être considéré comme une alternative en mémoire à votre base de données vectorielle préférée (par exemple Pinecone, Weavate). Il implémente uniquement les opérations essentielles:

Opération	Complexité	Description
Insérer	$ O (log (n)) $	Insérer un vecteur dans le graphique
Supprimer	$ O (m ^ 2 cdot log (n)) $	Supprimer un vecteur du graphique
Recherche	$ O (log (n)) $	Recherchez les voisins les plus proches d'un vecteur
Chercher	$ O (1) $	Récupérer un vecteur par id

Note

Les complexités sont approximatives où $ n $ est le nombre de vecteurs dans le graphique et $ M $ est le nombre maximum de voisins que chaque nœud peut avoir. Cet article est une bonne ressource pour comprendre l'effet des différents paramètres de construction.

Usage

 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] 

Persistance

Bien que toutes les opérations de graphiques soient en mémoire, hnsw fournit des installations pour charger / économiser du stockage persistant.

Pour une interface io.Reader / io.Writer , utilisez Graph.Export et Graph.Import .

Si vous utilisez un seul fichier comme backend, HNSW fournit à la place un type SavedGraph pratique:

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

Voir plus:

• Exporter
• Importer
• Graphique sauvé

Nous utilisons un encodage binaire rapide pour le graphique, vous pouvez donc vous attendre à enregistrer / charger presque à une vitesse de disque. Sur mon M3 MacBook, j'obtiens ces résultats de référence:

 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

Lors de l'enregistrement / chargement d'un graphique de 100 vecteurs avec 256 dimensions.

Performance

Dans l'ensemble, le plus grand effet que vous puissiez avoir sur les performances du graphique consiste à réduire la dimensionnalité de vos données. À 1536 Dimensions (Openai par défaut), 70% du processus de requête sous paramètres par défaut est dépensé dans la fonction de distance.

Si vous avez du mal avec la lenteur / latence, considérez:

• Réduction de la dimensionnalité
• Croissant $ M $

Et, si vous avez du mal avec une utilisation excessive de la mémoire, considérez:

• Réduction $ M $ aka Graph.M (le nombre maximum de voisins chaque nœud peut avoir)
• Réduction $ m_l $ aka Graph.Ml (le paramètre de génération de niveau)

Au-dessus de la mémoire

La mémoire de mémoire d'un graphique ressemble:

dollars

où:

• $ n $ est le nombre de vecteurs dans le graphique
• $ text {size (key)} $ est la taille moyenne de la clé en octets
• $ M $ est le nombre maximum de voisins chaque nœud peut avoir
• $ d $ est la dimensionnalité des vecteurs
• $ mem_ {graphique} $ La mémoire est-elle utilisée par la structure du graphique sur toutes les couches
• $ mem_ {base} $ La mémoire est-elle utilisée par les vecteurs eux-mêmes dans la base ou la 0ème couche

Vous pouvez déduire cela:

• Connectivité ( $ M $ ) est très cher si les clés sont grandes
• Si $ d cdot 4 $ est beaucoup plus grand que $ M cdot text {size (key)} $ , vous devez vous attendre à l'utilisation de la mémoire linéaire dépensée pour représenter les données vectorielles
• Si $ d cdot 4 $ est beaucoup plus petit que $ M cdot text {size (key)} $ , tu devrais vous attendre $ n cdot log (n) $ Utilisation de la mémoire dépensée pour représenter la structure des graphiques

Dans l'exemple d'un graphique avec 256 dimensions, et $ M = 16 $ , avec des touches de 8 octets, vous verriez que chaque vecteur prend:

• 256 $ CDOT 4 = 1024 $ octets de données
• 16 $ CDOT 8 = 128 $ octets de métadonnées

Et la croissance de la mémoire est principalement linéaire.