Граф Скин и проблема Хиттерс - PullRequest
Новая
       22

Граф Скин и проблема Хиттерс

0 голосов
/ 13 ноября 2018

Я читаю о структуре данных Count-Min Sketch, которая дает вероятностный ответ на запросы точек и диапазонов на основе параметра вероятности ошибки и параметра допуска. Например, КМ может ответить на вопрос «сколько раз с вероятностью 10% появляется элемент x в потоке данных».

Также возникла связанная с этим проблема тяжелых нападающих. Реализуя минимальную кучу для проблемы HH, я заметил, что в различных исследовательских работах указывается, что только если минимальное количество элементов в эскизе превышает пороговое значение, мы вставляем в кучу.

Мой вопрос: означает ли это, что мы вероятностно отвечаем на проблему тяжелых нападающих? Будет ли соответствующий вопрос «с вероятностью 10%, какой пункт был вторым по частоте в потоке данных?»

1 Ответ

0 голосов
/ 13 ноября 2018

Из Википедии:

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

Более формально, исправить некоторую положительную константу c> 1, пусть длина stream будет m, и пусть fi обозначает частоту значения i в потоке. Проблема частых элементов - вывести множество {i | фи> м / ц }.

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

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

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

Так что да. CMS может использоваться для определения частоты (приблизительно), которая может использоваться для ответа на вопрос HH.

...