Что такое ANN (Approximate Nearest Neighbors) и как работают алгоритмы поиска приближенных ближайших соседей?

ANN (Approximate Nearest Neighbors) — это класс алгоритмов, которые находят не гарантированно ближайшие, а «достаточно близкие» точки в многомерном пространстве. В отличие от точного kNN (полный перебор или kd-дерево), ANN жертвует строгой точностью ради кардинального ускорения на больших объёмах данных (миллионы векторов размерностью 100–1000+). Используется везде, где нужен быстрый поиск по смыслу: рекомендательные системы, поиск дубликатов, RAG в LLM.

Основная идея — построить индекс, который аппроксимирует структуру данных. Три популярных семейства:

• LSH (Locality-Sensitive Hashing) — хеширует векторы так, чтобы близкие точки с высокой вероятностью попадали в одну корзину. Поиск — перебор только внутри корзины. Просто, но качество сильно зависит от числа хеш-таблиц.
• IVF (Inverted File) — кластеризует данные (обычно K-means) и хранит списки точек для каждого центроида. При поиске выбирает несколько ближайших кластеров и перебирает только их. Параметр nprobe регулирует число просматриваемых кластеров — trade-off между скоростью и точностью.
• HNSW (Hierarchical Navigable Small World) — строит многоуровневый граф: на верхних уровнях — длинные связи для быстрого выхода в нужную область, на нижних — плотные локальные связи. Поиск — жадный спуск с вершины. Сейчас де-факто стандарт для высокоразмерных данных (используется в FAISS, Milvus, Qdrant). Параметры: efConstruction (качество построения), efSearch (глубина поиска).

На практике выбор алгоритма — компромисс. Например, FAISS от Facebook даёт готовые реализации: для точности 0.9 recall@10 на 1M векторов HNSW работает быстрее IVF, но требует больше памяти. Если данные меняются динамически, лучше HNSW (поддерживает вставку/удаление). Для статического набора и ограниченной памяти — IVF с квантованием (PQ).

Ключевой момент — метрика расстояния. Евклидово — для плотных признаков, косинус — для нормализованных эмбеддингов (часто в NLP). Перед построением индекса обычно нормализуют векторы.

Пример настройки FAISS (Python):

import faiss
dim = 768
index = faiss.IndexHNSWFlat(dim, 32)  # 32 — число соседей в графе
index.hnsw.efConstruction = 200
index.add(xb)  # xb — numpy array (N, dim)
index.hnsw.efSearch = 64
D, I = index.search(xq, k=10)  # xq — запросы