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

Question

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

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

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

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

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

Answer 1

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

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

Подробный анализ можно найти в примечаниях к лекциям, которые я приложил.

Answer 2

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

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

Answer 3

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

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

1. Если элемент еще не имеет счетчика и счетчиков
2. В противном случае, если элемент имеет счетчик, увеличьте его. а. увеличить счетчик строки кэша

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

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