Geometric Algorithms at Scale

Uber обрабатывает 28 миллионов GPS-точек в минуту от водителей по всему миру. Google Maps содержит миллиард полигонов зданий и хочет за 100 миллисекунд показать те, что попадают в текущий экран. Здравоохранение Великобритании за пандемию обработало триллион пар контактов через Bluetooth - геометрических близостей. Все эти системы упёрлись бы в стену линейного скана при наивной реализации; именно структуры R-tree, spatial hashing и GPU-параллелизм превращают вычислительную геометрию из учебной дисциплины в производственную инфраструктуру. Без них современная картография, ride-sharing и логистика были бы технически невозможны.

• **PostGIS / MongoDB / ElasticSearch:** R-tree (GiST/2dsphere) индексы поверх миллиардов записей с миллисекундным поиском
• **NVIDIA OptiX / Unreal Lumen:** GPU BVH строится на каждый кадр для трассировки лучей в сценах с миллионами треугольников
• **Apache Sedona / Databricks Mosaic:** distributed spatial-joins на petabyte-данных в реальных пайплайнах Geo BI

R-tree: пространственная индексация больших данных

Линейный скан по миллиарду точек или полигонов - неприемлем. PostGIS, MongoDB GeoSpatial, ElasticSearch Geo, SAP HANA Spatial - все используют R-tree (Antonin Guttman, 1984). Это сбалансированное B-дерево для прямоугольников: каждый внутренний узел хранит минимальный ограничивающий прямоугольник (MBR), охватывающий все его потомки. Поиск range query идёт сверху вниз, отсекая поддеревья, чьи MBR не пересекают целевую область. Высота дерева O(log_M N) при M детях на узел и N листьях, что даёт логарифмический поиск независимо от размерности (2D, 3D, 4D пространственно-временные данные).

Качество R-tree определяется стратегией вставки и расщепления. Guttman оригинально предложил quadratic split - O(N^2), R*-tree (Beckmann, 1990) использует heuristic-минимизацию overlap и dead space, что улучшает поиск на 30-40%. Hilbert R-tree (Kamel-Faloutsos, 1994) упорядочивает прямоугольники по Hilbert-кривой - даёт пространственно-locality для bulk loading. PostGIS GiST-индекс - реализация R*-tree поверх generalized search tree. Для статичных данных bulk loading через STR (Sort-Tile-Recursive) даёт оптимальное packing.

Spatial Hashing: грид как быстрая альтернатива дереву

R-tree оптимален при разнообразии размеров объектов и низком обновлении. Для динамических систем (физика игр, симуляция жидкостей, чат-приложения с геолокацией пользователей) спортивно используется spatial hashing: разбить пространство на однородный грид, для каждой ячейки хранить список объектов внутри. Поиск точек в радиусе R сводится к проверке O((R/cell)^d) ячеек - константа при фиксированном размере ячейки. Обновление позиции - один remove + один insert: O(1). Игровые движки Box2D и Bullet используют spatial hash для broad-phase collision detection. Uber использует geo-hashing (вариант spatial hash) для поиска ближайших водителей.

Grid resolution - ключевая настройка. Слишком крупная ячейка - проверка тысячи кандидатов; слишком мелкая - один объект попадает в десятки ячеек. Эмпирическое правило: средний размер ячейки ~ средний размер объекта. Hierarchical spatial hash - две сетки разного разрешения для объектов разных размеров. Geohash (Niemeyer, 2008) - кодирование (lat, lon) в строку: соседние ячейки имеют общий префикс, что позволяет хранить пространственные данные в Redis ZSET, MongoDB, Cassandra без специальных индексов.

GPU-параллелизм: геометрия как dataflow

Современный GPU - тысячи потоков, выполняющих один и тот же шейдер над разными данными (SIMT). Геометрические алгоритмы естественно ложатся на эту модель: вершинный шейдер обрабатывает каждую вершину независимо, fragment shader - каждый пиксель, compute shader - произвольную задачу. Convex hull, Delaunay triangulation, Voronoi diagrams - всё имеет эффективные GPU-реализации. CUDA-библиотеки cugraph, cuSpatial и RAPIDS дают спатиальные операции на datasets в миллиарды точек за секунды. NVIDIA OmniGraph и Unreal Niagara строят рендеринг частиц поверх GPU spatial queries.

Ключевые паттерны GPU-геометрии: parallel scan (prefix sum) для агрегации, parallel reduction для min/max/argmin, parallel sort для упорядочивания по Morton-кодам, atomic operations для конфликтов записи. GPU-grid и GPU-hash - расширения spatial hashing на GPU: ключи через atomicAdd, корзины параллельно. Главный bottleneck - memory bandwidth и divergence: ветвление if/else в шейдере останавливает warp, поэтому стараются избегать data-dependent branches.

Параллельные алгоритмы: divide-and-conquer на больших данных

Когда даже GPU не справляется, в дело вступают распределённые системы: Spark, Dask, Ray, Apache Sedona (бывший GeoSpark) обрабатывают пространственные данные на сотнях нодов. Ключевая техника - пространственное партиционирование: разделить плоскость на регионы (R-tree, KD-tree, quad-tree partitioning) так, чтобы каждый воркер обрабатывал свой регион независимо. Затем boundary objects обрабатываются отдельным merge-шагом. Это map-reduce, но с геометрической локальностью. Convex hull на миллиарде точек: parallel sort + Andrew's monotone chain на сегментах + merge - линейная масштабируемость до сотен нодов.

Apache Sedona расширяет Spark SQL пространственными функциями: ST_Contains, ST_Distance, ST_Intersects работают на distributed dataframes. Spatial join (найти все пары полигонов, пересекающиеся пространственно) - типовая O(N*M) операция - сводится к O((N+M) log N) через R-tree partitioning + nested-loop в каждом партишене. Google BigQuery GIS, Amazon Redshift Spatial, Databricks Mosaic - коммерческие реализации той же модели на petabyte-данных.

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

• **R-tree - стандарт пространственной индексации:** сбалансированное B-дерево для прямоугольников, основа PostGIS/MongoDB/ES.
• **Spatial hashing** выигрывает на динамических данных: O(1) update против O(log N) в R-tree, идеально для физики и геолокации.
• **GPU-геометрия через Morton-коды** даёт coalesced memory access и параллельное построение BVH за O(N) на тысячах потоков.
• **Distributed spatial joins** требуют пространственного партиционирования, а не hash-партишена, иначе shuffle становится O(N*M).

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

Масштабируемая геометрия объединяет идеи структур данных, GPU-вычислений и распределённых систем.

• Robotics и GIS — Те же R-tree и spatial hashing используются для path planning и GIS-запросов
• Распределённые системы: партиционирование — Пространственное партиционирование - аналог consistent hashing для геометрии

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

• R-tree оптимален для статичных данных, spatial hashing - для динамических. Где проходит граница, после которой имеет смысл иметь обе структуры одновременно?
• GPU-геометрия экономит порядки времени, но требует переписать код под shaders/CUDA. В каких условиях команда выберет хорошо настроенный CPU R-tree вместо GPU BVH?
• Distributed spatial join работает на петабайтах, но настройка spatial partitioner - нетривиальна. Какие практики помогают подобрать grid resolution и sample rate для R-tree partitioning?

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

• cgeom-09 — Range trees и k-d деревья - основа для масштабируемых геометрических запросов
• cgeom-11 — Триангуляция Делоне - базовая структура для пространственных индексов
• ds-16-graphs-intro — Геометрические графы (k-NN graph) - стандартный инструмент
• alg-14-dijkstra — A* - это Dijkstra с геометрической эвристикой
• par-01