hnsw -Download - hnsw -Quellcode -Download

hnsw

Anderer Quellcode

1.0.0

Herunterladen

Hnsw

Paket hnsw implementiert hierarchische schiffbare kleine Weltgrafiken in Go. Sie können sich darüber nachlesen, wie sie hier arbeiten. Im Wesentlichen ermöglichen sie eine schnelle ungefähre Suche nach dem nächsten Nachbarn mit hochdimensionalen Vektordaten.

Dieses Paket kann als In-Memory-Alternative zu Ihrer bevorzugten Vektordatenbank (z. B. Pnecone, WeaViate) betrachtet werden. Es implementiert nur die wesentlichen Operationen:

Betrieb	Komplexität	Beschreibung
Einfügen	$ O (log (n)) $	Fügen Sie einen Vektor in die Grafik ein
Löschen	$ O (m^2 cdot log (n)) $	Löschen Sie einen Vektor aus der Grafik
Suchen	$ O (log (n)) $	Suchen Sie nach den nächsten Nachbarn eines Vektors
Nachschlagen	$ O (1) $	Einen Vektor mit ID abrufen

Notiz

Komplexitäten sind ungefähr wo $ n $ ist die Anzahl der Vektoren in der Grafik und $ M $ ist die maximale Anzahl von Nachbarn, die jeder Knoten haben kann. Dieses Papier ist eine gute Ressource, um die Auswirkungen der verschiedenen Konstruktionsparameter zu verstehen.

Verwendung

 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]

Ausdauer

Während alle Grafikvorgänge in Memory sind, bietet hnsw Einrichtungen zum Laden/Einsparungen durch anhaltendem Speicher.

Verwenden Sie für eine io.Reader / io.Writer -Schnittstelle Graph.Export und Graph.Import .

Wenn Sie eine einzelne Datei als Backend verwenden, bietet HNSW stattdessen einen praktischen SavedGraph -Typ:

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

Weitere: mehr:

Export
Import
SavedGraph

Wir verwenden eine schnelle Binärcodierung für das Diagramm, sodass Sie rechnen können, nahezu bei Scheibengeschwindigkeit zu speichern/zu laden. Auf meinem M3 -MacBook erhalte ich diese Benchmark -Ergebnisse:

 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

beim Speichern/Laden eines Diagramms von 100 Vektoren mit 256 Abmessungen.

Leistung

Im Großen und Ganzen ist der größte Effekt, den Sie auf die Leistung des Diagramms haben können, die Dimensionalität Ihrer Daten. Bei 1536 Abmessungen (OpenAI -Standard) werden 70% des Abfragebegels unter Standardparametern in der Entfernungsfunktion ausgegeben.

Wenn Sie mit Langsamkeit / Latenz zu kämpfen haben, sollten Sie:

Reduzierung der Dimensionalität
Zunehmen $ M $

Und wenn Sie mit übermäßiger Speicherverwendung zu kämpfen haben, sollten Sie sich überlegen:

Reduzieren $ M $ aka Graph.M (die maximale Anzahl der Nachbarn, die jeder Knoten haben kann)
Reduzieren $ m_l $ aka Graph.Ml (der Parameter der Ebenegenerierung)

Speicheraufwand

Der Speicheraufwand einer Grafik sieht aus wie:

$$ displaylines {mem_ {graph} = n cdot log (n) cdot text {size (id)} cdot m \ mem_ {base} = n cdot d cdot 4 \ mem_ {Total} = mem_ {graph} + mem_ {base} $ $ $ $ $ $ $ $

Wo:

$ n $ ist die Anzahl der Vektoren in der Grafik
$ text {size (key)} $ ist die durchschnittliche Größe des Schlüssels in Bytes
$ M $ ist die maximale Anzahl von Nachbarn, die jeder Knoten haben kann
$ d $ ist die Dimensionalität der Vektoren
$ mem_ {graph} $ ist der Speicher, der von der Graph -Struktur über alle Schichten hinweg verwendet wird
$ mem_ {Base} $ ist der Speicher, der von den Vektoren selbst in der Basis oder der 0. Schicht verwendet wird

Sie können das schließen:

Konnektivität ( $ M $ ) ist sehr teuer, wenn Schlüssel groß sind
Wenn $ d cdot 4 $ ist weitaus größer als $ M cdot text {size (Schlüssel)} $ Sie sollten erwarten, dass die lineare Speicherverbrauch für die Darstellung von Vektordaten aufgewendet wird
Wenn $ d cdot 4 $ ist weit kleiner als $ M cdot text {size (Schlüssel)} $ , Sie sollten es erwarten $ n cdot log (n) $ Speicherverbrauch für die Darstellung der Graphenstruktur aufgewendet

Im Beispiel eines Diagramms mit 256 Dimensionen und $ M = 16 $ Mit 8 Byte -Schlüssel würden Sie sehen, dass jeder Vektor: