Derandomization de streaming

12

Os algoritmos de fluxo exigem, na maioria das vezes, randomização para fazer qualquer coisa não trivial e, devido à restrição de espaço pequeno, precisam de PRGs que usam pouco espaço. Conheço dois métodos que foram citados para uso em algoritmos de fluxo até agora:

  • kPRGs -wise independentes, como a família independente de quatro sentidos usada por Alon / Matias / Szegedy para o problema original de estimativa , e generalizações para métodos baseados em 2-estabilidade para (digamos) sketchingF22
  • O PRG de Nisan que funciona em geral para qualquer tipo de problema de espaço pequeno.

Estou particularmente interessado em métodos que podem ser implementados. Diante disso, ambas as abordagens acima parecem relativamente fáceis de implementar, mas estou curioso para saber se existem outras por aí.

Suresh Venkat
fonte

Respostas:

10

Alguns algoritmos de streaming usam gráficos de expansão. Essa é uma forma um tanto extremada de des randomização (sem bits aleatórios, em princípio).

Piotr
fonte
Você tem uma referência para tais exemplos?
Suresh Venkat
3
Uma dessas referências é: S. Ganguly, "Algoritmos de fluxo de dados via gráficos de expansão", ISAAC 2008. Existem também vários algoritmos para recuperação esparsa (um problema intimamente relacionado) que usam matrizes de expansão. Consulte a seguinte pesquisa para obter uma visão geral: A. Gilbert, P. Indyk, "Recuperação esparsa usando matrizes esparsas", Anais do IEEE, 2010.
Piotr
6

Em muitos algoritmos geométricos, a amostragem aleatória pode ser substituída por ε-redes e ε-aproximações (de algum espaço de intervalo apropriado com dimensão finita de VC) e estes podem ser mantidos eficientemente por um algoritmo de fluxo - veja meu artigo "Amostragem determinística e contagem de intervalos em geometria Data Streams "com Bagchi, Chaudhari e Goodrich do SoCG 2004 e ACM Trans. Alg. 2007 .

David Eppstein
fonte
Sim, esse é outro bom exemplo. Eu esqueci disso.
Suresh Venkat
6

Outra ferramenta são -biased espaços, por exemplo, usado, emϵ

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

Piotr
fonte