title: Ð ÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ Ð¿Ð»Ð°Ð½Ð°ÑÐ½Ð¾ÑÑÐ¸ Ð³ÑÐ°ÑÐ° Ð°Ð²ÑÐ¾Ð¼Ð¾Ð±Ð¸Ð»ÑÐ½ÑÑ Ð´Ð¾ÑÐ¾Ð³
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Implementation of the planarity of the graph of highways
Creators: name: Ð£ÑÐ°Ð½Ð¾Ð², ÐÐ½Ð´ÑÐµÐ¹
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2024
Subjects: Open Street Map
MapReduce
C++
Ð¿Ð»Ð°Ð½Ð°ÑÐ½Ð¾ÑÑÑ Ð³ÑÐ°ÑÐ°
Ð¾ÑÐ½Ð¾ÑÐ¸ÑÐµÐ»ÑÐ½ÑÐµ ÑÑÐ¾Ð²Ð½Ð¸
graph planarity
relative levels

description: ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐºÐµ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð½Ð¾Ð¹ ÑÐ¸ÑÑÐµÐ¼Ñ, Ð¾Ð±ÑÐ°Ð±Ð°ÑÑÐ²Ð°ÑÑÐµÐ¹ ÐºÐ°ÑÑÐ¾Ð³ÑÐ°ÑÐ¸ÑÐµÑÐºÐ¸Ðµ Ð´Ð°Ð½Ð½ÑÐµ Ð¸Ð· Ð¾ÑÐºÑÑÑÐ¾Ð³Ð¾ Ð¸ÑÑÐ¾ÑÐ½Ð¸ÐºÐ° OpenStreetMap Ð¿ÑÐ¸ Ð¿Ð¾Ð¼Ð¾ÑÐ¸ Ð¼Ð¾Ð´ÐµÐ»Ð¸ ÑÐ°ÑÐ¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð½ÑÑ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ð¹ MapReduce. Ð ÑÐ°Ð±Ð¾ÑÐµ Ð±ÑÐ´ÐµÑ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð° Ð¿Ð»Ð°Ð½Ð°ÑÐ½Ð¾ÑÑÑ Ð³ÑÐ°ÑÐ° Ð°Ð²ÑÐ¾Ð¼Ð¾Ð±Ð¸Ð»ÑÐ½ÑÑ Ð´Ð¾ÑÐ¾Ð³ Ð¿Ð¾ÑÑÐµÐ´ÑÑÐ²Ð¾Ð¼ ÑÐ°ÑÐ¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð¸Ñ Ð´Ð°Ð½Ð½ÑÑ Ð´Ð¾ÑÐ¾Ð¶Ð½Ð¾Ð³Ð¾ Ð³ÑÐ°ÑÐ° Ð¿Ð¾ Ð¿Ð°ÑÑÐ¸ÑÐ¸ÑÐ¼ Ð¿ÑÐ¸ Ð¿Ð¾Ð¼Ð¾ÑÐ¸ Ð¸Ð½Ð´ÐµÐºÑÐ°ÑÐ¸Ð¸ Ð³ÐµÐ¾Ð¼ÐµÑÑÐ¸Ð¸ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð¼ Geohash, Ð° ÑÐ°ÐºÐ¶Ðµ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ðµ Ð¾ÑÐ½Ð¾ÑÐ¸ÑÐµÐ»ÑÐ½ÑÑ ÑÑÐ¾Ð²Ð½ÐµÐ¹ Ð² ÑÐ·Ð»Ð°Ñ Ð³ÑÐ°ÑÐ°, Ð²Ð¼ÐµÑÑÐ¾ ÑÑÐ°Ð½Ð´Ð°ÑÑÐ½Ð¾Ð³Ð¾ ÑÐ¿Ð¾ÑÐ¾Ð±Ð° Ð¸Ð· OpenStreetMap Ñ ÑÑÐ°Ð½ÐµÐ½Ð¸ÐµÐ¼ Ð¾ÑÐ½Ð¾ÑÐ¸ÑÐµÐ»ÑÐ½ÑÑ ÑÑÐ¾Ð²Ð½ÐµÐ¹ Ñ ÑÐµÐ±ÐµÑ Ð³ÑÐ°ÑÐ°. Ð ÑÐ¾Ð´Ðµ ÑÐ°Ð±Ð¾ÑÑ Ð±ÑÐ»Ð° ÑÐ¾Ð·Ð´Ð°Ð½Ð° Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð° ÑÐ¸ÑÑÐµÐ¼Ð° Ñ Ð¸ÑÐ¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°Ð½Ð¸ÐµÐ¼ ÑÐ·ÑÐºÐ° C++ Ð¸ ÑÐ¸ÑÑÐµÐ¼Ñ ÑÐ°Ð±Ð¾ÑÑ Ñ Ð´Ð°Ð½Ð½ÑÐ¼Ð¸ MapReduce. ÐÐ°Ð½Ð½Ð°Ñ ÑÐ¸ÑÑÐµÐ¼Ð° ÐºÐ¾Ð½Ð²ÐµÑÑÐ¸ÑÑÐµÑ Ð´Ð°Ð½Ð½ÑÐµ Ð¸Ð· Ð±Ð¸Ð½Ð°ÑÐ½Ð¾Ð³Ð¾ ÑÐ¾ÑÐ¼Ð°ÑÐ° ÑÑÐ°Ð½ÐµÐ½Ð¸Ñ PBF Ð² ÐºÐ°ÑÑÐ¾Ð³ÑÐ°ÑÐ¸ÑÐµÑÐºÐ¸Ðµ Ð´Ð°Ð½Ð½ÑÐµ, Ð¿ÑÐµÐ´ÑÑÐ°Ð²Ð»ÐµÐ½Ð½ÑÐµ Ð² Ð²Ð¸Ð´Ðµ ÑÐ°Ð±Ð»Ð¸Ñ. ÐÑÐ»Ð¾ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð¾ Ð´Ð¾Ð±Ð°Ð²Ð»ÐµÐ½Ð¸Ðµ Ð½Ð¾Ð²ÑÑ ÑÐ·Ð»Ð¾Ð² Ð´Ð¾ÑÐ¾Ð¶Ð½Ð¾Ð³Ð¾ Ð³ÑÐ°ÑÐ° Ð´Ð»Ñ ÑÐ¾Ð±Ð»ÑÐ´ÐµÐ½Ð¸Ñ Ð¿ÑÐ°Ð²Ð¸Ð»Ð° Ð¿Ð»Ð°Ð½Ð°ÑÐ½Ð¾ÑÑÐ¸ Ð¸ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ðµ Ð¾ÑÐ½Ð¾ÑÐ¸ÑÐµÐ»ÑÐ½ÑÑ ÑÑÐ¾Ð²Ð½ÐµÐ¹ Ð´Ð»Ñ ÐºÐ°Ð¶Ð´Ð¾Ð³Ð¾ ÑÐ·Ð»Ð° Ð³ÑÐ°ÑÐ°. Ð¢Ð°ÐºÐ¾Ð¹ Ð¿Ð¾Ð´ÑÐ¾Ð´ Ð¿Ð¾Ð·Ð²Ð¾Ð»ÑÐµÑ ÑÑÑÐµÐºÑÐ¸Ð²Ð½Ð¾ ÑÐ°Ð±Ð¾ÑÐ°ÑÑ Ñ ÐºÐ°ÑÑÐ¾Ð³ÑÐ°ÑÐ¸ÑÐµÑÐºÐ¸Ð¼Ð¸ Ð´Ð°Ð½Ð½ÑÐ¼Ð¸, Ð°Ð½Ð°Ð»Ð¸Ð·Ð¸ÑÐ¾Ð²Ð°ÑÑ Ð¸Ñ Ð¸ Ð´Ð¾Ð¿Ð¾Ð»Ð½ÑÑÑ. Ð¡Ð¸ÑÑÐµÐ¼Ð°, Ð¿Ð¾Ð»ÑÑÐµÐ½Ð½Ð°Ñ Ð² ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ ÑÐ°Ð±Ð¾ÑÑ, Ð±ÑÐ»Ð° ÑÐ¾Ð¿Ð¾ÑÑÐ°Ð²Ð»ÐµÐ½Ð° Ð¿Ð¾ ÑÑÑÐµÐºÑÐ¸Ð²Ð½Ð¾ÑÑÐ¸ Ñ Ð¼ÐµÑÐ¾Ð´Ð¾Ð¼, Ð¿ÑÐ¸ ÐºÐ¾ÑÐ¾ÑÐ¾Ð¼ Ð²ÑÐµ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ñ, Ð¾Ð¿Ð¸ÑÐ°Ð½Ð½ÑÐµ Ð² Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ð¸, Ð²ÑÐ¿Ð¾Ð»Ð½ÑÑÑÑÑ Ð½Ð° Ð¾Ð´Ð½Ð¾Ð¼ ÐºÐ¾Ð¼Ð¿ÑÑÑÐµÑÐµ, Ð²Ð¼ÐµÑÑÐ¾ ÑÐ°ÑÐ¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð½ÑÑ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ð¹ Ð½Ð° Ð½ÐµÑÐºÐ¾Ð»ÑÐºÐ¸Ñ ÐºÐ¾Ð¼Ð¿ÑÑÑÐµÑÐ°Ñ.
description: This work is devoted to the development of a software system that processes cartographic data from the OpenStreetMap open source using the MapReduce distributed computing model. The work will implement the planarity of the highway graph by distributing the data of the road graph into partitions using the Geohash geometry indexing algorithm, as well as calculating relative levels at the nodes of the graph, instead of the standard method from OpenStreetMap with storing relative levels at the edges of the graph. During the work, a system was created and implemented using the C++ language and the MapReduce data management system. This system converts data from the PBF binary storage format into cartographic data presented in the form of tables. It was implemented to add new nodes of the road graph to comply with the planarity rule and calculate relative levels for each node of the graph. This approach allows to work effectively with cartographic data, analyze it and supplement it. The system obtained as a result of the work was compared in efficiency with a method in which all calculations described in the study are performed on a single computer, instead of distributed calculations on several computers.