arXiv Analytics

Sign in

arXiv:1504.05553 [cs.DS]AbstractReferencesReviewsResources

A Unified Approach for Clustering Problems on Sliding Windows

Vladimir Braverman, Harry Lang, Keith Levin, Morteza Monemizadeh

Published 2015-04-21Version 1

We explore clustering problems in the streaming sliding window model in both general metric spaces and Euclidean space. We present the first polylogarithmic space $O(1)$-approximation to the metric $k$-median and metric $k$-means problems in the sliding window model, answering the main open problem posed by Babcock, Datar, Motwani and O'Callaghan, which has remained unanswered for over a decade. Our algorithm uses $O(k^3 \log^6 n)$ space and $\operatorname{poly}(k, \log n)$ update time. This is an exponential improvement on the space required by the technique due to Babcock, et al. We introduce a data structure that extends smooth histograms as introduced by Braverman and Ostrovsky to operate on a broader class of functions. In particular, we show that using only polylogarithmic space we can maintain a summary of the current window from which we can construct an $O(1)$-approximate clustering solution. Merge-and-reduce is a generic method in computational geometry for adapting offline algorithms to the insertion-only streaming model. Several well-known coreset constructions are maintainable in the insertion-only streaming model using this method, including well-known coreset techniques for the $k$-median, $k$-means in both low-and high-dimensional Euclidean spaces. Previous work has adapted these techniques to the insertion-deletion model, but translating them to the sliding window model has remained a challenge. We give the first algorithm that, given an insertion-only streaming coreset construction of space $s$, maintains a $(1\pm\epsilon)$-approximate coreset in the sliding window model using $O(s^2\epsilon^{-2}\log n)$ space. For clustering problems, our results constitute the first significant step towards resolving problem number 20 from the List of Open Problems in Sublinear Algorithms.

Related articles: Most relevant | Search more
arXiv:1608.01700 [cs.DS] (Published 2016-08-04)
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
arXiv:1611.00129 [cs.DS] (Published 2016-11-01)
Submodular Maximization over Sliding Windows
arXiv:1805.03765 [cs.DS] (Published 2018-05-10)
Numerical Linear Algebra in the Sliding Window Model