Как математика улучшает геосервисы и помогает быстрее сориентироваться
Сегодня всё чаще требуется учитывать географическую привязку и выполнять поиск в локальном окружении клиента. Иными словами, регулярно возникает необходимость найти что-то (или кого-то) рядом с конкретным пользователем. «Где ближайший банкомат?», «Кто из друзей поблизости?», «Какие тут аптеки?». Подобные запросы миллионами поступают в сервисы геолокации каждый день, при этом существующие подходы к решению этой задачи не исчерпали возможностей оптимизации. Наверняка вы не раз сетовали на то, как долго обновляются метки на карте.
В этой статье эксперт отдела перспективных исследований российской компании «Криптонит» Игорь Нетай рассказывает о способе ускорить обнаружение объектов, принадлежащих одному географическому региону с произвольно заданными размерами. Материал станет частью научной работы о перспективах применения H-кривых в геохешинге.
С помощью рассмотренной в этой статье алгоритмической оптимизации можно быстрее выполнять поиск в различных масштабах — от полушария Земли до конкретного здания.
Координаты одной строкой
Удобство географической персонализации постепенно вытеснило паранойю, и во многих онлайн-сервисах теперь открыто используются данные о местоположении пользователей и различных объектов. Делаете заказ через интернет? Вам предложат забрать его в пункте выдачи поближе к дому. Вызываете такси? Сначала запрос передаётся водителям рядом с вами. Ищете кафе? На карте отобразятся ближайшие.
Все эти алгоритмы сводятся к решению одной и той же задачи: они определяют, какие координатные точки из базы данных входят в тот же условно заданный регион, что и указанная в запросе целевая точка (как правило, обозначающая местоположение пользователя). Для этого используется система кодирования географических координат в виде значений хеш-функции, называемых геохеши.
Пример: для точки с координатами 55°43'55» с.ш. и 37°38'39» в.д. соответствует геохеш ucfv09ev3, задающий квадратную область, в которую попадает московский офис «Криптонита».
Если вы интересовались применением хеш-функций в криптографии, то знаете, что получаемые с их помощью хеш-значения ничего не разглашают об исходных данных. При этом использование хеш-функций для кодирования географических координат максимизирует вероятность того, что чем больше старших разрядов совпадают в хеш-значениях, тем ближе точки на карте друг к другу. О том, как именно это достигается, мы поговорим ниже.
Когда «точнее» не значит «лучше»
Технически мы всегда имеем дело с приблизительными координатами из-за плавающей точности определения местоположения. В городе, среди высотных домов и обилия электромагнитных помех, она постоянно меняется в пределах десятков и даже сотен метров. Иногда из-за этого кажется, что человек быстро перемещается, хотя физически он остаётся на месте. Попытка использовать максимально точные координаты лишь сбивает с толку сервисы, определяющие местоположение пользователя.
Геохеш избавляет от этой проблемы, позволяя задать размер географической области поиска и желаемую точность координат через длину совпадающей левой части (префикса) девятизначного хеша. Если у двух геохешей совпадает лишь первая цифра, значит, соответствующие им координаты находятся в одном полушарии. При совпадении всех девяти цифр можно утверждать, что указанные координатные точки лежат в пределах квадрата стороной в несколько метров.
Представить работу системы геохеширования довольно легко. Мысленно разделите карту мира пополам, проведя вертикальную черту по нулевому меридиану. Так вы отделите Восточное полушарие от Западного. Теперь проведём горизонтальную линию по экватору, разделив Северное и Южное полушарие. Получилось четыре квадранта: северо-западный, северо-восточный, юго-западный и юго-восточный. Это самые большие регионы, которые можно задать всего одной цифрой геохеша.
Теперь разделите каждый из них на четыре части — получится 16 квадрантов поменьше. Продолжим разделять квадранты на более мелкие. Образуются сетки, состоящие из 64, 256, 1024, 4096, 16384, 65536 ячеек и так далее. Чем больше ячеек в сетке, тем меньше будет площадь каждой. Соответственно, точность указания координат вырастет, но и длина геохеша тоже, что повысит требования к вычислительным ресурсам. Как же быть?
Математически длина геохеша — это показатель степени. Если брать битовую систему (основание 2), то 9-значным хешем получится задать только 2^9 = 512 ячеек. Очень мало для практического применения! Раз длину менять нежелательно, меняем основание. Популярный в интернете формат base32 даёт уже 32^9 = 35 184 372 088 832 ячеек. 35 квадриллионов — это много, но достаточно ли? Сейчас посчитаем…
Площадь поверхности Земли составляет приблизительно 510 073 000 000 кв. км. Используя геохеш в формате base32 длиной 9 символов, получим сетку из 35 184 372 088 832 ячеек площадью по 0,0145 кв. км. (14 500 кв. м или 24 дачных участка по 6 соток). Такая точность не отвечает современным потребностям, поэтому OpenStreetMap и другие картографические сервисы продвигают свои альтернативы. Например, base64 даёт возможность уменьшить размер ячейки до 28 кв. м. при той же длине геохеша. Это уже близко к уровню погрешности гражданских систем спутниковой навигации.
Благодаря настраиваемому размеру географических зон поиска, при вызове такси сервис первым делом ищет машины, у которых первые 8 цифр геохеша такие же, как и у геохеша места подачи. Если таких не обнаружилось, запрос расширяется до 7 совпадающих цифр. Снова неудача? Ищем 6 из 9, а если и таких не нашлось, то повторяем процедуру сначала спустя несколько секунд. Машины движутся, а их геохеши быстро меняются. Если же геохеши совпали на 9 из 9 и начали синхронно меняться со временем — считаем, что пассажир в машине и начал поездку.
По аналогии с помощью геохешей можно искать что и кого угодно, а также задавать виртуальные периметры. Самокат с геотрекером покинул зону парковки, а поездка на нём не оплачена? Вероятно, его угоняют. Собака играла во дворе, а теперь её ошейник с GPS шлёт сигнал тревоги? Скорее отправляйтесь на её поиски, она где-то в этом квадранте! Теперь уже в соседнем, а значит — бежит в ту сторону!
Прелесть геохеша в том, что он обеспечивает гибкость настройки зоны поиска и повышает приватность пользователей. С ним нет необходимости передавать максимально точные координаты. Достаточно отправить геохеш, а он покажет, в какой области карты вы находитесь. При этом длина совпадающего префикса отображает, насколько близки выбранные координатные точки друг к другу. Вы можете выбрать точность до материка, страны, города, района, конкретного дома или его подъезда — вам решать, насколько паранойя важнее удобства.
Математическая оптимизация
Для эффективного использования геохешей важно, чтобы для близких координат их хеши мало отличались. С этой целью индексы координатных точек перенумеровывают с помощью фрактальной заполняющей пространство (заметающей) кривой. Впервые эту идею описал в 1966 году сотрудник IBM Гай Макдональд Мортон. Он предложил функцию под названием Z-кривая, с помощью которой значение любой точки задаётся чередованием двоичных цифр, соответствующих её координатам. Это позволяет свернуть двумерную (широта, долгота) систему координат в одномерный массив хеш-значений, а затем использовать удобные для хранения и поиска структуры данных, такие как B-деревья и таблицы хешей.
Популярной идея стала лишь в 2008 году, когдаГуставо Нимейер (программист, ставший техническим директором Canonical) реализовал её в своём сервисе Geohash. С тех пор различные варианты геохеша широко применяются для поиска по приблизительным координатам.
Заполняющие кривые дают дополнительные возможности оптимизации поиска по геохешам, и несколько кривых такого типа нашли применение в ИТ. Самые популярные из них — Z-кривая и кривая Гильберта.
Специалист отдела перспективных исследований российской компании «Криптонит» Игорь Нетай разработал новый тип заметающих кривых — H-кривые. По сравнению с Z-кривыми и кривыми Гильберта они строятся проще и требуют гораздо меньше вычислительных ресурсов, обеспечивая те же или лучшие практические свойства.
Игорь провёл ряд тестов, используя для сравнения метрик качества и бенчмарков материалы магистерской работы Hashing Geographical Point Data Using the Hilbert Space-Filling Curve (Tibor Vukovic, 2016, NTNU).
В ходе тестирования выяснилось, что, если при помощи директивы __builtin_prefetch компилятора GCC поместить в кэш процессора индексы опорных углов H-кривой, то можно сэкономить около 16 нс и получить реализацию даже быстрее, чем в случае с Z-кривой.
Эффективность использования заполняющих кривых в геохешинге сравнивалась и с точки зрения кластеризации (сохранения локальности). Это свойство отображает среднее количество последовательных блоков в индексах, которое влияет на скорость запросов к базе данных, хранящейся на дисковом массиве. С точки зрения этой метрики кривая Гильберта и H-кривая мало отличаются друг от друга, и обе оказываются предпочтительнее Z-кривой. Однако по скорости вычисления H-кривая оказывается существенно лучше. На операциях индексирования и деиндексирования использование H-кривой даёт выигрыш в 4–8 раз.
Также в работе Игоря Нетая сравнивались отличия геохэшей близких точек в метрике Левенштейна. Она отражает отличие по количеству операций вставки, замены и удаления для получения одной битовой последовательности из другой. Эта метрика более применима для оценки минимизации трафика. Как показали тесты, по этому свойству кривая Гильберта оказалась лучше Z-кривой в 51,8% случаев. При этом H-кривая в 74% случаев превосходит и кривую Гильберта, и Z-кривую одновременно.
По результатам исследования готовится научная статья, которая будет размещена в свободном доступе. Подробнее о перспективах применения H-кривых в геохешинге Игорь расскажет в своём докладе на Одиннадцатой школе-конференции «Алгебры Ли, алгебраические группы и теория инвариантов», которая пройдёт с 19 по 24 августа 2024 г. в Самаре. Код реализации Н-кривых Игорь Нетай выложил в открытом доступе на портале ГитХаб.
Выводы
Хеширование данных о географических точках с помощью заполняющей пространство H-кривой может рассматриваться как новый подход к оптимизации сервисов, использующих геолокацию. Он сэкономит вычислительные ресурсы и уменьшит время обработки запросов, что важно для сохранения конкурентного преимущества.
Также H-кривая обладает лучшими свойствами кластеризации, поэтому её применение имеет меньше ограничений в продвинутых геосервисах, использующих многослойное и динамическое наложение различных данных на карту.
