Using quad trees for calculating 2GIS traffic jams
Even without being a navigator, 2GIS collects and displays traffic information. Firstly, it is necessary to build optimal routes, and secondly, such data is very necessary for users in large cities.
The traffic jam service appeared in 2GIS in September 2011 and today operates in five cities ( Novosibirsk , St. Petersburg , Krasnoyarsk , Ufa , Kazan ). The plans for the near future are to launch traffic jams in all cities with over one million people.
Under the cut, the story is about what problems we encountered and how we solved them.
The basis of “Traffic Jams” is data, namely points. A single point carries the following basic information:
We get such points from our data providers, as well as users of the 2GIS mobile version. Before participating in the calculation, the data ends up in a raw data store based on MongoDB .
What is “point drawing” and why is it needed: A
traffic jam does not exist by itself, but is usually located on some road. The points themselves do not contain information on which section the device was driving at the time of registration, so they must be superimposed on the road network.
Thus, the attraction of points is the process of correlating to each point of a section of the road on which it was registered, taking into account its speed and direction of movement.
Let's take one point (Figure a), and try to determine in which section of the road it was registered.
It is clear that the desired section of the road is somewhere near the point, so the task immediately arises of finding the nearest segment of the road network in a certain radius (for example, 20 meters).
In this case, the direct and reverse directions of the nearest segment (Figure b) do not coincide very much with the direction that the device fixed at the moment of registration of the point (shown by an arrow), therefore this segment is not what we were looking for. It can be seen from the figure that the correct answer was nearby. Such situations may arise, for example, due to a significant error of devices (trackers). At more complex (possibly multi-level) junctions, they arise constantly, so such a search will not work.
We modify it as follows: we will not search for the nearest segment, but all segments in a radius. As a result of such a search, we will get several segments at once, and taking into account their direction, distance to them, and other attributes, we will be able to select the desired segment more correctly.
Everything would be fine, but the expensive network in some cities is very large, hundreds of thousands of segments, and the points that need to be attracted are millions in a few minutes, so along with the quality of the solution to the problem, the question also arises of the speed of the search.
Initially, there was no problem counting online traffic jams, but there was a task to process monthly data so that in our offline products we set the average monthly speeds on the roads and more realistic show the travel time.
Data from suppliers was aggregated in a central repository.
Since the central data warehouse uses PostgreSQL , this problem was also solved in the early stages using the PostGIS extension .
Simply put, the algorithm was something like this:
All this kitchen worked on stored procedures, although not very quickly, but there was no urgency in these data, since the task was solved for offline products.
On an average server, the speed was about 2,000 points per second.
With the advent of the “Online” mode, this solution was not enough: the data is updated every five minutes, so the full cycle of data processing should fit at this time. With an increase in the volume of data, this stage began to take so long that it was difficult to enter the entire cycle in five minutes even on a very powerful hardware.
The time has come to realize the long-overdue idea - the implementation of calculations in C ++.
In parallel, we began to develop 2 solutions - one based on the GEOS library, and the second completely from scratch based on quadtrees.
This solution appeared first because it used the ready-made GEOS library , which, by the way, is used by PostGIS. Quadtree indexes from this library were
used to search for the nearest segments . To do this, all segments of the road graph are loaded into the tree, the hit area around the point is indicated, and at the output we have a set of segments that intersect the hit area, then the segments are sorted by distance to the point and the nearest one is selected.
This implementation appeared second, but (looking a little ahead) it turned out to be a little more successful.
First, a few general definitions to add clarity.
A quad tree is a tree in which each internal node has four descendants.
The quad tree allows you to recursively split a two-dimensional space into four quadrants (regions).
Quad trees can store information about different types of data, however, we are interested in storing segments (segments), since the road network can simply be represented using segments.
To do this, we used the version of PM Quadtree optimized for storing segments - Polygonal Map Random Quadtree.
PMR Quadtree:
Minuses:
Each node of the tree represents a certain area (for example, square) and contains the following information:
A node stores only those segments that intersect its area. The number of segments in a node is variable.
Building a data structure is the process of sequentially inserting segments into a tree. Initially, the tree is empty.
Similar to the algorithms for constructing many other hierarchical data structures, the Quadtree PMR construction algorithm is based on top-down traversal . In other words, starting from the root node, we visit all the child nodes intersecting with the segment and add this segment to all the external nodes encountered.
A key aspect of Quadtree PMR is the split rule, that is, the condition under which a node is divided. For this purpose, some parameter t is used that limits the number of segments that can be contained in a node.
If the number of segments that intersects the region exceeds tand if the maximum level of depth is not reached, then this area is divided into four subsidiary, and all segments that intersect with it are inserted into new child nodes. It is worth noting that immediately after the split, the child nodes do not split again, even if the number of segments in the node exceeds t . This avoids over-partitioning and leads to probabilistic behavior in the sense that the order in which objects are inserted affects the structure of the resulting tree.
For search we will use priority queue .
We will place objects of three types in the queue:
The key in the queue is the distance to the starting point. Initially, the queue contains only the root node.
Now at each step we will take an object with a minimum distance from the queue and, depending on its type, carry out the appropriate operations:
Similarly, you can solve the problem of several nearby segments in a radius.
Comparing the implementation on GEOS and our own, we were pleasantly surprised:
On the same hardware for 300,000 segments:
As a result, our own solution formed the basis of the new point-attracting service, and allows us to draw points from all suppliers throughout Russia on an average server.
As a result, moving from PostGIS to a highly specialized solution in C ++, we got acceleration from 2k to 380k (190 times).
Write highly specialized bikes!
You can see how traffic jams service works right now , or by installing 2GIS on iOS or Android .
The traffic jam service appeared in 2GIS in September 2011 and today operates in five cities ( Novosibirsk , St. Petersburg , Krasnoyarsk , Ufa , Kazan ). The plans for the near future are to launch traffic jams in all cities with over one million people.
Under the cut, the story is about what problems we encountered and how we solved them.
The basis of “Traffic Jams” is data, namely points. A single point carries the following basic information:
- ID of the project (city);
- registration time;
- coordinates;
- instantaneous speed;
- direction of movement at the time of registration.
We get such points from our data providers, as well as users of the 2GIS mobile version. Before participating in the calculation, the data ends up in a raw data store based on MongoDB .
What is “point drawing” and why is it needed: A
traffic jam does not exist by itself, but is usually located on some road. The points themselves do not contain information on which section the device was driving at the time of registration, so they must be superimposed on the road network.
Thus, the attraction of points is the process of correlating to each point of a section of the road on which it was registered, taking into account its speed and direction of movement.
Let's take one point (Figure a), and try to determine in which section of the road it was registered.
It is clear that the desired section of the road is somewhere near the point, so the task immediately arises of finding the nearest segment of the road network in a certain radius (for example, 20 meters).
In this case, the direct and reverse directions of the nearest segment (Figure b) do not coincide very much with the direction that the device fixed at the moment of registration of the point (shown by an arrow), therefore this segment is not what we were looking for. It can be seen from the figure that the correct answer was nearby. Such situations may arise, for example, due to a significant error of devices (trackers). At more complex (possibly multi-level) junctions, they arise constantly, so such a search will not work.
We modify it as follows: we will not search for the nearest segment, but all segments in a radius. As a result of such a search, we will get several segments at once, and taking into account their direction, distance to them, and other attributes, we will be able to select the desired segment more correctly.
Everything would be fine, but the expensive network in some cities is very large, hundreds of thousands of segments, and the points that need to be attracted are millions in a few minutes, so along with the quality of the solution to the problem, the question also arises of the speed of the search.
What was before
Initially, there was no problem counting online traffic jams, but there was a task to process monthly data so that in our offline products we set the average monthly speeds on the roads and more realistic show the travel time.
Data from suppliers was aggregated in a central repository.
Since the central data warehouse uses PostgreSQL , this problem was also solved in the early stages using the PostGIS extension .
Simply put, the algorithm was something like this:
- At the preparation stage, polygons ( ST_Buffer function ) were built around all edges of the graph , the width (different for different classes of roads) of which determined the permissible deviation.
- The points were checked for getting into these polygons and acceptable edges were selected.
- The projection of a point ( ST_ClosestPoint function ) was built on all admissible edges and we received a sorting of the allowable edges by distance.
- Using sorting by distance, checking the azimuth of the point and the azimuth of the segment of the edge, the class and width of the road and the previous drawn points from this device, we determined the probable edge of the graph and considered the projection of the point on this edge as the drawn point and recorded it in the database.
All this kitchen worked on stored procedures, although not very quickly, but there was no urgency in these data, since the task was solved for offline products.
On an average server, the speed was about 2,000 points per second.
With the advent of the “Online” mode, this solution was not enough: the data is updated every five minutes, so the full cycle of data processing should fit at this time. With an increase in the volume of data, this stage began to take so long that it was difficult to enter the entire cycle in five minutes even on a very powerful hardware.
The time has come to realize the long-overdue idea - the implementation of calculations in C ++.
Search for quick solutions
In parallel, we began to develop 2 solutions - one based on the GEOS library, and the second completely from scratch based on quadtrees.
About GEOS
This solution appeared first because it used the ready-made GEOS library , which, by the way, is used by PostGIS. Quadtree indexes from this library were
used to search for the nearest segments . To do this, all segments of the road graph are loaded into the tree, the hit area around the point is indicated, and at the output we have a set of segments that intersect the hit area, then the segments are sorted by distance to the point and the nearest one is selected.
Own implementation of quad trees
This implementation appeared second, but (looking a little ahead) it turned out to be a little more successful.
First, a few general definitions to add clarity.
A quad tree is a tree in which each internal node has four descendants.
The quad tree allows you to recursively split a two-dimensional space into four quadrants (regions).
Quad trees can store information about different types of data, however, we are interested in storing segments (segments), since the road network can simply be represented using segments.
To do this, we used the version of PM Quadtree optimized for storing segments - Polygonal Map Random Quadtree.
PMR Quadtree:
- Uses a probabilistic partition rule;
- Each node contains a variable number of segments;
- Each segment is inserted into all nodes that it intersects;
- If the node contains the number of segments that exceeds the limit, then there is a split (only once) into 4 child nodes;
- Well suited for the task of finding the nearest segment.
Minuses:
- Possible imbalance of the tree.
Each node of the tree represents a certain area (for example, square) and contains the following information:
- Depth
- Area coordinates;
- Four descendants if the node is internal;
- Segments if the node is external.
A node stores only those segments that intersect its area. The number of segments in a node is variable.
Building
Building a data structure is the process of sequentially inserting segments into a tree. Initially, the tree is empty.
Similar to the algorithms for constructing many other hierarchical data structures, the Quadtree PMR construction algorithm is based on top-down traversal . In other words, starting from the root node, we visit all the child nodes intersecting with the segment and add this segment to all the external nodes encountered.
A key aspect of Quadtree PMR is the split rule, that is, the condition under which a node is divided. For this purpose, some parameter t is used that limits the number of segments that can be contained in a node.
If the number of segments that intersects the region exceeds tand if the maximum level of depth is not reached, then this area is divided into four subsidiary, and all segments that intersect with it are inserted into new child nodes. It is worth noting that immediately after the split, the child nodes do not split again, even if the number of segments in the node exceeds t . This avoids over-partitioning and leads to probabilistic behavior in the sense that the order in which objects are inserted affects the structure of the resulting tree.
Visualization
Tree search
For search we will use priority queue .
We will place objects of three types in the queue:
- internal nodes;
- external nodes;
- segments.
The key in the queue is the distance to the starting point. Initially, the queue contains only the root node.
Now at each step we will take an object with a minimum distance from the queue and, depending on its type, carry out the appropriate operations:
- Internal node. We add each of the four descendants to the queue if the distance from it to the point does not exceed R
- External node. Add to the queue all segments contained in it, the distance to which from the point does not exceed R
- Segment. Found the answer to the problem.
Similarly, you can solve the problem of several nearby segments in a radius.
Comparison
Comparing the implementation on GEOS and our own, we were pleasantly surprised:
On the same hardware for 300,000 segments:
| Geos | PMR Quadtree | |
|---|---|---|
| Building a tree | 2 seconds | 0.2 seconds |
| Memory consumption | 200 Mb | 50 Mb |
| Point draw | 35,500 dots per second | 383,500 dots per second |
As a result, our own solution formed the basis of the new point-attracting service, and allows us to draw points from all suppliers throughout Russia on an average server.
Conclusion
As a result, moving from PostGIS to a highly specialized solution in C ++, we got acceleration from 2k to 380k (190 times).
Write highly specialized bikes!
You can see how traffic jams service works right now , or by installing 2GIS on iOS or Android .
