Что такое IVF (Inverted File Index) и как он сравнивается с HNSW по speed/quality?

Краткий тезис

IVF (Inverted File Index) — это метод приближённого поиска ближайших соседей (ANN), основанный на предварительной кластеризации векторов и поиске только в нескольких ближайших кластерах. HNSW (Hierarchical Navigable Small World) — графовый метод, строящий иерархическую структуру для быстрого навигационного поиска. HNSW обычно обеспечивает более высокую скорость и точность (recall) при одинаковом времени поиска, но требует значительно больше оперативной памяти. IVF проще в реализации, дешевле по памяти и легче масштабируется на очень большие наборы данных (миллиарды векторов), однако уступает HNSW в качестве при фиксированных вычислительных ресурсах.

1. Термин: ANN (Approximate Nearest Neighbor) и зачем нужны индексы

Точный поиск k ближайших соседей (kNN) требует сравнения запроса со всеми векторами в базе — O(N*d) операций, что неприемлемо для миллионов и миллиардов векторов. Приближённый поиск ближайших соседей (ANN) жертвует небольшой точностью ради кардинального ускорения. Индексы — это структуры данных, которые организуют векторы так, чтобы поиск выполнялся за сублинейное время. IVF и HNSW — два самых популярных алгоритма ANN, реализованные в библиотеках вроде FAISS, ScaNN, Milvus.

2. Что такое IVF (Inverted File Index)

IVF основан на идее кластеризации и инвертированного списка.

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

1. Все векторы базы данных (N штук) кластеризуются алгоритмом K-means на nlist кластеров.
2. Для каждого кластера вычисляется центроид (вектор среднего).
3. Строится инвертированный список: для каждого кластера сохраняется список идентификаторов векторов, попавших в этот кластер (или сами векторы).

2.2 Поиск

1. Для запроса q вычисляются расстояния до всех центроидов.
2. Выбираются nprobe ближайших кластеров (nprobe ≤ nlist).
3. Векторы из выбранных кластеров сканируются, и среди них ищутся k ближайших соседей (точное сравнение).

2.3 Параметры

• nlist — количество кластеров. Чем больше, тем меньше векторов в каждом кластере, но больше центроидов для сравнения.
• nprobe — количество просматриваемых кластеров. Увеличение nprobe повышает recall, но замедляет поиск.

IVF часто комбинируют с Product Quantization (PQ) для сжатия векторов (IVF+PQ), что ещё сильнее снижает память.

3. Что такое HNSW (Hierarchical Navigable Small World)

HNSW строит многослойный граф на основе идеи small world networks (сеть с короткими путями между узлами).

3.1 Построение

• Создаётся несколько слоёв (уровней). Нижний слой содержит все векторы, каждый следующий — случайное подмножество (вероятность уменьшается экспоненциально).
• На каждом слое каждый вектор соединяется с M ближайшими соседями (на этом же слое). Связи образуют граф.
• Векторы вставляются последовательно: для нового вектора сначала определяется его максимальный слой, затем на каждом слое он встраивается в граф, соединяясь с ближайшими узлами.

3.2 Поиск

• Поиск начинается с самого верхнего слоя (там мало узлов). Выбирается стартовая точка (например, случайная).
• Жадный спуск: на каждом слое алгоритм переходит к соседу, ближайшему к запросу, пока не достигнет локального минимума.
• Затем спускается на следующий слой и повторяет, используя результат предыдущего слоя как начальную точку.
• На нижнем слое выполняется более точный поиск с расширением окрестности (параметр efSearch).

3.3 Параметры

• M — количество связей на узел (обычно 16–64). Больше M → выше качество, но больше памяти и время построения.
• efConstruction — размер динамического списка при построении (влияет на качество графа).
• efSearch — размер динамического списка при поиске (чем больше, тем выше recall, но медленнее).

4. Сравнение по speed (скорость)

Вывод по speed: HNSW обычно быстрее при высоком качестве поиска. IVF может быть быстрее, если пожертвовать точностью (маленький nprobe).

5. Сравнение по quality (recall / точность)

