Derandomizacja strumieniowa

12

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 szkicowaniakF22
  • 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.

Suresh Venkat
źródło

Odpowiedzi:

10

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

Piotr
źródło
Czy masz odniesienie do takich przykładów?
Suresh Venkat
3
Jednym z takich odniesień jest: S. Ganguly, „Algorytmy strumienia danych za pomocą grafów ekspanderów”, ISAAC 2008. Istnieje również kilka algorytmów odzyskiwania rzadkiego (ściśle powiązany problem) wykorzystujących macierze ekspanderów. Przegląd zawiera następujące badanie: A. Gilbert, P. Indyk, „Odzyskiwanie rzadkie przy użyciu rzadkich matryc”, Proceedings of IEEE, 2010.
Piotr
6

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 .

David Eppstein
źródło
tak, to kolejny dobry przykład. Zapomniałem o tym.
Suresh Venkat
6

ϵ

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

Piotr
źródło