Nearest Neighbor Search

ChatGPT и другие RAG-системы каждую секунду выполняют сотни миллионов поисков «найди похожие документы» среди миллиарда векторов размерностью 1536. Наивный линейный поиск занял бы минуты. kd-дерево здесь не помогает - оно хорошо работает только до 15-20 измерений, а не 1536. Задача nearest neighbor search в высоких измерениях породила целую индустрию алгоритмов.

• **Векторные базы данных:** Pinecone, Weaviate, Milvus, pgvector - все используют HNSW или его варианты для хранения и поиска embedding-векторов от языковых моделей.
• **Spotify Annoy:** поиск похожих треков в каталоге из 100+ миллионов треков; Annoy выбран за возможность memory-map индекса и параллельных запросов без блокировок.
• **Компьютерное зрение:** поиск похожих изображений в галереях (Google Photos, Face ID) - 128-2048-мерные дескрипторы лиц, FAISS с GPU-ускорением.

kd-дерево и точный поиск ближайшего соседа

В базе данных из 10 миллионов 3D-точек наивный линейный поиск ближайшего соседа требует 10 миллионов вычислений расстояния. kd-дерево (k-dimensional tree, Bentley 1975) разбивает пространство гиперплоскостями и превращает этот поиск в O(log n) операций в малых измерениях.

Сложность: построение O(n log n), запрос в худшем случае O(n), но в среднем O(log n) для d = 2, 3. Ключевая оптимизация: отсечение дальней ветки происходит, когда расстояние от запроса до разделяющей гиперплоскости превышает расстояние до текущего лучшего кандидата.

**Backtracking в kd-дереве:** алгоритм начинает как BST (идёт к ближайшему листу), затем поднимается назад и проверяет каждую гиперплоскость. Если шар радиуса «лучшее расстояние» не пересекает соседнюю половину - ветку можно отсечь. В 2D/3D это работает отлично; в 100D - почти никогда.

Locality Sensitive Hashing (LSH)

LSH - это семейство хэш-функций, у которых **вероятность коллизии убывает с расстоянием**: близкие точки хэшируются в одно ведро с высокой вероятностью, далёкие - с низкой. Это противоположность криптографическим хэшам, где коллизия нежелательна.

Для усиления различающей способности берут L таблиц, в каждой - g хэш-функций скомбинированных в одну (AND-конструкция для увеличения точности, OR-конструкция для увеличения полноты). Запрос: хэшировать в L таблицах, собрать кандидатов из всех совпавших вёдер, затем проверить евклидово расстояние до каждого.

**Настройка LSH:** параметр w (ширина ведра) определяет трейдоф: большой w - много кандидатов (высокий recall, медленный запрос), маленький w - мало кандидатов (быстрый запрос, можно пропустить ближайшего). Оптимум зависит от целевого расстояния r и допустимого отношения аппроксимации c.

Approximate NN: библиотеки и трейдофы

Современные ANN-библиотеки (Approximate Nearest Neighbors) используют разные структуры данных, каждая с уникальным трейдофом между recall, latency и памятью. Все они решают одну задачу: найти c-приближённого ближайшего соседа (c-ANN) - точку y такую, что dist(query, y) ≤ c · dist(query, NN) для константы c ≥ 1.

HNSW строит многоуровневый граф: верхние уровни содержат мало точек с длинными рёбрами (быстрая навигация), нижние - все точки с короткими рёбрами (точный поиск). Запрос начинается с верхнего уровня и жадно спускается к ближайшему соседу. Это аналог skip-list для метрических пространств.

Проклятие размерности

kd-дерево в 2D даёт запрос O(log n). В 10D сложность вырастает до O(n^{0.9}). В 100D - до O(n). Причина: проклятие размерности. При росте d объём пространства растёт экспоненциально, а все точки становятся «одинаково далёкими» друг от друга.

Математически: для n точек из равномерного распределения в d-мерном кубе минимальное расстояние до ближайшего соседа ∝ n^{-1/d}. При d = 100 и n = 10^6 это ∝ 10^{-0.06} ≈ 0.87 - ближайший сосед почти так же далёко, как случайная точка. kd-дерево вынуждено проверять почти все точки.

**Практический порог:** kd-дерево конкурентно с линейным поиском при d ≤ 15-20. Выше этого порога нужен ANN. Модели BERT/GPT работают в 768-4096 измерениях - только ANN. Исключение: если данные лежат на низкоразмерном многообразии в высоком пространстве (intrinsic dimensionality), структурированные методы снова работают.

Ключевые идеи

• **kd-дерево:** O(n log n) построение, O(log n) запрос в d ≤ 15-20 измерениях; выше - деградирует до O(n) из-за проклятия размерности.
• **LSH:** хэш-функции с убывающей вероятностью коллизии; близкие точки - в одно ведро, далёкие - в разные; случайные проекции для евклидова расстояния.
• **HNSW:** иерархический граф (skip-list для метрических пространств), O(log n) запросы, поддержка онлайн-вставок; стандарт для production векторного поиска.
• **Проклятие размерности:** при d > 20 все точки становятся равноудалёнными, точный NN-поиск вырождается в линейный; ANN с recall > 0.95 - единственная практическая альтернатива.

Связанные темы

Nearest Neighbor Search лежит в пересечении вычислительной геометрии и машинного обучения:

• Пространственные индексы (R-tree, kd-tree) — kd-дерево - частный случай пространственного индекса; R-tree используется в PostGIS для геоданных
• Dimension reduction (PCA, t-SNE, UMAP) — Снижение размерности до intrinsic dimensionality позволяет вернуться к эффективным точным методам поиска

Вопросы для размышления

• Проклятие размерности делает все точки «одинаково далёкими» в высоких измерениях. Как тогда семантический поиск по эмбеддингам вообще работает - ведь эмбеддинги тоже высокоразмерны?
• LSH гарантирует recall, а не precision: кандидаты из вёдер требуют дополнительной проверки. В каком сценарии правильнее пожертвовать recall ради скорости, и наоборот?
• HNSW строит граф, где каждый узел связан с M соседями. Какие свойства «малого мира» (small-world network) эксплуатирует этот алгоритм для эффективной навигации?

Связанные уроки

• alg-14-dijkstra