Расскажите идею HNSW и как устроен иерархический граф.

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

Иерархический граф устроен следующим образом:

• Есть несколько уровней, начиная с верхнего, где граф очень разреженный, и заканчивая нижним, где граф плотный.
• Каждый объект размещается на случайном уровне с вероятностью, убывающей экспоненциально.
• Поиск начинается с верхнего уровня, где быстро находят приближённый сосед, затем переходят на следующий уровень вниз, уточняя поиск.
• На каждом уровне поиск ведётся по графу с помощью жадного алгоритма, переходя к соседям, которые ближе к целевому вектору.

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