Bifalgorithm post

"How does Uber find you a driver in just a few seconds? When you request a cab, there are thousands of drivers moving around your city, and each driver is sending their location to Uber servers every four seconds. Uber's algorithm somehow finds you the right cab almost instantly. So let's see how Uber pulls that off. The obvious approach is to take your location and then calculate the distance between you and every driver in the city, and then pick the driver that has the least distance. But in reality, this is not a good approach. A big city can have tens of thousands of active drivers, and calculating distance for every single one of them will melt the servers. And remember, you're not the only customer. There are thousands of customers like you. So Uber does something else. Uber divides the entire planet into small, hexagonal cells. Each cell is less than a square kilometer. This is done by a system called H3 that Uber built. Every driver's latest location maps to exactly one hexagon. Uber only looks in which hexagon you are, plus the six hexagons touching your hexagon. And then Uber considers drivers that are present only in these hexagons. Basically, we now consider tens or hundreds of drivers instead of tens of thousands. If there are not enough drivers in your seven cells, then the algorithm adds the next layer of hexagons, and now you're checking 19 hexagons in total. You might ask why Uber is using hexagons The drivers around corners sit farther away than the drivers near sides, so the term nearby gets slightly distorted. Whereas a hexagon is closer to a circular shape, so all corners are more or less the same distance. Now for real-time matching with drivers, Uber keeps the latest locations of drivers in fast storage. Drivers are pinging continuously every 4 seconds, but for matching, only the latest position matters. I want to clarify one more point, which most of the people get wrong. The closest driver by straight line distance is often the wrong driver. For example, a car may be just 300 metres away, but it might be on the other side of a river, and it might actually be 15 minutes away from you. So Uber ranks the drivers not by plane distance. It ranks by estimated time of arrival along actual roads. And Uber doesn't match customers one at a time. Let's say you and another user named John request a cab at almost the same time, and the driver closest to you is about four minutes away. But that same driver is just two minutes from John, and John's only other option is 15 minutes away. If Uber hands you this driver, which is four minutes away, then John has to wait 15 minutes. Therefore, for Uber, it makes sense to assign you a different driver, which is five minutes away, and assign this driver to John. Yes, your waiting time increases from four to five minutes, but John's time got reduced from 15 minutes to two minutes. This is why Uber actually processes requests in batches, collects cab requests for a small time window, and matches drivers and users in a batch. And the goal is to minimize waiting time for the whole batch of users, not just for one user."

"How does Uber find you a driver in just a few seconds? When you request a cab, there are thousands of drivers moving around your city, and each driver is send…