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

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

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

История

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

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

Модели

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

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

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

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

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

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

Модель с раздвижным окном

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

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

Оценка

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

Алгоритм FM-эскиза

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

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

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

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

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

$\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 .

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 Если в потоке данных различных элементов.

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

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

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

Бар-Йосеф и др. в представил алгоритм k-минимального значения для определения количества различных элементов в потоке данных. Они использовали аналогичную хэш-функцию h , которую можно нормализовать к [0,1] как $h:[m]\rightarrow [0,1]$. Но они установили ограничение на количество значений в хеш-пространстве. Значение t принимается порядка $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ (т.е. меньшее значение аппроксимации ε требует большего t ). Алгоритм KMV сохраняет только t в хэш-пространстве наименьших значений хеш-функции. После того, как все m значений потока прибыли, $\upsilon =\mathrm {Max} (h(a_{i}))$ используется для расчета $F'_{0}={\dfrac {t}{\upsilon }}$. То есть в почти однородном хэш-пространстве они ожидают, что по крайней мере t элементов будут меньше $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) < Max(KMV) then
        Remove Max(KMV) from KMV set
        Insert h(a) to KMV 
    end if
end for 
return t/Max(KMV)

Анализ сложности КМВ

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

Расчет F _k

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

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

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

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

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

${\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 хранит значения a _p и r . Итак, для вычисления X нам нужно сохранить только биты log( n ) для хранения и _p биты ( n ) log для хранения r . Общее количество случайной величины X будет равно ⁠ $S_{1}*S_{2}$⁠ .

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

Упрощенный подход к расчету F ₂

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

Это еще больше снижает сложность расчета. $F_{2}$ к $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 }.

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

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

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

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

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

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

Энтропия

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

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

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

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

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

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

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

См. также

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

Ссылки

• Алон, Нога ; Матиас, Йоси ; Сегеди, Марио (1999), «Пространственная сложность аппроксимации частотных моментов», Journal of Computer and System Sciences , 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) 9 июля 2017 г. , получено 15 июля 2013 г.
• Гилберт, AC ; Котидис, Ю.; Мутукришнан, С .; Штраус, MJ (2001), «Просмотр вейвлетов в потоках: однопроходные сводки для приблизительных агрегатных запросов» (PDF) , Материалы Международной конференции по очень большим базам данных : 79–88 .
• Кейн, Дэниел М.; Нельсон, Джелани; Вудрафф, Дэвид П. (2010). «Оптимальный алгоритм решения задачи о различных элементах». Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных . ПОДС '10. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 41–52. CiteSeerX   10.1.1.164.142 . дои : 10.1145/1807085.1807094 . ISBN  978-1-4503-0033-9 . S2CID   10006932 . .
• Карп, РМ ; Пападимитриу, Швейцария ; Шенкер, С. (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 , hdl : 1802/2537 , ISBN  978-1595933195 , S2CID   240982 .
• Сюй, Цзюнь (Джим) (2007), Учебное пособие по потоковой передаче сетевых данных (PDF) .
• Хит Д., Касиф С., Косараджу Р., Зальцберг С., Салливан Г., «Изучение вложенных концепций с ограниченным хранилищем», Труды IJCAI'91, Материалы 12-й международной совместной конференции по искусственному интеллекту - Том 2, страницы 777–782, Morgan Kaufmann Publishers Inc. Сан-Франциско, Калифорния, США © 1991 г.
• Моррис, Роберт (1978), «Подсчет большого количества событий в маленьких регистрах», Communications of the ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID   36226357 .