Пожалуйста, определите этот алгоритм: вероятностные верхние k элементов в потоке данных

Я помню, как несколько лет назад слышал о следующем алгоритме, но не могу найти на него упоминания в Интернете. Он идентифицирует верхние элементы k (или сильные удары) в потоке данных из n элементов, используя только счетчики m. Это особенно полезно для поиска популярных поисковых запросов, нарушителей сетевых правил и т. Д. При минимальном использовании памяти.

Алгоритм: для каждого элемента,

  1. If the element does not already have a counter and counters < m, create a counter for the element and initialize to 1.
  2. Else if the element does have a counter, increment it.
  3. Else if the element does not have a counter and counters > m, decrement an existing counter c. If c reaches 0, replace its corresponding element, with the current element. (c is an index into the list of existing counters, where c increases in round robin fashion for each element that reaches this step.)

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

Но я хотел бы узнать больше о его вероятностных характеристиках - если меня интересуют только 100 лучших предметов, какой эффект дает использование 1000 жетонов вместо 100 жетонов?


stream algorithm
person Community    schedule 19.07.2009    source источник
comment
Не совсем уверен, но похоже, что экономит место от A. Metwally et al.   -  person Michael Foukarakis    schedule 29.05.2015
comment
@erickson, боюсь, не мой голос.   -  person Michael Foukarakis    schedule 30.05.2015

Ответы (3)


arrow_upward
4
arrow_downward

Вы говорите об известном алгоритме Мисра-Гриса, а алгоритм экономии места - это более быстрая версия алгоритма Мисра-Гриса. Пожалуйста, проверьте эту лекцию для получения подробной информации Алгоритм потоковой передачи Дартмут сек 1.2.

Одна вещь, которую я хочу отметить, заключается в том, что этот алгоритм не дает вам верхних k элементов, если вы использовали только k счетчиков, вместо этого он дает все элементы с частотой> m / k, где m - общая длина потока данных. .

Подробный анализ можно найти в прилагаемых мною конспектах лекций.

person xmerge    schedule 29.05.2015

arrow_upward
2
arrow_downward

Возможно, вы ищете алгоритм «Частый». Он использует счетчики k - 1 для поиска всех элементов, превышающих 1 / k от общего количества, и был опубликован в 1982 году Мисрой и Грисом. Это обобщение алгоритма "большинства" Бойера и Мура (или Фишера-Зальцберга), где k равно 2. Эти и связанные с ними алгоритмы представлены в полезной статье " Проблема Бритни Спирс ".

Я даю подробное объяснение алгоритма в другом месте на StackOverflow, которое я не буду здесь повторять. Важным моментом является то, что после одного прохода значения счетчика не точно указывают частоту элемента; они могут занижать счет с разницей, которая зависит от длины потока и, наоборот, от количества счетчиков (n / k). Все эти алгоритмы (включая «SpaceSaving» Метвалли) требуют второго прохода, если вам нужен точный подсчет, а не оценка частоты.

person erickson    schedule 20.07.2009
comment
Я действительно помню, как читал эту статью, когда она была опубликована. Но есть различие в алгоритмах шага 3. Алгоритм в статье будет уменьшать все счетчики, тогда как описанный мною только один счетчик. Смутно припоминаю, что это был важный фактор. Это делает его более эффективным, но я не знаю, как это влияет на точность. - person ; 20.07.2009

arrow_upward
0
arrow_downward

Похоже, алгоритм замены кэша ЦП наименее часто используется (LFU)

Алгоритм: для каждого элемента,

  1. Если у элемента еще нет счетчика и счетчиков ‹m, создайте счетчик для элемента и инициализируйте его 1. a. если кеш не заполнен, добавьте строку.
  2. В противном случае, если у элемента есть счетчик, увеличьте его. а. увеличить счетчик строки кэша

  3. В противном случае, если у элемента нет счетчика и счетчики> m, уменьшите значение существующего счетчика. Если c достигает 0, заменить соответствующий элемент текущим элементом. (c - это индекс в списке существующих счетчиков, где c увеличивается циклически для каждого элемента, который достигает этого шага.)

    • a. advance to the next candidate cache line
    • б. уменьшить счетчик текущих кандидатов
    • c. если он не достиг нуля, перейдите к a.
    • d. удалить строку кэша и заменить ее новой.
person Surt    schedule 08.09.2016