Просмотр кода страницы Поточный алгоритм

'''Поточный алгоритм''' ({{lang-en|streaming algorithm}}) — [[алгоритм]] для обработки последовательности данных в один или малое число проходов.

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

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

== История ==
Хотя подобные алгоритмы рассматривались в в работах первой половины 1980-х годов<ref>Munro, Paterson, 1980{{Уточнить}}</ref><ref name=autogenerated1>Flajolet, Martin, 1985{{Уточнить}}</ref>, понятие поточного алгоритма было впервые формализовано в работе [[Алон, Нога|Алона]], {{нп2|Матиас, Йосси|Матиаса|en|Yossi Matias}} и {{нп2|Сегеди, Марио|Сегеди|en|Mario Szegedy}} в [[1996 год в науке|1996 году]]. В 2005 году авторы были удостоены [[Премия Гёделя|премии Гёделя]] за вклад в теорию алгоритмов ({{lang-en|for their foundational contribution to streaming algorithms}}).

В 2005 году было введено понятие полупоточного алгоритма ({{lang-en|semi-streaming algorithm}})<ref>{{cite doi|10.1016/j.tcs.2005.09.013}}</ref> как алгоритмов обрабатывающих входящий поток за постоянное или логарифмическое{{Уточнить}}<!--логарифм от чего?--> число проходов.

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

Во многих публикациях по поточной обработке рассматривают задачу компьютерной статистики над таким распределением данных, которое слишком велико для эффективного хранения{{Уточнить}}<!-- неочевидно, что имелось в виду-->. Для данного класса задач предполагается, что вектор <math>\mathbf{a} = (a_1, \dots, a_n)</math> (инициализированный нулевой последовательностью <math>\mathbf{0}</math>) имеет некоторое количество «обновлений» в потоке. Цель таких алгоритмов — вычислить функции от <math>\mathbf{a}</math>, используя существенно меньше места, чем это потребовало бы полное представление вектора <math>\mathbf{a}</math>. Существуют две общих модели обновления таких данных: «касса» ({{lang-en|cash register}}) и «турникет» ({{lang-en|turnstile}}).

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

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

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

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

== Сравнение алгоритмов ==
Основные характеристики поточных алгоритмов:
* число допустимых проходов алгоритма над данными;
* доступная память;
* время обработки{{Уточнить}}<!--одного элемента, наверное?-->.
Данные алгоритмы имеют много общего с {{не переведено|:en:Online algorithm|онлайн-алгоритмами}}, так как алгоритм должен принимать решение до того, как все данные станут доступны, но есть и различия. В частности, поточные алгоритмы имеют возможность отложить принятие решение до момента прихода группы точек последовательности данных, в то время как онлайн-алгоритмы должны принимать решения по мере прихода каждой новой точки последовательности.

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

== Применение ==
Поточные алгоритмы имеют большое значение в задачах [[Мониторинг компьютерной сети|мониторинга]] и [[Управление компьютерной сетью|управления]] компьютерными сетями, например, их средствами возможно оперативное предотвращение [[Переполнение буфера|переполнений]] (отслеживание {{не переведено|:en:Elephant flow|гигантский поток (информатика)|гигантских потоков}}, оценка числа и ожидаемой длительности переполнений)<ref>J. Xu A Tutorial on Network Data Streaming</ref>. Также поточные алагоритмы могут применяться в базах данных, например, для оценки размера после операции [[Операция соединения (СУБД)|соединения таблиц]].

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

=== Проблемы с частотным распределением ===
<math>k</math>-ый момент частоты в векторе <math>\mathbf{a}</math> определяется как <math>F_k(\mathbf{a}) = \sum_{i=1}^n a_i^k</math>.

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

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

=== Поиск тяжёлых элементов ===
Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы:
* [[алгоритм большинства голосов Бойера — Мура]]
* [[алгоритм Карпа — Пападимитриу — Шенкера]],
* {{не переведено|:en:Count-Min sketch|Count-Min sketch}},
* [[алгоритм вязкой выборки]] ({{lang-en|sticky sampling}}),
* {{не переведено|:en:Lossy Count Algorithm|Lossy Count Algorithm}},
* «выборка и удержание» ({{lang-en|sample and hold}}),
* многоуровневый [[фильтр Блума]],
* подсчёт «набросков» ({{lang-en|Count-sketch}}),
* выборка на основе «набросков» {{lang-en|Sketch-guided sampling}},

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

=== Энтропия ===
Эмпирическая оценка энтропии над набором частот <math>\mathbf{a}</math> определяется как <math>F_k(\mathbf{a}) = \sum_{i=1}^n
\frac{a_i}{m}\log{\frac{a_i}{m}}</math>, где <math>m = \sum_{i=1}^n a_i</math><ref>Оценки энтропии были даны в работах: McGregor и др., Do Ba и др., Lall и др., Chakrabarti и др.{{Уточнить}}</ref>.

=== Машинное обучение ===
Основная задача {{нп2|поточное машинное обучение|поточного машинного обучения|en|online machine learning}} — обучить модель (например, классификатор) за один проход по обучающей выборке; для её решения обычно используются {{не переведено|:en:Feature hashing|методы предсказательного хеширования}}) и {{не переведено|:en:Stochastic gradient descent|стохастический нисходящий градиент}}).

=== Подсчёт числа уникальных элементов ===
Подсчёт числа уникальных элементов в потоке данных (момент <math>F_0</math>) является ещё одной{{Уточнить}}<!--ещё одной вкупе с какой?--> хорошо изученной проблемой. Первый алгоритм был предложен Флажоле и Мартеном<ref name=autogenerated1 />. В 2010 году был найден асимптотически оптимальный алгоритм<ref>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.</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{citation
  | title = The space complexity of approximating the frequency moments
  | last1=Alon | first1=Noga | author1-link = Noga Alon
  | last2=Matias | first2=Yossi
  | last3=Szegedy | first3=Mario | author3-link = Mario Szegedy
  | year = 1999
  | doi=10.1006/jcss.1997.1545
  | journal = [[Journal of Computer and System Sciences]]
  | volume = 58
  | issue = 1
  | issn = 0022-0000
  | pages = 137–147}}. First published as {{citation
  | contribution = The space complexity of approximating the frequency moments
  | last1=Alon | first1=Noga
  | last2=Matias | first2=Yossi
  | last3=Szegedy | first3=Mario
  | doi=10.1145/237814.237823
  | year = 1996
  | title = [[Symposium on Theory of Computing|Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)]]
  | isbn = 0-89791-785-5
  | pages = 20–29}}.
* {{citation
  | contribution = Models and issues in data stream systems
  | last1 = Babcock | first1=Brian
  | last2 = Babu | first2=Shivnath
  | last3 = Datar | first3= Mayur
  | last4 = Motwani | first4=Rajeev | author4-link = Rajeev Motwani
  | last5 = Widom | first5=Jennifer | author5-link = Jennifer Widom
  | url = http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf
  | doi = 10.1145/543613.543615 | pages = 1–16
  | title= Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002)
  | year = 2002}}.
* {{citation
  | title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
  | last1=Gilbert|first1=A. C. 
  | last2=Kotidis|first2=Y. 
  | last3=Muthukrishnan|first3=S. 
  | last4=Strauss|first4=M. J.
  | url = http://www.vldb.org/conf/2001/P079.pdf
  | journal = Proceedings of the International Conference on Very Large Data Bases
  | pages = 79–88
  | year = 2001}}.
