🚀 Попробуйте Zilliz Cloud, полностью управляемый Milvus, бесплатно — ощутите 10-кратное увеличение производительности! Попробовать сейчас>

milvus-logo
LFAI
  • Home
  • Blog
  • Начало работы с HNSWlib

Начало работы с HNSWlib

  • Engineering
November 25, 2024
Haziqa Sajid

Семантический поиск позволяет машинам понимать язык и выдавать лучшие результаты поиска, что очень важно для ИИ и аналитики данных. После того как язык представлен в виде вкраплений, поиск может осуществляться с помощью точных или приближенных методов. Приблизительный поиск ближайших соседей(ANN) - это метод, используемый для быстрого поиска точек в наборе данных, которые наиболее близки к заданной точке запроса, в отличие от точного поиска ближайших соседей, который может быть вычислительно дорогим для высокоразмерных данных. ANN позволяет ускорить поиск, предоставляя результаты, которые приблизительно близки к ближайшим соседям.

Одним из алгоритмов поиска приближенных ближайших соседей (ANN) является HNSW (Hierarchical Navigable Small Worlds), реализованный в HNSWlib, который и будет предметом сегодняшнего обсуждения. В этом блоге мы:

  • Поймем алгоритм HNSW.

  • Изучим HNSWlib и его ключевые особенности.

  • Настроим HNSWlib, рассмотрим построение индекса и реализацию поиска.

  • Сравним его с Milvus.

Понимание HNSW

Hierarchical Navigable Small Worlds (HNSW) - это структура данных на основе графов, которая позволяет эффективно искать сходство, особенно в высокоразмерных пространствах, путем построения многослойного графа сетей "малых миров". Представленная в 2016 году, HNSW решает проблемы масштабируемости, связанные с традиционными методами поиска, такими как перебор и поиск на основе деревьев. Он идеально подходит для приложений с большими массивами данных, таких как рекомендательные системы, распознавание образов и поиск с расширением (RAG).

Почему HNSW имеет значение

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

Принцип работы HNSW

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

  2. Концепция навигационных малых миров: Каждый слой в HNSW основан на концепции сети "малого мира", где узлы (точки данных) находятся на расстоянии всего нескольких "хопов" друг от друга. Алгоритм поиска начинает с самого верхнего, самого редкого слоя и работает вниз, переходя к все более плотным слоям для уточнения поиска. Такой подход напоминает переход от глобального обзора к детализации на уровне соседей, постепенно сужая область поиска.

Рис. 1: Пример навигационного графа малого мира

  1. Структура, похожая на пропускной список: Иерархический аспект HNSW напоминает список пропусков - вероятностную структуру данных, в которой более высокие уровни имеют меньшее количество узлов, что позволяет ускорить начальный поиск.

Рис. 2: Пример структуры списка пропусков

Чтобы найти 96 в данном списке пропусков, мы начинаем с верхнего уровня в крайнем левом узле с заголовком. Двигаясь вправо, мы встречаем 31, что меньше 96, поэтому переходим к следующему узлу. Теперь нам нужно спуститься на уровень ниже, где мы снова видим 31; поскольку оно все еще меньше 96, мы спускаемся еще на один уровень. Снова найдя 31, мы двигаемся вправо и достигаем 96 - нашего целевого значения. Таким образом, мы находим 96 без необходимости спускаться на самые нижние уровни списка пропусков.

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

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

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

Обзор HNSWlib

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

  • Структура на основе графа: Многослойный граф представляет точки данных, обеспечивая быстрый поиск ближайших соседей.

  • Эффективность работы с высокоразмерными данными: Оптимизирована для работы с высокоразмерными данными, обеспечивая быстрый и точный приблизительный поиск.

  • Сублинейное время поиска: достигается сублинейная сложность за счет пропуска слоев, что значительно повышает скорость.

  • Динамические обновления: Поддерживает вставку и удаление узлов в режиме реального времени, не требуя полной перестройки графа.

  • Эффективность использования памяти: Эффективное использование памяти, подходящее для больших наборов данных.

  • Масштабируемость: Хорошо масштабируется до миллионов точек данных, что делает его идеальным для приложений среднего масштаба, таких как рекомендательные системы.

