Потоковые алгоритмы требуют, чтобы рандомизация по большей части выполняла какие-либо нетривиальные задачи, а из-за ограничения малого пространства нужны PRG, которые занимают мало места. Я знаю два метода, которые были процитированы для использования в потоковых алгоритмах:
- зависимые независимые PRG, такие как 4-мудрое независимое семейство, используемое Alon / Matias / Szegedy для исходнойзадачи оценки F 2 , и обобщения для методов, основанных на 2-устойчивости, для (скажем) ℓ 2 зарисовок
- PRG от Nisan, который в целом работает для решения любых задач небольшого пространства.
Меня особенно интересуют методы, которые можно реализовать. На первый взгляд, оба вышеуказанных подхода кажутся относительно простыми для реализации, но мне любопытно, есть ли другие.
ds.algorithms
derandomization
streaming
pseudorandom-generators
Суреш Венкат
источник
источник
Во многих геометрических алгоритмах случайная выборка может быть заменена ε-сетями и ε-аппроксимациями (некоторого подходящего пространства диапазонов с конечной размерностью VC), и они могут эффективно поддерживаться потоковым алгоритмом - см. Мою статью «Детерминированная выборка и подсчет диапазонов в геометрической геометрии». «Потоки данных» с Bagchi, Chaudhari и Goodrich из SoCG 2004 и ACM Trans. Alg. 2007 .
источник
J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "О распределении симметричных потоковых вычислений", SODA 2008.
источник