License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.591
URN: urn:nbn:de:0030-drops-53250
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5325/
Go to the corresponding LIPIcs Volume Portal

Braverman, Vladimir ; Chestnut, Stephen R.

Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums

pdf-format:
35.pdf (0.5 MB)

Abstract

Given a stream with frequency vector f in n dimensions, we characterize the space necessary for approximating the frequency negative moments Fp, where p<0, in terms of n, the accuracy, and the L_1 length of the vector f. To accomplish this, we actually prove a much more general result. Given any nonnegative and nonincreasing function g, we characterize the space necessary for any streaming algorithm that outputs a (1 +/- eps)-approximation to the sum of the coordinates of the vector f transformed by g. The storage required is expressed in the form of the solution to a relatively simple nonlinear optimization problem, and the algorithm is universal for (1 +/- eps)-approximations to any such sum where the applied function is nonnegative, nonincreasing, and has the same or smaller space complexity as g. This partially answers an open question of Nelson (IITK Workshop Kanpur, 2009).

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2015:5325,
  author =	{Vladimir Braverman and Stephen R. Chestnut},
  title =	{{Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{591--605},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5325},
  URN =		{urn:nbn:de:0030-drops-53250},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.591},
  annote =	{Keywords: data streams, frequency moments, negative moments}
}

Keywords: data streams, frequency moments, negative moments
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI