Реализация географического индекса

В этом разделе будет рассмотрен геоиндекс на основе MMFiles. Алгоритм оптимизирован для доступа в памяти и оптимального использования кэша ЦП. Основная цель наших гео-запросов — как можно быстрее отклонить как можно больше удаленных точек результата.

Одним из ограничений подхода, использующего исключительно геострки, является попытка выполнить запрос для поиска точек рядом с целью (см. запись в блоге Часть I). Иногда точки, расположенные близко друг к другу на поверхности, могут иметь совершенно разные префиксы геострок и не могут быть просканированы без поиска. Мы реализовали тип Metric Tree для оптимизации запросов ближайших соседей.

Для последовательного выполнения быстрых запросов геостроки Гильберта объединяются с двоичным деревом поиска, текущая реализация выбирает древовидную структуру AVL.

Дерево AVL строго сбалансировано, чтобы гарантировать O(log(n)) производительность поиска и вставки. Это означает, что обе ветви корневого узла будут иметь разницу в высоте не более 1. В каждом листе дерева AVL мы храним список максимум из 6 точек, прежде чем лист снова разделится. Точки в каждом листе должны быть близки друг к другу на кривой Гильберта, основное предположение всегда состоит в том, что близкие геоструны также будут близки на поверхности земли. Поисковые запросы выигрывают от наличия высокой древовидной структуры, которая позволяет легко уменьшить количество возможных точек.

Для поддержки типичных операций CRUD в индексе нам нужна возможность эффективно вставлять и удалять элементы. Это означает, что для каждого нового элемента нам нужно найти правильный лист в дереве. Требуется функция сравнения, которая позволяет нам быстро перемещаться по дереву индексов, т. е. нужно ли нам идти вниз к левому или правому дочернему элементу, начиная с корневого узла.

Геоиндекс ArangoDB достигает этого, сохраняя расстояние до набора глобальных фиксированных точек в каждом внутреннем узле (горшке). Эти фиксированные точки F_1,…,F_6 являются точками на поверхности земли, в настоящее время северным и южным полюсами, а также равноудаленными точками на экваторе. Ничего принципиально особенного в этом выборе нет, единственное требование к этим точкам — чтобы они находились примерно на одинаковом расстоянии друг от друга.

Каждый горшок содержит максимальное расстояние всех дочерних горшков или точек до каждой из 6 фиксированных точек, которые определяют область на поверхности земли. Эти максимальные расстояния по существу определяют геометрическую форму, которая динамически изменяется в соответствии с содержащимися координатами. В отличие от R-дерева, VP-дерева или других типичных структур, используемых для географических индексов, эти границы основаны не только на фиксированной геометрии, такой как ограничивающий прямоугольник или круг.

Вычисление расстояния по координате каждой из фиксированных точек может быть выполнено очень быстро, потому что нам на самом деле не нужно вычислять точные расстояния. Такой меры, как x²+y²+z² (евклидово расстояние в квадрате), достаточно для сравнения расстояний на приблизительной сфере. Кроме того, расстояния хранятся внутри как 16-битные целые числа для экономии места.

Сравнение производительности

Ради интереса я сравним наш код с реализацией структуры данных Vantage-Point Tree пространственный индекс. VP-Tree — это структура данных, разделяющая пространство, которая позволяет эффективно запрашивать ближайших соседей.

Этот тест не претендует на то, чтобы быть полностью окончательным, он просто служит для получения представления о характеристиках производительности нашего алгоритма по сравнению с реализацией известного алгоритма для той же проблемы. На приведенных ниже диаграммах показано время, необходимое для создания обоих индексов и заполнения их точками, а также общее время для поиска 256 ближайших соседей по 500 случайно выбранным целевым координатам. Как видите, структура данных ArangoDB может быть заполнена быстрее, чем VP-Tree, и имеет сравнимую производительность запросов.

В коде используется версия структуры геоиндекса ArangoDB в памяти, которая используется в нашем механизме хранения MMFiles. Используемая реализация VP-Tree взята отсюда и является довольно простой адаптацией. Эталонные тесты выполняют запросы ближайших соседей для случайно выбранных местоположений на различных типах выборочных данных геолокации:
Существует два типа наборов данных (10.000, 100.0000, …) определяет наборы данных, заполненные случайно сгенерированными географическими координатами, тогда как набор данных мировые города можно найти здесь и содержит (что неудивительно) названия и расположение всех городов мира.

Исходный код бенчмарка доступен на GitHub. Он должен работать на любой Unix-подобной системе с современным компилятором C++. Для части кода ArangoDB соответствующие части выглядят следующим образом:

Для получения дополнительной информации вы также можете посмотреть это великолепное выступление моего коллеги Ричарда.

Дорожная карта для расширенной поддержки гео в ArangoDB

Интеграция geo_cursor уже была хорошим шагом вперед для ArangoDB, но, конечно же, нужно реализовать еще больше полезных функций.

Как упоминалось выше, текущий геоиндекс оптимизирован для нашего механизма хранения MMFiles, но еще не для нашего нового механизма RocksDB, который доступен, начиная с ArangoDB 3.2. Все больше и больше пользователей переходят на RocksDB в качестве механизма хранения, и мы будем интегрировать оптимизированное решение для поддержки эффективных гео-запросов также с этим механизмом. Работа над этим уже началась.

Конечно, скорость — это еще не все, поэтому мы также хотим предоставить более широкий набор географических функций, интегрировав полную поддержку GeoJSON, включая полигоны, мультиполигоны и другие примитивы геометрии.

С помощью этих функций можно выполнять более сложные запросы и создавать, например. Механизмы рекомендаций с учетом местоположения путем объединения модели данных графа с аспектами геолокации или использования нескольких моделей данных. Например, в эпоху беспилотных автомобилей можно найти ближайшую доступную команду технического обслуживания (гео-запрос) с правильным разрешением (графовая модель) для устранения данной проблемы (автоматически отправляется в базу данных, например, в виде документа JSON или ключа/ пара значений).

Как ранее публиковалось на ArangoDB