24 Comments

I could surely use this any time my friends ask “what’s your ETA”... I always grossly underestimate how much time I need ha!

Expand full comment
author

nice

Expand full comment
Dec 4, 2023·edited Dec 4, 2023Liked by Neo Kim

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.

Expand full comment
author

thank you so much for sharing the link, Leo. Love it

Expand full comment

Great article with simple explanations. Very cool to find out how this works under the hood. Appreciate the article, NK

Expand full comment
author

I'm so happy to read feedback from you, Jordan. Thank you so much.

Expand full comment

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!

Expand full comment
author

you're welcome, appreciate the feedback a lot.

Expand full comment
Dec 4, 2023Liked by Neo Kim

I am glad that I just witnessed the usage of graphs in real world application,

Thanks for taking time explaining things.

Expand full comment
author

you're welcome

Expand full comment

I thought this is coming from Google Maps, they provide the ETA.

Thanks for sharing.

Expand full comment
author

happy to, thanks for the comment.

Expand full comment

Very useful article! I like the diagrams, they make the heavy technical aspects easy to understand. Thanks for sharing this, NK!

Expand full comment
author

thanks

Expand full comment

I've just noticed that I read and commented on this before :) seems like I love it every time I read it 😂

Expand full comment

Great article!!

Expand full comment
author

thanks

Expand full comment

Fantastic article. It's amazing to see such valuable information so freely shared. Really appreciate the service you provided.

Expand full comment
Aug 14·edited Aug 14

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?

Expand full comment

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

Expand full comment

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.

Expand full comment
author

My guess would be because it's their core domain (DDD) and they want to stay competitive.

Expand full comment

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?

Expand full comment
author

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.

Expand full comment
Error