HNSW (Hierarchical Navigable Small World) — это алгоритм для приближённого поиска ближайших соседей (ANN). Простыми словами, он помогает очень быстро находить похожие векторы среди миллионов или миллиардов других, жертвуя лишь малой долей точности.
Представьте, что вам нужно найти деревню в незнакомой стране:
Верхний уровень (самый грубый) — это карта мира с одними столицами. Вы сразу прыгаете в нужную страну.
Средний уровень — карта региона с крупными городами. Вы уточняете маршрут.
Нижний уровень — подробная карта улиц с каждым домом. Здесь вы находите конкретную деревню.
HNSW строит многослойный граф именно так. На верхних слоях — мало точек (узлов) и длинные связи (как «магистрали»). На нижних — все точки и короткие связи.
Как работает
Построение (индексация): каждый новый вектор вставляется в случайно выбранный уровень. На каждом уровне устанавливаются связи с ближайшими соседями.
Поиск начинается с самого верхнего слоя, где «жадный» алгоритм быстро находит лучшее приближение. Затем спускается на уровень ниже, используя найденное как отправную точку. Повторяет до самого низа, где находит финальных кандидатов.
LSH (Locality Sensitive Hashing) — сильное приближение, мало памяти
Flat (brute-force) — точный, но очень медленный для больших данных
HNSW — это баланс скорости, точности и памяти, смещённый в сторону высокой скорости и точности ценой потребления памяти. Если ваши данные помещаются в RAM, HNSW почти всегда будет лучшим выбором для поиска по эмбеддингам.
