1 Search Results for "Levin, Keith"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2015.350

Clustering on Sliding Windows in Polylogarithmic Space

Authors: Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract

In PODS 2003, Babcock, Datar, Motwani and O'Callaghan gave the first streaming solution for the 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 the window size and tau in (0,1/2) is a user-specified 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 k-median clustering in the sliding window model, where alpha and beta are constants, under the assumption, also made by Babcock et al., that the optimal k-median 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 well-known techniques for solving problems in the sliding window model to functions that are not smooth, such as the k-median cost.

Cite as

Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering on Sliding Windows in Polylogarithmic Space. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 350-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.FSTTCS.2015.350,
  author =	{Braverman, Vladimir and Lang, Harry and Levin, Keith and Monemizadeh, Morteza},
  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 =	{350--364},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.350},
  URN =		{urn:nbn:de:0030-drops-56549},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.350},
  annote =	{Keywords: Streaming, Clustering, Sliding windows}
}

Refine by Author
1 Braverman, Vladimir
1 Lang, Harry
1 Levin, Keith
1 Monemizadeh, Morteza

Refine by Classification

Refine by Keyword
1 Clustering
1 Sliding windows
1 Streaming

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Levin, Keith"

Clustering on Sliding Windows in Polylogarithmic Space

Abstract

Cite as

Thanks for your feedback!

Could not send message