Примечание: HNSWlib отлично подходит для создания простых прототипов приложений векторного поиска. Однако из-за ограничений по масштабируемости для более сложных сценариев, включающих сотни миллионов или даже миллиарды точек данных, могут быть использованы лучшие варианты, такие как специально созданные векторные базы данных. Давайте посмотрим на это в действии.

Начало работы с HNSWlib: Пошаговое руководство

В этом разделе мы продемонстрируем использование HNSWlib в качестве библиотеки векторного поиска, создав индекс HNSW, вставив данные и выполнив поиск. Начнем с установки:

Установка и импорт

Чтобы начать работу с HNSWlib в Python, сначала установите ее с помощью pip:

pip install hnswlib

Затем импортируйте необходимые библиотеки:

import hnswlib 
import numpy as np

Подготовка данных

В этом примере мы будем использовать NumPyдля генерации случайного набора данных с 10 000 элементов, каждый из которых имеет размерность 256.

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

Давайте создадим данные:

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

Теперь наши данные готовы, давайте создадим индекс.

Построение индекса

При построении индекса нам необходимо определить размерность векторов и тип пространства. Создадим индекс:

p = hnswlib.Index(space='l2', dim=dim)
  • space='l2': Этот параметр определяет метрику расстояния, используемую для сходства. Если установить значение 'l2', то будет использоваться евклидово расстояние (норма L2). Если вместо этого установить значение 'ip', то будет использоваться внутреннее произведение, что полезно для таких задач, как косинусное сходство.
  • dim=dim: Этот параметр задает размерность точек данных, с которыми вы будете работать. Она должна соответствовать размерности данных, которые вы планируете добавить в индекс.

Вот как инициализировать индекс:

p.init_index(max_elements=num_elements, ef_construction=200, M=16)
  • max_elements=num_elements: Здесь задается максимальное количество элементов, которые могут быть добавлены в индекс. Num_elements - это максимальная емкость, поэтому мы задаем значение 10 000, так как мы работаем с 10 000 точками данных.
  • ef_construction=200: Этот параметр управляет компромиссом между точностью и скоростью построения при создании индекса. Более высокое значение улучшает запоминание (точность), но увеличивает использование памяти и время построения. Обычные значения варьируются от 100 до 200.
  • M=16: Этот параметр определяет количество двунаправленных связей, создаваемых для каждой точки данных, что влияет на точность и скорость поиска. Типичные значения находятся в диапазоне от 12 до 48; 16 часто является хорошим балансом для умеренной точности и скорости.
p.set_ef(50)  # This parameter controls the speed/accuracy trade-off
  • ef: Параметр ef, сокращение от "exploration factor", определяет, сколько соседей просматривается во время поиска. При более высоком значении ef исследуется больше соседей, что, как правило, повышает точность (запоминание) поиска, но также делает его более медленным. И наоборот, более низкое значение ef ускоряет поиск, но может снизить точность.

В данном случае значение ef, равное 50, означает, что алгоритм поиска будет оценивать до 50 соседей при нахождении наиболее похожих точек данных.

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

Выполнение поиска

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

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors
  • query_vector: Эта строка генерирует случайный вектор с той же размерностью, что и индексированные данные, обеспечивая совместимость для поиска ближайших соседей.
  • knn_query: Метод ищет ближайших соседей k для query_vector в пределах индекса p. Он возвращает два массива: labels, которые содержат индексы ближайших соседей, и distances, которые указывают расстояния от вектора запроса до каждого из этих соседей. Здесь k=5 указывает, что мы хотим найти пять ближайших соседей.

Вот результаты после печати меток и расстояний:

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)
> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

Вот и все, простое руководство для начала работы с HNSWlib.

