В информатике , потоковые алгоритмы алгоритмы для обработки потоков данных , в котором входные данные представлены в виде последовательности элементов , и могут быть рассмотрены лишь в нескольких проходов ( как правило , только один ). В большинстве моделей эти алгоритмы имеют доступ к ограниченной памяти (обычно логарифмической по размеру и / или максимальному значению в потоке). У них также может быть ограниченное время обработки для каждого элемента.
Эти ограничения могут означать, что алгоритм дает приблизительный ответ на основе сводки или «наброска» потока данных.
История
Хотя алгоритмы потоковой передачи уже были изучены Манро и Патерсоном [1] еще в 1978 году, а также Филиппом Флажолетом и Дж. Найджелом Мартином в 1982/83 годах [2], область потоковых алгоритмов была впервые формализована и популяризирована в 1996 году. статья Ноги Алон , Йоси Матиас и Марио Сегеди . [3] За эту статью авторы позже выиграли премию Гёделя в 2005 году «за их фундаментальный вклад в потоковые алгоритмы». С тех пор большой объем работы был сосредоточен на алгоритмах потоковой передачи данных, охватывающих широкий спектр областей информатики, таких как теория, базы данных, сети и обработка естественного языка.
Полупотоковые алгоритмы были введены в 2005 году как ослабление потоковых алгоритмов для графов [4], в которых разрешенное пространство линейно по количеству вершин n , но только логарифмически по количеству ребер m . Это ослабление все еще имеет значение для плотных графов и может решить интересные проблемы (например, связность), которые неразрешимы в космос.
Модели
Модель потока данных
В модели потока данных некоторые или все входные данные представлены как конечная последовательность целых чисел (из некоторой конечной области), которая обычно недоступна для произвольного доступа , но вместо этого поступает по одному в «потоке». [5] Если поток имеет длину n, а размер домена - m , алгоритмы обычно ограничиваются использованием пространства, которое является логарифмическим по m и n . Обычно они могут сделать лишь небольшое постоянное количество проходов над потоком, иногда всего один . [6]
Модели турникетов и кассовых аппаратов
Большая часть литературы по потоковой передаче посвящена вычислению статистических данных о частотных распределениях, которые слишком велики для хранения. Для этого класса задач существует вектор (инициализируется нулевым вектором ), для которого в потоке представлены обновления. Цель этих алгоритмов - вычислить функции используя значительно меньше места, чем нужно для представления точно. Существуют две распространенные модели обновления таких потоков, которые называются «кассовый аппарат» и «турникет». [7]
В модели кассового аппарата каждое обновление имеет вид , чтобы увеличивается на некоторое положительное целое число . Примечательный частный случай - это когда (разрешены только вставки единиц).
В модели турникета каждое обновление имеет вид , чтобы увеличивается на некоторое (возможно отрицательное) целое число . В модели «строгий турникет» нет в любой момент может быть меньше нуля.
Модель раздвижного окна
В нескольких статьях также рассматривается модель «скользящего окна». [ необходима цитата ] В этой модели интересующая функция вычисляет окно фиксированного размера в потоке. По мере продвижения потока элементы из конца окна удаляются из рассмотрения, а новые элементы из потока занимают их место.
Помимо вышеупомянутых задач, связанных с частотами, изучались также некоторые другие типы задач. Многие проблемы с графами решаются в настройке, в которой матрица смежности или список смежности графа передаются в неизвестном порядке. Есть также некоторые проблемы, которые очень зависят от порядка потока (т. Е. Асимметричные функции), такие как подсчет количества инверсий в потоке и поиск самой длинной возрастающей подпоследовательности. [ необходима цитата ]
Оценка
Производительность алгоритма, работающего с потоками данных, измеряется тремя основными факторами:
- Число проходов, которые алгоритм должен сделать над потоком.
- Доступная память.
- Время работы алгоритма.
Эти алгоритмы имеют много общего с онлайн-алгоритмами, поскольку оба требуют принятия решений до того, как будут доступны все данные, но они не идентичны. Алгоритмы потока данных имеют только ограниченную доступную память, но они могут откладывать действие до прибытия группы точек, в то время как онлайн-алгоритмы должны предпринимать действия сразу после прибытия каждой точки.
Если алгоритм представляет собой приближенный алгоритм, то еще одним ключевым фактором является точность ответа. Точность часто указывается как приближение, означающее, что алгоритм достигает ошибки менее чем с вероятностью .
Приложения
Алгоритмы потоковой передачи имеют несколько применений в сетях, таких как мониторинг сетевых каналов на предмет наличия слоновьих потоков , подсчет количества отдельных потоков, оценка распределения размеров потоков и т. Д. [8] У них также есть приложения в базах данных, такие как оценка размера соединения [ необходима цитата ] .
Некоторые проблемы с потоковой передачей
Частотные моменты
К частоте момент го набора частот определяется как .
Первый момент представляет собой просто сумму частот (т. е. общее количество). Второй моментполезен для вычисления статистических свойств данных, таких как коэффициент вариации Джини . определяется как частота наиболее частых элементов.
Основополагающая статья Алона, Матиаса и Сегеди была посвящена проблеме оценки частотных моментов. [ необходима цитата ]
Расчет частотных моментов
Прямой подход к нахождению частотных моментов требует поддержки регистра m i для всех различных элементов a i ∈ (1,2,3,4, ..., N ), что требует по крайней мере памяти порядка. [3] Но у нас есть ограничения по объему и требуется алгоритм, который выполняет вычисления в гораздо меньшем объеме памяти. Этого можно добиться, используя приблизительные значения вместо точных значений. Алгоритм, который вычисляет ( ε, δ ) аппроксимацию F k , где F ' k - ( ε, δ ) -приближенное значение F k . [9] Где ε - параметр аппроксимации, а δ - параметр достоверности. [10]
Вычисление F 0 (отдельные элементы в потоке данных)
Алгоритм FM-Sketch
Flajolet et al. в [2] введен вероятностный метод подсчета, вдохновленный статьей Роберта Морриса . [11] Моррис в своей статье говорит, что если требование точности отброшено, счетчик n может быть заменен счетчиком log n, который может храниться в log log n битах. [12] Flajolet et al. в [2] этот метод был улучшен за счет использования хэш-функции h, которая, как предполагается, равномерно распределяет элемент в хеш-пространстве (двоичная строка длины L ).
Пусть бит ( y, k ) представляет k-й бит в двоичном представлении y
Позволять представляет позицию наименее значимого 1-бита в двоичном представлении y i с подходящим соглашением для.
Пусть 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
- Для тогда BITMAP [ i ] определенно равен 1
- Для тогда BITMAP [ i ] представляет собой границу нулей и единиц
K-алгоритм минимального значения
Предыдущий алгоритм описывает первую попытку аппроксимировать F 0 в потоке данных Флайолетом и Мартином. Их алгоритм выбирает случайную хеш-функцию, которая, как они предполагают, равномерно распределяет хеш-значения в хеш-пространстве.
Bar-Yossef et al. в [10] введен алгоритм k-минимального значения для определения количества различных элементов в потоке данных. Они использовали аналогичную хеш-функцию h, которую можно нормализовать до [0,1] как. Но они установили ограничение t на количество значений в хеш-пространстве. Значение t принимается порядка(т.е. меньшее значение аппроксимации ε требует большего t ). Алгоритм KMV сохраняет в хэш-пространстве только t -маленьких значений хеш-функции. После того, как все m значений потока прибыли, используется для расчета. То есть в почти однородном хэш-пространстве они ожидают, что как минимум t элементов будет меньше, чем.
Процедура 2 K-Минимальное значениеИнициализировать первые значения t KMV для а в а1 до доесли h (a)Удалить Макс (KMV) из набора KMVВставить h (a) в KMV конец, есликонец для возврат т / макс (кмв)
Анализ сложности KMV
Алгоритм KMV может быть реализован в пространство битов памяти. Каждое значение хеш-функции требует определенного порядкабиты памяти. Есть хеш-значения заказа. Время доступа можно сократить, если мы сохраним хеш-значения t в двоичном дереве. Таким образом, временная сложность будет снижена до.
Расчет F k
Alon et al. оценивает F k путем определения случайных величин, которые могут быть вычислены в заданном пространстве и времени. [3] Ожидаемое значение случайных величин дает приблизительное значение F k .
Предположим, что длина последовательности m известна заранее. Затем создайте случайную величину X следующим образом:
- Выберите р случайный член последовательности А с индексом на р ,
- Позволять , представляет количество вхождений l в членах последовательности A, следующей за p .
- Случайная переменная .
Предположим, что S 1 порядкаи S 2 будет порядка. Алгоритм принимает S 2 случайная величина Y 1 , Y 2 , ..., Y S 2 и выводит средний Y . Где Y i - среднее значение X ij, где 1 ≤ j ≤ S 1 .
Теперь вычислите математическое ожидание случайной величины E ( X ) .
Сложность F k
От алгоритма для вычисления F K обсуждался выше, мы можем видеть , что каждое случайную величину X хранит значение в р и г . Таким образом, для вычисления X нам нужно поддерживать только войти ( п ) битов для хранения в р и журнала ( п ) битов для хранения г . Общее количество случайной величины X будет.
Следовательно, общая сложность пространства, занимаемого алгоритмом, имеет порядок
Более простой подход к вычислению F 2
Предыдущий алгоритм вычисляет в порядке биты памяти. Alon et al. в [3] упростил этот алгоритм, используя четырехмерную независимую случайную величину со значениями, отображенными в.
Это дополнительно снижает сложность расчета к
Частые элементы
В модели потока данных проблема частых элементов состоит в том, чтобы вывести набор элементов, которые составляют больше, чем некоторая фиксированная часть потока. Особым случаем является проблема большинства , которая состоит в том, чтобы определить, составляет ли какое-либо значение большую часть потока.
Более формально, зафиксируйте некоторую положительную константу c > 1, пусть длина потока будет m , и пусть f i обозначает частоту значения i в потоке. Проблема частых элементов состоит в том, чтобы вывести набор { i | f i > m / c}. [13]
Некоторые известные алгоритмы:
- Алгоритм большинства голосов Бойера – Мура
- Счетчик-мин эскиз
- Подсчет с потерей
- Многоступенчатые фильтры Блума
- Резюме Мисры – Гриса
Обнаружение событий
Обнаружение событий в потоках данных часто выполняется с использованием алгоритма сильных ударов, как указано выше: наиболее часто встречающиеся элементы и их частота определяются с использованием одного из этих алгоритмов, а затем наибольшее увеличение по сравнению с предыдущим моментом времени регистрируется как тенденция. Этот подход можно усовершенствовать, используя экспоненциально взвешенные скользящие средние и дисперсию для нормализации. [14]
Подсчет отдельных элементов
Подсчет количества различных элементов в потоке (иногда называемый моментом F 0 ) - еще одна хорошо изученная проблема. Первый алгоритм для этого был предложен Флажолетом и Мартином. В 2010 году Дэниел Кейн , Джелани Нельсон и Дэвид Вудрафф нашли асимптотически оптимальный алгоритм для этой проблемы. [15] Он использует пространство O ( ε 2 + log d ) , время обновления и отчетности в худшем случае O (1) , а также универсальные хеш-функции и независимое по r семейство хешей, где r = Ω (log (1 / ε ) / log log (1 / ε )) .
Энтропия
(Эмпирическая) энтропия набора частот определяется как , где .
Онлайн обучение
Изучите модель (например, классификатор ) за один проход по обучающей выборке.
- Хеширование функций
- Стохастический градиентный спуск
Нижние оценки
Нижние оценки были вычислены для многих изученных проблем потоковой передачи данных. Безусловно, наиболее распространенным методом вычисления этих нижних оценок является использование сложности связи . [ необходима цитата ]
Смотрите также
- Интеллектуальный анализ потока данных
- Кластеризация потока данных
- Онлайн алгоритм
- Потоковая обработка
- Последовательный алгоритм
Заметки
- ^ Манро, Дж. Ян; Патерсон, Майк (1978). «Отбор и сортировка с ограниченным объемом памяти». Девятнадцатый ежегодный симпозиум по Основы информатики, Анн - Арбор, штат Мичиган, США, 16-18 октября 1978 года . Компьютерное общество IEEE. С. 253–258. DOI : 10,1109 / SFCS.1978.32 .
- ^ a b c Флажолет и Мартин (1985)
- ^ a b c d Алон, Матиас и Сегеди (1996)
- ^ Файгенбаум, Жанна; Сампатх, Каннан (2005). «О задачах графа в полупотоковой модели» . Теоретическая информатика . 348 (2).
- ^ Бэбкок, Брайан; Бабу, Шивнатх; Датар, Маюр; Мотвани, Раджив; Видом, Дженнифер (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.
- ^ Schubert, 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. Впервые опубликовано как Алон, Нога; Матиас, Йосси; Сегеди, Марио (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 Неизвестный параметр
|book-title=
игнорируется ( справка ) . - Карп, РМ ; Пападимитриу, Швейцария ; Шенкер, 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.