На сайте "Сnews.ru" опубликована статья ФИО_автора "Россиянин создал метод ускорения сервисов геолокации". Приводим фрагмент, плностью с материалом можно ознакомиться по ссылке.

Созданному специалистом российской компании «Криптонит» методу 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.