ℹ️HNSWℹ️

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

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

Поиск ближайших соседей в HNSW использует метод увеличения (zooming-in). Он начинается во входной ноде самого верхнего уровня и рекурсивно выполняет жадный обход графов на каждом уровне, пока не достигнет локального минимума на самом дне.

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


Как это работает?

▪️HNSW организует векторы в многослойную графовую структуру.
▪️Узлы в каждом слое поддерживают связи на основе расстояний в векторном пространстве.
▪️Навигация происходит иерархически, начиная с верхнего слоя и спускаясь вниз для уточнения поиска.
▪️Более высокие слои строятся путем подвыборки узлов из нижних слоев.

Почему HNSW?

▪️Скорость: иерархическая структура означает, что алгоритм поиска может перемещаться по графу быстрее, чем при плоской структуре.
▪️Масштабируемость: Поскольку кэш-память хранит только верхний слой, а затем добавляет только соседние векторы в дальнейших слоях, это очень эффективно и масштабируемо.
▪️Адаптируемость: HNSW очень надежен и может одновременно работать с импортом и запросами.

@sqlhub