DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2016.6

A Framework for Estimating Stream Expression Cardinalities

Authors: Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract

Given m distributed data streams A_1,..., A_m, we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over A_1,..., A_m. We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability.

Cite as

Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler. A Framework for Estimating Stream Expression Cardinalities. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dasgupta_et_al:LIPIcs.ICDT.2016.6,
  author =	{Dasgupta, Anirban and Lang, Kevin J. and Rhodes, Lee and Thaler, Justin},
  title =	{{A Framework for Estimating Stream Expression Cardinalities}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.6},
  URN =		{urn:nbn:de:0030-drops-57754},
  doi =		{10.4230/LIPIcs.ICDT.2016.6},
  annote =	{Keywords: sketching, data stream algorithms, mergeability, distinct elements, set operations}
}

Search Results

Documents authored by Rhodes, Lee

A Framework for Estimating Stream Expression Cardinalities

Abstract

Cite as

Thanks for your feedback!

Could not send message