How Uber Computes ETA at Half a Million Requests per Second
ฝัง
- เผยแพร่เมื่อ 6 ก.พ. 2025
- Uber ETA:
• They represent the physical map as a graph
• They compute ETA by finding the shortest path in a directed weighted graph
• They don't use Dijkstra’s algorithm because it won't scale with O(n logn) time complexity
• They partition the graph and then precompute the best path within every partition
• They reduce the time complexity from O(n^2) to O(n) by partitioning the graph
• They populate the edge weights of the graph with traffic information
• They do map matching to find accurate ETA
• They use the Kalman filter and Viterbi algorithm for map matching
----------------------------------------------------------------
SUBSCRIBE OR I STOP WRITING
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
→ @systemdesignone
I think some fundamental info is missing.
First you talk about shortest path then you started talking about the best path. This could be different from the shortest path depending on the traffic. How it could be precomputed efficiently if it continuously changes?
Another missing point is how actually they've moved from On² to On.
Whithout these info this nice channel is not much useful for system design interviews or actual design improvements.
I hope you'll have the time to dig deeper in the next ones.
Thanks!
I see, thanks for the feedback.
👍👍👍
thank you for the support.
@@systemdesignone Thank you for opening TH-cam channel.