Поточный алгоритм

22.11.2021

Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.

Поточные алгоритмы решают задачи, в которых данные приходят последовательно и в большом объёме. Примером может служить анализ сетевого трафика на стороне маршрутизатора. Подобные задачи накладывают на поточные алгоритмы естественные ограничения по доступной памяти (намного меньше, чем размер входных данных) и времени обработки каждого элемента последовательности. Зачастую, обработка данных возможна только в один проход.

Строгие ограничения на время и память часто делают невозможным точное решение исследуемой задачи. Обычно поточные алгоритмы являются вероятностными и дают приближение на точный ответ.

История

Хотя подобные алгоритмы рассматривались в работах первой половины 1980-х годов, понятие поточного алгоритма было впервые формализовано в работе Алона, Матиаса (англ. Yossi Matias) и Сегеди (англ. Mario Szegedy) в 1996 году. В 2005 году авторы были удостоены премии Гёделя за вклад в теорию алгоритмов (англ. for their foundational contribution to streaming algorithms).

В 2005 году было введено понятие полупоточного алгоритма (англ. semi-streaming algorithm) как алгоритмов обрабатывающих входящий поток за постоянное или логарифмическое[уточнить] число проходов.

Модель

В модели потоковых данных считается, что часть или весь набор входных данных, над которыми необходимо осуществлять обработку, недоступен для произвольного доступа: входные данные поступают последовательно и непрерывно в одном или нескольких потоках. Потоки данных могут быть представлены упорядоченной последовательностью точек («обновлений»), доступ к которым может осуществляться по порядку и только один или ограниченное число раз.

Во многих публикациях по поточной обработке рассматривают задачу компьютерной статистики над таким распределением данных, которое слишком велико для эффективного хранения[уточнить]. Для данного класса задач предполагается, что вектор a = ( a 1 , … , a n ) {displaystyle mathbf {a} =(a_{1},dots ,a_{n})} (инициализированный нулевой последовательностью 0 {displaystyle mathbf {0} } ) имеет некоторое количество «обновлений» в потоке. Цель таких алгоритмов — вычислить функции от a {displaystyle mathbf {a} } , используя существенно меньше места, чем это потребовало бы полное представление вектора a {displaystyle mathbf {a} } . Существуют две общих модели обновления таких данных: «касса» (англ. cash register) и «турникет» (англ. turnstile).

В «кассовой» модели каждое «обновление» представляется в форме ⟨ i , c ⟩ {displaystyle langle i,c angle } и модифицируют вектор таким образом, что a i {displaystyle a_{i}} увеличивается на некоторое положительное целое число c {displaystyle c} . Особым случаем является случай c = 1 {displaystyle c=1} (разрешена вставка только одной единицы).

В «турникетной» модели каждое «обновление» представляется в форме ⟨ i , c ⟩ {displaystyle langle i,c angle } и модифицируют вектор таким образом, что a i {displaystyle a_{i}} увеличивается на некоторое положительное или отрицательное целое число c {displaystyle c} . В строгой модели, в любой момент времени a i {displaystyle a_{i}} не может быть отрицательным.

В ряде источников дополнительно рассматривают «слайд-оконную» модель. В данной модели интересующая функция вычисляется над окном ограниченной размерности из потоковых данных, элементы с конца окна не принимаются во внимание, пока новые данные из потока не займут их место.

В данных алгоритмах рассматриваются не только вопросы, связанные с частотными характеристиками данных, но и ряд других. Много задач на графах решаются в условиях того, что матрица смежности графа потоково подгружается в некотором заранее неизвестном порядке. Иногда, напротив, необходимо решить задачу оценки порядка данных, например, посчитать число инверсных значений в потоке и найти наибольшую возрастающую последовательность.

Сравнение алгоритмов

Основные характеристики поточных алгоритмов:

  • число допустимых проходов алгоритма над данными;
  • доступная память;
  • время обработки[уточнить].

