Clustering Problems on Sliding Windows
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10316200" target="_blank" >RIV/00216208:11320/16:10316200 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/1.9781611974331.ch95" target="_blank" >http://dx.doi.org/10.1137/1.9781611974331.ch95</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611974331.ch95" target="_blank" >10.1137/1.9781611974331.ch95</a>
Alternative languages
Result language
angličtina
Original language name
Clustering Problems on Sliding Windows
Original language description
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 [5], which has remained unanswered for over a decade. Our algorithm uses O(k3 log6 W) space and poly(k, log W) update time, where W is the window size. 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 [11] 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-433-1
ISSN
—
e-ISSN
—
Number of pages
17
Pages from-to
1374-1390
Publisher name
SIAM
Place of publication
Neuveden
Event location
Arlington, Virginia, USA
Event date
Jan 10, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—