65 citations · 262 across the 38 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
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…
cs.DS2008
Sketching and Streaming Entropy via Approximation Theory
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertio…