Clustering Problems on Sliding Windows

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Clustering Problems on Sliding Windows

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Clustering Problems on Sliding Windows

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-433-1

ISSN

—

e-ISSN

—

Počet stran výsledku

17

Strana od-do

1374-1390

Název nakladatele

SIAM

Místo vydání

Neuveden

Místo konání akce

Arlington, Virginia, USA

Datum konání akce

10. 1. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—