
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
A technique introduced by Indyk and Woodruff [STOC 2005] has
inspired several recent advances in datastream algorithms.
We show that a number of these results follow easily from
the application of a single probabilistic method
called {\em Precision Sampling}.
Using this method, we obtain simple datastream algorithms that maintain
a randomized sketch of an input vector $x=(x_1,\ldots x_n)$,
which is useful for the following applications:
\begin{itemize}
\item
Estimating the $F_k$moment of $x$, for $k>2$.
\item
Estimating the $\ell_p$norm of $x$, for $p\in[1,2]$, with small update time.
\item
Estimating cascaded norms $\ell_p(\ell_q)$ for all $p,q>0$.
\item$\ell_1$ sampling, where the goal is to produce an element $i$ with
probability (approximately) $x_i/\x\_1$. It extends to similarly
defined $\ell_p$sampling, for $p\in [1,2]$.
\end{itemize}
For all these applications the algorithm is essentially the same:
premultiply the vector $x$ entrywise by a wellchosen random vector, and run a
heavyhitter estimation algorithm on the resulting vector.
Our sketch is a linear function of $x$, thereby allowing general
updates to the vector $x$.
Precision Sampling itself addresses the problem of estimating
a sum $\sum_{i=1}^n a_i$ from weak estimates of each real $a_i\in[0,1]$.
More precisely, the estimator first chooses a desired precision
$u_i\in(0,1]$ for each $i\in[n]$,
and then it receives an estimate of every $a_i$ within additive $u_i$.
Its goal is to provide a good approximation to $\sum a_i$
while keeping a tab on the cost $\sum_i (1/u_i)$.
Here we refine previous work [Andoni, Krauthgamer, and Onak, FOCS 2010]
which shows that as long as $\sum a_i=\Omega(1)$, a good multiplicative
approximation can be achieved using total precision of only $O(n\log n)$.