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

редактировать

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

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

СОДЕРЖАНИЕ

1 История
2 модели
- 2.1 Модель потока данных
- 2.2 Модели турникетов и кассовых аппаратов
- 2.3 Модель с раздвижным окном
3 Оценка
4 Приложения
5 Некоторые проблемы с потоковой передачей
- 5.1 Частотные моменты
  - 5.1.1 Расчет частотных моментов
    - 5.1.1.1 Вычисление F 0 (отдельные элементы в DataStream)
      - 5.1.1.1.1 Алгоритм FM-Sketch
      - 5.1.1.1.2 Алгоритм K- минимального значения
      - 5.1.1.1.3 Анализ сложности KMV
    - 5.1.1.2 Расчет F k
      - 5.1.1.2.1 Сложность F k
      - 5.1.1.2.2 Более простой подход к вычислению F 2
- 5.2 Частые элементы
- 5.3 Обнаружение событий
- 5.4 Подсчет отдельных элементов
- 5.5 Энтропия
- 5.6 Онлайн-обучение
6 Нижние оценки
7 См. Также
8 Примечания
9 ссылки

История

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

Полупотоковые алгоритмы были введены в 2005 году как ослабление потоковых алгоритмов для графов, в которых разрешенное пространство линейно по количеству вершин n, но только логарифмически по количеству ребер m. Это ослабление все еще имеет значение для плотных графов и может решить интересные проблемы (например, связность), которые неразрешимы в пространстве. ${\ Displaystyle о (п)}$ $на)$

Модели

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

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

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

Большая часть литературы по потоковой передаче посвящена вычислению статистических данных о частотных распределениях, которые слишком велики для хранения. Для этого класса проблем существует вектор (инициализированный нулевым вектором), обновления которого представлены ему в потоке. Целью этих алгоритмов является вычисление функций с использованием значительно меньшего пространства, чем требуется для точного представления. Существует две распространенных модели обновления таких потоков, которые называются «кассовый аппарат» и «турникет». ${\ Displaystyle \ mathbf {а} = (а_ {1}, \ точки, а_ {п})}$ $\ mathbf {a} = (a_ {1}, \ dots, a_ {n})$ ${\ displaystyle \ mathbf {0}}$ $\ mathbf {0}$ ${\ Displaystyle \ mathbf {а}}$ $\ mathbf {а}$ ${\ Displaystyle \ mathbf {а}}$ $\ mathbf {а}$

В модели кассового аппарата каждое обновление имеет форму, поэтому она увеличивается на некоторое положительное целое число. Примечательным частным случаем является когда (разрешены только вставки единиц). ${\ Displaystyle \ langle я, с \ rangle}$ $\ langle i, c \ rangle$ ${\ displaystyle a_ {i}}$ $а_ {i}$ ${\ displaystyle c}$ $c$ ${\ displaystyle c = 1}$ $с = 1$

В модели турникета каждое обновление имеет форму, которая увеличивается на некоторое (возможно отрицательное) целое число. В модели «строгий турникет» ни в какое время не может быть меньше нуля. ${\ Displaystyle \ langle я, с \ rangle}$ $\ langle i, c \ rangle$ ${\ displaystyle a_ {i}}$ $а_ {i}$ ${\ displaystyle c}$ $c$ ${\ displaystyle a_ {i}}$ $а_ {i}$

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

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

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

Оценка

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

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

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

Если алгоритм представляет собой приближенный алгоритм, то еще одним ключевым фактором является точность ответа. Точность часто указывается как приближение, что означает, что алгоритм достигает ошибки, меньшей вероятности. ${\ displaystyle (\ epsilon, \ delta)}$ $(\ эпсилон, \ дельта)$ ${\ displaystyle \ epsilon}$ $\ epsilon$ ${\ displaystyle 1- \ delta}$ $1- \ дельта$

Приложения

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

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

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