Данные алгоритмы имеют много общего с онлайн-алгоритмами, так как алгоритм должен принимать решение до того, как все данные станут доступны, но есть и различия. В частности, поточные алгоритмы имеют возможность отложить принятие решение до момента прихода группы точек последовательности данных, в то время как онлайн-алгоритмы должны принимать решения по мере прихода каждой новой точки последовательности.

Если алгоритм является приближённым, то точность ответа является ещё одним показателям. Точность алгоритма часто представляется как величина ( ϵ , δ ) {displaystyle (epsilon ,delta )} , означающая то, что алгоритм достигнет ошибки меньше ϵ {displaystyle epsilon } с вероятностью 1 − δ {displaystyle 1-delta } .

Применение

Поточные алгоритмы имеют большое значение в задачах мониторинга и управления компьютерными сетями, например, их средствами возможно оперативное предотвращение переполнений (отслеживание гигантских потоков, оценка числа и ожидаемой длительности переполнений). Также поточные алгоритмы могут применяться в базах данных, например, для оценки размера после операции соединения таблиц.

Примеры задач, решаемых поточными алгоритмами

Проблемы с частотным распределением

k {displaystyle k} -ый момент частоты в векторе a {displaystyle mathbf {a} } определяется как F k ( a ) = ∑ i = 1 n a i k {displaystyle F_{k}(mathbf {a} )=sum _{i=1}^{n}a_{i}^{k}} .

Первый момент F 1 {displaystyle F_{1}} — это простая сумма частот (то есть, общее число). Второй момент F 2 {displaystyle F_{2}} полезен для вычисления статистических параметров данных, например Коэффициент Джини. F ∞ {displaystyle F_{infty }} определяется как частота наиболее часто встречающегося элемента.

Также изучены вопросы оценки моментов частот.

Поиск тяжёлых элементов

Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы:

  • алгоритм большинства голосов Бойера — Мура
  • алгоритм Карпа — Пападимитриу — Шенкера,
  • Count-Min sketch,
  • алгоритм вязкой выборки (англ. sticky sampling),
  • Lossy Count Algorithm,
  • «выборка и удержание» (англ. sample and hold),
  • многоуровневый фильтр Блума,
  • подсчёт «набросков» (англ. Count-sketch),
  • выборка на основе «набросков» англ. Sketch-guided sampling,

Отслеживание тренда

Отслеживанием тренда в потоке данных обычно производится в следующем порядке: наиболее частые элементы и их частоты определяются на основе одного из вышеперечисленных алгоритмов[уточнить]<--алгоритмов поиска тяжёлых элементов? а если эту секцию перенсут ниже?-->, а затем наибольшее увеличение относительно предыдущего момента времени отмечается как тренд. Для этого используется экспоненциальная скользящая средняя и различная нормировка. Он используется O(ε² + log d) места и O(1) для худщего случая обновления при универсальной хеш-функции из семейства r-умных независимых хеш-функций с r = Ω(log(1/ε)/ log log(1/ε))[уточнить].

Энтропия

Эмпирическая оценка энтропии над набором частот a {displaystyle mathbf {a} } определяется как F k ( a ) = ∑ i = 1 n a i m log ⁡ a i m {displaystyle F_{k}(mathbf {a} )=sum _{i=1}^{n}{frac {a_{i}}{m}}log {frac {a_{i}}{m}}} , где m = ∑ i = 1 n a i {displaystyle m=sum _{i=1}^{n}a_{i}} .

Машинное обучение

Основная задача онлайнового обучения машин — обучить модель (например, классификатор) за один проход по обучающей выборке; для её решения обычно используются методы предсказательного хеширования) и стохастический нисходящий градиент).

Подсчёт числа уникальных элементов

Подсчёт числа уникальных элементов в потоке данных (момент F 0 {displaystyle F_{0}} ) является ещё одной[уточнить] хорошо изученной проблемой. Первый алгоритм был предложен Флажоле и Мартеном. В 2010 году был найден асимптотически оптимальный алгоритм.