Разработали новый пространственный индекс для обратного гео-кодера и метод поиска адресов по координатам, использующий данный индекс.

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

Для быстрого выполнения такого поиска наш обратный гео-кодер использует пространственный индекс в виде пирамиды (дерева) вложенных тайлов, на которые нарезана карта гео-кодера. В предыдущей реализации этого индекса и в алгоритме поиска по нему было выявлено замедление при обработке пространственных запросов в полярных широтах. В особо сложных ситуациях запрос мог выполняться несколько сотен миллисекунд. Проблема была обусловлена методом нарезки исходной карты на тайлы и формирования из них многослойного дерева-пирамиды на некоторых широтах, а также методом спуска по дереву и отбора подходящих тайлов для пространственных запросов в районе полюсов Земли.

Для решения проблемы была переработана структура гео-индекса. При построении дерева тайлов добавили дополнительные промежуточные слои на участках с плотной застройкой и сократили число тайлов в малонаселённых областях. Это поспособствовало более точному поиску. Также изменили порядок обхода дерева тайлов при обработке пространственных запросов. В новой реализации при поиске делается несколько спусков по дереву, чтобы точно отобрать только листья, пересекающиеся с исходной искомой областью. Это даёт существенное сокращение размера выборки адресов-кандидатов, проверяемых на предмет соответствия исходному пространственному запросу.

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