Query Processing at a Proxy

In addition to forecasting future values, the prediction engine at the proxy also provides a confidence interval for each predicted value. The confidence interval represents a bound on the error in the predicted value and is crucial for query processing at the proxy. Since each query arrives with an error tolerance, the proxy compares the error tolerance of a query with the confidence interval of the predictions, and the current push threshold, $\delta$. If the confidence interval is tighter than the error tolerance, then the predicted values are sufficiently accurate to respond to the query. Otherwise the actual value is fetched from the remote sensor to answer the query. Thus, many queries can be processed locally even if the requested data was never reported by the sensor. As a result, PRESTO can ensure low latencies for such queries without compromising their error tolerance. The processing of queries in this fashion is similar to that proposed in the BBQ data acquisition system [3], although there are significant differences in the techniques.

For a Seasonal ARIMA $(0, 1, 1) \times (0, 1, 1)_S$ model, the confidence interval of $l$ step ahead forecast, $\lambda(l)$ is:

$$\lambda(l) = \pm u_{\varepsilon/2}(1+\sum^{l-1}_{j=1}(1-\theta)^2)^{1/2}\sigma$$ (4)

where $u_{\varepsilon/2}$ is value of the unit Normal distribution at $\varepsilon/2$, $\sigma$ is the variance of $1$ step ahead prediction error.