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

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

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

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

Історія

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

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

Модель

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

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

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

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

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

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

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

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

Якщо алгоритм є наближеним, то ще одним показником є точність відповіді. Точність алгоритму часто подають як величину ${\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 }}$ визначають як частоту елемента, що зустрічається найчастіше.

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

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

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

• алгоритм більшості голосів Боєра — Мура
• ,
• ^[en] ,
• (англ. sticky sampling),
• ^[en],
• «вибірка та утримання» (англ. 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}}$.

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

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

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

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

Примітки

1. Munro та Paterson, (1980)
2. Flajolet та Martin, (1985)
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.; (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 .
7. Оцінки ентропії наведено в працях: McGregor та ін., Do Ba та ін., Lall та ін., Chakrabarti та ін.^[]
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, .

Література

• Alon, Noga; Matias, Yossi; (1999), The space complexity of approximating the frequency moments, , 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, , с. 20—29, CiteSeerX 10.1.1.131.4984, doi:10.1145/237814.237823, ISBN , S2CID 1627911.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; ; (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.
• ; 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 .
• Karp, R. M.; Papadimitriou, C. H.; (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).

Посилання

• 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
• 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