12
$\begingroup$

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

Some streaming algorithms use expander graphs. This is a somewhat extreme form of de-randomization though (no random bits, in principle).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have a reference for such examples ? $\endgroup$
    – Suresh Venkat
    Commented Aug 26, 2010 at 1:30
  • 3
    $\begingroup$ One such reference is: S. Ganguly, "Data stream algorithms via expander graphs", ISAAC 2008. There are also several algorithms for sparse recovery (a closely related problem) that use expander matrices. See the following survey for an overview: A. Gilbert, P. Indyk, "Sparse recovery using sparse matrices", Proceedings of IEEE, 2010. $\endgroup$
    – Piotr
    Commented Aug 26, 2010 at 2:42
6
$\begingroup$

In many geometric algorithms random sampling can be replaced by ε-nets and ε-approximations (of some appropriate range space with finite VC dimension) and these can be maintained efficiently by a streaming algorithm — see my paper "Deterministic Sampling and Range Counting in Geometric Data Streams" with Bagchi, Chaudhari, and Goodrich from SoCG 2004 and ACM Trans. Alg. 2007.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes, that's another good example. I forgot about that. $\endgroup$
    – Suresh Venkat
    Commented Aug 26, 2010 at 4:12
6
$\begingroup$

Another tool are $\epsilon$-biased spaces, used e.g., in

J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "On Distributing Symmetric Streaming Computations", SODA 2008.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.