WikiDer > Алгоритм потоковой передачи

Streaming algorithm

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

Эти ограничения могут означать, что алгоритм дает приблизительный ответ на основе сводки или «наброска» потока данных.

История

Хотя алгоритмы потоковой передачи уже были изучены Манро и Патерсоном.[1] еще в 1978 г., а также Филипп Флажоле и Дж. Найджел Мартин в 1982/83 г.,[2] область потоковых алгоритмов была впервые формализована и популяризирована в статье 1996 г. Нога Алон, Йоси Матиас, и Марио Сегеди.[3] За эту работу авторы позже выиграли Премия Гёделя в 2005 г. «за их фундаментальный вклад в алгоритмы потоковой передачи». С тех пор большой объем работы был сосредоточен на алгоритмах потоковой передачи данных, охватывающих широкий спектр областей компьютерных наук, таких как теория, базы данных, сети и обработка естественного языка.

Полупотоковые алгоритмы были введены в 2005 году как ослабление потоковых алгоритмов для графов [1], в котором разрешенное пространство линейно по количеству вершин п, но только логарифмический по количеству ребер м. Это ослабление по-прежнему имеет значение для плотных графов и может решить интересные проблемы (например, связность), которые неразрешимы в Космос.

Модели

Модель потока данных

В модели потока данных некоторые или все входные данные представлены в виде конечной последовательности целых чисел (из некоторой конечной области), которая обычно недоступна для произвольный доступ, но вместо этого прибывает по одному "потоком".[4] Если поток имеет длину п и домен имеет размер м, алгоритмы обычно ограничиваются использованием пространства, которое логарифмический в м и п. Обычно они могут сделать лишь небольшое постоянное количество проходов над потоком, иногда всего один.[5]

Модели турникетов и кассовых аппаратов

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

В модели кассового аппарата каждое обновление имеет вид , так что увеличивается на некоторое положительное целое число . Примечательный частный случай - это когда (разрешены только единицы).

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

Модель раздвижного окна

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

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

Оценка

Производительность алгоритма, работающего с потоками данных, измеряется тремя основными факторами:

  • Количество проходов, которые алгоритм должен сделать над потоком.
  • Доступная память.
  • Время работы алгоритма.

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

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

Приложения

У алгоритмов потоковой передачи есть несколько приложений в сеть например, мониторинг сетевых ссылок для слоновые потоки, подсчет количества четких потоков, оценка распределения размеров потоков, и скоро.[7] У них также есть базы данных приложений, такие как оценка размера присоединиться[нужна цитата].

Некоторые проблемы с потоковой передачей

Частотные моменты

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

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

Основополагающая статья Алона, Матиаса и Сегеди касалась проблемы оценки частотных моментов.

Расчет частотных моментов

Прямой подход к нахождению частотных моментов требует ведения реестра мя для всех отдельных элементов ая ∈ (1,2,3,4,...,N) что требует как минимум памяти порядка .[3] Но у нас есть ограничения по объему и требуется алгоритм, который выполняет вычисления в гораздо меньшем объеме памяти. Это может быть достигнуто путем использования приближений вместо точных значений. Алгоритм, вычисляющий (ε, δ) приближение Fk, куда F 'k это (ε, δ) -приблизительное значение Fk.[8] Где ε - параметр аппроксимации, а δ - параметр уверенности.[9]

Расчет F0 (Отдельные элементы в потоке данных)
Алгоритм FM-Sketch

Flajolet et al. в [2] представил вероятностный метод подсчета, который был вдохновлен статьей Роберт Моррис[10]. Моррис в своей статье говорит, что если отбросить требование точности, счетчик п можно заменить счетчиком бревно п который можно хранить в журнал журнал п биты.[11] Flajolet et al. в [2] улучшил этот метод, используя хеш-функцию час который, как предполагается, равномерно распределяет элемент в хеш-пространстве (двоичная строка длиной L).

Позволять кусочек(у, к) представляют k-й бит в двоичном представлении у

Позволять представляет позицию наименее значимого 1 бита в двоичном представлении уя с подходящим соглашением для .

Позволять А быть последовательностью потока данных длины M мощность которого необходимо определить. Позволять БИТОВАЯ КАРТА [0...L - 1] быть

