HNSW: Hierarchical Navigable Small World

• M: 16 default. Higher = better recall, more RAM
• ef_construction: 100-500. Index build quality — one-time cost
• ef: search-time param. Higher = better recall, slower. 32-200 typical
• Memory: 4-10x vector size due to graph links. 1M × 1536-dim FP32 → ~30 GB
• Recall: >95% при ef=100 для most datasets

# pgvector HNSW
CREATE INDEX ON docs USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

-- Query tuning
SET hnsw.ef_search = 100;  -- runtime param
SELECT * FROM docs ORDER BY embedding <=> query_vec LIMIT 5;

• Vector DB
• Embeddings
• Semantic Search

HNSW (Hierarchical Navigable Small World) индекс представляет собой эффективную структуру данных для выполнения поиска ближайших соседей (ANN) в многомерных векторных пространствах. Он обеспечивает высокую скорость поиска и низкую вычислительную сложность, что делает его идеальным для работы с большими наборами данных, например, в задачах обработки изображений или текстов.

Основное преимущество HNSW заключается в его способности поддерживать баланс между точностью и производительностью. Структура HNSW позволяет пользователю настраивать параметры, такие как максимальное количество соседей и уровень графа, что дает возможность оптимизировать алгоритм под конкретные задачи.

HNSW индекс строится на основе графовой структуры, где каждый узел представляет собой вектор, а ребра соединяют узлы, которые являются ближайшими соседями. Алгоритм состоит из двух основных этапов: построение графа и поиск ближайших соседей.

Построение графа

На этапе построения графа создаются несколько уровней, где каждый уровень содержит подмножество узлов. Для добавления нового узла алгоритм выбирает случайный уровень и соединяет его с ближайшими соседями. Это позволяет поддерживать высокую плотность связи между узлами на каждом уровне, что существенно ускоряет процесс поиска.

Поиск ближайших соседей

Поиск начинается с верхнего уровня графа и плавно спускается вниз. На каждом уровне осуществляется локальный поиск, который позволяет быстро находить ближайшие узлы. После достижения нижнего уровня, алгоритм применяет точный поиск, чтобы определить наиболее близкие векторы.

Эффективность HNSW можно продемонстрировать на практике. Например, для создания HNSW индекса с использованием библиотеки nmslib, можно использовать следующий код:

import nmslib

# Создаем HNSW индекс
index = nmslib.init(method='hnsw', space='l2')

# Добавляем векторы в индекс
index.addDataPointBatch(data)

# Строим индекс
index.createIndex({'post': 2}, print_progress=True)

HNSW индекс обладает рядом значительных преимуществ, которые делают его популярным выбором для ANN:

• Высокая скорость поиска: HNSW обеспечивает время поиска, близкое к логарифмическому, что делает его эффективным для больших наборов данных.
• Гибкость настройки: Пользователи могут настраивать параметры индекса, чтобы достичь оптимального баланса между точностью и производительностью.
• Поддержка динамических данных: HNSW позволяет добавлять новые векторы в уже существующий индекс без необходимости его пересоздания.

Тем не менее, у HNSW есть и свои недостатки:

• Память: Структура графа может потреблять значительное количество памяти, особенно при работе с большими данными.
• Сложность реализации: Реализация HNSW может быть сложной для начинающих разработчиков, требуя глубокого понимания алгоритмических основ.

В заключение, HNSW индекс является мощным инструментом для поиска ближайших соседей в многомерных векторных пространствах, предлагая высокую производительность и точность. При правильной настройке и использовании он может существенно улучшить эффективность обработки данных в различных приложениях.