HNSW_SQ

HNSW_SQ сочетает в себе иерархические графы HNSW (Hierarchical Navigable Small World) со скалярным квантованием (Scalar Quantization, SQ), создавая передовой метод векторного индексирования, который предлагает контролируемый компромисс между размером и точностью. По сравнению со стандартным HNSW, этот тип индекса сохраняет высокую скорость обработки запросов при незначительном увеличении времени построения индекса.

Обзор

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

HNSW

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

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

SQ

SQ - это метод сжатия векторов путем представления их меньшим количеством битов. Например:

• SQ8 использует 8 бит, отображая значения на 256 уровней. Дополнительную информацию см. в IVF_SQ8.

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

Hnsw Sq

Такое снижение точности значительно уменьшает занимаемую память и ускоряет вычисления, сохраняя при этом важную структуру данных.

SQ4UCompatible with Milvus 2.6.8+

Для сценариев, требующих экстремальной скорости запросов и минимального использования памяти, Milvus представляет SQ4U, 4-битную унифицированную скалярную квантификацию. Это агрессивная форма скалярного квантования, которая сжимает значение каждого измерения с плавающей точкой в 4-битное целое число без знака.

Буква "U" в слове SQ4U означает Uniform. В отличие от неравномерного скалярного квантования, которое обычно вычисляет минимальные и максимальные значения независимо для каждого измерения (Per-Dimension Quantization), SQ4U применяет стратегию глобального равномерного квантования:

1. Глобальная статистика: Система вычисляет одно минимальное значение vmin и один диапазон значений vdiff, который применяется ко всем измерениям вектора (или ко всему сегменту вектора).

2. Равномерное отображение: Глобальный диапазон значений делится на 16 равных интервалов. Каждое значение с плавающей точкой в векторе, независимо от того, к какой размерности оно относится, отображается на 4-битное целое число (0-15) с помощью этих общих параметров.

Преимущества производительности:

• 8-кратный коэффициент сжатия: Уменьшает размер в 8 раз по сравнению с FP32 и в 2 раза по сравнению с SQ8, значительно снижая нагрузку на пропускную способность памяти, которая часто является узким местом при векторном поиске.

• Оптимизация SIMD: Компактная структура позволяет современным процессорам (AVX2/AVX-512) обрабатывать больше измерений за цикл. Использование глобальных параметров исключает необходимость загрузки изменяющихся значений масштаба/смещения при расчете расстояния, что позволяет полностью насытить конвейер инструкций.

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

HNSW + SQ

HNSW_SQ объединяет сильные стороны HNSW и SQ для эффективного приближенного поиска ближайших соседей. Вот как работает этот процесс:

1. Сжатие данных: SQ сжимает векторы с помощью sq_type (например, SQ6 или SQ8), что уменьшает расход памяти. Такое сжатие может снизить точность, но позволяет системе работать с большими наборами данных.

2. Построение графиков: Сжатые векторы используются для построения 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_SQ по векторному полю в 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_SQ", # 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
        "sq_type": "SQ6", # Scalar quantizer type
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

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

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

• 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	Максимальное количество связей （или ребер), которое может иметь каждый узел в графе, включая как исходящие, так и входящие ребра. Этот параметр напрямую влияет как на построение индекса, так и на поиск.	Тип: Целое число Диапазон: [2, 2048] Значение по умолчанию: 30 (до 30 исходящих и 30 входящих ребер на узел).	Большее значение M обычно приводит к повышению точности, но увеличивает объем памяти и замедляет построение индекса и поиск. Рассмотрите возможность увеличения M для наборов данных с высокой размерностью или в случаях, когда важна высокая запоминаемость. Уменьшайте M, если важны расход памяти и скорость поиска. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [5, 100].
	efConstruction	Количество соседей-кандидатов, рассматриваемых для подключения при построении индекса. Для каждого нового элемента оценивается больший пул кандидатов, но максимальное количество реально установленных соединений все равно ограничено M.	Тип: Целое число Диапазон: [1, int_max]. Значение по умолчанию: 360	Более высокое значение efConstruction обычно приводит к более точному индексу, так как исследуется больше потенциальных соединений. Однако это также приводит к увеличению времени индексирования и увеличению использования памяти при построении. Рассмотрите возможность увеличения efConstruction для повышения точности, особенно в сценариях, где время индексирования менее критично. Уменьшите efConstruction, чтобы ускорить построение индекса, если ограничены ресурсы. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [50, 500].
SQ	sq_type	Определяет метод скалярного квантования для сжатия векторов. Каждый вариант предлагает свой баланс между сжатием и точностью: SQ4U: Кодирует векторы с использованием 4-битного равномерного квантования. Этот режим обеспечивает максимальную скорость и сжатие. SQ6: Кодирование векторов с использованием 6-битных целых чисел. SQ8: Кодирует векторы с использованием 8-битных целых чисел. BF16: Использует формат Bfloat16. FP16: Использует стандартный 16-битный формат с плавающей точкой.	Тип: Строка Диапазон: [ SQ4U, SQ6, SQ8, BF16, FP16 ]. Значение по умолчанию: SQ8	Выбор sq_type зависит от потребностей конкретного приложения. SQ4U выбирается для максимальной скорости и эффективности использования памяти. SQ6 или SQ8 могут подойти для сбалансированной производительности. С другой стороны, если точность имеет первостепенное значение, можно предпочесть BF16 или FP16.
	refine	Булевский флаг, определяющий, применяется ли шаг уточнения во время поиска. Уточнение заключается в повторном ранжировании исходных результатов путем вычисления точных расстояний между вектором запроса и кандидатами.	Тип: Булево Диапазон: [true, false]. Значение по умолчанию: false	Установите значение true, если важна высокая точность и вы можете смириться с небольшим замедлением времени поиска. Используйте false, если приоритетом является скорость, а незначительный компромисс в точности допустим.
	refine_type	Определяет точность данных, используемых для уточнения. Эта точность должна быть выше, чем точность сжатых векторов (заданная параметром sq_type), что влияет как на точность ранжированных векторов, так и на занимаемую ими память.	Тип: Строка Диапазон:[ SQ6, SQ8, BF16, FP16, FP32 ] Значение по умолчанию: None	Используйте FP32 для максимальной точности при больших затратах памяти, или SQ6/SQ8 для лучшего сжатия. BF16 и FP16 предлагают сбалансированную альтернативу.

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

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

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