IVF_PQ

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

Обзор

IVF_PQ означает Inverted File with Product Quantization- гибридный подход, сочетающий индексирование и сжатие для эффективного векторного поиска и извлечения информации. В нем задействованы два основных компонента: Inverted File (IVF) и Product Quantization (PQ).

ЭКО

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

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

1. Кластеризация: Ваш набор векторных данных делится на определенное количество кластеров с помощью алгоритма кластеризации, например k-means. Каждый кластер имеет центроид (репрезентативный вектор для кластера).

2. Назначение: Каждый вектор назначается в кластер, центроид которого находится ближе всего к нему.

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

4. Поиск: При поиске ближайших соседей алгоритм поиска сравнивает вектор запроса с центроидами кластеров и выбирает наиболее перспективный кластер (кластеры). Затем поиск сужается до векторов, входящих в эти выбранные кластеры.

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

PQ

Квантование по продукту (PQ) - это метод сжатия высокоразмерных векторов, который значительно снижает требования к хранению данных и обеспечивает быстрое выполнение операций поиска по сходству.

Процесс PQ включает в себя следующие основные этапы:

Ivf Pq 1

1. Декомпозиция размерности: Алгоритм начинает с разложения каждого высокоразмерного вектора на m равных по размеру подвекторов. Это разложение преобразует исходное D-мерное пространство в m дизъюнктивные подпространства, где каждое подпространство содержит D/m измерений. Параметр m управляет гранулярностью разложения и напрямую влияет на степень сжатия.

2. Генерация кодовой книги подпространства: Внутри каждого подпространства алгоритм применяет кластеризацию k-means для получения набора репрезентативных векторов (центроидов). Эти центроиды в совокупности формируют кодовую книгу для данного подпространства. Количество центроидов в каждой кодовой книге определяется параметром nbits, где каждая кодовая книга содержит ^2nbits центроидов. Например, если nbits = 8, то каждая кодовая книга будет содержать 256 центроидов. Каждому центроиду присваивается уникальный индекс с разрядом nbits.

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

4. Сжатое представление: Окончательное сжатое представление состоит из индексов m, по одному из каждого подпространства, которые в совокупности называются PQ-кодами. Такое кодирование позволяет сократить объем памяти с D × 32 бит (в предположении 32-битных чисел с плавающей точкой) до m × n бит, что обеспечивает значительное сжатие при сохранении возможности аппроксимации расстояний между векторами.

Более подробную информацию о настройке и оптимизации параметров см. в разделе Index params.

Вычисление расстояния с помощью PQ

При выполнении поиска по сходству с вектором запроса PQ обеспечивает эффективное вычисление расстояния за счет следующих шагов:

1. Препроцессирование запроса

   • Вектор запроса декомпозируется на подвекторы m в соответствии с оригинальной структурой декомпозиции PQ.

   • Для каждого подвектора запроса и соответствующей ему кодовой книги (содержащей ^2nbits центроидов) вычисляются и сохраняются расстояния до всех центроидов.

   • При этом создается m таблиц поиска, где каждая таблица содержит ^2nbits расстояний.

2. Аппроксимация расстояний

   Для любого вектора базы данных, представленного PQ-кодами, его приблизительное расстояние до вектора запроса вычисляется следующим образом:

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

   • Просуммируйте эти m расстояния, чтобы получить приблизительное расстояние, основанное на определенном типе метрики (например, евклидово расстояние).

Ivf Pq 2

IVF + PQ

Индекс IVF_PQ объединяет сильные стороны IVF и PQ для ускорения поиска. Процесс работает в два этапа:

1. Грубая фильтрация с помощью ЭКО: ЭКО разбивает векторное пространство на кластеры, сокращая область поиска. Вместо того чтобы оценивать весь набор данных, алгоритм фокусируется только на кластерах, наиболее близких к вектору запроса.

2. Тонкое сравнение с помощью PQ: внутри выбранных кластеров PQ использует сжатые и квантованные представления векторов для быстрого вычисления приблизительных расстояний.

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

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

Чтобы построить индекс IVF_PQ по векторному полю в 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_PQ", # 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": 4, # Number of sub-vectors to split eahc vector into
    } # Index building params
)

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

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

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

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

  • m: Количество субвекторов, на которые нужно разбить вектор.

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

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

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

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

search_params = {
    "params": {
        "nprobe": 10, # Number of clusters to 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=3,  # TopK results to return
    search_params=search_params
)

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

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

  • nprobe: Количество кластеров для поиска.

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

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

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

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

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

	Параметр	Описание	Диапазон значений	Предложение по настройке
ЭКО	nlist	Количество кластеров, создаваемых с помощью алгоритма k-means при построении индекса.	Тип: Integer Диапазон: [1, 65536] Значение по умолчанию: 128	Большие значения nlist улучшают отзыв за счет создания более точных кластеров, но увеличивают время построения индекса. Оптимизируйте значение в зависимости от размера набора данных и доступных ресурсов. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [32, 4096].
PQ	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].

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

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

	Параметр	Описание	Диапазон значений	Предложение по настройке
ЭКО	nprobe	Количество кластеров для поиска кандидатов.	Тип: Целое число Диапазон: [1, nlist]. Значение по умолчанию: 8	Большие значения позволяют искать больше кластеров, что улучшает запоминание благодаря расширению области поиска, но ценой увеличения задержки запроса. Установите значение nprobe пропорционально значению nlist, чтобы сбалансировать скорость и точность. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [1, nlist].