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

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

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

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

Зміст

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Підрахунок числа унікальних елементів в потоці даних (момент F 0 >) є ще однією [уточнити] добре вивченою проблемою. Перший алгоритм був запропонований Флажолі та Мартеном [2] . У 2010 році було знайденоасимптотично оптимальний алгоритм [7] .