Let us first present an approach to \(L_p\)  sampling from data streams for \(p \in (0, 2]\)  [1]}, [2]}. Let \(\mathcal {S}\)  be a data stream of pairs \(i, w_i\)  where \(i\)  is the item and \(w_i \in \mathbb {R}\)  the weight update for item \(i\) , for \(i \in [n]\) . The objective is to return each item \(i\)  with probability roughly \(|\mathbf {f}[i]|^p/\Vert \mathbf {f}\Vert ^p_p\) , where \(\mathbf {f}[i] = \sum _{(i, w_i) \in \mathcal {S}}w_i\) . (Note that items are supposed to occur multiple times in the stream.) The problem is trivial if we can afford to store the entire frequency vector \(\mathbf {f}\)  but for larger \(n\)  this can be prohibitively expensive. The idea is to reweight each item by scaling it by a random number \(1/r_i^{1/p}\)  for a uniformly sampled \(r_i \in (0, 1]\) . Let \(z_i = \mathbf {f}[i]/r_i^{1/p}\)  be the reweighted weight of item \(i\) . The crucial observation is that
\(\Pr [z_i \ge \Vert \mathbf {f}\Vert _p] = \Pr [r_i \le {\mathbf {f}[i]^p}/{\Vert \mathbf {f}\Vert _p^p}] = \frac{\mathbf {f}[i]^p}{\Vert \mathbf {f}\Vert _p^p}\) 