К частоте момент го набора частот определяется как. ${\ Displaystyle \ mathbf {а}}$ $\ mathbf {а}$ ${\ Displaystyle F_ {k} (\ mathbf {a}) = \ sum _ {я = 1} ^ {n} a_ {i} ^ {k}}$ ${\ Displaystyle F_ {k} (\ mathbf {a}) = \ sum _ {я = 1} ^ {n} a_ {i} ^ {k}}$

Первый момент - это просто сумма частот (то есть общее количество). Второй момент полезен для вычисления статистических свойств данных, таких как коэффициент вариации Джини. определяется как частота наиболее частых элементов. ${\ displaystyle F_ {1}}$ $F_ {1}$ ${\ displaystyle F_ {2}}$ $F_ {2}$ ${\ displaystyle F _ {\ infty}}$ $F _ {\ infty}$

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

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

Прямой подход к нахождению частотных моментов требует поддержки регистра m i для всех различных элементов a i ∈ (1,2,3,4,..., N), что требует по крайней мере памяти порядка. Но у нас есть ограничения по объему, и нам нужен алгоритм, который выполняет вычисления в гораздо меньшем объеме памяти. Этого можно добиться, используя приблизительные значения вместо точных значений. Алгоритм, который вычисляет ( ε, δ) аппроксимацию F k, где F ' k - ( ε, δ) -приближенное значение F k. Где ε - параметр аппроксимации, а δ - параметр достоверности. ${\ displaystyle \ Omega (N)}$ $\ Омега (N)$

Вычисление F 0 (отдельные элементы в DataStream)

Основная статья: Проблема с подсчетом

Алгоритм FM-Sketch

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

{\ displaystyle h: [м] \ rightarrow [0,2 ^ {L} -1]}

ч: [м] \ rightarrow [0,2 ^ {L} -1]

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

{\ displaystyle y = \ sum _ {k \ geq 0} \ mathrm {bit} (y, k) * 2 ^ {k}}

y = \ sum _ {k \ geq 0} \ mathrm {bit} (y, k) * 2 ^ {k}

Let представляет позицию наименее значимого 1-бита в двоичном представлении y i с подходящим соглашением для. ${\ displaystyle \ rho (y)}$ $\ rho (y)$ ${\ displaystyle \ rho (0)}$ $\ rho (0)$

{\ displaystyle \ rho (y) = {\ begin {cases} \ mathrm {Min} (k: \ mathrm {bit} (y, k) == 1) amp; {\ text {if}} ygt; 0 \\ L amp; {\ text {if}} y = 0 \ end {case}}}

{\ displaystyle \ rho (y) = {\ begin {cases} \ mathrm {Min} (k: \ mathrm {bit} (y, k) == 1) amp; {\ text {if}} ygt; 0 \\ L amp; {\ text {if}} y = 0 \ end {case}}}

Пусть A будет последовательностью потока данных длины M, мощность которой необходимо определить. Пусть BITMAP [0... L - 1] будет

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

Procedure FM-Sketch: for i in 0 to L − 1 do BITMAP[i] := 0 end for for x in A: do Index := ρ(hash(x)) if BITMAP[index] = 0 then BITMAP[index] := 1 end if end for B := Position of left most 0 bit of BITMAP[] return 2 ^ B

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

Ибо тогда BITMAP [ i ], безусловно, равен 0 ${\ Displaystyle я \ gg \ журнал (N)}$ $я \ gg \ log (N)$
Ибо тогда BITMAP [ i ] определенно равен 1 ${\ Displaystyle я \ ll \ журнал (N)}$ $я \ ll \ log (N)$
Для затем BITMAP [ я ] является бахрома из 0 и 1. ${\ Displaystyle я \ приблизительно \ журнал (N)}$ $я \ приблизительно \ журнал (N)$

K- алгоритм минимального значения

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

