Поточный алгоритм: различия между версиями
[непроверенная версия] | [непроверенная версия] |
→Проблемы с частотным распределением: Опечатка. Метки: с мобильного устройства из мобильной версии |
NapalmBot (обсуждение | вклад) м Исправление псевдозаголовков (см. Википедия:Доступность#Заголовки) |
||
(не показано 28 промежуточных версий 14 участников) | |||
Строка 1: | Строка 1: | ||
'''Поточный алгоритм''' ({{lang-en|streaming algorithm}}) — [[алгоритм]] для обработки последовательности данных в один или малое число проходов. |
'''Поточный алгоритм''' ({{lang-en|streaming algorithm}}) — [[алгоритм]] для обработки [[Последовательность|последовательности]] [[Поток данных|данных]] в один или малое число проходов. |
||
Поточные алгоритмы решают задачи, в которых данные приходят последовательно и в большом |
Поточные алгоритмы решают задачи, в которых данные приходят последовательно и в большом объёме. Примером может служить анализ сетевого трафика на стороне [[маршрутизатор]]а. Подобные задачи накладывают на поточные алгоритмы естественные ограничения по доступной памяти (намного меньше, чем размер входных данных) и времени обработки каждого элемента последовательности. Зачастую, обработка данных возможна только в один проход. |
||
Строгие ограничения на время и память часто делают невозможным точное решение исследуемой задачи. Обычно |
Строгие ограничения на время и память часто делают невозможным точное решение исследуемой задачи. Обычно поточные алгоритмы являются вероятностными и дают приближение на точный ответ. |
||
== История == |
== История == |
||
Хотя подобные алгоритмы рассматривались |
Хотя подобные алгоритмы рассматривались в работах первой половины 1980-х годов<ref>{{Harvtxt|Munro|Paterson|1980}}</ref><ref name=autogenerated1>{{Harvtxt|Flajolet|Martin|1985}}</ref>, понятие поточного алгоритма было впервые формализовано в работе [[Алон, Нога|Алона]], {{нп2|Матиас, Йосси|Матиаса|en|Yossi Matias}} и {{нп2|Сегеди, Марио|Сегеди|en|Mario Szegedy}} в [[1996 год в науке|1996 году]]<ref name=autogenerated2>{{Harvtxt|Alon|Matias|Szegedy|1996}}</ref>. В 2005 году авторы были удостоены [[Премия Гёделя|премии Гёделя]] за вклад в теорию алгоритмов ({{lang-en|for their foundational contribution to streaming algorithms}}). |
||
В 2005 году было введено понятие |
В 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>\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> не может быть отрицательным. |
В «турникетной» модели каждое «обновление» представляется в форме <math>\langle i,c\rangle</math> и модифицируют вектор таким образом, что <math>a_i</math> увеличивается на некоторое положительное или отрицательное целое число <math>c</math>. В строгой турникетной модели, в любой момент времени <math>a_i</math> не может быть отрицательным. |
||
В ряде источников дополнительно рассматривают |
В ряде источников дополнительно рассматривают модель на скользящем окне. В данной модели функция вычисляется над окном фиксированной длины. По мере обработки потока, старые элементы удаляются с одного конца окна, а новые добавляются с другого. |
||
В |
В поточных алгоритмах рассматриваются не только вопросы, связанные с частотными характеристиками данных, но и ряд других. Много задач на графах решаются в условиях того, что [[матрица смежности]] графа потоково подгружается в некотором заранее неизвестном порядке. Также существуют задачи, когда порядок имеет особое значение. Например, задачи подсчета числа [[Перестановка#Связанные_определения|инверсий]] или поиска наибольшей возрастающей подпоследовательности. |
||
== Сравнение алгоритмов == |
== Сравнение алгоритмов == |
||
Строка 27: | Строка 27: | ||
* число допустимых проходов алгоритма над данными; |
* число допустимых проходов алгоритма над данными; |
||
* доступная память; |
* доступная память; |
||
* время обработки |
* время обработки отдельного элемента. |
||
Данные алгоритмы имеют много общего с {{ |
Данные алгоритмы имеют много общего с {{iw|Онлайн-алгоритм|онлайн-алгоритмами|en|Online algorithm}}, так как алгоритм должен принимать решение до того, как все данные станут доступны, но есть и различия. В частности, поточные алгоритмы имеют возможность отложить принятие решение до момента прихода группы точек последовательности данных, в то время как онлайн-алгоритмы должны принимать решения по мере прихода каждой новой точки последовательности. |
||
Если алгоритм является приближённым, то точность ответа является ещё одним показателям. Точность алгоритма часто представляется как величина <math>(\epsilon,\delta)</math>, означающая то, что алгоритм достигнет ошибки меньше <math>\epsilon</math> с вероятностью <math>1-\delta</math>. |
Если алгоритм является приближённым, то точность ответа является ещё одним показателям. Точность алгоритма часто представляется как величина <math>(\epsilon,\delta)</math>, означающая то, что алгоритм достигнет ошибки меньше <math>\epsilon</math> с вероятностью <math>1-\delta</math>. |
||
== Применение == |
== Применение == |
||
Поточные алгоритмы имеют большое значение в задачах [[Мониторинг компьютерной сети|мониторинга]] |
Поточные алгоритмы имеют большое значение в задачах [[Мониторинг компьютерной сети|мониторинга]] компьютерных сетей. Например, отслеживание потоков высокой интенсивности, оценка общего числа различных потоков, приблеженная оценка распределения интенсивности потоков и т.п.<ref>J. Xu A Tutorial on Network Data Streaming</ref>. Также поточные алгоритмы могут применяться в базах данных, например, для оценки размера [[Операция соединения (СУБД)|соединения таблиц]]. |
||
== Примеры задач, решаемых поточными алгоритмами == |
== Примеры задач, решаемых поточными алгоритмами == |
||
Строка 46: | Строка 46: | ||
=== Поиск тяжёлых элементов === |
=== Поиск тяжёлых элементов === |
||
Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы: |
Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы: |
||
* [[алгоритм большинства голосов Бойера — Мура]] |
|||
* [[алгоритм Карпа — Пападимитриу — Шенкера]], |
* [[алгоритм Карпа — Пападимитриу — Шенкера]], |
||
* {{ |
* {{нп1|Count-Min sketch||en|Count-Min sketch}}, |
||
* [[алгоритм вязкой выборки]] ({{lang-en|sticky sampling}}), |
* [[алгоритм вязкой выборки]] ({{lang-en|sticky sampling}}), |
||
* {{ |
* {{нп1|Lossy Count Algorithm||en|Lossy Count Algorithm}}, |
||
* «выборка и удержание» ({{lang-en|sample and hold}}), |
* «выборка и удержание» ({{lang-en|sample and hold}}), |
||
* многоуровневый [[фильтр Блума]], |
* многоуровневый [[фильтр Блума]], |
||
Строка 56: | Строка 57: | ||
=== Отслеживание тренда === |
=== Отслеживание тренда === |
||
Отслеживанием тренда в потоке данных обычно производится в следующем порядке: наиболее частые элементы и их частоты определяются на основе одного из вышеперечисленных алгоритмов, а затем наибольшее увеличение относительно предыдущего момента времени отмечается как тренд. Для этого используется экспоненциальная [[скользящая средняя]] и различная нормировка<ref>{{cite doi|10.1145/2623330.2623740}}</ref>. Он используется O(ε² + log d) места и O(1) для худщего случая обновления при универсальной хеш-функции из семейства r-умных независимых хеш-функций с r = Ω(log(1/ε)/ log log(1/ε)){{уточнить}}<!--r-умные — общепринятый термин?-->. |
Отслеживанием тренда в потоке данных обычно производится в следующем порядке: наиболее частые элементы и их частоты определяются на основе одного из вышеперечисленных алгоритмов{{уточнить}}<--алгоритмов поиска тяжёлых элементов? а если эту секцию перенсут ниже?-->, а затем наибольшее увеличение относительно предыдущего момента времени отмечается как тренд. Для этого используется экспоненциальная [[скользящая средняя]] и различная нормировка<ref>{{cite doi|10.1145/2623330.2623740}}</ref>. Он используется O(ε² + log d) места и O(1) для худщего случая обновления при универсальной хеш-функции из семейства r-умных независимых хеш-функций с r = Ω(log(1/ε)/ log log(1/ε)){{уточнить}}<!--r-умные — общепринятый термин?-->. |
||
=== Энтропия === |
=== Энтропия === |
||
Строка 63: | Строка 64: | ||
=== Машинное обучение === |
=== Машинное обучение === |
||
Основная задача |
Основная задача [[Онлайновое машинное обучение|онлайнового машинного обучения]] — обучить модель (например, классификатор) за один проход по обучающей выборке; для её решения обычно используются {{нп1|методы предсказательного хеширования||en|Feature hashing}}) и {{нп1|стохастический нисходящий градиент||en|Stochastic gradient descent}}). |
||
=== Подсчёт числа уникальных элементов === |
=== Подсчёт числа уникальных элементов === |
||
Строка 106: | Строка 107: | ||
* {{citation |
* {{citation |
||
| title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
| title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
||
| last1=Gilbert|first1=A. C. |
| last1=Gilbert|first1=A. C. | author1-link = Гилберт, Анна |
||
| last2=Kotidis|first2=Y. |
| last2=Kotidis|first2=Y. |
||
| last3=Muthukrishnan|first3=S. |
| last3=Muthukrishnan|first3=S. |
||
Строка 122: | Строка 123: | ||
| year = 2010 |
| year = 2010 |
||
| isbn = 978-1-4503-0033-9 |
| isbn = 978-1-4503-0033-9 |
||
⚫ | |||
| location = Indianapolis, Indiana, USA |
|||
⚫ | |||
| url = http://doi.acm.org/10.1145/1807085.1807094 |
|||
| doi = 10.1145/1807085.1807094 |
| doi = 10.1145/1807085.1807094 |
||
| publisher = ACM |
| publisher = ACM |
||
| location = New York, NY, USA |
| location = New York, NY, USA |
||
| citeseerx = 10.1.1.164.142 |
|||
}}. |
}}. |
||
* {{citation |
* {{citation |
||
| title = A simple algorithm for finding frequent elements in streams and bags |
| title = A simple algorithm for finding frequent elements in streams and bags |
||
Строка 138: | Строка 138: | ||
| journal = ACM Transactions on Database Systems}}. |
| journal = ACM Transactions on Database Systems}}. |
||
* {{citation |
* {{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 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
|year = 2006 |
|||
}}{{Недоступная ссылка|date=Ноябрь 2018 |bot=InternetArchiveBot }}. |
|||
* {{citation |
* {{citation |
||
| title = A Tutorial on Network Data Streaming |
| title = A Tutorial on Network Data Streaming |
||
Строка 155: | Строка 161: | ||
== Ссылки == |
== Ссылки == |
||
* [http://www.cs.princeton.edu/~moses/papers/stream-kmedian.ps Princeton Lecture Notes] |
* [https://web.archive.org/web/20100617185154/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://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.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.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://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://groups.csail.mit.edu/cag/streamit/index.shtml StreamIt — programming language and compilation infrastructure by MIT CSAIL]{{Недоступная ссылка|date=мая 2021 |bot=InternetArchiveBot }} |
||
* [http://domino.research.ibm.com/comm/research_projects.nsf/pages/esps.spade.html IBM Spade — Stream Processing Application Declarative Engine] |
* [https://archive.today/20080127205615/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-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://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://ilpubs.stanford.edu:8090/535/1/2002-19.pdf Stanford STREAM project survey] |
||
Строка 169: | Строка 175: | ||
* [http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf Xu’s SIGMETRICS 2007 tutorial] |
* [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.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://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/ Dartmouth] |
||
* [http://stellar.mit.edu/S/course/6/fa07/6.895/ MIT] |
* [http://stellar.mit.edu/S/course/6/fa07/6.895/ MIT] |
||
* [http://dsp.rice.edu/courses/elec631 Rice] |
* [http://dsp.rice.edu/courses/elec631 Rice] |
||
* [http://www.cs.rutgers.edu/~muthu/str05.html Rutgers] |
* [http://www.cs.rutgers.edu/~muthu/str05.html Rutgers] |
||
* [http://www.cse.buffalo.edu/ |
* [https://web.archive.org/web/20090909014654/http://www.cse.buffalo.edu/%7Eatri/courses/data-stream/ University at Buffalo] |
||
{{rq|wikify|check}} |
{{rq|wikify|check}} |
||
Текущая версия от 06:18, 12 октября 2024
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Поточные алгоритмы решают задачи, в которых данные приходят последовательно и в большом объёме. Примером может служить анализ сетевого трафика на стороне маршрутизатора. Подобные задачи накладывают на поточные алгоритмы естественные ограничения по доступной памяти (намного меньше, чем размер входных данных) и времени обработки каждого элемента последовательности. Зачастую, обработка данных возможна только в один проход.
Строгие ограничения на время и память часто делают невозможным точное решение исследуемой задачи. Обычно поточные алгоритмы являются вероятностными и дают приближение на точный ответ.
История
[править | править код]Хотя подобные алгоритмы рассматривались в работах первой половины 1980-х годов[1][2], понятие поточного алгоритма было впервые формализовано в работе Алона, Матиаса (англ. Yossi Matias) и Сегеди (англ. Mario Szegedy) в 1996 году[3]. В 2005 году авторы были удостоены премии Гёделя за вклад в теорию алгоритмов (англ. for their foundational contribution to streaming algorithms).
В 2005 году было введено понятие полупоточных алгоритмов (англ. semi-streaming algorithm)[4] как алгоритмов обрабатывающих входящий поток за постоянное или логарифмическое от размера объема данных число проходов.
Модель
[править | править код]В модели потоковых данных считается, что часть или весь набор входных данных, над которыми необходимо осуществлять обработку, недоступен для произвольного доступа: входные данные поступают последовательно и непрерывно в одном или нескольких потоках. Потоки данных могут быть представлены упорядоченной последовательностью точек («обновлений»), доступ к которым может осуществляться по порядку и только один или ограниченное число раз.
Во многих публикациях по поточной обработке рассматривают задачу вычисления статистик над частотным распределением данных. При этом объем самих данных слишком велик для эффективного хранения. Примерами нетривиальных задач являются вычисление медианы, произвольных персенталей или количество уникальных элементов в потоке. Формально, для данного класса задач предполагается, что вектор (инициализированный нулевой последовательностью ) имеет некоторое количество «обновлений». Каждое обновление увеличивает или уменьшает значение в отдельной ячейке вектора. Цель алгоритма — вычислить функции от , используя существенно меньше места, чем это потребовало бы полное как представление вектора , так и схоранение объема обрабатываемых данных. Существуют две общих модели обновления таких данных: «касса» (англ. cash register) и «турникет» (англ. turnstile).
В «кассовой» модели каждое «обновление» представляется в форме и модифицируют вектор таким образом, что увеличивается на некоторое положительное целое число . Зачастую , что обозначает тривиальную инкрементную модель.
В «турникетной» модели каждое «обновление» представляется в форме и модифицируют вектор таким образом, что увеличивается на некоторое положительное или отрицательное целое число . В строгой турникетной модели, в любой момент времени не может быть отрицательным.
В ряде источников дополнительно рассматривают модель на скользящем окне. В данной модели функция вычисляется над окном фиксированной длины. По мере обработки потока, старые элементы удаляются с одного конца окна, а новые добавляются с другого.
В поточных алгоритмах рассматриваются не только вопросы, связанные с частотными характеристиками данных, но и ряд других. Много задач на графах решаются в условиях того, что матрица смежности графа потоково подгружается в некотором заранее неизвестном порядке. Также существуют задачи, когда порядок имеет особое значение. Например, задачи подсчета числа инверсий или поиска наибольшей возрастающей подпоследовательности.
Сравнение алгоритмов
[править | править код]Основные характеристики поточных алгоритмов:
- число допустимых проходов алгоритма над данными;
- доступная память;
- время обработки отдельного элемента.
Данные алгоритмы имеют много общего с онлайн-алгоритмами[англ.], так как алгоритм должен принимать решение до того, как все данные станут доступны, но есть и различия. В частности, поточные алгоритмы имеют возможность отложить принятие решение до момента прихода группы точек последовательности данных, в то время как онлайн-алгоритмы должны принимать решения по мере прихода каждой новой точки последовательности.
Если алгоритм является приближённым, то точность ответа является ещё одним показателям. Точность алгоритма часто представляется как величина , означающая то, что алгоритм достигнет ошибки меньше с вероятностью .
Применение
[править | править код]Поточные алгоритмы имеют большое значение в задачах мониторинга компьютерных сетей. Например, отслеживание потоков высокой интенсивности, оценка общего числа различных потоков, приблеженная оценка распределения интенсивности потоков и т.п.[5]. Также поточные алгоритмы могут применяться в базах данных, например, для оценки размера соединения таблиц.
Примеры задач, решаемых поточными алгоритмами
[править | править код]Проблемы с частотным распределением
[править | править код]-ый момент частоты в векторе определяется как .
Первый момент — это простая сумма частот (то есть, общее число). Второй момент полезен для вычисления статистических параметров данных, например Коэффициент Джини. определяется как частота наиболее часто встречающегося элемента.
Также изучены вопросы оценки моментов частот.
Поиск тяжёлых элементов
[править | править код]Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы:
- алгоритм большинства голосов Бойера — Мура
- алгоритм Карпа — Пападимитриу — Шенкера,
- Count-Min sketch[англ.],
- алгоритм вязкой выборки (англ. sticky sampling),
- Lossy Count Algorithm[англ.],
- «выборка и удержание» (англ. sample and hold),
- многоуровневый фильтр Блума,
- подсчёт «набросков» (англ. Count-sketch),
- выборка на основе «набросков» англ. Sketch-guided sampling,
Отслеживание тренда
[править | править код]Отслеживанием тренда в потоке данных обычно производится в следующем порядке: наиболее частые элементы и их частоты определяются на основе одного из вышеперечисленных алгоритмов[уточнить]<--алгоритмов поиска тяжёлых элементов? а если эту секцию перенсут ниже?-->, а затем наибольшее увеличение относительно предыдущего момента времени отмечается как тренд. Для этого используется экспоненциальная скользящая средняя и различная нормировка[6]. Он используется O(ε² + log d) места и O(1) для худщего случая обновления при универсальной хеш-функции из семейства r-умных независимых хеш-функций с r = Ω(log(1/ε)/ log log(1/ε))[уточнить].
Энтропия
[править | править код]Эмпирическая оценка энтропии над набором частот определяется как , где [7].
Машинное обучение
[править | править код]Основная задача онлайнового машинного обучения — обучить модель (например, классификатор) за один проход по обучающей выборке; для её решения обычно используются методы предсказательного хеширования[англ.]) и стохастический нисходящий градиент[англ.]).
Подсчёт числа уникальных элементов
[править | править код]Подсчёт числа уникальных элементов в потоке данных (момент ) является ещё одной[уточнить] хорошо изученной проблемой. Первый алгоритм был предложен Флажоле и Мартеном[2]. В 2010 году был найден асимптотически оптимальный алгоритм[8].
Примечания
[править | править код]- ↑ Munro & Paterson (1980)
- ↑ 1 2 Flajolet & Martin (1985)
- ↑ Alon, Matias & Szegedy (1996)
- ↑ Feigenbaum Joan, Kannan Sampath, McGregor Andrew, Suri Siddharth, Zhang Jian. On graph problems in a semi-streaming model // Theoretical Computer Science. — 2005. — Декабрь (т. 348, № 2-3). — С. 207—216. — ISSN 0304-3975. — doi:10.1016/j.tcs.2005.09.013.
- ↑ J. Xu A Tutorial on Network Data Streaming
- ↑ Schubert Erich, Weiler Michael, Kriegel Hans-Peter. SigniTrend // Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. — 2014. — ISBN 9781450329569. — doi:10.1145/2623330.2623740.
- ↑ Оценки энтропии были даны в работах: McGregor и др., Do Ba и др., Lall и др., Chakrabarti и др.[уточнить]
- ↑ 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. 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, CiteSeerX 10.1.1.164.142, 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
Курсы
Для улучшения этой статьи желательно:
|