Использование квадродеревьев при расчёте пробок 2ГИС

    Даже не являясь навигатором, 2ГИС собирает и показывает информацию о пробках. Во-первых, это необходимо для построения оптимальных маршрутов, а во-вторых — такие данные очень нужны пользователям в больших городах.

    В 2ГИС сервис пробок появился в сентябре 2011 года и сегодня работает в пяти городах (Новосибирск, Санкт-Петербург, Красноярск, Уфа, Казань). В планах на ближайшее будущее — запустить пробки во всех городах-миллионниках.

    Под катом история про то, с какими проблемами мы столкнулись и как их решили.


    Основа «Пробок» — это данные, а именно точки. Отдельная точка несёт следующую основную информацию:
    • идентификатор проекта(города);
    • время регистрации;
    • координаты;
    • моментальная скорость;
    • направление движения в момент регистрации.

    Такие точки мы получаем от наших поставщиков данных, а также пользователей мобильной версии 2ГИС. Перед тем как поучаствовать в расчёте, данные попадают в хранилище сырых данных, основанное на MongoDB.

    Что такое «притяжка точек» и зачем она нужна:
    Автомобильная пробка не существует сама по себе, а обычно расположена на какой-нибудь дороге. Сами точки не несут информации о том, по какому участку проезжало устройство в момент регистрации, поэтому их необходимо наложить на дорожную сеть.

    Таким образом, притяжка точек — процесс соотнесения каждой точке участка дороги, на котором она была зарегистрирована, с учётом её скорости и направления движения.



    Давайте возьмём одну точку (рисунок a), и попробуем определить, на каком участке дороги она была зарегистрирована.



    Понятно, что нужный участок дороги где-то рядом с точкой, поэтому сразу встаёт задача поиска ближайшего сегмента дорожной сети в некотором радиусе (например, 20 метров).

    В данном случае прямое и обратное направления ближайшего сегмента (рисунок b) очень не совпадает с направлением, которое зафиксировало устройство в момент регистрации точки (показано стрелкой), поэтому этот сегмент — не то, что мы искали. Из рисунка видно, что правильный ответ оказался рядом. Такие ситуации могут возникать, например, из-за существенной погрешности устройств (трекеров). На более сложных (возможно, многоуровневых) развязках они возникают постоянно, поэтому такой поиск не подойдёт.
    Модифицируем его следующим образом: будем искать не ближайший сегмент, а все сегменты в радиусе. В результате такого поиска получим сразу несколько сегментов, и уже с учётом их направления, расстояния до них, и прочих атрибутов сможем более правильно выбрать искомый сегмент.

    Всё бы хорошо, но дорожая сеть в некоторых городах очень большая, сотни тысяч сегментов, а точек, которые нужно притянуть, — миллионы за несколько минут, так что наравне с качеством решения задачи встаёт вопрос и скорости поиска.

    Что было раньше


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

    Поскольку центральное хранилище данных использует PostgreSQL, то и эта задача на ранних этапах решалась с помощью расширения PostGIS.
    Упрощенно, алгоритм был примерно следующий:
    • На этапе подготовки вокруг всех ребер графа строились полигоны (функция ST_Buffer), ширина (разная для разных классов дорог) которых определяла допустимое отклонение.
    • Точка проверялись на попадание в эти полигоны и выбирались допустимые ребра.
    • На все допустимые ребра строилась проекция точки (функция ST_ClosestPoint) и мы получали сортировку допустимых ребер по расстоянию.
    • Используя сортировку по расстоянию, проверяя азимут точки и азимут сегмента ребра, класс и ширину дороги и предыдущие притянутые точки от данного устройства мы определяли вероятное ребро графа и проекцию точки на это ребро считали притянутой точкой и записывали в базу.

    Вся эта кухня на хранимых процедурах работала, хотя и не очень быстро, но и срочности никакой в этих данных не было, так как задача решалась для офлайн-продуктов.

    На среднем сервере, скорость получалась около 2 000 точек в секунду.

    C появлением режима «Онлайн» этого решения стало недостаточно: данные обновляются каждые пять минут, так что полный цикл обработки данных должен укладываться в это время. С увеличением объёма данных этот этап стал выполняться настолько долго, что вписать в пять минут весь цикл было затруднительно даже на весьма мощном «железе».

    Пришло время реализовать уже давно назревавшую идею — реализация расчётов на C++.

    Поиск быстрых решений


    Параллельно мы начали разрабатывать 2 решения — одно на основе библиотеки GEOS, а второе на полностью с нуля на основании квадродеревьев.

    О GEOS


    Это решение появилось первым, так как использовало готовую библиотеку GEOS, которую, кстати, использует и PostGIS.

    Для поиска ближайших сегментов использовались Quadtree индексы из этой библиотеки.

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

    Собственная реализация квадродеревьев


    Эта реализация появилась второй, но (немного забегая вперед) получилась немного более удачной.

    Сначала несколько общих определений, чтобы добавить ясности.

    Квадродерево — это дерево, в котором каждый внутренний узел имеет четыре потомка.
    Квадродерево позволяет рекурсивно разбить двухмерное пространство на четыре квадранта (области).



    Квадродеревья способны хранить информацию о разных типах данных, однако нас интересует хранение сегментов(отрезков), поскольку дорожную сеть можно просто представить именно с помощью сегментов.

    Для этого мы использовали оптимизированную для хранения сегментов версию PM Quadtree — Polygonal Map Random Quadtree.

    PMR Quadtree:
    • Использует вероятностное правило разбиения;
    • Каждый узел содержит переменное количество сегментов;
    • Каждый сегмент вставляется во все узлы, которые пересекает;
    • Если узел содержит количество сегментов, превышающее ограничение, то происходит разбиение(только однажды) на 4 дочерних узла;
    • Хорошо подходит для задачи поиска ближайшего сегмента.

    Минусы:
    • Возможна разбалансировка дерева.

    Каждый узел дерева представляет некоторую область(например, квадратную) и содержит следующую информацию:
    • Глубину;
    • Координаты области;
    • Четыре потомка, если узел внутренний;
    • Сегменты, если узел внешний.

    Узел хранит только те сегменты, которые пересекают его область. Количество сегментов в узле переменно.

    Построение


    Построение структуры данных представляет собой процесс последовательной вставки сегментов в дерево. Изначально дерево пустое.
    Аналогично алгоритмам построения многих других иерархических структур данных, алгоритм построения PMR Quadtree основан на обходе сверху-вниз (top-down traversal). Другими словами, начиная с корневого узла мы посещаем все дочерние узлы, пересекающиеся с сегментом, и добавляем этот сегмент во все встретившиеся внешние узлы.

    Ключевой аспект PMR Quadtree — правило разбиения, то есть условие, при котором узел делится. Для этой цели используется некоторый параметр t, ограничивающий количество сегментов, которое может содержаться в узле.
    Если количество сегментов, которое пересекается с областью, превышает t и если не достигнут максимальный уровень глубины, то эта область делится на четыре дочерних, а все сегменты, которые с ним пересекались, вставляются в новые дочерние узлы. Стоить заметить, что сразу после разбиения дочерние узлы не разбиваются снова, даже если количество сегментов в узле превышает t. Это позволяет избежать чрезмерного разбиения и приводит к вероятностному поведению в том смысле, что порядок, в котором объекты вставляются, влияет на структуру полученного дерева.

    Визуализация






    Поиск в дереве


    Для поиска будем использовать очередь с приоритетом.
    В очередь будем помещать объекты трёх типов:
    • внутренние узлы;
    • внешние узлы;
    • сегменты.

    Ключ в очереди — расстояние до исходной точки. Изначально очередь содержит только корневой узел.

    Теперь на каждом шаге будем брать из очереди объект с минимальным расстоянием и, в зависимости от его типа, проводить соответствующие операции:
    • Внутренний узел. Добавим в очередь каждый из четырёх потомков, если расстояние от него до точки не превышает R
    • Внешний узел. Добавим в очередь все содержащиеся в нём сегменты, расстояние до которых от точки не превышает R
    • Сегмент. Найден ответ на задачу.

    Аналогично можно решить задачу нескольких ближайших сегментов в радиусе.

    Сравнение


    Сравнив реализацию на GEOS и собственную, мы были приятно удивлены:
    На одном и том же железе для 300 000 сегментов:
    GEOS PMR Quadtree
    Построение дерева 2 секунды 0,2 секунды
    Потребление памяти 200 Мб 50 Мб
    Притяжка точек 35 500 точек в секунду 383 500 точек в секунду

    В итоге собственное решение и легло в основу нового сервиса притяжки точек, и позволяет на среднем сервере делать притяжку точек от всех поставщиков по всей России.

    Заключение


    В итоге, перейдя от PostGIS к узкоспециализированному решению на C++, мы получили ускорение с 2к до 380к (в 190 раз).

    Пишите узкоспециализированные велосипеды!

    Как работает сервис пробок, можно посмотреть прямо сейчас, или установив 2ГИС на iOS, или Android.
    2ГИС
    138,00
    Карта города и справочник предприятий
    Поделиться публикацией

    Похожие публикации

    Комментарии 20

      0
      Не совсем ясно…
      Зашел на сайт, выбрал Уфу — вижу: Не больше 2-х машин на горизонте, а где именно то? на какой дороге?
        0
        Так ведь это показано цветом на карте. :)
        0
        А в PC версию есть планы добавить пробки?
          –3
          А зачем они там? Ведь, чтобы посмотреть пробки, нужен интернет, а если есть интернет, есть и 2ГИС Онлайн. :)
            +5
            Очень странная мотивация.
            +2
            Да, в новой версии они вполне вероятны. В следующем году.
            +2
            GEOS, конечно, чуть ли не стандарт, но когда я решил заглянуть в его исходники, я ужаснулся неоптимальности… практически всего.
            Так что либо искать другие хорошие библиотеки (которых нет), либо да, писать собственные решения.
              +3
              А kd-tree не подошло?
                0
                Вариант с K-D деревом рассматривался, но так и не попробовали.
                Удалось достаточно быстро посмотреть, как с задачей справляется pmr quadtree, на нём и остановились.
                  +1
                  Мы решали похожую задачу. Есть 200к точек. Нужно найти ближайшую точку для пользователя в заданном радиусе.

                  Создание дерева 2сек, 30к выборок == 1 сек на моем слабеньком ноуте. Писали на Java, использовали готовое KD-tree. Реализация решения заняла 2 часа.

                  Нас производительность устраивала, потому не оптимизировали. Но путей для оптимизации там море. Уверен, что вполне можно было бы подобраться к Вашему решению, может как-то выделю время…
                0
                Плоховаты ваши пробки пока, на Яндексе гораздо правдивее. Бердское шоссе возле ул. Русской на юг в вечер пятницы забито и стоит, а по вашим данным почему-то там скорость 50 км/ч.
                  +3
                  Вы же понимаете, что качество пробок напрямую зависит от количества поставщиков данных. Мы постоянно работаем над увеличением количества поставщиков с тем, чтобы обеспечивать полное и качественное покрытие города.
                  В Новосибирске ситуация в ближайшее время должна улучшиться.
                  0
                  А можно я задам вопрос по роутингу, но чуть в сторону от темы статьи?
                  У вас граф роутинга — отдельно хранящаяся и редактируемая сущность, или его топология хранится в той же базе, что и вся остальная топология, а для работы с графом извлекается из нее? То есть на практическом примере: если в городе Н построили новую улицу, она вносится в одно единственное место для хранения, или в два (и более) разных?
                  Хочется понять, на что ваш сервис больше похож архитектурно — на Яндекс или на OpenStreetMap.
                    0
                    Хочется понять, на что ваш сервис больше похож архитектурно — на Яндекс или на OpenStreetMap.

                    Архитектура Яндекса на месте не стоит и бурно развивается: blog.yandex.ru/post/72397/
                    Чтобы оперативно исправлять ошибки, дорожный граф и дороги должны храниться в одной и той же базе и редактироваться одним и тем же инструментом.
                      0
                      Скажите честно, вы — чиновник или SEOшник?
                      Я задал вполне конкретный вопрос по поводу архитектуры 2GIS.
                      Вы ответили, но ваш ответ состоит из:
                      — цитаты из моего вопроса;
                      — хвалебной фразы про Яндекс со ссылкой на их статью (которая не имеет к моему вопросу ни малейшего отношения по простой причине — там про роутинг ничего не написано);
                      — указания на общий факт, который лично мне и так известен, а к упомянутому выше вами Яндексу не имеет также никакого отношения.

                      Вы что-то хотели мне сообщить или цель комментария — ссылка на блог Яндекса?
                        0
                        Скажите честно, вы — чиновник или SEOшник?

                        Я программист.
                        Я задал вполне конкретный вопрос по поводу архитектуры 2GIS. Вы ответили, но ваш ответ состоит из:

                        Про 2GIS я вам ответить не могу, так как там не работаю и устройства их системы не знаю. Однако в вашем вопросе содержится ошибочное утверждение, по поводу которого я и написал.
                        хвалебной фразы про Яндекс со ссылкой на их статью (которая не имеет к моему вопросу ни малейшего отношения по простой причине — там про роутинг ничего не написано)

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

                        Ваши сведения устарели. Можете сопоставить«общий факт» и наличие инфраструктуры для быстрой публикации обновлений.
                          0
                          Быструю публикацию обновлений картинки карты они умели. Граф править вручную — тоже (после того как им в публичном месте на грубую ошибку или неактуальность указали — тут, на Хабре, был пример год назад с дублером Дмитровского шоссе в Москве). В статье, на которую вы ссылаетесь, есть текст:
                          В процессе работы над мировой картой мы полностью переписали ядро Яндекс.Карт. Благодаря этому у нас появилась возможность внедрить единый дизайн, а также инфраструктура для быстрой публикации обновлений. Теперь вносить изменения и исправлять неточности на Яндекс.Картах стало гораздо проще.

                          Из него абсолютно не следует, что теперь хранение и редактирование осуществляется так, как вы описали (и как я имел в виду, приводя пример OSM), есть только общие слова о «полной переработке» — что они конкретно значат, мне неизвестно.
                          А вам?

                          Более того, потыкав в известные мне лично «проблемные» места я все еще вижу, что местами соединение улиц нарисовано, а маршрут прокладывается не через это соединение (хотя нет там никаких запретов точно). Хотя совпадение линий графа и линий карты все же улучшилось, это я признаю как факт. Так что создается впечатление, что что-то переписали (да, прогресс), но полного порядка еще нет.
                            0
                            Из него абсолютно не следует, что теперь хранение и редактирование осуществляется так, как вы описали (и как я имел в виду, приводя пример OSM)

                            Тем не менее, оно именно такое. И это позволяет намного оперативнее и качественнее реагировать на фидбек пользователей.
                            Более того, потыкав в известные мне лично «проблемные» места я все еще вижу, что местами соединение улиц нарисовано, а маршрут прокладывается не через это соединение (хотя нет там никаких запретов точно). Хотя совпадение линий графа и линий карты все же улучшилось, это я признаю как факт. Так что создается впечатление, что что-то переписали (да, прогресс), но полного порядка еще нет.

                            Вы спрашивали про хранение и редактирование данных в едином месте. Это то, с чем работают картографы, мастер реплика. Если в неё будут ходить все сервисы, то и производительность будет никакая и единая точка отказа получится. Кроме того, для разных задач данные выгодно хранить в разном виде, со всякими дополнительными индексами. Это приводит к тому, что версии данных на разных сервисах могут немного отличаться. И чем чаще делаются релизы, тем меньше таких нестыковок.
                            В ОСМ, который вы ставите в пример, используется тот же самый подход. Характерные артефакты можно также найти и на гуглокартах.
                              0
                              Тем не менее, оно именно такое.

                              Как это должно было быть понятно из процитированного фрагмента статьи в блоге Яндекса и того, что вы неписали?
                              Вы спрашивали про хранение и редактирование данных в едином месте.

                              Для начала, я не спрашивал про то, как это устроено в Яндексе.
                              Далее, то что вы описываете, мне прекрасно известно.

                              Могу даже ткнуть пальцем в map.project-osrm.org/ где дата и время импорта графа написана в явном виде на закладке Configuration (обновления происходят раз в сутки), а тайловая картинка (по крайней мере, на слое osm.org) обновляется практически в реальном времени. И данные берутся изначально из одной общей базы, а только отрисовываются и конвертируются для роутинга и т.п. отдельно.

                              Это несколько отличается от ситуации, когда эти данные даже происхождение могут иметь разное, так? Вот потому я Яндекс и приводил как «плохой пример». Если даже сейчас все несколько иначе, тем не менее, раньше было так. Удивлен вашему упорству по выставлению Яндекса в выгодном свете. Не стали бы вы развивать тему — на ровном месте (когда по сути вопроса сказать было нечего) — не пришлось бы тратить время на ерунду.
                      +1
                      В единой базе, в своем слое (слой дорожного графа).

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое