Изменения
Исправлены формулы и формулировки
== Постановка задачи ==
Рассмотрим постановку задачи о потоке данных. Пусть дан вектор <math>a</math> размерности <math>n</math>. Пусть состояние вектора в момент <math>t</math> задано как <math>a(t) = [a_1(t), a_2(t), \dots, a_n(t)]</math> и <math>a(0) = [0, 0, \dots, 0]</math>. Зададимся потоком пар <math>(i_1, c_1), (i_2, c_2), \dots, (i_m, c_m), \dots, 1 \leq i_m \leq n</math> и будем обновлять вектор <math>a</math> следующим образом:
<tex> a_{i_t}(t) \leftarrow a_{i_t}(t-1) + c_t, </tex>
[[Файл:cm_sketch.png|thumb|500px| Рисунок 1 — Процедура обновления Count-Min Sketch.]]
'''Count-Min Sketch''' (CM Sketch) {{---}} это вероятностная структура данных, предложенная Г. Кормоудом (англ. G. Cormode) и С. Мутукришнаном (англ. S. Muthukrishnan) в 2003 году. Рассмотренный в этом разделе подход позволяет оценить <math>a_{i}</math> при <math>c_t \geq 0 \:\: \forall jt</math>. CM Sketch может также быть применен для оценки <math>a_{i}</math> когда существуют <math>c_t < 0</math>, а также для алгоритмов оценки скалярного произведения (англ. inner product query) и суммы промежутка величин <math>a_{l}, a_{l+1}, \dots, a_{r}</math> (англ. range query)<ref name="smsketch">Graham Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2003</ref>.
'''Структура данных.''' CM Sketch с параметрами <math>(\varepsilon, \delta)</math> — это структура данных, которая включает в себя двумерный массив шириной <math>w = \lceil \frac{e}{\varepsilon} \rceil</math> и глубиной <math>d = \lceil \ln \frac{1}{\delta} \rceil</math>: <math>count[1, 1], count[1, 2], \dots, count [d, w]</math>, а также <math>d</math> попарно независимых [[Хеш-таблица|хэш-функций]] из [[Универсальное семейство хеш-функций|универсального семейства]]:
Оценим размер ошибки, накапливающийся в <math>count[j, h_j(i)]</math>. Зададимся индикаторной величиной <math>I_{i,j,k}</math>, равной единице если <math>(i \neq k) \land (h_j(i) = h_j(k))</math> и нулю в противном случае. Так как хэш-функции попарно независимы, получаем
<tex> E(I_{i,j,k}) = Pr[h_j(i) = h_j(k)] \leq \frac{1}{range(h_j)} = \leq \frac{\varepsilon}{e}, </tex>
где <math>range(h_j)</math> — размер интервала значений, которые может принимать хэш-функция <math>h_j</math>. Обозначим размер ошибки, накапливающийся в <math>count[j, h_j(i)]</math> как случайную величину <math>X_{i,j} = \sum_{k=1}^{n} I_{i,j,k}a_k</math>, т.е. <math>count[j, h_j(i)] = a_i + X_{i,j}</math>. В таком случае
|statement=Оценка значения <tex>a_{i}</tex> полученная с помощью Count Sketch удовлетворяет
<tex> a_{i} - \sqrt{\frac{3}{Rw}} ||\mathbf{a}||_2 \leq \hat{a}_i \leq a_{i} + \sqrt{\frac{3}{Rw}} ||\mathbf{a}||_2. </tex>
|proof=Воспользуемся схемой доказательства, сходной с той, что была использована для Count-Min Sketch. С учетом коллизий хэш-функций получаем значение, хранимое в счетчике <math>count[j, h_j(i)]</math>:
== Применение ==
С момента появления Count-Min Sketch и Count Sketch эти структуры данных стали широко использоваться для подсчета статистики, например, для отслеживания популярности контента среди разных групп пользователей. Рассмотрим пример с подсчетом числа просмотров для твита. Отслеживание всех Попытка отследить число просмотров на разных веб-сайтах результируется в большом потоке приводит к работе с большим потоком данных, которым сложно управлять. Кроме того, ситуация, когда твит наберет большое число просмотров на одной платформе и окажется незамеченным на других, маловероятна, поэтому разработчики могут не волноваться о больших погрешностях. Использование скетча для каждого отдельного твита занимает ненамного больше места чем само сообщение и метаданные о нем, но при этом позволяет отслеживать, какие платформы привлекают больше всего читателей с хорошей точностью.
Скетчи также популярны в телекоммуникационных сетях, через узлы которых проходит большое количество трафика, которое не может быть сохранено в явном виде. Сбор статистики о распределении трафика в сети позволяет эффективно управлять ею, снижая загруженность критических узлов.<ref name="use">Graham Cormode, "What is Data Sketching, and Why Should I Care?", 2017</ref>
