IVF_RABITQCompatible with Milvus 2.6.x

Индекс IVF_RABITQ - это алгоритм индексации на основе двоичного квантования, который квантует векторы FP32 в двоичное представление. Этот индекс обеспечивает исключительную эффективность хранения с коэффициентом сжатия 1 к 32, сохраняя при этом относительно хорошие показатели запоминания. Он поддерживает опциональное уточнение для достижения более высокого уровня запоминания ценой дополнительной памяти, что делает его универсальной заменой IVF_SQ8 и IVF_FLAT в сценариях с ограниченным объемом памяти.

Обзор

IVF_RABITQ означает Inverted File with RaBitQ quantization, объединяющий две мощные техники для эффективного поиска и хранения векторов.

IVF

Inverted File (IVF) организует пространство векторов в управляемые регионы с помощью кластеризации k-means. Каждый кластер представлен центроидом, который служит точкой отсчета для векторов внутри этого кластера. Такой подход к кластеризации сокращает пространство поиска, позволяя алгоритму сосредоточиться только на наиболее релевантных кластерах при обработке запроса.

Чтобы узнать больше о технических деталях IVF, обратитесь к разделу IVF_FLAT.

RaBitQ

RaBitQ - это современный метод бинарного квантования с теоретическими гарантиями, представленный в научной статье "RaBitQ: квантование высокоразмерных векторов с теоретическим ограничением ошибки для приближенного поиска ближайших соседей" Цзяньяна Гао и Ченга Лонга.

RaBitQ представляет несколько инновационных концепций:

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

Теоретическая основа: Основная формула аппроксимации расстояния имеет вид:

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Где:

• $or\mathbf{o_r}$ or - вектор данных из набора данных.
• $qr\mathbf{q_r}$ qr - вектор запроса
• $co\mathbf{c_o}$ co - ближайший центроидный вектор ЭКО для $or\mathbf{o_r}$ o r
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) и $C_1(\mathbf{o_r}, \mathbf{c_o})$ C ${}_{}(o$ r, c o ) являются предварительно вычисленными константами
• $o~\tilde{\mathbf{o}}$ ~ квантованный двоичный вектор, хранящийся в индексе
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩$ представляет собой операцию точечного произведения.

Эффективность вычислений: Бинарная природа $o~\tilde{\mathbf{o}}$ ~ делает вычисления расстояний чрезвычайно быстрыми, что особенно выгодно при использовании современных архитектур процессоров с выделенными инструкциями AVX-512 VPOPCNTDQ на процессорах Intel Ice Lake+ или AMD Zen 4+.

Алгоритмические усовершенствования: RaBitQ эффективно интегрируется с такими известными методами, как подходFastScan и случайные вращения, что повышает производительность.

ЭКО + RaBitQ

Индекс IVF_RABITQ сочетает в себе эффективную кластеризацию IVF и передовое двоичное квантование RaBitQ:

1. Грубая фильтрация: IVF разбивает векторное пространство на кластеры, значительно сокращая область поиска за счет фокусировки на наиболее релевантных областях кластеров.

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

3. Дополнительное уточнение: Если эта функция включена, индекс хранит дополнительные уточненные данные, используя форматы более высокой точности (SQ6, SQ8, FP16, BF16 или FP32), чтобы улучшить показатели запоминания за счет увеличения объема памяти.

Milvus реализует IVF_RABITQ с использованием следующих фабричных строк FAISS:

• С уточнением: "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• Без уточнения: "RR({dim}),IVF{nlist},RaBitQ"

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

Чтобы построить индекс IVF_RABITQ для векторного поля в 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="IVF_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

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

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

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

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

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

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

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

search_params = {
    "params": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement 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 при построении индекса.

	Параметр	Описание	Диапазон значений	Предложение по настройке
ЭКО	nlist	Количество кластеров, создаваемых с помощью алгоритма k-means при построении индекса. Каждый кластер, представленный центроидом, хранит список векторов. Увеличение этого параметра уменьшает количество векторов в каждом кластере, создавая меньшие, более целенаправленные разделы.	Тип: Целое число Диапазон: [1, 65536] Значение по умолчанию: 128	Большие значения nlist улучшают отзыв за счет создания более точных кластеров, но увеличивают время построения индекса. Оптимизируйте значение в зависимости от размера набора данных и доступных ресурсов. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [32, 4096].
RaBitQ	refine	Включает процесс уточнения и сохраняет уточненные данные.	Тип: Булево Диапазон: [true, false]. Значение по умолчанию: false	Установите значение true, если требуется коэффициент запоминания 0,9+. Включение уточнения повышает точность, но увеличивает требования к хранению и время создания индекса.
	refine_type	Определяет представление данных, используемое для уточнения, когда включено refine.	Тип: Строка Диапазон: [SQ6, SQ8, FP16, BF16, FP32]. Значение по умолчанию: Нет	Перечисленные значения представлены в порядке возрастания частоты запоминания, уменьшения QPS и увеличения размера хранилища. SQ8 рекомендуется в качестве отправной точки, обеспечивая хороший баланс между точностью и использованием ресурсов.

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

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

	Параметр	Описание	Диапазон значений	Предложение по настройке
ЭКО	nprobe	Количество кластеров для поиска кандидатов. Большие значения позволяют искать в большем количестве кластеров, что улучшает запоминание благодаря расширению области поиска, но ценой увеличения задержки запроса.	Тип: Целое число Диапазон: [1, nlist]. Значение по умолчанию: 8	Увеличение этого значения улучшает запоминание, но может замедлить поиск. Установите значение nprobe пропорционально значению nlist, чтобы сбалансировать скорость и точность. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [1, nlist].
RaBitQ	rbq_query_bits	Устанавливает, будет ли применяться дополнительное скалярное квантование вектора запроса. Если установлено значение 0, запрос используется без квантования. Если задано значение в пределах [1, 8], запрос препроцессируется с использованием n-битного скалярного квантования.	Тип: Целое число Диапазон: [0, 8] Значение по умолчанию: 0	Значение по умолчанию 0 обеспечивает максимальную скорость отзыва, но самую низкую производительность. Мы рекомендуем протестировать значения 0, 8 и 6, поскольку они обеспечивают схожую скорость отзыва, а 6 - самую быструю. Для более высоких требований к отзыву используйте меньшие значения.
	refine_k	Процесс уточнения использует более качественное квантование, чтобы выбрать необходимое количество ближайших соседей из refine_k раз большего пула кандидатов, отобранных с помощью IVF_RABITQ.	Тип: Плавающая величина Диапазон: [1, float_max) Значение по умолчанию: 1	Более высокие значения refine_k уменьшают QPS, но увеличивают коэффициент запоминания. Начните с 1 и тестируйте значения 2, 3, 4 и 5, чтобы найти оптимальный компромисс между QPS и recall для вашего набора данных.