Clustering on Sliding Windows in Polylogarithmic Space.

摘要: In PODS 2003, Babcock, Datar, Motwani and O'Callaghan gave the first streaming solution for k-median problem on sliding windows using O(frack k tau^4 W^2tau log^2 W) space, with a O(2^O(1/tau)) approximation factor, where W is window size tau in (0,1/2) user-specified parameter. They left as an open question whether it possible to improve this polylogarithmic space. Despite much progress clustering windows, has remained more than decade. In paper, we partially answer main posed by O'Callaghan. We present algorithm yielding exponential improvement space compared previous result given et al. particular, give (alpha,beta)-approximation metric model, alpha beta are constants, under assumption, also made Babcock al., that optimal cost any bounded polynomial size. justify assumption showing when size, no sublinear possible. Our technical contribution simple but elegant extension of smooth functions introduced Braverman Ostrovsky, which allows us apply well-known techniques solving problems model to not smooth, such cost.