  Clustering is an important technique for identifying structural information
in large-scale data analysis, where the underlying dataset may be too large to
store. In many applications, recent data can provide more accurate information
and thus older data past a certain time is expired. The sliding window model
captures these desired properties and thus there has been substantial interest
in clustering in the sliding window model.
  In this paper, we give the first algorithm that achieves near-optimal
$(1+\varepsilon)$-approximation to $(k,z)$-clustering in the sliding window
model, where $z$ is the exponent of the distance function in the cost. Our
algorithm uses
$\frac{k}{\min(\varepsilon^4,\varepsilon^{2+z})}\,\text{polylog}\frac{n\Delta}{\varepsilon}$
words of space when the points are from $[\Delta]^d$, thus significantly
improving on works by Braverman et. al. (SODA 2016), Borassi et. al. (NeurIPS
2021), and Epasto et. al. (SODA 2022).
  Along the way, we develop a data structure for clustering called an online
coreset, which outputs a coreset not only for the end of a stream, but also for
all prefixes of the stream. Our online coreset samples
$\frac{k}{\min(\varepsilon^4,\varepsilon^{2+z})}\,\text{polylog}\frac{n\Delta}{\varepsilon}$
points from the stream. We then show that any online coreset requires
$\Omega\left(\frac{k}{\varepsilon^2}\log n\right)$ samples, which shows a
separation from the problem of constructing an offline coreset, i.e.,
constructing online coresets is strictly harder. Our results also extend to
general metrics on $[\Delta]^d$ and are near-optimal in light of a
$\Omega\left(\frac{k}{\varepsilon^{2+z}}\right)$ lower bound for the size of an
offline coreset.
