FLAT vs IVF: Как работает индекс обратного файла

Те же данные, тот же запрос — но другая стратегия поиска. Перетащите точку запроса, настройте nprobeи нажмите «Запустить поиск», чтобы увидеть, как « IVF » пропускает большую часть данных.

nprobe2

Поиск 2 из 8 кластеров

Скорость20ms

Чем ниже значение, тем быстрее анимация

FLAT — Полный перебор

просматривает каждую точку

Сравнения

200 / 200

Статус

✓ Готово

Recall

100%

IVF — Инвертированный файл

поиски nprobe кластеры

Сравнения

33 / 33

Статус

✓ Готово

Recall@5

100%

Что происходит?

Фаза построения (уже выполнена): алгоритм K-means разделил точки 200 на 8 кластеров. Каждый кластер имеет центроид (отмечен знаком ×).
Шаг 1 — оценка центроидов: « IVF » сначала вычисляет расстояние от запроса до каждого центроида. Это всего лишь 8 сравнений, независимо от размера набора данных.
Шаг 2 — выберите ближайшие кластеры « nprobe »: они подсвечиваются. Все остальные кластеры полностью пропускаются.
Шаг 3 — сканирование точек внутри выбранных кластеров: только ~50 из 200 точек.

Компромисс: чем больше nprobe → больше просканированных кластеров → более высокая точность извлечения, но более медленная работа. Меньший nprobe → быстрее, но вы можете пропустить истинных соседей, находящихся в непросканированных кластерах. Попробуйте установить nprobe = 1 и перетащить запрос к границе кластера, чтобы увидеть падение коэффициента полноты.

Что такое индекс « IVF »?

IVF (Inverted File) — это индекс ближайших соседей, основанный на кластеризации. При построении алгоритм k-means разбивает все векторы на nlist кластеры, каждый из которых представлен своим центроидом. При выполнении запроса алгоритм поиска сначала сравнивает запрос только с центроидами, выбирает ближайшие nprobe кластеров и сканирует только векторы внутри них — пропуская всё остальное.

Milvus Поставляется с несколькими вариантами алгоритма « IVF », в которых точность достигается за счёт увеличения потребления памяти: IVF_FLAT хранит исходные векторы (наибольшая точность), IVF_SQ8 сжимает каждое измерение до одного байта (примерно в 4 раза меньше памяти, небольшая потеря точности), и IVF_PQ применяет квантование произведения для значительно более высокой степени сжатия с большей потерей точности.

Настройка nlist и nprobe

nlist (время построения): количество кластеров метода k-средних. Обычной отправной точкой является значение « 4 × sqrt(N) » для N векторов. Большее количество кластеров означает, что каждый из них меньше — сканирование происходит быстрее, но проход по центроидам требует больше ресурсов, а граничные эффекты усиливаются.
nprobe (время запроса): количество кластеров, которые нужно просканировать за один запрос. Это основной регулятор, влияющий на соотношение «коэффициент восстановления/задержка» — именно этим управляет ползунок выше. Начните примерно с nlist / 16 и увеличивайте значение, пока точность поиска не достигнет заданного уровня.
Выбор варианта: начните с « IVF_FLAT ». Перейдите к « IVF_SQ8 », если памяти не хватает, и к « IVF_PQ » только в том случае, если набор данных слишком велик для « SQ8 » — и проверяйте точность извлечения на своих данных после каждого шага вниз.

IVF vs HNSW vs DiskANN

IVF быстро собирается, имеет небольшую нагрузку на память сверх объёма векторов и прост для анализа — но при одинаковом целевом показателе recall индекс « HNSW » обычно быстрее отвечает на запросы в памяти. Выбирайте « IVF », если вы часто перестраиваете индексы (важна скорость сборки), если память ограничена (IVF_SQ8/IVF_PQ), или если вам нужно предсказуемое и настраиваемое поведение сканирования. Выбирайте HNSW для минимальной задержки запросов в памяти, а DiskANN — когда векторы больше не помещаются в RAM вообще.

Часто задаваемые вопросы

В чём разница между IVF_FLAT, IVF_SQ8 и IVF_PQ?

Все три кластеризуют векторы одинаково; они различаются способом хранения векторов внутри кластеров. « IVF_FLAT » сохраняет исходные векторы с плавающей запятой (наилучший показатель recall). « IVF_SQ8 » квантует каждое измерение до 8 бит, сокращая объем памяти примерно в 4 раза с небольшой потерей показателя recall. « IVF_PQ » заменяет векторы короткими кодами с квантованием по произведению, обеспечивая максимальное сжатие и наибольшую потерю показателя recall.

Как выбрать « nlist » и « nprobe »?

Общее эмпирическое правило: « nlist » = 4 × sqrt(N) для N векторов, затем настраивайте « nprobe » во время запроса. Большее значение « nprobe » сканирует больше кластеров: чем выше recall, тем выше задержка. Начните примерно с « nlist » /16 и увеличивайте значение, пока recall на выделенном наборе запросов не достигнет заданного значения.

Почему алгоритм « IVF » пропускает некоторых истинных ближайших соседей?

Из-за границ кластеров. Если запрос попадает вблизи края кластера, некоторые из его истинных соседей могут находиться в соседнем кластере, который не входил в число просканированных кластеров « nprobe ». Это можно увидеть на визуализации, перетащив точку запроса вблизи границы с показателем « nprobe » = 1.

Что лучше использовать: IVF или HNSW?

При одинаковой точности извлечения алгоритм « HNSW » обычно быстрее при поиске в памяти, но использует больше памяти и собирается медленнее. Алгоритм « IVF » собирается быстро и хорошо сочетается с квантованием (SQ8/PQ), когда памяти мало. Для наборов данных, которые полностью выходят за пределы RAM, вместо этого рассмотрите использование DiskANN.

Узнайте больше: ознакомьтесь с документацией по параметрам индекса в «IVF_FLAT » или просмотрите раздел «Index Explained» для получения полного руководства по принятию решений.