Как ответить
Поиск ближайших соседей (kNN) — это задача нахождения k точек из заданного множества, которые наиболее близки к запросу по выбранной метрике (евклидово расстояние, косинусная близость и т.д.). Все методы делятся на точные (возвращают гарантированно правильный результат) и приближённые (ANNS — Approximate Nearest Neighbor Search, допускают небольшую погрешность ради скорости). Выбор зависит от размерности данных, размера базы и требований к латентности.
Точные методы
- Линейный (brute-force) поиск — O(n*d) на запрос, просто, но медленно при миллионах точек. Работает как baseline.
- KD-дерево — разбивает пространство по осям (как бинарное дерево поиска, только многомерное). Эффективно до ~20 измерений, при большей размерности падает до линейного поиска из-за проклятия размерности.
- Ball-дерево — использует гиперсферы, лучше KD-дерева на некоторых распределениях, но тоже страдает от размерности.
- R-дерево и его вариации — для пространственных данных (GIS), редко применяют в ML.
Приближённые методы (ANNS)
- Locality-Sensitive Hashing (LSH) — хеширует точки так, что близкие с высокой вероятностью попадают в одну корзину. Использует случайные проекции. На практике даёт неплохую скорость, но требует много памяти для хранения нескольких хеш-таблиц.
- IVF (Inverted File Index) — кластеризует данные (например, k-means), при поиске проверяет только точки из ближайших кластеров. Комбинация с продуктным квантованием (PQ) сильно сжимает вектора — это основа FAISS.
- HNSW (Hierarchical Navigable Small World) — строит многоуровневый граф: верхние уровни — «express lanes» для быстрого перемещения, нижние — детальная окрестность. Один из самых быстрых и точных алгоритмов (используется в Qdrant, Milvus, Chroma). Чувствителен к конфигурации (efConstruction, M).
- Annoy (Approximate Nearest Neighbors Oh Yeah) — строит случайные проекции и деревья (forest), хорош для чтения, но не поддерживает динамическое добавление.
Практические соображения
- Для задач ML на низких размерностях (2–20) можно использовать KD-дерево из sklearn или scipy. Для высоких размерностей (сотни или тысячи — эмбеддинги текста, изображений) нужен приближённый поиск.
- Лучшая на сегодня комбинация: IVF+PQ+HNSW — так работают современные векторные базы. Например, FAISS предлагает IndexIVFPQ с поиском через HNSW над центроидами.
- Выбор метрики: L2 — по умолчанию, косинусная — для нормализованных векторов, inner product — для рекомендательных систем.
import faiss # пример построения индекса FAISS
import numpy as np
d = 128 # размерность
xb = np.random.random((10000, d)).astype('float32')
# создаём плоский индекс (точный)
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)
D, I = index_flat.search(xb[:5], k=5) # поиск 5 ближайших
# приближённый IVF-PQ
nlist = 100
index_ivf = faiss.IndexIVFPQ(index_flat, d, nlist, m=8, nbits=8)
index_ivf.train(xb)
index_ivf.add(xb)
D2, I2 = index_ivf.search(xb[:5], k=5)
Итог: для продакшна с миллионами векторов чаще используют HNSW (как в Qdrant) или FAISS с IVF-PQ. Точные методы — только для прототипов или очень малых данных.