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

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

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

История

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

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

Модель

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

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

В «кассовой» модели каждое «обновление» представляется в форме ${\displaystyle \langle i,c\rangle }$ и модифицируют вектор таким образом, что ${\displaystyle a_{i}}$ увеличивается на некоторое положительное целое число ${\displaystyle c}$ . Зачастую ${\displaystyle c=1}$ , что обозначает тривиальную инкрементную модель.

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

Энтропия

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

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

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

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

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

Примечания

Литература

• ; Matias, Yossi; (1999), "The space complexity of approximating the frequency moments", , 58 (1): 137—147, doi : , ISSN . First published as Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments", , pp. 20—29, doi : , ISBN 0-89791-785-5 .
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev ; (2002), "Models and issues in data stream systems", (PDF) , pp. 1—16, doi : .
• Gilbert, A. C. ; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), (PDF) , Proceedings of the International Conference on Very Large Data Bases : 79—88 .
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), An optimal algorithm for the distinct elements problem , PODS '10, New York, NY, USA: ACM, pp. 41—52, CiteSeerX , doi : , ISBN 978-1-4503-0033-9 {{ citation }} : Неизвестный параметр |booktitle= игнорируется ( справка ) .
• ; ; (2003), "A simple algorithm for finding frequent elements in streams and bags", ACM Transactions on Database Systems , 28 (1): 51—55, doi : .
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006), "Data streaming algorithms for estimating entropy of network traffic", (PDF) , doi : (недоступная ссылка) .
• Xu, Jun (Jim) (2007), (PDF) .

Ссылки

• , by , MIT
• (compiled by ) from discussion at the IITK Workshop on Algorithms for Data Streams, 2006.
• (недоступная ссылка)

Учебники

• by
• , by Broder and Mitzenmacher
• , by and

Курсы