Какие существуют полезные алгоритмы, которые работают с огромными потоками данных, и их результаты довольно малы, и можно вычислить результат для смеси двух потоков, каким-то образом объединив их результаты?
Я могу назвать несколько:
- Очевидные вещи, как сумма, мин, макс, кол, топ-К и т. Д
- Приближенные так называемые «основанные на эскизах» потоковые алгоритмы для гистограмм, подсчета различных элементов или вычисления квантилей
Какие еще есть?
(Мне интересно, потому что я пишу хобби-проект для мониторинга распределенных систем, полезность которого напрямую определяется полезностью таких алгоритмов)
Ответы:
Гуха и др. '03 дают алгоритм аппроксимации для k-медианной кластеризации в потоковой модели. Их алгоритм делит данные на непересекающиеся куски, находит O (k) -центры для каждого непересекающегося кусочка и затем объединяет результаты, чтобы получить k центров. Похоже, это тот тип алгоритма, который вы ищете.
источник
В статье Багки, Чаудхари, Эппштейна и Гудрича решается ряд потоковых геометрических задач с использованием базовой подпрограммы для вычисления -nets и -approximations для подходяще выбранных пространств диапазонов. Эта подпрограмма использует аддитивную структуру этих объектов, разрабатывая иерархическую схему для их вычисления (где виртуальный поток уровня объединяет блоки в виртуальном уровень потока, а уровень 0 - исходный поток). По сути это рендеринг стратегии «разделяй и властвуй» снизу вверх. с обновлениями по «краю» дерева рекурсии. По структуре он очень похож на статью Гухи и др., Упомянутую Левом.ε i th ( i - 1 ) thε ε ith (i−1)th
источник
Я нашел статью ( «Распределение частотно-зависимых вычислений потока данных» ), в которой говорится, что каждая функция распределения частоты потока является объединяемой (хотя она не дает явного и эффективного построения для операции объединения). И доказательство кажется очень интересным, включая некоторую теорию колец. Необходимо прочитать предыдущую статью того же автора ( «Нижние оценки частотной оценки потоков данных» ), основной результат которого используется в качестве основы для этого.
Это напоминает мне о третьей теореме гомоморфизма ...
источник
Исследование языков запросов с непрерывным потоком может дать некоторое представление. Одним из таких языков является CQL , который, я считаю, принимается Oracle. Языки позволяют вычислять функции по скользящим окнам потока (включая окна размера 1). Эта дипломная работа бакалавра предоставляет недавний обзор языка, включая некоторые примеры. В этой статье дается обзор некоторых языков потоковой обработки, которые должны быть полезны для поиска ссылок на другие связанные исследования.
Я знаю, что это не дает прямого ответа на ваш вопрос, но должно помочь вам познакомиться с исследованиями, проведенными людьми, исходящими из одной и той же отправной точки.
источник
Этот вопрос мне кажется несколько круглым. Если у задачи есть свойство, которое вы хотите, то для него есть алгоритм на основе эскиза и слияния. Как уже упоминалось выше, есть работа по кластеризации, аппроксимациям и наборам ядер, которые предоставляют вам это. Кроме того, большинство потоковых алгоритмов позволяют объединять потоки, просто (концептуально) объединяя один поток с другим.
Кроме того, я не уверен, что алгоритмы потоковой передачи top-k можно объединить, но я могу ошибаться.
источник
Извините за некромантизм в этом, но я подумал, что вы могли бы взглянуть на некоторую работу по распределенному непрерывному мониторингу в потоках, где вам дают несколько потоков, и цель состоит в том, чтобы отслеживать некоторую совокупную статистику на центральном сайте мониторинга при минимизации связи. Модель звучит для меня тесно связанной с вашей мотивацией. Посмотрите на ссылки в книге Мутху . Одна статья такая .
Бумага Гангули тоже очень интересная.
источник