How Uber Computes ETA: A Simplified Breakdown

Ever wondered how Uber calculates Estimated Time of Arrival (ETA) so efficiently? Here’s a quick professional rundown of their approach:

  1. Mapping as a Graph:
    The physical map is represented as a directed, weighted graph where nodes represent intersections and edges represent road segments.

  2. Efficient Pathfinding:
    To compute ETA, Uber determines the shortest path on the graph. However, traditional algorithms like Dijkstra's are not scalable due to their O(n * log n) time complexity.

  3. Graph Partitioning:
    The map is partitioned into smaller subgraphs, and the optimal paths within each partition are precomputed, significantly improving efficiency.

  4. Time Complexity Reduction:
    By partitioning the graph, Uber reduces the computational complexity from O(n²) to O(n), enabling faster real-time processing.

  5. Dynamic Edge Weights:
    Real-time traffic data is used to dynamically update the edge weights, ensuring ETA calculations reflect current road conditions.

  6. Map Matching for Accuracy:
    Advanced techniques like the Kalman filter (for smoothing GPS data) and the Viterbi algorithm (for path alignment) are used to map the vehicle's position accurately to the road network.

Comparison in Map Matching:

Feature Kalman Filter Viterbi Algorithm
Purpose Smooths noisy GPS data for accurate position estimation. Finds the most probable path on the map given noisy GPS data.
Input A sequence of GPS points, motion model. GPS points, road network, transition probabilities.
Output A smoothed position estimate. A sequence of road segments (most probable path).
Best Use Case When real-time position estimation is required. When aligning a path to a road network is critical.
Time Dependency Processes data point-by-point in real-time. Processes data over a window or the entire journey.

This blend of graph theory, real-time data, and algorithmic optimization allows Uber to deliver reliable ETAs at scale.

Back to blog