хеш-пространство, где ρ(хешированные значения) записываются. Приведенный ниже алгоритм затем определяет приблизительную мощность А.

Процедура FM-Sketch: для i в 0 до L - 1 выполнить BITMAP [i]: = 0 конец для x в A: выполнить Index: = ρ (hash (x)), если BITMAP [index] = 0, то BITMAP [index ]: = 1 конец, если конец для B: = Позиция крайнего левого бита 0 BITMAP [] вернуть 2 ^ B

Если есть N отдельные элементы в потоке данных.

  • За тогда БИТОВАЯ КАРТА[я] конечно 0
  • За тогда БИТОВАЯ КАРТА[я] конечно 1
  • За тогда БИТОВАЯ КАРТА[я] представляет собой бахрому из нулей и единиц
K-алгоритм минимального значения

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

Bar-Yossef et al. в [9] представил алгоритм k-минимального значения для определения количества отдельных элементов в потоке данных. Они использовали аналогичную хеш-функцию час который можно нормировать на [0,1] как . Но они установили предел т количеству значений в хэш-пространстве. Значение т предполагается порядка (т.е. меньшее значение приближения ε требует большего т). Алгоритм KMV сохраняет только т-маленькие значения хеш-функции в хеш-пространстве. В конце концов м прибыли значения потока, используется для расчета. То есть в почти однородном хэш-пространстве они ожидают не менее т элементы должны быть меньше чем .

Процедура 2 K-Minimum Value Инициализировать первые t значений KMV для a в a1 в do, если h (a) 
Анализ сложности KMV

Алгоритм KMV может быть реализован в пространство бит памяти. Каждое значение хеш-функции требует определенного порядка биты памяти. Есть хеш-значения заказа . Время доступа можно сократить, если сохранить т хеш-значения в двоичном дереве. Таким образом, временная сложность будет уменьшена до .

Расчет Fk

Алон и др. в [3] оценки Fk путем определения случайных величин, которые могут быть вычислены в заданном пространстве и времени. Ожидаемое значение случайной величины дает приблизительное значение Fk.

Предположим длину последовательности м известно заранее.

Создайте случайную величину Икс следующее:

  • Выбирать ап быть случайным членом последовательности А с индексом в п,
  • Позволять , представляет количество вхождений л внутри членов последовательности А следующий ап.
  • Случайная переменная .

Предполагать S1 быть в порядке и S2 быть в порядке . Алгоритм принимает S2 случайная переменная Y1, Y2, ..., YS2 и выводит медианное значение Y . Где Yя это среднее значение Иксijгде 1 ≤ jS1.

Теперь вычислим математическое ожидание случайной величины. E(Икс).

Сложность Fk

Из алгоритма расчета Fk обсуждалось выше, мы видим, что каждая случайная величина Икс хранит стоимость ап и р. Итак, чтобы вычислить Икс нам нужно только поддерживать бревно(п) биты для хранения ап и бревно(п) биты для хранения р. Общее количество случайной величины Икс будет .

Следовательно, общая сложность пространства, занимаемого алгоритмом, имеет порядок

Более простой подход к расчету F2

Предыдущий алгоритм вычисляет в порядке биты памяти. Алон и др. в [3] упростил этот алгоритм, используя четырехмерную независимую случайную величину со значениями, сопоставленными с .

Это еще больше снижает сложность расчета к

Частые элементы

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

Более формально зафиксируем некоторую положительную константу c > 1, пусть длина потока будет м, и разреши жя обозначают частоту значения я в потоке. Проблема частых элементов заключается в том, чтобы вывести набор { я | жя > м / ц}.[12]

Некоторые известные алгоритмы:

Обнаружение событий

Обнаружение событий в потоках данных часто выполняется с использованием алгоритма сильных ударов, как указано выше: наиболее частые элементы и их частота определяются с использованием одного из этих алгоритмов, затем наибольшее увеличение по сравнению с предыдущим моментом времени регистрируется как тенденция. Этот подход можно улучшить, используя экспоненциально взвешенные скользящие средние и дисперсия для нормализации.[13]

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

