Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been cited for use in stream algorithms thus far:
- $k$-wise independent PRGs like the 4-wise independent family used by Alon/Matias/Szegedy for the original $F_2$ estimation problem, and generalizations for 2-stability-based methods for (say) $\ell_2$ sketching
- Nisan's PRG that works in general for any kind of small-space problem.
I'm particular interested in methods that can be implemented. On the face of it, both of the above approaches seem relatively easy to implement, but I'm curious if there are any others out there.