3 citations · 3 across the 1 of their papers we have counts for
2 papers
cs.DS2009★ 3 cited
A Near-Optimal Algorithm for L1-Difference
Jelani Nelson, David P. Woodruff
We give the first L_1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time. This answers the first open problem in the list of…
cs.DS2008
Revisiting Norm Estimation in Data Streams
Daniel M. Kane, Jelani Nelson, David P. Woodruff
The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i <-- x_i…