HNSW

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

Обзор

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

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

Вот как это работает:

1. Точка входа: Поиск начинается с фиксированной точки входа на верхнем слое, которая представляет собой заранее определенный узел графа.

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

3. Спуск по слоям: После достижения локального минимума на текущем слое алгоритм переходит на нижний слой, используя заранее установленную связь, и повторяет жадный поиск.

4. Окончательное уточнение: Этот процесс продолжается до тех пор, пока не будет достигнут нижний слой, где на последнем этапе уточнения определяются ближайшие соседи.

HNSW

Производительность HNSW зависит от нескольких ключевых параметров, которые управляют как структурой графа, так и поведением поиска. К ним относятся:

• M: Максимальное количество ребер или связей, которые может иметь каждый узел в графе на каждом уровне иерархии. Более высокое значение M приводит к более плотному графу и увеличивает запоминание и точность, так как поиск имеет больше путей для исследования, но при этом потребляет больше памяти и замедляет время вставки из-за дополнительных связей. Как показано на рисунке выше, M = 5 означает, что каждый узел в графе HNSW напрямую связан максимум с 5 другими узлами. Это создает умеренно плотную структуру графа, в которой узлы имеют множество путей для достижения других узлов.

• efConstruction: Количество кандидатов, учитываемых при построении индекса. Более высокое значение efConstruction обычно приводит к лучшему качеству графа, но требует больше времени на построение.

• ef: Количество соседей, оцениваемых во время поиска. Увеличение ef повышает вероятность нахождения ближайших соседей, но замедляет процесс поиска.

Подробнее о том, как настроить эти параметры в соответствии с вашими потребностями, читайте в разделе Index params.

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

Чтобы построить индекс HNSW по векторному полю в Milvus, используйте метод add_index(), указав index_type, metric_type и дополнительные параметры для индекса.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="HNSW", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "M": 64, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 100 # Number of candidate neighbors considered for connection during index construction
    } # Index building params
)

В данной конфигурации:

• index_type: Тип индекса, который будет построен. В этом примере задайте значение HNSW.

• metric_type: Метод, используемый для вычисления расстояния между векторами. Поддерживаются следующие значения: COSINE, L2 и IP. Подробнее см. в разделе Типы метрик.

• params: Дополнительные параметры конфигурации для построения индекса.

  • M: Максимальное количество соседей, с которыми может соединиться каждый узел.

  • efConstruction: Количество соседей-кандидатов, рассматриваемых для подключения при построении индекса.

  Чтобы узнать больше параметров построения, доступных для индекса HNSW, обратитесь к разделу Параметры построения индекса.

После того как параметры индекса настроены, вы можете создать индекс, используя метод create_index() напрямую или передавая параметры индекса в метод create_collection. Подробности см. в разделе Создание коллекции.

Поиск по индексу

После того как индекс создан и сущности вставлены, можно выполнять поиск по сходству в индексе.

search_params = {
    "params": {
        "ef": 10, # Number of neighbors to consider during the search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field", # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=10,  # TopK results to return
    search_params=search_params
)

В этой конфигурации:

• params: Дополнительные параметры конфигурации для поиска по индексу.

  • ef: : Количество соседей, учитываемых при поиске.

  Чтобы узнать больше параметров поиска, доступных для индекса HNSW, обратитесь к разделу Параметры поиска по индексу.

Параметры индекса

В этом разделе представлен обзор параметров, используемых для построения индекса и выполнения поиска по нему.

Параметры построения индекса

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

Параметр	Описание	Диапазон значений	Предложение по настройке
M	Максимальное количество связей （или ребер), которое может иметь каждый узел в графе, включая как исходящие, так и входящие ребра. Этот параметр напрямую влияет как на построение индекса, так и на поиск.	Тип: Integer Диапазон: [2, 2048] Значение по умолчанию: 30 (до 30 исходящих и 30 входящих ребер на узел).	Большее значение M обычно приводит к повышению точности, но увеличивает объем памяти и замедляет построение индекса и поиск. Рассмотрите возможность увеличения M для наборов данных с высокой размерностью или в случаях, когда важна высокая запоминаемость. Уменьшайте M, если важны расход памяти и скорость поиска. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [5, 100].
efConstruction	Количество соседей-кандидатов, рассматриваемых для подключения при построении индекса. Для каждого нового элемента оценивается больший пул кандидатов, но максимальное количество фактически установленных соединений все равно ограничено M.	Тип: Integer Диапазон: [1, int_max]. Значение по умолчанию: 360	Более высокое значение efConstruction обычно приводит к более точному индексу, поскольку исследуется больше потенциальных соединений. Однако это также приводит к увеличению времени индексирования и потреблению памяти при построении. Рассмотрите возможность увеличения efConstruction для повышения точности, особенно в сценариях, где время индексирования менее критично. Уменьшите efConstruction, чтобы ускорить построение индекса, если ограничены ресурсы. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [50, 500].

Параметры поиска, специфичные для индекса

В следующей таблице перечислены параметры, которые могут быть настроены в search_params.params при поиске по индексу.

Параметр	Описание	Диапазон значений	Предложение по настройке
ef	Управляет широтой поиска при извлечении ближайших соседей. Он определяет, сколько узлов будет посещено и оценено как потенциальные ближайшие соседи. Этот параметр влияет только на процесс поиска и применяется исключительно к нижнему слою графа.	Тип: Integer Диапазон: [1, int_max]. Значение по умолчанию: limit (TopK ближайших соседей для возврата).	Большее значение ef обычно приводит к повышению точности поиска, так как учитывается большее количество потенциальных соседей. Однако это также увеличивает время поиска. Рассмотрите возможность увеличения ef, когда достижение высокого отзыва является критически важным, а скорость поиска менее важна. Рассмотрите возможность уменьшения ef, чтобы отдать предпочтение более быстрому поиску, особенно в сценариях, где небольшое снижение точности допустимо. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [K, 10K].