Range Search и kd-деревья

1975 год. Стэнфорд. Аспирант Джон Бентли придумывает kd-дерево за один вечер - потому что устал ждать, пока компьютер перебирает весь массив звёздных координат. NASA потом использует эту структуру для каталога Hipparcos. Сегодня та же идея живёт внутри каждого GPS-навигатора, scikit-learn KNeighborsClassifier и vector database Qdrant.

• **GPS-навигаторы**: поиск ближайшей АЗС или поворота - kd-tree query за миллисекунды по миллионам объектов карты
• **scikit-learn KNeighborsClassifier**: при d <= 20 строит kd-дерево автоматически - O(sqrt(n) + k) вместо O(n) на каждый predict
• **Vector databases (Qdrant, Weaviate, Pinecone)**: HNSW - эволюция kd-идеи для d=768 embedding space, recall 95%+ при 1M векторов
• **PostGIS и геобазы данных**: R-tree (обобщение kd) для spatial queries - 'найди все рестораны в полигоне'

Orthogonal Range Search: задача

1975 год. Стэнфорд. Джон Бентли - аспирант второго года - придумывает kd-дерево за один вечер. Ему было скучно ждать, пока компьютер перебирает весь массив звёздных координат при каждом геопространственном запросе. NASA потом использовала эту структуру для каталога Hipparcos: 118 000 объектов, тысячи запросов в секунду. Без kd-дерева - O(n) на каждый запрос. С ним - O(sqrt(n)) в среднем. Сегодня kd-деревья внутри каждого GPS-навигатора, scikit-learn KNeighborsClassifier и библиотеки FAISS от Meta.

**Orthogonal range search**: дано множество точек $P \subset \mathbb{R}^d$ и прямоугольный запрос $Q = [x_1, x_2] \times [y_1, y_2] \times \ldots$, найти все $p \in P \cap Q$. Слово 'orthogonal' означает, что границы параллельны осям координат - никаких наклонных прямоугольников.

Наивное решение: линейный скан за O(n). Работает, но убивает на масштабе. База данных с 10 млн точек геолокации, запрос '100 кафе рядом' - при 1000 запросов/с это 10 млрд операций в секунду. Нужна структура, которая отсекает целые регионы пространства без просмотра каждой точки.

**Стратегия**: разделить пространство на прямоугольные регионы. Каждый узел дерева хранит разделяющую гиперплоскость. При запросе: если регион узла не пересекается с $Q$ - отсечь всё поддерево. Если регион целиком внутри $Q$ - вернуть все точки без проверки. Иначе - рекурсия.

Сложность range search в 2D kd-дереве: O(sqrt(n) + k), где k - число найденных точек. В d измерениях: $O(n^{1-1/d} + k)$. При d=1 это O(log n + k) - binary search. При d=2 - O(sqrt(n)). При d=10 коэффициент $n^{1-1/d}$ приближается к n - начинается проклятие размерности.

Построение kd-дерева

kd-дерево - это BST, обобщённый на k измерений. На каждом уровне чередуется ось разбиения: уровень 0 - делим по x, уровень 1 - по y, уровень 2 - снова по x. Медиана точек по текущей оси становится разделяющей плоскостью. Левое поддерево - точки левее медианы, правое - правее. Результат: сбалансированное дерево глубиной O(log n).

**Выбор оси разбиения** влияет на качество дерева. Три стратегии: (1) циклическое чередование (depth % k) - простейший вариант Bentley 1975; (2) ось с максимальным спредом - точки распределяются равномернее; (3) surface area heuristic - используется в ray tracing BVH, минимизирует вероятность пересечения луча с узлом.

Scikit-learn KNeighborsClassifier по умолчанию строит kd-дерево при d <= 20 и не более 30 точек на лист. При большем d автоматически переключается на ball tree - структуру с гиперсферами вместо прямоугольников. FAISS от Meta идёт дальше: при d > 100 используется иерархический NSW-граф вместо деревьев - approximate nearest neighbor за O(log n) с гарантией recall.

