Requirements of a Map application
A map application tracks where a user is and gives the best route from a source to a destination.
The features taken up:
- Location tracking along whatever route the user chooses.
- A route from source to destination, updated along the way.
- Adding new locations, such as a restaurant or a house.
- Finding nearby stores, such as gas stations within a radius of one or two kilometers. The search is by Cartesian distance, not along the route.
- Traffic updates.
- Estimated time of arrival, built into the routing algorithm.
The features left out are public transport, a custom time to leave, ratings and reviews, live sharing, and location history. Public transport is regular, has start and end times, and has a limited number of routes.
The best route is a straight line, which most of the time does not exist. A route can minimize distance, tolls, turns or the chance of route changes: a highway is chosen over a thin road for the same 30 minutes. This design minimizes one thing, time.
Routing Challenges in Maps
Routing on a map means finding the minimum path from a source to a destination, where one number defines a road: the time taken to move from one end to the other.
Running a graph algorithm looks simple, and the scale of the problem is massive. There are two challenges.
- Locations in the middle of the road. A source or a destination is more likely to be between the ends of a road than at an end.
- Too many paths. From Mumbai to Pune the highway takes around three hours, and the other paths also arrive. The thousands of ways are inside each city, from a place such as Powai or Andheri to the highway and from the highway to the destination.
The one option is approximation.
A location in the middle of a road is converted to a nearby corner point. Points on a road that have turns are marked as limiters, and the source and the destination each use a nearby limiter.
Partitioning Algorithm: Splitting the graph into regions
Partitioning splits the graph of roads into regions with a hub each, so that fewer routes are computed between a source and a destination.
There are too many paths from a source to a destination, and two approaches: reduce the number of routes, or compute the result faster with some approximation.
On a small graph every route is calculated: one takes 8 minutes and the other takes 10. From Powai to Andheri, around 10 or 15 kilometers, calculating all the possible routes every time is too much.
Reducing the routes:
- The two locations are split into regions.
- Each region gets a hub, a common point where most routes start. It might be connected to a highway.
- Every point in a region connects to its hub.
- The best route between the hubs is pre-computed.
The path may not be optimal: a point closer to the destination than the hub still travels to the hub. The trade-off is a quick suggestion to the user, not the best possible one.
Graph partitioning algorithms find the hubs.
Finding the shortest path - A* search
A* search finds a route by approximation: at each point it picks the next point with the lowest sum of the time to reach it and the estimated time from it to the destination.
There are too many routes to cache. From the source x, the possible next points are y, p and q. The cost of going to the destination d through y is the time from x to y plus the estimated time from y to d. The minimum of the three costs gives the route.
The points and edges are stored in a graph database, which has the graph algorithms inbuilt. Edges are roads with the time required to travel on them.
Accurate edge times come from live data. A person broadcasts the location at A at time T1 and at B at T2, and the average of T2 minus T1 is the expected time from A to B.
The estimated time is a heuristic: the Cartesian distance at the current speed. 3 kilometers at 40 kilometers an hour is around 5 minutes.
GeoHash and other proximity filters
GeoHash assigns a hash to a location from its latitude and longitude, and locations that share a prefix are near each other.
Location tracking is push updates to the server: the GPS location is sent every five seconds. It needs no WebSocket, because the communication is not bi-directional. In a tunnel without internet, the client uses the cached route and the accelerometer.
Finding a nearby store takes three filters:
- Relevance. A keyword search on title and description, so that a search for a pharmacy finds a medicine shop. Ratings and reviews screen out closed stores and scams.
- Proximity. A square around the source, sized by the maximum distance a person walks, such as five kilometers.
- Walking time. Stores with an estimated time of arrival greater than 20 minutes are filtered out.
GeoHash does the proximity filter. It splits the world into four pieces, each with its own bits, and splits each piece recursively, adding to the same prefix. It is inaccurate: it misses some nearby destinations and picks up some far ones.
Detecting traffic jams and broadcasting updates
A traffic update changes the estimated time of arrival for every user whose route uses a road that has become faster or slower.
Three signals mark a stretch from X to Y:
- Updates from users on the road about congestion, a breakdown or construction.
- The average time to finish the stretch: an expected 2 minutes against an average of 15 minutes in the past 5 minutes.
- The number of users in the stretch. A dramatic increase suggests a traffic jam or a roadblock.
The weight of X to Y in the graph database is updated from 2 minutes to 30 minutes.
By proximity: user locations are stored in a quad tree or a Hilbert curve, and all users within 5 kilometers of X or Y get the update. Each client checks whether its active route uses X to Y, and if so requests a new route from its current position.
By popular interconnections: a cache maps each highway to the users whose active routes use it, and a highway's update goes to those users.
Calculating an accurate and efficient estimated time of arrival
The estimated time of arrival is a function of the route: the sum of the time to travel every interconnection on it.
The map is split into regions, and each region is recursively broken into sub-regions. A hub represents each region. Region R1 holds R2, R3, R4 and R5, and region R6 holds R7, R8 and R9.
- A route from a source in R3 to a destination in R7 moves up to the parent, R3 to R1.
- It crosses at the same level, R1 to R6.
- It moves down the sub-regions, R6 to R7.
Only the fastest two or three connections between regions are kept, so Dijkstra's has few edges to look into. A new route that consistently takes three minutes where the normal one takes six replaces the slowest connection.
The route may not be optimal: 10 minutes instead of 8 or 6. Users care about a small ETA and almost equally about a predictable one, and well-known routes vary less.
The more historical data there is on an interconnection, the more accurate the prediction.