Braverman, Vladimir ;
Lang, Harry ;
Levin, Keith ;
Monemizadeh, Morteza
Clustering on Sliding Windows in Polylogarithmic Space
Abstract
In PODS 2003, Babcock, Datar, Motwani and O'Callaghan gave the first streaming solution for the kmedian 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 the window size and tau in (0,1/2) is a userspecified parameter. They left as an open question whether it is possible to improve this to polylogarithmic space. Despite much progress on clustering and sliding windows, this question has remained open for more than a decade.
In this paper, we partially answer the main open question posed by Babcock, Datar, Motwani and O'Callaghan. We present an algorithm yielding an exponential improvement in space compared to the previous result given in Babcock, et al. In particular, we give the first polylogarithmic space (alpha,beta)approximation for metric kmedian clustering in the sliding window model, where alpha and beta are constants, under the assumption, also made by Babcock et al., that the optimal kmedian cost on any given window is bounded by a polynomial in the window size. We justify this assumption by showing that when the cost is exponential in the window size, no sublinear space approximation is possible. Our main technical contribution is a simple but elegant extension of smooth functions as introduced by Braverman and Ostrovsky, which allows us to apply wellknown techniques for solving problems in the sliding window model
to functions that are not smooth, such as the kmedian cost.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs:2015:5654,
author = {Vladimir Braverman and Harry Lang and Keith Levin and Morteza Monemizadeh},
title = {{Clustering on Sliding Windows in Polylogarithmic Space}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {350364},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5654},
URN = {urn:nbn:de:0030drops56549},
doi = {10.4230/LIPIcs.FSTTCS.2015.350},
annote = {Keywords: Streaming, Clustering, Sliding windows}
}
14.12.2015
Keywords: 

Streaming, Clustering, Sliding windows 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

14.12.2015 