Подсчет количества отдельных элементов в потоке (иногда называемыйF0 момент) - еще одна хорошо изученная задача, первый алгоритм для которой был предложен Флажолетом и Мартином. В 2010, Дэниел Кейн, Джелани Нельсон и Дэвид Вудрафф нашли асимптотически оптимальный алгоритм для этой задачи.[14] Оно использует О(ε2 + журнал d) пространство, с О(1) наихудшее время обновления и отчетности, а также универсальные хэш-функции и р-мудро независимое семейство хешей, где р = Ω (журнал (1 /ε) / журнал журнал (1 /ε)).

Энтропия

(Эмпирическая) энтропия набора частот определяется как , куда .

Оценка этого количества в потоке была сделана:

Онлайн обучение

Изучите модель (например, классификатор) за один проход по обучающей выборке.


Нижние границы

Нижние оценки были вычислены для многих изученных проблем потоковой передачи данных. Безусловно, наиболее распространенной техникой для вычисления этих нижних оценок было использование сложность коммуникации.

Смотрите также

Примечания

  1. ^ Манро, Дж. Ян; Патерсон, Майк (1978). «Отбор и сортировка при ограниченном хранилище». 19-й ежегодный симпозиум по основам компьютерных наук, Анн-Арбор, Мичиган, США, 16-18 октября 1978 г.. Компьютерное общество IEEE. С. 253–258. Дои:10.1109 / SFCS.1978.32.
  2. ^ а б c Флажолет и Мартин (1985)
  3. ^ а б c d Алон, Матиас и Сегеди (1996)
  4. ^ Бэбкок, Брайан; Бабу, Шивнатх; Датар, Маюр; Мотвани, Раджив; Видом, Дженнифер (2002). Модели и проблемы в системах потоков данных. Материалы двадцать первого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. PODS '02. Нью-Йорк, Нью-Йорк, США: ACM. С. 1–16. CiteSeerX 10.1.1.138.190. Дои:10.1145/543613.543615. ISBN 978-1581135077. S2CID 2071130.
  5. ^ Бар-Йосеф, Зив; Jayram, T. S .; Кумар, Рави; Sivakumar, D .; Тревизан, Лука (2002-09-13). Подсчет отдельных элементов в потоке данных. Методы рандомизации и аппроксимации в компьютерных науках. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 1–10. CiteSeerX 10.1.1.12.6276. Дои:10.1007/3-540-45726-7_1. ISBN 978-3540457268.
  6. ^ Гилберт и др. (2001)
  7. ^ Сюй (2007)
  8. ^ Индик, Петр; Вудрафф, Дэвид (2005-01-01). Оптимальные аппроксимации частотных моментов потоков данных.. Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений. STOC '05. Нью-Йорк, Нью-Йорк, США: ACM. С. 202–208. Дои:10.1145/1060590.1060621. ISBN 978-1-58113-960-0. S2CID 7911758.
  9. ^ а б Бар-Йосеф, Зив; Jayram, T. S .; Кумар, Рави; Sivakumar, D .; Тревизан, Лука (13 сентября 2002). Rolim, José D. P .; Вадхан, Салил (ред.). Подсчет отдельных элементов в потоке данных. Конспект лекций по информатике. Springer Berlin Heidelberg. С. 1–10. CiteSeerX 10.1.1.12.6276. Дои:10.1007/3-540-45726-7_1. ISBN 978-3-540-44147-2.
  10. ^ Моррис (1978)
  11. ^ Флажолет, Филипп (1985-03-01). «Примерный подсчет: подробный анализ». BIT вычислительная математика. 25 (1): 113–134. CiteSeerX 10.1.1.64.5320. Дои:10.1007 / BF01934993. ISSN 0006-3835. S2CID 2809103.
  12. ^ Кормод, Грэм (2014). «Сводки Мисра-Гриса». Ин Као, Мин-Ян (ред.). Энциклопедия алгоритмов. Springer США. С. 1–5. Дои:10.1007/978-3-642-27848-8_572-1. ISBN 9783642278488.
  13. ^ Schubert, E .; Weiler, M .; Кригель, Х. (2014). SigniTrend: масштабируемое обнаружение возникающих тем в текстовых потоках с помощью хешированных пороговых значений значимости. Материалы 20-й международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных - KDD '14. С. 871–880. Дои:10.1145/2623330.2623740. ISBN 9781450329569.
  14. ^ Кейн, Нельсон и Вудрафф (2010)

Рекомендации