Приближенный поиск частых элементов. Оценка моментов
Алгоритмы обработки потоковых данных


Что: Лекция
Когда: Воскресенье, 09 ноября 2014, 11:15–12:50
Где: ПОМИ РАН
Слайды: streaming_algorithms_lecture_091114.pdf

Описание

Понятие эскиза. Оценка частот элементов через эскизы.

  • Алгоритм Чарикара-Чена-Фараха-Колтона. Для любого \(x\) выдает ответ в отрезке \([f_x - \varepsilon \cdot ||f||_2, f_x + \varepsilon \cdot ||f||_2]\) c вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-2} \log \delta^{-1} (\log n + \log m))\).
  • Алгоритм Кормода-Муфукришнана. Для любого \(x\) выдает ответ в отрезке \([f_x, f_x + \varepsilon \cdot ||f||_1]\) с вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-1} \log \delta^{-1} (\log n + \log m))\).
  • Алгоритм Алона-Матиаса-Сзегеди. Оценка момента \(F_2\) через эскиз. Выдает ответ с точность \(\pm \varepsilon ||f||_2\) c вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-2}\log \delta^{-1} (\log n + \log m))\)
  • Алгоритм Вудраффа. Линейная регрессия при небольшом числе предикторов \(d\) на \(n\) наблюдениях. Выдает вектор коэффициентов \(\hat{x}\) такой, что \(||A\hat{x} - b||_2 \leq (1 + \varepsilon) \min_x ||Ax - b||_2\) с вероятностью \(1 - \delta\). Память: \(O(d^2 \varepsilon^{-1} \log \delta^{-1} \log (nd)\).
  • Алгоритм Алона-Матиаса-Сзегеди. Оценка произвольного момента \(F_k\) при константе \(k \geq 1\). Память \(O(\varepsilon^{-2} \log \delta^{-1} n^{1 - \frac{1}{k}} (\log m + \log n))\).

Статья Дэвида Вудраффа (2012)
Статья Алона, Матиаса, Сзегеди (1999)
остальное можно посмотреть в конспекте Дармутского колледжа.

Материалы