# What predictive models allow me to make new predictions on a series in constant time, without needing to recompute previous ones?

I'm a software developer working on a system that stores thousands of independent metrics, each with several tens of thousands of timeseries data points. We'd like to make predictions about where the metrics are headed.

For each metric, we want to do two things:

1. Make a prediction for as many of the observations as we can, as if we had seen only the observations up to that point.

That is, if we have a sequence of timeseries observations $O = [(t_0, v_0), (t_1, v_1), (t_2, v_2), \cdots]$, then we want to produce a new prediction series $P = [(t_0, p_0), (t_1, p_1), (t_2, p_2), \cdots]$, with the same time indices. For a given time $t$, the series can only use observations that came before $t$ to make the prediction at $t$.

The prediction is permitted to require some minimum number of observations before making any predictions -- that is, the prediction series can start at an index other than $t_0$ (but $P$ can only include indices present in $O$).

The time indices $t_0, t_1, \cdots$ are not guaranteed to be equally spaced.

1. In the future, when new observations for that metric come in, we don't want to have to recompute all the previous predictions to make one more prediction.

That is, we might first receive 500 observations, make ~500 predictions, receive 3 more observations, make 3 more predictions, and so on. But the cost of making those additional 3 predictions should not include recomputing the first 500 -- the cost to compute one additional prediction should, ideally, be constant (or hopefully bounded).

Finally, because I'll be building this myself, predictive accuracy is less important than implementation complexity. I'd be writing this in Python or Ruby, which have passable statistical libraries, but they don't compare to R or MATLAB and one can't generally assume that things are done for you.

Are there well-known statistical predictive models with reference implementations that satisfy these conditions?