Bar-Yossef et al. во введен алгоритм k-минимального значения для определения количества отдельных элементов в потоке данных. Они использовали аналогичную хеш-функцию h, которую можно нормировать на [0,1] как. Но они установили ограничение t на количество значений в хеш-пространстве. Предполагается, что значение t имеет порядок (т. Е. Меньшее значение аппроксимации ε требует большего t). Алгоритм KMV сохраняет в хэш-пространстве только t -маленьких значений хеш-функции. После того, как все m значений потока прибыли, используется для вычисления. То есть в почти однородном хэш-пространстве они ожидают, что по крайней мере t элементов будет меньше, чем. ${\ displaystyle h: [м] \ rightarrow [0,1]}$ $h: [m] \ rightarrow [0,1]$ ${\ displaystyle O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)}$ $O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)$ ${\ Displaystyle \ upsilon = \ mathrm {Макс} (ч (а_ {я}))}$ $\ upsilon = \ mathrm {Макс} (h (a_ {i}))$ ${\ displaystyle F '_ {0} = {\ dfrac {t} {\ upsilon}}}$ $F '_ {0} = {\ dfrac {t} {\ upsilon}}$ ${\ displaystyle O \ left ({\ dfrac {t} {F_ {0}}} \ right)}$ $O \ left ({\ dfrac {t} {F_ {0}}} \ right)$

Procedure 2 K-Minimum Value Initialize first t values of KMV for a in a1 to an do if h(a) lt; Max(KMV) then Remove Max(KMV) from KMV set Insert h(a) to KMV end if end for return t/Max(KMV)

Анализ сложности KMV

Алгоритм KMV может быть реализован в пространстве битов памяти. Каждое значение хеш-функции требует пространства битов памяти порядка. Есть хеш-значения заказа. Время доступа можно сократить, если мы сохраним хеш-значения t в двоичном дереве. Таким образом, временная сложность будет уменьшена до. ${\ Displaystyle О \ влево (\ влево ({\ dfrac {1} {\ varepsilon _ {2}}} \ вправо) \ CDOT \ log (м) \ вправо)}$ $O \ left (\ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right) \ cdot \ log (m) \ right)$ ${\ Displaystyle О (\ журнал (м))}$ ${\ Displaystyle О (\ журнал (м))}$ ${\ displaystyle O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)}$ $O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)$ ${\ Displaystyle О \ влево (\ журнал \ влево ({\ dfrac {1} {\ varepsilon}} \ вправо) \ CDOT \ журнал (м) \ вправо)}$ $O \ left (\ log \ left ({\ dfrac {1} {\ varepsilon}} \ right) \ cdot \ log (m) \ right)$

Расчет F k

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

Предположим, что длина последовательности m известна заранее. Затем создайте случайную величину X следующим образом:

Выберите р случайный член последовательности А с индексом на р, ${\ displaystyle a_ {p} = l \ in (1,2,3, \ ldots, n)}$ $a_ {p} = l \ in (1,2,3, \ ldots, n)$
Пусть, представляет количество вхождений l в членах последовательности A, следующей за p. ${\ displaystyle r = | \ {q: q \ geq p, a_ {q} = l \} |}$ ${\ displaystyle r = | \ {q: q \ geq p, a_ {q} = l \} |}$
Случайная величина. ${\ Displaystyle Х = м (г ^ {к} - (г-1) ^ {к})}$ $X = m (r ^ {k} - (r-1) ^ {k})$

Предположим, что S 1 порядка, а S 2 порядка. Алгоритм берет случайную величину S 2 и выводит медиану. Где Y i - среднее значение X ij, где 1 ≤ j ≤ S 1. ${\ Displaystyle О (п ^ {1-1 / к} / \ лямбда ^ {2})}$ $О (п ^ {1-1 / к} / \ лямбда ^ {2})$ ${\ Displaystyle О (\ журнал (1 / \ varepsilon))}$ $О (\ журнал (1 / \ varepsilon))$ ${\ displaystyle Y_ {1}, Y_ {2},..., Y_ {S2}}$ ${\ displaystyle Y_ {1}, Y_ {2},..., Y_ {S2}}$ ${\ displaystyle Y}$ $Y$

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

