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

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

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

История [ править ]

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

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

Модели [ править ]

Модель потока данных [ править ]

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

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

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

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

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

Модель раздвижного окна [ править ]

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

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

Оценка [ править ]

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

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

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

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

Приложения [ править ]

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

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

Частотные моменты [ править ]

К частоте момент го набора частот определяется как .${\displaystyle \mathbf {a} }$${\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 . ^[8] Где ε${\displaystyle \Omega (N)}$- параметр аппроксимации, а δ - параметр уверенности. ^[9]

Вычисление F ₀ (отдельные элементы в потоке данных) [ править ]

Алгоритм FM-Sketch [ править ]

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

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

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

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

Let представляет позицию наименее значимого 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] будет

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

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

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

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

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

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

Bar-Yossef et al. в ^[9] введен алгоритм 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), тоУдалить Макс (KMV) из набора KMVВставить h (a) в KMV конец, есликонец для возврат т / макс (кмв)

Анализ сложности 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 путем определения случайных величин, которые могут быть вычислены в заданном пространстве и времени. Ожидаемое значение случайной величины дает приблизительное значение F _k .

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

Постройте случайную величину X следующим образом:

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

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

Теперь вычислите математическое ожидание случайной величины 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 [ править ]

От алгоритма для вычисления F _K обсуждался выше, мы можем видеть , что каждое случайную величину X хранит значение в _р и г . Таким образом, для вычисления X нам нужно поддерживать только войти ( п ) битов для хранения в _р и журнала ( п ) битов для хранения г . Общее количество случайной величины 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)}$

Более простой подход к вычислению F ₂ [ править ]

Предыдущий алгоритм выполняет вычисления в порядке битов памяти. Алон и др. в ^[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}. ^[12]

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

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

Обнаружение событий [ править ]

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

Подсчет отдельных элементов [ править ]

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

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

• МакГрегор и др. ^{[ необходима цитата ]}
• Do Ba et al. ^{[ необходима цитата ]}
• Lall et al. ^{[ необходима цитата ]}
• Чакрабарти и др. ^{[ необходима цитата ]}

Онлайн-обучение [ править ]

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

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

Нижние границы [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Алон, Нога ; Матиас, Йосси ; Сегеди, Марио (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.
• Кейн, Дэниел М .; Нельсон, Джелани; Вудрафф, David P. (2010), оптимальный алгоритм для задачи различных элементов , стручки '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.