Approximating Large Frequency Moments with Pick-and-Drop Sampling

DOI10.1007/978-3-642-40328-6_4MaRDI QIDQ2851847zbMATH OpenOpenAlexFDO

Authors Vladimir Braverman, Rafail Ostrovsky

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0202

zbMATH Keywords

data streamsfrequency momentssampling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Online algorithms; streaming algorithms (68W27)

Abstract: Given data stream $D=p_1,p_2,\mathrm{...},p_m$ of size $m$ of numbers from $1,\mathrm{...},n$, the frequency of $i$ is defined as $f_i=|j:p_j=i|$. The $k$-th emph{frequency moment} of $D$ is defined as $F_k=su{m}_{i=1}^n{f}_i^k$. We consider the problem of approximating frequency moments in insertion-only streams for $kge3$. For any constant $c$ we show an $O(n^{1-2/k}log(n)lo{g}^{(c)}(n))$ upper bound on the space complexity of the problem. Here $lo{g}^{(c)}(n)$ is the iterative $log$ function. To simplify the presentation, we make the following assumptions: $n$ and $m$ are polynomially far; approximation error $epsilon$ and parameter $k$ are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a emph{pick-and-drop sampling}; it samples a heavy element (i.e., element $i$ with frequency $Omega(F_k)$) with probability $Omega(1/n^{1-2/k})$ and gives approximation $ilde{f}_{i}ge(1-epsilon)f_i$. In addition, the estimations never exceed the real values, that is $ilde{f}_{j}le{f}_j$ for all $j$. As a result, we reduce the space complexity of finding a heavy element to $O(n^{1-2/k}log(n))$ bits. We apply our method of recursive sketches and resolve the problem with $O(n^{1-2/k}log(n)lo{g}^{(c)}(n))$ bits.

Recommendations

• Sampling moments of resamples
• scientific article; zbMATH DE number 1112441
• Adaptive sampling of large deviations
• Some Useful Moment Results in Sampling Problems
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Sampling at a random time with a heavy-tailed distribution
• Sampling from binomial and Poisson distributions: a method with bounded computation times
• Efficient large deviation estimation based on importance sampling
• Approximate counting and sampling via local central limit theorems

Cited in

(6)

• Sampling at a random time with a heavy-tailed distribution
• Generalizing the layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams
• An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Continuous monitoring of _p norms in data streams
• Separations for estimating large frequency moments on data streams

This page was built for publication: Approximating Large Frequency Moments with Pick-and-Drop Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851847)