Поточный алгоритм: различия между версиями

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


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


=== Проблемы с частотным распределением ===
=== Проблемы с частотным распределением ===

Версия от 19:54, 27 февраля 2015

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

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

История

Хотя подобные алгоритмы рассматривались в в работах первой половины 1980-х годов[1][2], понятие поточного алгоритма было впервые формализовано в работе Алона?! (англ. Noga Alon), Матиаса (англ. Yossi Matias) и Сегеди (англ. Mario Szegedy) в 1996 году. В 2005 годы авторы были удостоены премии Гёделя за вклад в теорию алгоритмов (англ. for their foundational contribution to streaming algorithms).

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

Модель

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

Во многих публикациях по поточной обработке рассматривают задачу компьютерной статистики над таким распределением данных, которое слишком велико для эффективного хранения[уточнить]. Для данного класса задач предполагается, что вектор (инициализированный нулевой последовательностью ) имеет некоторое количество «обновлений» в потоке. Цель таких алгоритмов — вычислить функции от , используя существенно меньше места, чем это потребовало бы полное представление вектора . Существуют две общих модели обновления таких данных: «касса» (англ. cash register) и «турникет» (англ. turnstile).

В «кассовой» модели каждое «обновление» представляется в форме и модифицируют вектор таким образом, что увеличивается на некоторое положительное целое число . Особым случаем является случай (разрешена вставка только одной единицы).

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

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

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

Сравнение алгоритмов

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

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

Данные алгоритмы имеют много общего с шаблон не поддерживает такой синтаксис, так как алгоритм должен принимать решение до того, как все данные станут доступны, но есть и различия. В частности, поточные алгоритмы имеют возможность отложить принятие решение до момента прихода группы точек последовательности данных, в то время как онлайн-алгоритмы должны принимать решения по мере прихода каждой новой точки последовательности.

Если алгоритм является приближённым, то точность ответа является ещё одним показателям. Точность алгоритма часто представляется как величина , означающая то, что алгоритм достигнет ошибки меньше с вероятностью .

Применение

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

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

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

-ый момент частоты в векторе определяется как .

Первый момент  — это простая сумма частот (то есть, общее число). Второй момент полезен для вычисления статистических параметров данных, например Коэффициент Джини. определяется как частота наиболее часто встречающегося элементов.

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

Поиск тяжёлых элементов

Задача состоит в поиске наиболее часто встречающегося элемента в потоке данных. Здесь применяются следующие алгоритмы:

Отслеживание тренда

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

Энтропия

Эмпирическая оценка энтропии над набором частот определяется как , где [6].

Машинное обучение

Основная задача поточного машинного обучения (англ. online machine learning) — обучить модель (например, классификатор) за один проход по обучающей выборке; для её решения обычно используются шаблон не поддерживает такой синтаксис) и шаблон не поддерживает такой синтаксис).

Подсчёт особых элементов

Измерение число особых элементов в потоке данных (момент ) является ещё одной[уточнить] хорошо изученной проблемой. Первый алгоритм был предложен Флажоле и Мартеном[2]. В 2010 году был найден асимптотически оптимальный алгоритм[7].

Примечания

  1. Munro, Paterson, 1980[уточнить]
  2. 1 2 Flajolet, Martin, 1985[уточнить]
  3. [1][уточнить]
  4. J. Xu A Tutorial on Network Data Streaming
  5. 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». pp. 871—880. 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. [исправить]
  6. Оценки энтропии были даны в работах: McGregor и др., Do Ba и др., Lall и др., Chakrabarti и др.[уточнить]
  7. 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, 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).

Ссылки

Учебники
Курсы
  • Dartmouth
  • MIT
  • Rice
  • Rutgers
  • University at Buffalo