HNSW_PRQ

HNSW_PRQ использует графы Hierarchical Navigable Small World (HNSW) с Product Residual Quantization (PRQ), предлагая продвинутый метод векторного индексирования, который позволяет тонко настроить компромисс между размером индекса и точностью. PRQ выходит за рамки традиционного Product Quantization (PQ), вводя шаг остаточного квантования (RQ) для сбора дополнительной информации, что приводит к повышению точности или созданию более компактных индексов по сравнению с методами, основанными исключительно на PQ. Однако дополнительные шаги могут привести к большим вычислительным затратам при построении индекса и поиске.

Обзор

HNSW_PRQ сочетает в себе две техники индексирования: HSNW для быстрой навигации по графам и PRQ для эффективного сжатия векторов.

HNSW

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

Дополнительную информацию см. на сайте HNSW.

PRQ

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

На следующем рисунке показано, как это работает.

Hnsw Prq

1. Квантование по продукту (PQ)

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

2. Остаточное квантование (RQ)

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

   Параметр nrq определяет, сколько раз этот остаток будет итеративно квантоваться, что позволяет точно настроить баланс между эффективностью и точностью сжатия.

3. Окончательное представление при сжатии

   После того как RQ завершает квантование остатка, целочисленные коды от PQ и RQ объединяются в один сжатый индекс. Захватывая детали, которые PQ может упустить, RQ повышает точность без значительного увеличения объема памяти. Эта синергия между PQ и RQ и определяет PRQ.

HNSW + PRQ

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

1. Сжатие данных: Каждый вектор сначала преобразуется с помощью PQ в грубое представление, а затем остатки квантуются с помощью RQ для дальнейшего уточнения. В результате получается набор компактных кодов, представляющих каждый вектор.

2. Построение графа: Сжатые векторы (включая коды PQ и RQ) служат основой для построения графа HNSW. Поскольку данные хранятся в компактной форме, граф требует меньше памяти, и навигация по нему ускоряется.

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

4. (Необязательно) Уточнение результатов: Первоначальные результаты по кандидатам могут быть уточнены для повышения точности на основе следующих параметров:

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

   • refine_type: Определяет уровень точности данных, используемых при уточнении (например, SQ6, SQ8, BF16). Выбор более высокой точности, например FP32, может дать более точные результаты, но требует больше памяти. Эта точность должна превышать точность исходного набора сжатых данных на sq_type.

   • refine_k: Действует как коэффициент увеличения. Например, если ваш топ k равен 100, а refine_k - 2, система переранжирует 200 лучших кандидатов и возвращает 100 лучших, повышая общую точность.

Полный список параметров и допустимых значений см. в разделе Index params.

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

Чтобы построить индекс HNSW_PRQ по векторному полю в 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_PRQ", # 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": 30, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 360, # Number of candidate neighbors considered for connection during index construction
        "m": 384, 
        "nbits": 8,
        "nrq": 1,
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

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

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

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

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

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

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

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

search_params = {
    "params": {
        "ef": 10, # Parameter controlling query time/accuracy trade-off
        "refine_k": 1 # The magnification factor
    }
}

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=3,  # TopK results to return
    search_params=search_params
)

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

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

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

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

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

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

	Параметр	Описание	Диапазон значений	Предложение по настройке
HNSW	M	Максимальное количество связей （или ребер), которое может иметь каждый узел в графе, включая как исходящие, так и входящие ребра. Этот параметр напрямую влияет как на построение индекса, так и на поиск.	Тип: Integer Диапазон: [2, 2048] Значение по умолчанию: 30 (до 30 исходящих и 30 входящих ребер на узел).	Большее значение M обычно приводит к повышению точности, но увеличивает объем памяти и замедляет построение индекса и поиск. Рассмотрите возможность увеличения M для наборов данных с высокой размерностью или когда высокая запоминаемость имеет решающее значение. Уменьшайте M, если важны расход памяти и скорость поиска. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [5, 100].
	efConstruction	Количество соседей-кандидатов, рассматриваемых для соединения при построении индекса. Для каждого нового элемента оценивается больший пул кандидатов, но максимальное количество фактически установленных соединений по-прежнему ограничено M.	Тип: Integer Диапазон: [1, int_max]. Значение по умолчанию: 360	Более высокое значение efConstruction обычно приводит к более точному индексу, поскольку исследуется больше потенциальных соединений. Однако это также приводит к увеличению времени индексирования и потреблению памяти при построении индекса. Рассмотрите возможность увеличения efConstruction для повышения точности, особенно в сценариях, где время индексирования менее критично. Уменьшите efConstruction, чтобы ускорить построение индекса, если ограничены ресурсы. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [50, 500].
PRQ	m	Количество подвекторов (используемых для квантования), на которые нужно разделить каждый высокоразмерный вектор в процессе квантования.	Тип: Целое число Диапазон: [1, 65536] Значение по умолчанию: Нет	Большее значение m может повысить точность, но также увеличивает сложность вычислений и потребление памяти. m должно быть делителем размерности вектора(D), чтобы обеспечить правильное разложение. Обычно рекомендуемое значение m = D/2. В большинстве случаев мы рекомендуем задавать значение в этом диапазоне: [D/8, D].
	nbits	Количество битов, используемых для представления индекса центроида каждого субвектора в сжатом виде. Оно напрямую определяет размер каждой кодовой книги. Каждая кодовая книга будет содержать 2nbits центроидов. Например, если значение nbits равно 8, то каждый субвектор будет представлен 8-битным индексом центроида. Это позволяет использовать28 (256) возможных центроидов в кодовой книге для данного субвектора.	Тип: Целое число Диапазон: [1, 24] Значение по умолчанию: 8	Большее значение nbits позволяет использовать большие кодовые книги, что потенциально приводит к более точному представлению исходных векторов. Однако это также означает использование большего количества битов для хранения каждого индекса, что приводит к меньшему сжатию. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [1, 16].
	nrq	Управляет количеством остаточных субквантователей, используемых на этапе RQ. Большее количество субквантователей потенциально позволяет достичь большего сжатия, но может привести к большим потерям информации.	Тип: Integer Диапазон: [1, 16] Значение по умолчанию: 2	Большее значение nrq позволяет выполнять дополнительные шаги остаточной субквантизации, что потенциально приводит к более точному восстановлению исходных векторов. Однако это также означает хранение и вычисление большего количества субквантователей, что приводит к увеличению размера индекса и большим вычислительным затратам.
	refine	Булевский флаг, определяющий, применяется ли шаг уточнения при поиске. Уточнение заключается в повторном ранжировании исходных результатов путем вычисления точных расстояний между вектором запроса и кандидатами.	Тип: Boolean Диапазон: [true, false]. Значение по умолчанию: false	Установите значение true, если важна высокая точность и вы можете смириться с небольшим замедлением времени поиска. Используйте false, если скорость является приоритетом, а незначительный компромисс в точности допустим.
	refine_type	Определяет точность данных, используемых в процессе уточнения. Эта точность должна быть выше, чем точность сжатых векторов (заданная параметрами m и nbits ).	Тип: String Диапазон:[ SQ6, SQ8, BF16, FP16, FP32 ]. Значение по умолчанию: None	Используйте FP32 для максимальной точности при больших затратах памяти или SQ6/SQ8 для лучшего сжатия. BF16 и FP16 предлагают сбалансированную альтернативу.

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

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

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