SYS Системы и большие данные Структура данных
Count-Min Sketch
Также: Count-Min sketch · CM sketch · набросок Count-Min · подсчёт частот в потоке · heavy hitters · частые элементы · conservative update
Сколько раз встретился элемент потока, если хранить счётчик на каждый нельзя: d строк по w счётчиков, в каждой строке своя хеш-функция, ответ — минимум из d клеток. Оценка никогда не меньше правды и почти никогда не больше её на e·N/w. На словах «Войны и мира» видно и сильную сторону — частые слова почти точны, — и слабую: редкие тонут в шуме.
«Пьер» встречается в «Войне и мире» 1390 раз, «Наташа» — 827, «Аустерлиц» — 3. Чтобы знать частоту каждого слова, нужен словарь на все 47 585 разных слов. А если слова — это адреса в сетевом трафике, и разных миллиарды? Count-Min Sketch хранит фиксированную таблицу счётчиков, раздаёт слова по клеткам хешами и отвечает минимумом. Ниже первые 100 000 слов романа идут в таблицу из четырёх строк. Выберите слово: подсветятся его четыре клетки, и видно, сколько в каждой правды, а сколько чужого.
В каждой клетке «Пьера» — его настоящие появления плюс все слова, которые хеш этой строки положил туда же. Шум в разных строках разный: строки хешируют независимо. Ответ — наименее загрязнённая клетка, минимум. Он никогда не бывает меньше правды и тем ближе к ней, чем шире таблица: при 256 клетках в строке «Пьер» получает +269 к своим 208, при 1024 — всего +29.
Идея
Таблица из d строк по w счётчиков и d независимых хеш-функций — по одной на строку. Пришёл элемент — в каждой строке прибавляем 1 к его клетке. Спросили частоту — берём минимум из его d клеток. Каждая клетка равна правде плюс сумма чужих элементов, попавших туда же, поэтому ошибка только вверх; минимум выбирает строку, где чужих меньше всего.
Это родственник фильтра Блума: там клетки — биты и вопрос «был ли элемент», здесь клетки — счётчики и вопрос «сколько раз». И у того и у другого ошибка односторонняя: фильтр может сказать «был» про небывший элемент, набросок может завысить частоту, но никогда не занизит.
Сколько он ошибается
Пусть через набросок прошло N элементов, и хеш-функции строк независимы и раздают элементы по клеткам равномерно. Тогда для любого элемента оценка не меньше его настоящей частоты f, а с вероятностью не меньше 1 − e−d не больше f + e·N/w.
Нижняя граница очевидна: в каждой клетке элемента лежат все его появления. Возьмём одну строку и обозначим шум X — сумму частот чужих элементов, попавших в нашу клетку. Каждый чужой элемент попадает туда с вероятностью 1/w, поэтому E[X] ≤ N/w. По неравенству Маркова P(X > e·N/w) ≤ E[X] / (e·N/w) ≤ 1/e. Минимум превышает f + e·N/w, только если это случилось во всех d строках сразу, а строки независимы: вероятность не больше e−d.
Отсюда и правило выбора размеров. Хотите ошибку не больше ε·N с вероятностью 1 − δ — берите w = ⌈e/ε⌉ и d = ⌈ln(1/δ)⌉. Обратите внимание, что ошибка отсчитывается от длины всего потока N, а не от частоты слова. Для слова, которое встречается тысячу раз, лишние полсотни — пять процентов; для слова, которое встретилось трижды, — в двадцать раз больше правды. Вот все слова романа сразу:
Частые слова лежат на диагонали: их шум меньше их самих. Редкие висят горизонтальной полосой на высоте шума, и для них набросок бесполезен — при 32 КБ и четырёх строках каждое из 36 тысяч слов, встреченных не больше трёх раз, завышено как минимум вдвое. Гарантия при этом выполняется с запасом: выше пунктира e·N/w — одно слово из 47 585, хотя теорема разрешает 1,8 %. Отсюда главное правило применения: Count-Min хорош для частых элементов, для «тяжёлых» запросов, адресов, слов, и не годится, чтобы считать редкие.
Осторожное обновление
Обычный набросок прибавляет 1 во все клетки элемента, хотя оценке нужна только минимальная. Осторожное обновление — его придумали Кристиан Эстан и Джордж Варгезе для подсчёта сетевого трафика — поднимает каждую клетку элемента лишь до значения «текущая оценка + 1», а уже большие не трогает. Правда по-прежнему под всеми клетками, а шума меньше: включите его в первой сцене и посмотрите на редкие слова. Цена — наброски нельзя складывать поклеточно и нельзя вычитать: результат зависит от порядка потока. Обе версии рядом — первая задача в конце статьи.
Самые частые элементы
Набросок отвечает на вопрос о любом элементе, но сам не помнит, какие элементы были. Чтобы найти самые частые, к нему добавляют кучу из k кандидатов: после каждого элемента смотрим его оценку и, если она больше наименьшей в куче, кладём элемент туда. На «Войне и мире» десять самых частых слов по наброску в точности совпадают с настоящими — «и», «в», «не», «что», «он», — потому что их частоты в десятки раз больше шума.
Для этой задачи есть и детерминированный способ без хешей — алгоритм Мисры — Гриса. Он держит k счётчиков слов и, когда они заняты, а пришло новое слово, уменьшает все на единицу. Каждое слово, которое встречается больше n/(k + 1) раз, гарантированно остаётся в счётчиках, а его счётчик занижен не больше чем на n/(k + 1). Это вторая задача.
Код
Набросок 4 × 2048 — 32 КБ счётчиков — на всём тексте романа. Хешей на строку не четыре, а два: d хешей получают из двух как h1 + i·h2. Адам Кирш и Майкл Мицценмахер в 2006 году показали, что такой приём для фильтра Блума почти не ухудшает точность, и в наброске он работает так же.
«Пьер» и «Наташа» завышены на 3–8 %, «Аустерлиц» — в 24 раза: 72 вместо 3. Ни одной точной оценки — при 47 585 словах на 8192 клетки в каждой клетке в среднем по шесть слов. Медианная ошибка +55, а гарантия обещает не больше +579 для всех, кроме 1,8 % слов; на деле выше границы одно слово. И десятка самых частых не сдвинулась.
Сколько это стоит
Добавление и запрос — d хешей и d обращений к памяти, O(d). Память — d·w счётчиков, не зависящая ни от длины потока, ни от числа разных элементов: при ε = 0,1 % и δ = 1 % это 2719 × 5 счётчиков, около 53 КБ, на любой поток. Наброски с одинаковыми хешами складываются поклеточно — набросок объединения потоков, — и вычитаются, если нужно убрать часть потока; так их собирают с разных серверов и за разные дни.
Где работает
Сети. Маршрутизатору нужно знать, какие адреса шлют больше всего трафика, а держать счётчик на каждый адрес нельзя: их миллионы, а памяти на линейной скорости — килобайты. Задача «тяжёлых потоков» и стала одной из главных для наброска, и осторожное обновление пришло именно отсюда.
Данные. В Apache Spark набросок Count-Min строится одной функцией над столбцом таблицы. В Redis есть команды CMS.INCRBY и CMS.QUERY в модуле вероятностных структур — рядом с фильтром Блума и HyperLogLog.
Популярное в потоке. Частые запросы поисковика, хештеги, товары: набросок с кучей отвечает «что сейчас в топе», не храня полного счёта.
История
Набросок описали Грэм Кормод и С. Мутукришнан в 2004 году; журнальная версия вышла в 2005-м под названием «An improved data stream summary: the count-min sketch and its applications». Похожая структура с подсчётом и минимумом встречалась и раньше — как подсчитывающий фильтр Блума у Фана, Цао, Алмейды и Бродера в 2000 году и у Эстана и Варгезе в 2002-м, — но именно Кормод и Мутукришнан дали простые гарантии через e/ε и ln(1/δ) и показали, сколько задач на потоках решается одной таблицей.
Задачи
В первой задаче нужно вести два наброска на одном потоке — обычный и осторожный — на словах «Войны и мира». Во второй — найти частые слова алгоритмом Мисры — Гриса и понять, какие из них остаются в счётчиках гарантированно.
Две оценки Частые слова за один проходДанные: «Война и мир», Л. Н. Толстой, общественное достояние