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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Потоковые алгоритмы имеют несколько применений в сетях, таких как мониторинг сетевых соединений для потоков слонов , подсчет количества отдельных потоков, оценка распределения размеров потоков и т. д. ^[8] Они также имеют приложения в базах данных, такие как оценка размера объединения [ ^{необходима ссылка ]} .

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

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

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

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

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

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

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

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

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

${\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}$

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

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

Процедура FM-Sketch: для i в диапазоне от 0 до L − 1 сделать BITMAP[i] := 0 конец для для x в A: сделать Индекс := ρ(хэш(x)) если BITMAP[индекс] = 0 тогда BITMAP[индекс] := 1 конец, если конец для B := Положение самого левого нулевого бита BITMAP[] возврат 2 ^ B

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

• Тогда BITMAP [ i ] определенно равен 0${\displaystyle i\gg \log(N)}$
• Тогда BITMAP [ i ] определенно равен 1${\displaystyle i\ll \log(N)}$
• Тогда BITMAP [ i ] представляет собой полосы из нулей и единиц .${\displaystyle i\approx \log(N)}$

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

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

Процедура 2 K-минимальное значениеИнициализируем первые значения t KMVдля а в а1 к делать если h(a) < Max(KMV), то Удалить Max(KMV) из набора KMV Вставьте h(a) в KMV конец, есликонец длявозврат т/Макс(КМВ)

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

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

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

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

Предположим, что S ₁ имеет порядок , а S ₂ имеет порядок . Алгоритм берет случайную величину S ₂ и выводит медиану . Где Y _i — среднее значение X _ij , где 1 ≤ j ≤ S ₁ .${\displaystyle O(n^{1-1/k}/\lambda ^{2})}$${\displaystyle O(\log(1/\varepsilon ))}$${\displaystyle Y_{1},Y_{2},...,Y_{S2}}$${\displaystyle Y}$

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

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

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

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

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

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

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

Более формально, зафиксируем некоторую положительную константу c > 1, пусть длина потока будет m , и пусть f _i обозначает частоту значения i в потоке. Проблема частых элементов заключается в выводе набора { i | f i _> m/c }. ^[13]

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

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

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

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

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

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

• Хеширование функций
• Стохастический градиентный спуск

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

• Анализ потока данных
• Кластеризация потока данных
• Онлайн алгоритм
• Потоковая обработка
• Последовательный алгоритм

• Алон, Нога ; Матиас, Йосси ; Сегеди, Марио (1999), «Пространственная сложность аппроксимации частотных моментов», Журнал компьютерных и системных наук , 58 (1): 137–147, doi : 10.1006/jcss.1997.1545 , ISSN  0022-0000. Впервые опубликовано как Алон, Нога; Матиас, Йосси; Сегеди, Марио (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, заархивировано из оригинала (PDF) 2017-07-09 , извлечено 2013-07-15.
• Гилберт, А.С .; Котидис, И.; Мутукришнан, С.; Штраус, М.Дж. (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..
• Карп, Р. М.; Пападимитриу , Ч. Х .; Шенкер, С. (2003), «Простой алгоритм поиска часто встречающихся элементов в потоках и пакетах», ACM Transactions on Database Systems , 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, hdl : 1802/2537 , ISBN 978-1595933195, S2CID  240982^{[ постоянная неработающая ссылка ]} .
• Сюй, Цзюнь (Джим) (2007), Учебное пособие по потоковой передаче данных по сети (PDF).
• Хит, Д., Касиф, С., Косараджу, Р., Зальцберг, С., Салливан, Г., «Изучение вложенных концепций с ограниченным объемом памяти», Труды IJCAI'91 Труды 12-й международной объединенной конференции по искусственному интеллекту - Том 2, Страницы 777–782, Morgan Kaufmann Publishers Inc. Сан-Франциско, Калифорния, США ©1991
• Моррис, Роберт (1978), «Подсчет большого количества событий в небольших регистрах», Сообщения ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID  36226357.