Streaming-Derandomisierung

12

Stream-Algorithmen erfordern größtenteils eine Randomisierung, um nicht-triviale Aufgaben zu erledigen. Aufgrund der Platzbeschränkung sind PRGs erforderlich, die nur wenig Platz beanspruchen. Ich kenne zwei Methoden, die bisher für die Verwendung in Stream-Algorithmen angeführt wurden:

  • k weise unabhängige PRGs wie die 4-weise unabhängige Familie, die von Alon / Matias / Szegedy für das ursprüngliche Schätzproblem verwendet wurde, und Verallgemeinerungen für 2-stabilitätsbasierte Methoden für (say) SkizzierungF22
  • Nisans PRG, das im Allgemeinen für jede Art von Platzproblemen geeignet ist.

Ich interessiere mich besonders für Methoden, die implementiert werden können. Auf den ersten Blick scheinen beide Ansätze relativ einfach umzusetzen zu sein, aber ich bin gespannt, ob es noch andere gibt.

Suresh Venkat
quelle

Antworten:

10

Einige Streaming-Algorithmen verwenden Expander-Diagramme. Dies ist jedoch eine etwas extreme Form der Ent-Randomisierung (im Prinzip keine zufälligen Bits).

Piotr
quelle
Haben Sie eine Referenz für solche Beispiele?
Suresh Venkat
3
Eine solche Referenz ist: S. Ganguly, "Datenstromalgorithmen über Expandergraphen", ISAAC 2008. Es gibt auch mehrere Algorithmen für die Wiederherstellung mit geringer Dichte (ein eng verwandtes Problem), die Expander-Matrizen verwenden. Die folgende Übersicht gibt einen Überblick: A. Gilbert, P. Indyk, "Sparse Recovery using sparse matrices", Proceedings of IEEE, 2010.
Piotr
6

In vielen geometrischen Algorithmen kann die Zufallsabtastung durch ε-Netze und ε-Approximationen (eines geeigneten Bereichsraums mit endlicher VC-Dimension) ersetzt werden, und diese können durch einen Streaming-Algorithmus effizient aufrechterhalten werden - siehe meine Arbeit "Deterministische Abtastung und Bereichszählung in Geometric" Datenströme "mit Bagchi, Chaudhari und Goodrich von SoCG 2004 und ACM Trans. Alg. 2007 .

David Eppstein
quelle
Ja, das ist ein weiteres gutes Beispiel. Ich habe das vergessen.
Suresh Venkat
6

ϵ

J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "Über die Verteilung symmetrischer Streaming-Berechnungen", SODA 2008.

Piotr
quelle