  Kernel regression is an essential and ubiquitous tool for non-parametric data
analysis, particularly popular among time series and spatial data. However, the
central operation which is performed many times, evaluating a kernel on the
data set, takes linear time. This is impractical for modern large data sets.
  In this paper we describe coresets for kernel regression: compressed data
sets which can be used as proxy for the original data and have provably bounded
worst case error. The size of the coresets are independent of the raw number of
data points, rather they only depend on the error guarantee, and in some cases
the size of domain and amount of smoothing. We evaluate our methods on very
large time series and spatial data, and demonstrate that they incur negligible
error, can be constructed extremely efficiently, and allow for great
computational gains.
