hnsw 다운로드 hnsw 소스 코드 다운로드

hnsw

기타 소스코드

1.0.0

다운로드

HNSW

패키지 hnsw 계층 적 항해 가능한 작은 세계 그래프를 구현합니다. 그들이 여기서 어떻게 작동하는지 읽을 수 있습니다. 본질적으로, 그들은 고차원 벡터 데이터를 사용하여 빠른 대략적인 가장 가까운 이웃 검색을 허용합니다.

이 패키지는 좋아하는 벡터 데이터베이스 (예 : 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 text {size (id)} cdot m \ mem_ {base} = n cdot d cdot 4 \ mem_ {Total} = mem_ {Graph} + mem_} $$

어디:

$ n $ 그래프의 벡터 수입니다
$ text {size (key)} $ 키의 평균 크기는 바이트입니다
$ m $ 각 노드가 가질 수있는 최대 이웃 수입니다.
$ d $ 벡터의 치수입니다
$ mem_ {그래프} $ 모든 레이어에서 그래프 구조에 사용되는 메모리입니다.
$ 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 바이트 키가 있으면 각 벡터가 다음을 취할 수 있습니다.