1 Search Results for "Gayen, Sutanu"

Document

DOI: 10.4230/LIPIcs.SWAT.2018.22

New Algorithms for Distributed Sliding Windows

Authors: Sutanu Gayen and N. V. Vinodchandran

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract

Computing functions over a distributed stream of data is a significant problem with practical applications. The distributed streaming model is a natural computational model to deal with such scenarios. The goal in this model is to maintain an approximate value of a function of interest over a data stream distributed across several computational nodes. These computational nodes have a two-way communication channel with a coordinator node that maintains an approximation of the function over the entire data stream seen so far. The resources of interest, which need to be minimized, are communication (primary), space, and update time. A practical variant of this model is that of distributed sliding window (dsw), where the computation is limited to the last W items, where W is the window size. Important problems such as sampling and counting have been investigated in this model. However, certain problems including computing frequency moments and metric clustering, that are well studied in other streaming models, have not been considered in the distributed sliding window model. We give the first algorithms for computing the frequency moments and metric clustering problems in the distributed sliding window model. Our algorithms for these problems are a result of a general transfer theorem we establish that transforms any algorithm in the distributed infinite window model to an algorithm in the distributed sliding window model, for a large class of functions. In particular, we show an efficient adaptation of the smooth histogram technique of Braverman and Ostrovsky, to the distributed streaming model. Our construction allows trade-offs between communication and space. If we optimize for communication, we get algorithms that are as communication efficient as their infinite window counter parts (upto polylogarithmic factors).

Cite as

Sutanu Gayen and N. V. Vinodchandran. New Algorithms for Distributed Sliding Windows. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gayen_et_al:LIPIcs.SWAT.2018.22,
  author =	{Gayen, Sutanu and Vinodchandran, N. V.},
  title =	{{New Algorithms for Distributed Sliding Windows}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.22},
  URN =		{urn:nbn:de:0030-drops-88481},
  doi =		{10.4230/LIPIcs.SWAT.2018.22},
  annote =	{Keywords: distributed streaming, distributed functional monitoring, distributed sliding window, frequency moments, k-median clustering, k-center clustering}
}

Refine by Author
1 Gayen, Sutanu
1 Vinodchandran, N. V.

Refine by Classification
1 Theory of computation → Distributed algorithms
1 Theory of computation → Sketching and sampling
1 Theory of computation → Streaming models

Refine by Keyword
1 distributed functional monitoring
1 distributed sliding window
1 distributed streaming
1 frequency moments
1 k-center clustering
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Gayen, Sutanu"

New Algorithms for Distributed Sliding Windows

Abstract

Cite as

Thanks for your feedback!

Could not send message