How might Google go about estimating and updating traffic speeds?

Question

This is, I guess, a specific example of a wider class of problem, one to which there must be a well-established solution, but which I, as a relative layman when it comes to statistics have thus far been unable to find.

I understand that Google can track the speed of cars on road segments, and therefore has a set of speed observations which are taken at irregular intervals. I initially, therefore, have two questions:

1. How can one take those irregular observations and come up with an estimate of current traffic speed (or indeed traffic speed at any point in time during the set of observations) given that traffic speed will vary over time, and
2. How can the uncertainty in that estimate be calculated given a knowledge of when the observations were taken?

For my second question, I would assume that the further in the past one's last observation was taken, the greater the uncertainty in the estimate, but how can this be formalised mathematically?

Is this a Bayesian problem?

Answer 1

There are many possible ways to approach this problem, depending on exactly what data you have and what your goals are. The most standard type of solution would be from the family of Kalman Filters. This is a Bayesian model, which updates our estimate (and uncertainty) for a quantity based on noisy measurements.

There are basically three components to the model:

1. Modeling the internal dynamics of the state. In the traffic case, this might say that traffic speeds change slowly over time, but can sometimes decrease very rapidly (e.g. due to an accident).
2. Modeling how external driving forces (which we know about) will affect the state. This could be time of day in the traffic case.
3. Modeling how noisy measurements are generated from the state. Perhaps traffic data comes from large trucks, so we say that measurements will be slight underestimates of the true speed except when the speeds are very low, and we have quantified how noisy the estimates are.

You can then plug in your assumptions and get the optimal estimator. Note that the vanilla Kalman filter assumes that all these models are linear, but more complex versions can allow for arbitrarily complicated models.

Answer 2

I would start with the dumbest thing like this $$\hat v(t,x)=(1-\phi) v_{limit}+\phi v(\tau,z)$$ where $$\phi=e^{-\kappa(z-x)^2-\theta(t-\tau)}$$ Here, $\hat v(t,x)$ current estimate of the speed at the coordinate $x$, $v(\tau,z)$ - last speed reading from the nearest road segment with coordinate $z$, $v_{limit}$ speed limit, $\kappa,\theta$ coefficients.

You can make it more complicated by adding multiple speed readings instead of the latest and nearest. The $\phi$ makes sure that in the absence of recent and near readings, the speed limit is your best estimate of the speed. It accounts for proximity both in time and space.

I should totally patent this.