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

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

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

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

История

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

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

Модель

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

Энтропия

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

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

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

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

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

Литература

• Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments", Journal of Computer and System Sciences, 58 (1): 137—147, doi:10.1006/jcss.1997.1545, ISSN 0022-0000. First published as Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments", Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996), pp. 20—29, doi:10.1145/237814.237823, ISBN 0-89791-785-5.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002), "Models and issues in data stream systems", Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF), pp. 1—16, doi:10.1145/543613.543615.
• Gilbert, A. C.; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), "Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries" (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, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 {{citation}}: Неизвестный параметр |booktitle= игнорируется (справка).
• Karp, R. M.; Papadimitriou, C. H.; Shenker, S. (2003), "A simple algorithm for finding frequent elements in streams and bags", ACM Transactions on Database Systems, 28 (1): 51—55, doi:10.1145/762471.762473.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006), "Data streaming algorithms for estimating entropy of network traffic", Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) (PDF), doi:10.1145/1140277.1140295.
• Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming (PDF).

Ссылки

• Princeton Lecture Notes
• Streaming Algorithms for Geometric Problems, by Piotr Indyk, MIT
• Dagstuhl Workshop on Sublinear Algorithms
• IIT Kanpur Workshop on Data Streaming
• List of open problems in streaming (compiled by Andrew McGregor) from discussion at the IITK Workshop on Algorithms for Data Streams, 2006.
• StreamIt — programming language and compilation infrastructure by MIT CSAIL
• IBM Spade — Stream Processing Application Declarative Engine
• IBM InfoSphere Streams

Учебники

• Data Stream Algorithms and Applications by S. Muthu Muthukrishnan
• Stanford STREAM project survey
• Network Applications of Bloom filters, by Broder and Mitzenmacher
• Xu’s SIGMETRICS 2007 tutorial
• Lecture notes from Data Streams course at Barbados in 2009, by Andrew McGregor and S. Muthu Muthukrishnan

Курсы

• Dartmouth
• MIT
• Rice
• Rutgers
• University at Buffalo