Derandomizacja strumieniowa

Algorytmy strumieniowe wymagają w większości przypadków randomizacji, aby zrobić coś nietrywialnego, a ze względu na ograniczenie małej przestrzeni potrzebują programów PRG, które zajmują mało miejsca. Znam dwie metody, które do tej pory były cytowane w algorytmach strumieniowych:

• -niezależne PRG-y, takie jak 4-mądra, niezależna rodzina używana przez Alona / Matiasa / Szegedy'ego w pierwotnymproblemie estymacji F 2 , i uogólnienia dla metod opartych na 2 stabilności dla (powiedzmy) sketch 2 szkicowania$k$$F_2$$\ell_2$
• PRG Nisana, który działa ogólnie na każdy problem związany z małą przestrzenią.

Szczególnie interesują mnie metody, które można wdrożyć. Na pierwszy rzut oka oba powyższe podejścia wydają się stosunkowo łatwe do wdrożenia, ale jestem ciekawy, czy są jeszcze jakieś inne.

Niektóre algorytmy przesyłania strumieniowego wykorzystują wykresy ekspanderów. Jest to jednak nieco ekstremalna forma de-randomizacji (w zasadzie żadnych losowych bitów).

W wielu algorytmach geometrycznych losowe próbkowanie można zastąpić ε-sieciami i aproksymacjami ε (pewnej odpowiedniej przestrzeni zakresu ze skończonym wymiarem VC) i można je skutecznie utrzymywać za pomocą algorytmu przesyłania strumieniowego - patrz mój artykuł „Próbkowanie deterministyczne i zliczanie zakresu w geometryce Strumienie danych ”z udziałem Bagchi, Chaudhari i Goodrich z SoCG 2004 i ACM Trans. Alg. 2007 .

$\epsilon$

J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, „On Distributioning Symmetric Streaming Computations”, SODA 2008.