Count–min sketch

В інформатиці count–min sketch (CM-ескіз; англ. count–min sketch) — це імовірнісна структура даних, що слугує таблицею частот подій у потоці даних. Вона використовує геш-функції для відображення подій у частоти, але, на відміну від геш-таблиці, займає лише сублінійний обсяг пам'яті — ціною того, що частоти деяких подій завищуються через колізії. Count–min sketch винайшли 2003 року Ґрем Кормоуд (Graham Cormode) і С. Муту Мутукрішнан (S. Muthu Muthukrishnan), а описали його в статті 2005 року.

Count–min sketch — це альтернатива до count sketch та AMS sketch; його можна вважати реалізацією лічильникового фільтра Блума. Проте їх використовують по-різному: count–min sketch зазвичай має сублінійну кількість клітинок, тоді як лічильниковий фільтр Блума розмірюють під кількість елементів у множині.

Мета базової версії — споживати потік подій (по одній за раз) і підраховувати частоту різних типів подій. У будь-який момент ескіз можна запитати про частоту конкретного типу події ${\displaystyle i}$ зі всесвіту типів подій ${\displaystyle 𝒰}$; він поверне оцінку, що перебуває на певній відстані від справжньої частоти, з певною ймовірністю.

Сама структура даних — це двовимірний масив з ${\displaystyle w}$ стовпців і ${\displaystyle d}$ рядків. З кожним із ${\displaystyle d}$ рядків пов'язана окрема геш-функція; геш-функції мають бути попарно незалежними. Параметри можна обрати так:

${\displaystyle w=\lceil e/\epsilon \rceil ,d=\lceil \ln (1/\delta )\rceil }$

де похибка у відповіді на запит перебуває в межах адитивного фактора ${\displaystyle \epsilon }$ з імовірністю ${\displaystyle 1-\delta }$, а ${\displaystyle e}$ — число Ейлера.

Коли надходить нова подія типу ${\displaystyle i}$, для кожного рядка ${\displaystyle j}$ застосовують відповідну геш-функцію, щоб отримати індекс стовпця ${\displaystyle k=h_j(i)}$, а потім збільшують значення в рядку ${\displaystyle j}$, стовпці ${\displaystyle k}$ на одиницю.

Точковий запит питає про лічильник типу події ${\displaystyle i}$. Оцінений лічильник дається найменшим значенням у таблиці:

${\displaystyle {\hat{a}}_i=\underset{j}{min}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[j,h_j(i)]}$

Для кожного ${\displaystyle i}$ маємо ${\displaystyle a_i\le {\hat{a}}_i}$, де ${\displaystyle a_i}$ — справжня частота. Крім того, оцінка гарантує, що ${\displaystyle {\hat{a}}_i\le a_i+\epsilon N}$ з імовірністю ${\displaystyle 1-\delta }$, де ${\displaystyle N=\sum _{i\in 𝒰}{a}_i}$ — розмір потоку.

Запит скалярного добутку оцінює скалярний добуток між гістограмами, представленими двома ескізами. Нехай ${\displaystyle {\widehat{a\cdot b}}_j=\sum _{k=0}^w{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}}_a[j,k]\cdot {\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}}_b[j,k]}$. Тоді скалярний добуток оцінюють як ${\displaystyle \widehat{a\cdot b}=\underset{j}{min}{\widehat{a\cdot b}}_j}$, причому ${\displaystyle a\cdot b\le \widehat{a\cdot b}}$.

Як і count sketch, count–min sketch є лінійним ескізом. Якщо побудувати ескіз на кожному з двох потоків і додати ескізи, результат буде таким самим, як якби потоки спершу конкатенували. Це робить ескіз злиттєздатним і придатним для розподілених середовищ.

Звичайний оцінювач-мінімум є зсунутим: ескіз може завищувати, але ніколи не занижує справжній лічильник у точковому запиті. Запропоновано кілька варіацій для усунення зсуву:

• Оцінювач hCount* — багаторазово випадково обирає ${\displaystyle d}$ записів і бере мінімум, щоб отримати незсунену оцінку зсуву.
• Оцінювач максимальної правдоподібності (MLE) — завжди здатен зрівнятися з оцінювачем-мінімумом або перевершити його.
• Консервативне оновлення — оновлює ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[j,h_j(i)]\leftarrow max\{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[j,h_j(i)],{\hat{a}}_i+c\}}$. Робить ескіз нелінійним, але він лишається злиттєздатним.

• Фільтр Блума
• MinHash
• Feature hashing

• Cormode, Graham; Muthukrishnan, S. (2005). An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms.
• Оригінальна стаття в англійській Вікіпедії