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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you have a reference for such examples ? $\endgroup$ – Suresh Venkat Aug 26 '10 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 Aug 26 '10 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.

$\endgroup$
  • $\begingroup$ yes, that's another good example. I forgot about that. $\endgroup$ – Suresh Venkat Aug 26 '10 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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