Recall@k — доля истинных ближайших соседей, попавших в результаты.

Пример (из бенчмарков FAISS на SIFT1M):

• IVF (nlist=4096, nprobe=64): recall@1 ~ 0.85, latency ~ 2 ms
• HNSW (M=32, efSearch=64): recall@1 ~ 0.99, latency ~ 1 ms

6. Сравнение по memory (RAM)

Вывод: IVF значительно экономичнее по памяти, особенно в комбинации с PQ. HNSW требует в 1.5–3 раза больше RAM.

7. Другие аспекты сравнения

7.1 Масштабируемость

• IVF хорошо масштабируется на миллиарды векторов за счёт кластеризации и возможности распределённого хранения (sharding по кластерам).
• HNSW сложнее масштабировать: граф становится слишком большим для одной машины, требуются распределённые версии (например, HNSW в Milvus с сегментацией).

7.2 Обновление (добавление/удаление)

• IVF: добавление нового вектора — просто найти ближайший кластер и добавить в его список. Удаление — удалить из списка. Перекластеризация не требуется, но со временем качество может упасть (нужен ребилд).
• HNSW: динамическая вставка возможна (алгоритм поддерживает вставку новых узлов в граф), но удаление сложнее (требует перестроения связей). Часто проще перестроить индекс полностью.

7.3 Простота настройки

• IVF: всего два основных параметра (nlist, nprobe), легко подбираются.
• HNSW: три параметра (M, efConstruction, efSearch), более чувствителен к настройке. Неправильный выбор M может сильно ухудшить качество.

8. Когда выбирать IVF, а когда HNSW

9. Практические рекомендации (на примере FAISS)

import faiss
import numpy as np

# Генерация данных
d = 128  # размерность
nb = 100000  # количество векторов в базе
nq = 1000    # количество запросов
xb = np.random.random((nb, d)).astype('float32')
xq = np.random.random((nq, d)).astype('float32')

# IVF (Flat — без сжатия)
nlist = 100
quantizer = faiss.IndexFlatL2(d)  # центроиды ищутся точным L2
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
index_ivf.train(xb)
index_ivf.add(xb)
index_ivf.nprobe = 10  # количество просматриваемых кластеров
D_ivf, I_ivf = index_ivf.search(xq, k=10)

# HNSW (Flat)
index_hnsw = faiss.IndexHNSWFlat(d, M=32)  # M — количество связей
index_hnsw.hnsw.efConstruction = 40  # качество построения
index_hnsw.add(xb)
index_hnsw.hnsw.efSearch = 64  # качество поиска
D_hnsw, I_hnsw = index_hnsw.search(xq, k=10)

Настройка параметров: используйте бенчмарки на своих данных. Для IVF начните с nlist = sqrt(N), nprobe = 10–100. Для HNSW — M=16–64, efSearch = 50–200.

10. Пет-проект для закрепления

Задача: Сравнить IVF и HNSW на синтетическом датасете (1M векторов размерности 128) по метрикам recall@10 и latency.

Инструменты: Python, FAISS, NumPy, Matplotlib, time.

Шаги:

1. Сгенерировать 1M случайных векторов (база) и 1000 запросов.
2. Построить IVF (nlist=1000, nprobe=10,50,100) и HNSW (M=32, efSearch=50,100,200).
3. Для каждого индекса измерить среднее время поиска и recall@10 (сравнивая с точным kNN через IndexFlatL2).
4. Построить график recall vs latency для обоих методов.
5. Замерить потребление памяти (через sys.getsizeof или анализ размера файла индекса).

Ожидаемый результат: Вы увидите, что HNSW достигает recall 0.95+ при latency ~1-2 мс, а IVF — только при nprobe > 50, но с latency ~5-10 мс. Память HNSW будет в 1.5-2 раза больше.

11. Связь с другими вопросами

12. Навигация

• Предыдущий: 221
• Следующий: 223
• Индекс: 00. Индекс разборов

Навигация

• Предыдущий: 221
• Следующий: 223
• Индекс: 00. Индекс разборов