Балансировка через медиану критична: несбалансированное kd-дерево деградирует в O(n) поиск. Для динамических данных (точки вставляются онлайн) стандартное kd-дерево не перебалансируется. В таких случаях используют k-d-b деревья или R*-деревья.

Nearest Neighbor и проклятие размерности

Nearest neighbor search в kd-дереве - рекурсия с backtracking. Спускаемся к листу как в BST, запоминаем кандидата. При возврате - проверяем: а вдруг в другом поддереве есть точка ближе? Критерий: гиперсфера радиуса 'текущее лучшее расстояние' пересекает разделяющую плоскость? Если нет - отсекаем. Если да - заходим. В 2D в среднем посещается O(log n) узлов.

Проклятие размерности - не метафора. При d=2 гиперсфера nearest neighbor пересекает в среднем O(sqrt(n)) гиперплоскостей. При d=10 - уже $O(n^{0.9})$. При d=100 - почти весь датасет. Интуиция: в высоких измерениях все точки 'примерно одинаково далеко'. Разрыв между ближайшей и дальней точкой стремится к нулю в относительных единицах.

**Количественно**: для n точек равномерно в $[0,1]^d$ расстояние до ближайшего соседа $\approx n^{-1/d}$. При d=2, n=10000: расстояние $\approx 0.01$. При d=100, n=10000: $\approx 0.955$ - почти диаметр куба. ANN-библиотеки (FAISS, hnswlib, ScaNN) решают это через приближённый поиск с гарантией recall.

Meta FAISS - самая используемая ANN-библиотека в мире. Под капотом - HNSW (Hierarchical Navigable Small World): граф, где каждая точка связана с ближайшими соседями на нескольких уровнях детализации. Поиск: O(log n) с recall 95%+ при d=128. Pinecone, Qdrant, Weaviate - все используют HNSW или его вариации. kd-дерево осталось для d < 20; для embedding search (d=768, d=1536) - только ANN.

Практическое правило (Richard Bellman, 1957): kd-дерево эффективно при $n \gg 2^d$. При d=10 нужно n > 1024, при d=20 - n > 10^6. Иначе - возвращайтесь к наивному поиску или используйте HNSW.

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

• **Orthogonal range search** - найти все точки в прямоугольном запросе. kd-дерево: O(sqrt(n) + k) в 2D через отсечение регионов
• **kd-tree construction** - медианное разбиение с чередованием осей (depth % k). O(n log n) на построение, O(n) память
• **Nearest neighbor search** - спуск к листу + backtracking: заходим в дальнее поддерево только если гиперсфера пересекает разделяющую плоскость
• **Проклятие размерности**: при d > 20 kd-дерево вырождается. FAISS HNSW - решение для high-dim embedding search

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

Range search и kd-деревья пересекаются с несколькими ключевыми областями:

• Диаграмма Вороного — Dual structure: Voronoi cell = nearest-neighbor region для одной точки
• BST и деревья поиска — kd-дерево - обобщение BST на k измерений
• kNN классификатор — kNN использует k-nearest neighbor search напрямую
• Nearest Neighbor (продвинутый) — Следующий урок: HNSW, ball-tree, approximate NN

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

• Почему отсечение в kd-tree работает через сравнение гиперсферы с гиперплоскостью, а не через прямую проверку расстояний до всех точек?
• При каком значении d граница между 'kd-tree быстрее наивного' и 'kd-tree не лучше O(n)' проходит для конкретного n?
• Как HNSW решает проблему проклятия размерности там, где kd-дерево капитулирует?

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

• cgeom-05 — Диаграмма Вороного - dual structure для nearest-neighbor search
• cgeom-07 — Следующий урок строит advanced NN search поверх kd-дерева
• ds-11-bst — kd-дерево - BST, обобщённый на k измерений
• ml-14-knn — kNN классификатор напрямую использует nearest neighbor search
• alg-10-binary-search — Binary search в 1D - частный случай range search
• ds-19-segment-tree