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

При сохранении/загрузке графика из 100 векторов с 256 измерениями.

Производительность

В целом, наибольшим эффектом, который вы можете оказать на производительность графика, это уменьшение размерности ваших данных. В 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_ {base} $$ $

где:

• $ 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 $ Метаданные байты

И рост памяти в основном линейный.