Потоковий алгоритм

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

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

Суворі обмеження на час і пам'ять часто унеможливлюють точне розв'язання досліджуваної задачі. Зазвичай потокові алгоритми є ймовірнісними та дають наближення до точної відповіді.

Історія

Хоча подібні алгоритми розглянуто в працях першої половини 1980-х років^[1]^[2], поняття потокового алгоритму вперше формалізовано в роботі Алона, Матіаса^[en] та Сегеді^[en] 1996 року^[3]. 2005 року авторів відзначено премією Геделя за внесок у теорію алгоритмів (англ. for their foundational contribution to streaming algorithms).

2005 року введено поняття напівпотокового алгоритму (англ. semi-streaming algorithm)^[4] як алгоритму, що обробляє вхідний потік за стале або логарифмічне від обсягу даних число проходів.

Модель

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

У низці джерел додатково розглядають модель на ковзному вікні. У цій моделі функція обчислюється над вікном фіксованої довжини. У міру обробки потоку старі елементи видаляються з одного краю вікна, а нові додаються з іншого.

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

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

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

У потокових алгоритмах розглядаються як питання, пов'язані з частотними характеристиками даних, так і низка інших. Багато задач на графах розв'язуються в умовах того, що матриця суміжності графа потоково підвантажується в деякому невідомому наперед порядку. Також є задачі, коли порядок має особливе значення. Наприклад, задача підрахунку числа інверсій або пошуку найбільшої зростальної підпослідовності.

Порівняння алгоритмів

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

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

Ці алгоритми мають багато спільного з онлайновими алгоритмами, оскільки алгоритм повинен приймати рішення до того, як стануть доступними всі дані, але є й відмінності. Зокрема, потокові алгоритми мають можливість відкласти ухвалення рішення до моменту приходу групи точок послідовності даних, тоді як онлайнові алгоритми повинні приймати рішення в міру приходу кожної нової точки послідовності.

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

Застосування

Потокові алгоритми важливі в задачах моніторингу комп'ютерних мереж. Наприклад, відстеження потоків високої інтенсивності, оцінення загальної кількості різних потоків, наближене оцінення розподілу інтенсивності потоків тощо^[5]. Також потокові алгоритми можуть застосовуватись у базах даних, наприклад, для оцінення розміру декартового добутку таблиць.

Приклади задач, які розв'язують потокові алгоритми

Задачі з частотним розподілом

$k$ -ий момент частоти у векторі $\mathbf {a}$ визначають як $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}$ .

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

Також вивчено питання оцінення моментів частот.

Пошук важких елементів

Задача полягає в пошуку в потоці даних елемента, який зустрічається найчастіше. Тут застосовуються такі алгоритми:

алгоритм більшості голосів Боєра — Мура
алгоритм Карпа — Пападимитріу — Шенкера ,
Count-Min sketch^[en] ,
алгоритм в'язкої вибірки (англ. sticky sampling),
Алгоритм підрахунку втрат^[en],
«вибірка та утримання» (англ. sample and hold),
багаторівневий фільтр Блума,
підрахунок «начерків» (англ. Count-sketch),
вибірка на основі «начерків» (англ. Sketch-guided sampling).

Відстеження тренду

Відстеження тренду в потоці даних зазвичай проводять у такому порядку: найчастіші елементи та їхні частоти визначають на основі одного зі згаданих вище алгоритмів, а потім найбільше збільшення відносно попереднього моменту часу відзначають як тренд. Для цього застосовують експоненційне рухоме середнє і різне нормування^[6]. Алгоритм використовує 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}$ ^[7].

Машинне навчання

Основна задача онлайнового машинного навчання — навчити модель (наприклад, класифікатор) за один прохід за навчальною вибіркою; для її розв'язання зазвичай використовують методи передбачального гешування^[en] і стохастичний градієнтний спуск.

Підрахунок числа унікальних елементів

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

Примітки

↑ Munro та Paterson, (1980)
↑ Flajolet та Martin, (1985)
↑ Alon, Matias та Szegedy, (1996)
↑ Feigenbaum, Joan; Sampath, Kannan (2005). On graph problems in a semi-streaming model. Theoretical Computer Science. 348 (2): 207—216. doi:10.1016/j.tcs.2005.09.013.
↑ J. Xu A Tutorial on Network Data Streaming
↑ Schubert, E.; Weiler, M.; Kriegel, H. P. (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. с. 871—880. doi:10.1145/2623330.2623740. ISBN 9781450329569.
↑ Оцінки ентропії наведено в працях: McGregor та ін., Do Ba та ін., Lall та ін., Chakrabarti та ін.^{[уточнити]}
↑ Flajolet та Martin, (1985)
↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), «An optimal algorithm for the distinct elements problem», Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '10, New York, NY, USA: ACM, pp. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9.

Література

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Вперше опубліковано як 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), с. 20—29, CiteSeerX 10.1.1.131.4984, doi:10.1145/237814.237823, ISBN 978-0-89791-785-8, S2CID 1627911.
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), с. 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, с. 41—52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9.
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, Piotr Indyk, MIT
Dagstuhl Workshop on Sublinear Algorithms
IIT Kanpur Workshop on Data Streaming
List of open problems in streaming (зібрав Andrew McGregor) за обговоренням на 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 Muthu Muthukrishnan
Stanford STREAM project survey
Network Applications of Bloom filters, по Broder and Mitzenmacher
Xu's SIGMETRICS 2007 tutorial
Lecture notes from Data Streams курс на Barbados в 2009, Andrew McGregor and S. Muthu Muthukrishnan

[1] Munro та Paterson, (1980)

[autogenerated12-2] Flajolet та Martin, (1985)

[autogenerated22-3] Alon, Matias та Szegedy, (1996)

[4] Feigenbaum, Joan; Sampath, Kannan (2005). On graph problems in a semi-streaming model. Theoretical Computer Science. 348 (2): 207—216. doi:10.1016/j.tcs.2005.09.013.

[5] J. Xu A Tutorial on Network Data Streaming

[6] Schubert, E.; Weiler, M.; Kriegel, H. P. (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. с. 871—880. doi:10.1145/2623330.2623740. ISBN 9781450329569.

[7] Оцінки ентропії наведено в працях: McGregor та ін., Do Ba та ін., Lall та ін., Chakrabarti та ін.^{[уточнити]}

[autogenerated1-8] Flajolet та Martin, (1985)

[9] Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), «An optimal algorithm for the distinct elements problem», Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '10, New York, NY, USA: ACM, pp. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]