{\ displaystyle {\ begin {array} {lll} E (X) amp; = amp; \ sum _ {i = 1} ^ {n} \ sum _ {i = 1} ^ {m_ {i}} (j ^ { k} - (j-1) ^ {k}) \\ amp; = amp; {\ frac {m} {m}} [(1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {1} ^ {k} - (m_ {1} -1) ^ {k})) \\ amp;amp; \; + \; (1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {2} ^ {k} - (m_ {2} -1) ^ {k})) + \ ldots \\ amp;amp; \; + \; (1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {n} ^ {k} - (m_ {n} -1) ^ {k}))] \\ amp; = amp; \ sum _ {i = 1} ^ {n} m_ {i} ^ {k} = F_ {k} \ end {array}}}

{\ displaystyle {\ begin {array} {lll} E (X) amp; = amp; \ sum _ {i = 1} ^ {n} \ sum _ {i = 1} ^ {m_ {i}} (j ^ { k} - (j-1) ^ {k}) \\ amp; = amp; {\ frac {m} {m}} [(1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {1} ^ {k} - (m_ {1} -1) ^ {k})) \\ amp;amp; \; + \; (1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {2} ^ {k} - (m_ {2} -1) ^ {k})) + \ ldots \\ amp;amp; \; + \; (1 ^ {k} + (2 ^ {k} -1 ^ {k}) + \ ldots + (m_ {n} ^ {k} - (m_ {n} -1) ^ {k}))] \\ amp; = amp; \ sum _ {i = 1} ^ {n} m_ {i} ^ {k} = F_ {k} \ end {array}}}

Сложность F k

От алгоритма для вычисления F K обсуждался выше, мы можем видеть, что каждое случайную величину X хранит значение в р и г. Таким образом, для вычисления X нам нужно поддерживать только войти ( п) битов для хранения в р и журнала ( п) битов для хранения г. Общее количество случайной величины X будет равно. ${\ displaystyle S_ {1} * S_ {2}}$ ${\ displaystyle S_ {1} * S_ {2}}$

Следовательно, общая сложность пространства, занимаемого алгоритмом, имеет порядок ${\ displaystyle O \ left ({\ dfrac {k \ log {1 \ over \ varepsilon}} {\ lambda ^ {2}}} n ^ {1- {1 \ over k}} \ left (\ log n + \ журнал m \ right) \ right)}$ ${\ displaystyle O \ left ({\ dfrac {k \ log {1 \ over \ varepsilon}} {\ lambda ^ {2}}} n ^ {1- {1 \ over k}} \ left (\ log n + \ журнал m \ right) \ right)}$

Более простой подход к вычислению F 2

Предыдущий алгоритм выполняет вычисления в порядке битов памяти. Алон и др. в упрощенном алгоритме с использованием четырехмерной независимой случайной величины со значениями, сопоставленными с. ${\ displaystyle F_ {2}}$ $F_ {2}$ ${\ Displaystyle О ({\ sqrt {n}} (\ журнал м + \ журнал п))}$ $О ({\ sqrt {n}} (\ log m + \ log n))$ ${\ displaystyle \ {- 1,1 \}}$ $\ {- 1,1 \}$

Это дополнительно снижает сложность вычислений до ${\ displaystyle F_ {2}}$ $F_ {2}$ ${\ displaystyle O \ left ({\ dfrac {\ log {1 \ over \ varepsilon}} {\ lambda ^ {2}}} \ left (\ log n + \ log m \ right) \ right)}$ ${\ displaystyle O \ left ({\ dfrac {\ log {1 \ over \ varepsilon}} {\ lambda ^ {2}}} \ left (\ log n + \ log m \ right) \ right)}$

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

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

Более формально, зафиксируйте некоторую положительную константу c gt; 1, пусть длина потока равна m, и пусть fi обозначает частоту значения i в потоке. Проблема частых элементов состоит в том, чтобы вывести набор { i | fi gt; m / c}.

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

Алгоритм большинства голосов Бойера – Мура
Счетчик-мин эскиз
Подсчет с потерей
Многоступенчатые фильтры Блума
Резюме Мисра – Гриса

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

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

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

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

Энтропия

