Геопространственная инженерия данных пространственный индексирование

Геопространственная инженерия данных' - 'геоданные' 'Пространственное индексирование' - 'индексация

Оптимизация запросов, улучшение времени выполнения и приложения геопространственной науки о данных

Фото от Tamas Tuzes-Katai на Unsplash

Вступление: зачем нужен пространственный индекс?

При работе с геопространственными научными данными очень важно думать о оптимизации кода, который вы пишете. Как сделать агрегацию или объединение наборов данных с сотнями миллионов строк быстрее? В этом посте я расскажу о том, как реализуется пространственный индекс, каковы его преимущества и ограничения, и рассмотрим библиотеку индексирования H3 от Uber для некоторых интересных приложений геопространственной науки о данных. Приступим!

🗺 Что такое пространственный индекс?

Обычный индекс – это то, что вы можете найти в конце книги: список слов и места их упоминания в тексте. Это помогает вам быстро найти любое упоминание интересующего вас слова в определенном тексте. Без этого удобного инструмента вам пришлось бы вручную просматривать каждую страницу вашей книги, искать то упоминание, которое вы хотели прочитать.

В современных базах данных такая проблема запросов и поиска также очень актуальна. Индексирование часто делает поиск данных быстрее, чем фильтрация, и вы можете создавать индексы на основе интересующего вас столбца. В особенности для геопространственных данных инженеры часто должны работать с такими операциями, как “пересечение” или “рядом с”. Как мы можем создать пространственный индекс, чтобы эти операции были максимально быстрыми? Сначала давайте посмотрим на некоторые геопространственные данные:

Два непересекающихся объекта (изображение автора)

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

Создание большого ограничивающего прямоугольника (изображение автора)

Для ответа на вопрос, пересекаются ли эти два объекта, база данных сравнивает, есть ли у двух ограничивающих прямоугольников общая площадь. Как видите, это может быстро привести к ложным положительным результатам. Чтобы исправить эту проблему, геопространственные базы данных, такие как PostGIS, обычно разбивают эти большие ограничивающие прямоугольники на все более мелкие:

Уменьшение: создание дочерних ограничивающих прямоугольников (изображение автора)

Эти разделы хранятся в R-деревьях. R-деревья – это иерархическая структура данных: они отслеживают большой “родительский” ограничивающий прямоугольник, его детей, детей его детей и так далее. Ограничивающий прямоугольник каждого родителя содержит ограничивающие прямоугольники его детей:

Визуализация R-дерева (изображение автора)

Операция “пересечение” является одной из ключевых операций, которая получает выгоду от этой структуры. При запросе на пересечение база данных просматривает это дерево с вопросом “пересекается ли текущий ограничивающий прямоугольник с интересующим объектом?”. Если да, она смотрит на дочерние ограничивающие прямоугольники и задает тот же вопрос. По мере продвижения по дереву она быстро проходит мимо ветвей, которые не имеют пересечений, и тем самым улучшает производительность запроса. В конце концов, она возвращает требуемую пересекающуюся геометрию.

🧰 В практике: попробуем использовать пространственный индекс с помощью GeoPandas

Давайте теперь рассмотрим на практике, как выглядит использование обычной процедуры по строкам по сравнению с пространственным индексом. Я буду использовать 2 набора данных, представляющих участки переписи населения Нью-Йорка, а также объекты города (лицензированные через Открытые данные и доступные здесь и здесь). Сначала давайте попробуем операцию “пересечение” в GeoPandas на одной из геометрий участков переписи населения. “Пересечение” в GeoPandas – это функция по строкам, которая проверяет каждую строку интересующего нас столбца на пересечение с нашей геометрией или нет.

GeoPandas также предлагает операцию пространственного индекса, который использует R-деревья и позволяет нам выполнять также пересечения. Вот сравнение времени выполнения двух методов за 100 запусков операции пересечения (пометка: поскольку функция пересечения по умолчанию медленная, я выбрал около 100 геометрий из исходного набора данных):

💨 Насколько быстрее пространственный индекс? (изображение автора)

Как видите, пространственный индекс значительно улучшил производительность по сравнению с обычным методом пересечения. Фактически, вот 95% доверительные интервалы для времени выполнения каждого метода:

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

💻 Как выглядят другие пространственные индексы?

Другие компании также адаптировали свои собственные пространственные индексы. Uber использует H3, гексагональную иерархическую систему индексации, которая разбивает мир на равные гексагоны. Гексагоны имеют много преимуществ при моделировании движения людей по городу или при решении проблем, таких как вычисление радиуса. Геопространственные данные размещаются в этих гексагонах, которые служат основной единицей анализа компании. Сетка конструируется путем наложения 122 гексагональных ячеек на икосаэдральную проекцию карты, и она поддерживает широкий спектр функций, включая агрегацию, объединение и применение методов машинного обучения.

Эта система, а также множество ее функциональности, являются открытыми и доступными на GitHub для анализа. Одна из функций API H3 – преобразование точек с широтой и долготой в строки, представляющие уникальный гексагон в соответствии с указанным разрешением. Давайте выполним эту операцию на всей базе данных объектов и также преобразуем строки гексагонов в полигоны:

Одним из вопросов, которые часто возникают в таких проектах анализа пространственных данных, является то, сколько проектов в гексагонах относятся к некоторому столбцу, скажем, “агентство”. К счастью, это очень легко рассчитать и визуализировать теперь, когда у нас есть данные разбитые на гексагоны H3:

Какие агентства имеют больше объектов? (изображение автора)

В этом случае вы можете видеть, что DCAS (Департамент городских административных услуг) и PARKS (Департамент парков и отдыха) – это два агентства с наибольшим количеством объектов на каждый гексагон. Это, вероятно, имеет смысл, поскольку у этих двух агентств может быть больше физических объектов (подумайте об административных зданиях или зонах отдыха, таких как парки).

Заключение

Пространственные индексы, как вы видели, являются очень полезными инструментами оптимизации для геопространственной науки и анализа данных. В случае простого запроса на пересечение, использование пространственного индекса значительно повысило производительность запроса по сравнению со стандартной функцией пересечения GeoPandas. Было много тонкостей в реализации этого индекса, а также его последствий, таких как наличие огромных ветвей кластеризованных данных. Как мы видели, компании разработали свои собственные решения: одним из примеров является открытый индекс Uber H3, который позволяет нам отвечать на различные вопросы пространственного анализа. В то время как я продемонстрировал операцию подсчета объектов на основе агентства, H3 обеспечивает базовую основу для других более сложных приложений машинного обучения.

Если вам нравится такой контент, но вы хотите узнать о технологиях городского планирования более широко, я также пишу рассылку под названием “Хроники выхода из зоны комфорта”. Я призываю вас ознакомиться с ней!

Спасибо за чтение!