Как уже говорилось, HNSWlib - это отличный векторный поисковый механизм для создания прототипов или экспериментов с наборами данных среднего размера. Если у вас более высокие требования к масштабируемости или вам нужны другие функции корпоративного уровня, возможно, вам придется выбрать специально разработанную векторную базу данных, такую как Milvus с открытым исходным кодом или полностью управляемый сервис на Zilliz Cloud. Итак, в следующем разделе мы сравним HNSWlib с Milvus.

HNSWlib против специализированных векторных баз данных, таких как Milvus

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

Библиотеки векторных индексов, такие как HNSWlib, улучшаютпоиск и извлечениевекторов, но не обладают функциями управления, присущими полноценным базам данных. С другой стороны, векторные базы данных, такие как Milvus, предназначены для работы с векторными вкраплениями в масштабе, обеспечивая преимущества в управлении данными, индексировании и запросах, которых обычно не хватает отдельным библиотекам. Вот некоторые другие преимущества использования Milvus:

  • Высокоскоростной поиск по векторному сходству: Milvus обеспечивает производительность поиска на миллисекундном уровне в векторных наборах данных миллиардного масштаба, что идеально подходит для таких приложений, как поиск изображений, рекомендательные системы, обработка естественного языка(NLP) и поиск с расширенной генерацией(RAG).

  • Масштабируемость и высокая доступность: Созданная для работы с огромными объемами данных, система Milvus масштабируется горизонтально и включает механизмы репликации и обхода отказа для обеспечения надежности.

  • Распределенная архитектура: Milvus использует распределенную, масштабируемую архитектуру, которая разделяет хранение и вычисления на нескольких узлах для гибкости и надежности.

  • Гибридный поиск: Milvus поддерживает мультимодальный поиск, гибридный разреженный и плотный поиск, а также гибридный плотный и полнотекстовый поиск, предлагая универсальные и гибкие функции поиска.

  • Гибкая поддержка данных: Milvus поддерживает различные типы данных - векторы, скаляры и структурированные данные - обеспечивая беспрепятственное управление и анализ в рамках одной системы.

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

  • Интеграция с искусственным интеллектом: Milvus интегрирован с различными популярными фреймворками и технологиями искусственного интеллекта, что облегчает разработчикам создание приложений с использованием привычного технологического стека.

Milvus также предоставляет полностью управляемый сервис в облаке Ziliz Cloud, который не доставляет хлопот и работает в 10 раз быстрее, чем Milvus.

Сравнение: Milvus против HNSWlib

ХарактеристикаMilvusHNSWlib
МасштабируемостьЛегко справляется с миллиардами векторовПодходит для небольших наборов данных из-за экономии оперативной памяти
Идеально подходит дляПрототипирования, экспериментов и приложений корпоративного уровняОриентирован на прототипы и легкие задачи ANN
ИндексированиеПоддерживает 10+ алгоритмов индексирования, включая HNSW, DiskANN, квантование и двоичное индексирование.Используется только HNSW на основе графа
ИнтеграцияПредлагает API и облачные нативные сервисыСлужит в качестве легкой автономной библиотеки
ПроизводительностьОптимизируется для больших данных, распределенных запросовПредлагает высокую скорость, но ограниченную масштабируемость

В целом, Milvus предпочтительнее для крупных производственных приложений со сложными потребностями в индексировании, в то время как HNSWlib идеально подходит для прототипирования и более простых случаев использования.

Заключение

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

HNSWlib - отличный способ начать. Однако если вы хотите создавать сложные и готовые к производству приложения ИИ, то лучшим вариантом будут специально созданные векторные базы данных. Например, Milvus - это векторная база данных с открытым исходным кодом, обладающая множеством возможностей для предприятий, таких как высокоскоростной векторный поиск, масштабируемость, доступность, а также гибкость в отношении типов данных и языка программирования.

Читать далее

Like the article? Spread the word

Продолжить чтение