(Эмпирическая) энтропия набора частот определяется как, где. ${\ Displaystyle \ mathbf {а}}$ $\ mathbf {а}$ ${\ displaystyle F_ {k} (\ mathbf {a}) = \ sum _ {i = 1} ^ {n} {\ frac {a_ {i}} {m}} \ log {\ frac {a_ {i} } {m}}}$ $F_ {k} (\ mathbf {a}) = \ sum _ {i = 1} ^ {n} {\ frac {a_ {i}} {m}} \ log {\ frac {a_ {i}} {m }}$ ${\ Displaystyle м = \ сумма _ {я = 1} ^ {п} а_ {я}}$ $m = \ sum _ {i = 1} ^ {n} a_ {i}$

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

Основная статья: Машинное обучение онлайн

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

Нижние оценки

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

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

Примечания

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

использованная литература

Алон, Нога ; Матиас, Йосси ; Сегеди, Марио (1999), "Пространственная сложность аппроксимации частотных моментов", Журнал компьютерных и системных наук, 58 (1): 137–147, DOI : 10.1006 / jcss.1997.1545, ISSN 0022-0000. Впервые опубликовано как Alon, Noga; Матиас, Йосси; Сегеди, Марио (1996), "Пространственная сложность аппроксимации частотных моментов", Труды 28-го симпозиума ACM по теории вычислений (STOC 1996), стр. 20–29, CiteSeerX 10.1.1.131.4984, doi : 10.1145 / 237814.237823, ISBN 978-0-89791-785-8, S2CID 1627911.
Бэбкок, Брайан; Бабу, Шивнатх; Датар, Маюр; Мотвани, Раджив ; Видом, Дженнифер (2002), «Модели и проблемы в системах потоков данных», Труды 21-го Симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PODS 2002) (PDF), стр. 1–16, CiteSeerX 10.1. 1.138.190, DOI : 10,1145 / 543613,543615, ISBN 978-1581135077, S2CID 2071130.
Гилберт, AC ; Kotidis, Y.; Muthukrishnan, S.; Штраус, MJ (2001), "Серфинговые вейвлеты на потоках: сводные данные за один проход для приближенных агрегированных запросов" (PDF), Труды Международной конференции по очень большим базам данных: 79–88.
Кейн, Дэниел М.; Нельсон, Джелани; Вудрафф, Дэвид П. (2010). «Оптимальный алгоритм для проблемы отдельных элементов». Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. PODS '10. Нью-Йорк, Нью-Йорк, США: ACM. С. 41–52. CiteSeerX 10.1.1.164.142. DOI : 10.1145 / 1807085.1807094. ISBN 978-1-4503-0033-9. S2CID 10006932. .
Карп, РМ ; Пападимитриу, Швейцария ; Шенкер, S. (2003), "Простой алгоритм для поиска частых элементов в потоках и мешков", ACM Сделки по системам баз данных, 28 (1): 51-55, CiteSeerX 10.1.1.116.8530, DOI : 10,1145 / 762471,762473, S2CID 952840.
Лалл, Эшвин; Секар, Вьяс; Огихара, Мицунори; Сюй, Цзюнь; Чжан, Хуэй (2006), "Алгоритмы потоковой передачи данных для оценки энтропии сетевого трафика", Труды совместной международной конференции по измерению и моделированию компьютерных систем (ACM SIGMETRICS 2006) (PDF), стр. 145, DOI : 10,1145 / 1140277,1140295, ЛВП : 1802/2537, ISBN 978-1595933195, S2CID 240982.
Сюй, Джун (Джим) (2007), Учебное пособие по потоковой передаче сетевых данных (PDF).
Хит, Д., Касиф, С., Косараджу, Р., Зальцберг, С., Салливан, Г., «Изучение вложенных концепций с ограниченным хранилищем», Материалы 12-й международной совместной конференции по искусственному интеллекту. 2, Pages 777-782, Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США © 1991
Моррис, Роберт (1978), "Подсчет большого количества событий в небольших регистрах", коммуникации АСМА, 21 (10): 840-842, DOI : 10,1145 / 359619,359627, S2CID 36226357.