
We will use an \(\ell _p\) -sampling sketch of [1]} to sample from an importance sampling distribution \(\) , and

Concurrently, we prepare \(2d\)  linear sketches: \(d\)  sketches \((x_{\cdot , j})\)  to evaluate (REF ), one for each \(j \in [d]\) , and \(d\)  sketches \(^{\prime }(\Pr _{}[j])\)  to evaluate \(\Pr _{}[j]\) , one for each \(j \in [d]\) . The non-trivial part is to sketch the sketches. by compressing the \(2d\)  linear sketches into a \(O((nd))\) -bit Count-Min data structure [2]}.

