Thus, we need to detect a reweighted item whose weight exceeds \(\Vert \mathbf {f}\Vert _p\) . The solution in [1]}, [2]} is to show that with constant probability there exists a unique item whose weight exceeds \(\Vert \mathbf {f}\Vert _p\)  and the total weight of all other items is bounded. Thus, if we know the value of \(\Vert \mathbf {f}\Vert _p\) , a space-efficient solution is to keep a sketch data structure form which we can detect the heavy hitter that will be the sampled item. Estimating the norm of a frequency vector is a fundamental problem with known solutions [3]}, [4]}, therefore the approach yields a space-efficient solution to \(L_p\)  sampling from data streams.
