Great article! The images are really well-made. When I used to work at Uber, we actually used H3 (https://www.uber.com/blog/h3/) to split the map into hexagons for various map-related optimizations, like setting pricing.
Very simple explanation to a complex problem, shows a smart mind that understand the problem very well and helped me and I am sure others understand it easily.
I haven't really seen graphs be used in a real world application, so it's good to see a system design implemented using them.
Great illustrative images btw. :) Thanks NK for a great article!
Great article. Got a small question, I see that uber precomputes data for partitions. How does this precomputed edge data considers the current traffic situation, if i want to travel with in the partition
Before reading this article, I was under the impression that Uber relied on a third-party service for ETA calculations, but it turns out they don't use the Google Maps API for this purpose. For any scenario they used Google Maps API for ETA?
I could surely use this any time my friends ask “what’s your ETA”... I always grossly underestimate how much time I need ha!
nice
Great article! The images are really well-made. When I used to work at Uber, we actually used H3 (https://www.uber.com/blog/h3/) to split the map into hexagons for various map-related optimizations, like setting pricing.
thank you so much for sharing the link, Leo. Love it
Great article with simple explanations. Very cool to find out how this works under the hood. Appreciate the article, NK
I'm so happy to read feedback from you, Jordan. Thank you so much.
Very simple explanation to a complex problem, shows a smart mind that understand the problem very well and helped me and I am sure others understand it easily.
I haven't really seen graphs be used in a real world application, so it's good to see a system design implemented using them.
Great illustrative images btw. :) Thanks NK for a great article!
you're welcome, appreciate the feedback a lot.
I am glad that I just witnessed the usage of graphs in real world application,
Thanks for taking time explaining things.
you're welcome
I thought this is coming from Google Maps, they provide the ETA.
Thanks for sharing.
happy to, thanks for the comment.
Very useful article! I like the diagrams, they make the heavy technical aspects easy to understand. Thanks for sharing this, NK!
thanks
I've just noticed that I read and commented on this before :) seems like I love it every time I read it 😂
Great article!!
thanks
Fantastic article. It's amazing to see such valuable information so freely shared. Really appreciate the service you provided.
Okay suppose whole world is made of X San Francisco Bay areas which has Y road intersections.
So total nodes across the world map = X * Y
1. Without partitioning dijkstra time complexity of order (X*Y) log (X*Y)
2. With partitioning i am interacting with boundary nodes only for each partition.
So now, number of boundary nodes per partition = Y ^ 1/2 (as going area to perimeter)
and effective time complexity becomes of order (X * Y^1/2) log(X * Y^1/2)
Just to give an idea, lets take X = 10K, Y = 500, 000 (half million)
1. without paritioning time complexity of order ~ 5e9 (5 * 10 ^ 9)
2. with partitioning time complexity of order ~ 7e6
Doesn't sound much of an optimization assuming X can be very large as we are talking about the world here
Am i missing something here?
Great article. Got a small question, I see that uber precomputes data for partitions. How does this precomputed edge data considers the current traffic situation, if i want to travel with in the partition
Why do you think Uber uses this approach? Building graphs from map requires tons of CPU and RAM.
They use Google API for maps that supports routing and ETAs. Uber competitors do the same.
My guess would be because it's their core domain (DDD) and they want to stay competitive.
Before reading this article, I was under the impression that Uber relied on a third-party service for ETA calculations, but it turns out they don't use the Google Maps API for this purpose. For any scenario they used Google Maps API for ETA?
I don't know the answer to this question. Perhaps somebody working at Uber could answer it.
I think they consider ETA as their core domain, so probably don't want to rely on a third-party.