  Modern mobile applications such as navigation services and ride-sharing
platforms rely heavily on geospatial technologies, most critically predictions
of the time required for a vehicle to traverse a particular route, or the
so-called estimated time of arrival (ETA). There are various methods used in
practice, which differ in terms of the geographic granularity at which the
predictive model is trained -- e.g., segment-based methods predict travel time
at the level of road segments (or a combination of several adjacent road
segments) and then aggregate across the route, whereas route-based methods use
generic information about the trip, such as origin and destination, to predict
travel time. Though various forms of these methods have been developed, there
has been no rigorous theoretical comparison regarding their accuracies, and
empirical studies have, in many cases, drawn opposite conclusions. We provide
the first theoretical analysis of the predictive accuracy of various ETA
prediction methods and argue that maintaining a segment-level architecture in
predicting travel time is often of first-order importance. Our work highlights
that the accuracy of ETA prediction is driven not just by the sophistication of
the model but also by the spatial granularity at which those methods are
applied.