* {{citation | last1 = Kane | first1 = Daniel M.
 | last2 = Nelson | first2 = Jelani 
 | last3 = Woodruff | first3 = David P.
 | title = An optimal algorithm for the distinct elements problem
 | booktitle = Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
 | series = PODS '10
 | year = 2010
 | isbn = 978-1-4503-0033-9
 | location = Indianapolis, Indiana, USA
 | pages = 41–52
 | url = http://doi.acm.org/10.1145/1807085.1807094
 | doi = 10.1145/1807085.1807094
 | publisher = ACM
 | location = New York, NY, USA
}}.
* {{citation
  | title = A simple algorithm for finding frequent elements in streams and bags
  | last1=Karp|first1=R. M. | author1-link = Richard Karp
  | last2=Papadimitriou|first2=C. H. | author2-link = Christos Papadimitriou
  | last3=Shenker|first3=S. | author3-link = Scott Shenker
  | year = 2003
  | volume = 28 | issue = 1 | pages = 51–55 | doi = 10.1145/762471.762473
  | journal = ACM Transactions on Database Systems}}.
* {{citation
  | contribution = Data streaming algorithms for estimating entropy of network traffic
  | last1 = Lall | first1 = Ashwin
  | last2 = Sekar | first2 = Vyas
  | last3 = Ogihara | first3 = Mitsunori
  | last4 = Xu | first4 = Jun
  | last5 = Zhang | first5 = Hui
  | title = Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006)
  | doi = 10.1145/1140277.1140295
  | url = ftp://ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf
  | year = 2006}}.
* {{citation
  | title = A Tutorial on Network Data Streaming
  | last1 = Xu | first1=Jun (Jim)
  | url = http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf
  | year = 2007}}.

== Ссылки ==
* [http://www.cs.princeton.edu/~moses/papers/stream-kmedian.ps Princeton Lecture Notes]
* [http://people.csail.mit.edu/indyk/GEOSTREAM/geostream-bib.ps Streaming Algorithms for Geometric Problems], by [[Piotr Indyk]], MIT
* [http://www.dagstuhl.de/de/program/calendar/semhp/?semnr=05291 Dagstuhl Workshop on Sublinear Algorithms]
* [http://www.cse.iitk.ac.in/users/sganguly/workshop.html IIT Kanpur Workshop on Data Streaming]
* [http://www.cs.umass.edu/~mcgregor/papers/07-openproblems.pdf List of open problems in streaming] (compiled by [[Andrew McGregor]]) from discussion at the IITK Workshop on Algorithms for Data Streams, 2006.
* [http://groups.csail.mit.edu/cag/streamit/index.shtml StreamIt — programming language and compilation infrastructure by MIT CSAIL]
* [http://domino.research.ibm.com/comm/research_projects.nsf/pages/esps.spade.html IBM Spade — Stream Processing Application Declarative Engine]
* [http://www-01.ibm.com/software/data/infosphere/streams/ IBM InfoSphere Streams]
;Учебники
* [http://www.cs.rutgers.edu/~muthu/stream-1-1.ps Data Stream Algorithms and Applications] by [[S. Muthu Muthukrishnan]]
* [http://ilpubs.stanford.edu:8090/535/1/2002-19.pdf Stanford STREAM project survey]
* [http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf Network Applications of Bloom filters], by Broder and Mitzenmacher
* [http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf Xu’s SIGMETRICS 2007 tutorial]
* [http://www.cs.mcgill.ca/~denis/notes09.pdf Lecture notes from Data Streams course at Barbados in 2009], by [[Andrew McGregor]] and [[S. Muthu Muthukrishnan]]
;Курсы
* [http://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/ Dartmouth]
* [http://stellar.mit.edu/S/course/6/fa07/6.895/ MIT]
* [http://dsp.rice.edu/courses/elec631 Rice]
* [http://www.cs.rutgers.edu/~muthu/str05.html Rutgers]
* [http://www.cse.buffalo.edu/~atri/courses/data-stream/ University at Buffalo]
{{rq|wikify|check}}

[[Категория:Алгоритмы]]