Как ответить
Для ускорения поиска ближайших соседей среди множества векторов используют структуры данных, которые сокращают количество полных сравнений. Самый популярный подход в production — комбинация инвертированного файла (IVF) с продуктовой квантизацией (PQ) или иерархический граф HNSW. Выбор зависит от размера данных, требуемой точности и доступной памяти.
HNSW (Hierarchical Navigable Small World) строит многоуровневый граф, где на верхних уровнях хранятся длинные связи (быстрая навигация), а на нижних — точные соседи. Параметры: M (количество связей на узел, обычно 16–64) и efConstruction (глубина поиска при построении). На запросе параметр efSearch управляет точностью. HNSW даёт отличную точность (обычно >95% recall) при скорости поиска за O(log N), но требует памяти около (M * 4 + размер вектора) на точку.
IVF+PQ работает иначе: сначала кластеризуем векторы (K-Means, обычно 256–4096 центров), затем для каждого вектора храним его принадлежность к кластеру и квантованный остаток. Продуктовая квантизация разбивает вектор на подвекторы и кодирует каждый индексом из небольшого словаря (например, 8 бит на подвектор). Это сжимает вектор до нескольких байт. Поиск: выбираем ближайшие кластеры (nprobe), внутри них сравниваем квантованные векторы. IVF+PQ сильно экономит память (вектор 128-мерный можно сжать до 16 байт), но точность ниже HNSW. Часто используется в FAISS.
Пример построения индекса IVF+PQ на Python с FAISS:
import faiss
import numpy as np
d = 128 # размерность
nlist = 256 # количество кластеров
m = 16 # количество подвекторов для PQ
# Обучающие данные
xb = np.random.random((100000, d)).astype('float32')
# Индекс: IVF с квантованием по косинусной метрике (inner product)
quantizer = faiss.IndexFlatIP(d) # для косинуса используем Inner Product после нормализации
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
index.train(xb)
index.add(xb)
# Поиск
xq = np.random.random((10, d)).astype('float32')
index.nprobe = 10 # количество просматриваемых кластеров
D, I = index.search(xq, k=5)Для HNSW в FAISS:
index = faiss.IndexHNSWFlat(d, M=32)
index.hnsw.efConstruction = 200
index.add(xb)
index.hnsw.efSearch = 100
D, I = index.search(xq, k=5)На практике стоит тестировать оба подхода на своих данных. HNSW лучше для высоких требований к точности, IVF+PQ — для ограниченной памяти. Также есть LSH (Locality-Sensitive Hashing) для специфических метрик (например, хэммингова), но в общем случае он уступает по точности.