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
- 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.
ds.algorithms
derandomization
streaming
pseudorandom-generators
Suresh Venkat
źródło
źródło
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 .
źródło
J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, „On Distributioning Symmetric Streaming Computations”, SODA 2008.
źródło