Поделиться
Россиянин создал метод ускорения сервисов геолокации
Созданному специалистом российской компании «Криптонит» методу H-кривых нашлось применение в оптимизации сервисов геолокации. По словам разработчика внедрение H-кривых в сервисы позволит значительно ускорить время обработки запросов и сэкономить вычислительные ресурсы.
Новая технология оптимизации геоинформационных сервисов
Сотрудник компании «Криптонита» Игорь Нетай разработал новый метод оптимизации сервисов геолокации с помощью H-кривых (аш-кривых), который позволит значительно сэкономить вычислительные ресурсы сервисов, при этом ускорив время время обработки запросов.
Игорь Нетай - специалист отдела перспективных исследований «Криптонита», входящего в «ИКС холдинг», и занятого разработкой ПО и ПАК для хранения и анализа больших данных.
Новый метод будет полезен в любой сфере, где требуется точное и детальное представление географических данных и их анализ, начиная от картографии, где метод может помочь в создании более точных и подробных карт, а также в улучшении навигационных систем. Типичному пользователю подобных сервисов это позволит быстрее выполнять поиск в различных масштабах.
Как это работает
Технически все нынешние ГИС сервисы работают с помощью геохешей — метод присоединения географических метаданных к различным информационным ресурсам, таким как фотографии, видео, веб-сайты, RSS, SMS, QR-коды и другие файлы. Эти данные характеризуют описываемые ими ресурсы и состоят из координат широты и долготы, а также могут включать высоту, азимут, расстояние, погрешность, название населённых пунктов и временную метку.
Для эффективного использования геохешей важно, чтобы для близких координат их хеши мало отличались. С этой целью индексы координатных точек перенумеровывают с помощью фрактальной заполняющей пространство (заметающей) кривой. Он предложил функцию под названием H-кривая, с помощью которой значение любой точки задаётся чередованием двоичных цифр, соответствующих ее координатам.
Игорь Нетай провел ряд тестов, в ходе которых выяснилось, что при помещении кэш процессора индексы опорных углов H-кривой, то можно сэкономить около 16 нс и получить реализацию даже быстрее, чем в случае с Z-кривой.
Заполняющие кривые используются для улучшения процесса геохешинга. Они помогают сохранять информацию о местоположении в индексах, что делает запросы к базе данных быстрее. Кривая Гильберта и H-кривая имеют схожие свойства, но H-кривая работает быстрее. Использование H-кривой может ускорить процесс индексирования и деиндексирования в 4-8 раз.
Также было проведено сравнение геохэшей близких точек в метрике Левенштейна. Эта метрика показывает, насколько похожи две последовательности. Она помогает оценить, сколько операций нужно сделать, чтобы получить одну последовательность из другой. Кривая Гильберта оказалась лучше Z-кривой в 51,8% случаев. H-кривая оказалась лучше в 74% случаев.
Что такое H-кривые
Как пояснил сам разработчик данной технологии на подобный вопрос от CNews: «Н-кривые — это циклические фрактальные заполняющие кривые. Они строятся при помощи более простых симметрий (примерно, как у Z-кривой), чем кривая Гильберта, поэтому эффективнее вычисляются. Н-кривые непрерывны и обладают хорошими геометрическими свойствами, поэтому они существенно лучше Z-кривой».
У крупных компаний, таких как Google, есть огромное количество данных, которые сложно организовать и найти. Индекс, который помогает найти нужные данные, занимает только 1% от общего объема данных. Поэтому, когда происходит поиск на различных сайтах, запрос должен пройти через множество дисков, чтобы найти нужные данные.
Когда просматривается фото или видео на определенной площадке, запрос сначала преобразуется в поисковый запрос, который затем отправляется по всей системе, чтобы собрать нужные данные с разных дисков. Скорость этого процесса зависит от того, как быстро система может прочитать индекс. Для его ускорения используются алгоритмы, основанные на параметрических кривых. В случае файловых индексов, параметрические кривые удобны тем, что они представляют координаты блоков данных как функцию одного параметра. Если индексировать по кривым определенного вида, то соседние точки на них будут соответствовать соседним блокам, что гарантированно ускорит их считывание.
Одной из наиболее часто используемых параметрических кривых является кривая Гильберта. Она относится к «заполняющим пространство кривым», потому что при построении она заполняет всю указанную область.
Кроме кривой Гильберта, также используются Z-кривые, кривая Мура и другие. Каждая из них имеет свои преимущества и недостатки в практической реализации.
Как аналог к уже существующим методам Игорь Нетай разработал новый алгоритм для построения заметающих кривых, которые могут быть использованы для улучшения работы кластерных файловых систем. Упомянутые кривые, называемые H-кривыми, обладают теми же свойствами, что и кривые Гильберта, но строятся проще и требуют меньше вычислительных ресурсов. Это полезно для повышения скорости работы файловых систем, а могут быть использованы в геоинформационных системах (ГИС), где позволят сопоставлять множество слоев с каждой точкой на карте. Особенный эффект применение метода Нетая принесет, когда число слоев постоянно растет, например, с добавлением спутниковых снимков, информации о пробках и камерах на дорогах, названий компаний в каждом здании и фотографий популярных мест.
Алгоритмы на основе заметающих кривых также могут успешно применяться в мобильных версиях ГИС, где аппаратные ресурсы ограничены, а координаты пользователя быстро меняются.
Дальнейшее развитие технологии
По результатам данного исследования готовится научная статья, которая будет находиться в свободном доступе. Подробнее о перспективах применения H-кривых в геохешинге Игорь Нетай расскажет в своем докладе на Одиннадцатой школе-конференции «Алгебры Ли, алгебраические группы и теория инвариантов», которая пройдет с 19 по 24 августа 2024 г. в Самаре.
Исходный код реализации H-кривых был выложен на GitHub от компании «Криптонит» до того, как сервис начал блокировать российские аккаунты. А текст с алгоритмом, описанием и результатами бенчмарков доступен в том числе на arXiv.org.
На вопрос редакции почему все материалы исследования находятся в свободном доступе разработчик дал такой ответ: «Это — результат по математике и алгоритмам, что обычно открыто распространяется»
Аналогов похожих геометрических конструкций и данного метода, по словам Нетая, не много.
«Конструкций фрактальных заполняющих кривых очень много, но всё подряд применять не пытаются. Для многих конструкций сложность и реализация не будут сильно отличаться от кривой Гильберта, если строить непрерывные кривые так, как это обычно делают. Я использую немного другой подход к конструкции и строю самую простую кривую с хорошими свойствами. Аналогов новых геометрических конструкций на рынке, наверное, не очень много. По данной теме я их не встречал.»
Математика и технологии часто существуют отдельно друг от друга. Даже если есть математические результаты, которые могут улучшить технологии, до практической реализации и применения обычно проходит много времени. Применение математики в технологиях не происходит автоматически, даже если есть код. И не всегда «технологическая сторона» быстро обращает внимание на нужную математику. Особенно, если не знать, что в каких-то задачах есть прогресс, который может быть очень важным для математики и технологий. «Да, мы на весь мир публикуем математические, общие результаты. Но взаимодействие математики и технологий мы улучшаем в России. Само собой развитие не случается — оно требует усилий и времени» — говорит Игорь Нетай.
Короткая ссылка
