Изменения

Задача о '''приблизительном подсчете числа вхождений''': пусть дан некоторый поток данных <math>S = s_1, s_2, \dots, s_i, \dots, \: s_j \in U</math>. Необходимо подсчитать, сколько раз элемент <math>x \in U</math> встретился в потоке <math>S</math> на момент времени <math>t</math>, т.е. <math>\sum_{j=1}^{t} I(I_{s_j = x)}</math>. В данной статье рассмотрены две структуры данных, позволяющие решить эту задачу: Count-Min Sketch и Count Sketch. Обе структуры данных были предложены в начале 00-х в ответ на необходимость сбора информации об увеличившемся потоке интернет-трафика.

<tex> a_{i’}(t) \leftarrow a_{i’}(t-1) \:\:\: \forall i’ \neq i_t. </tex>

'''Count-Min Sketch''' (CM Sketch) {{---}} это вероятностная структура данных, предложенная Г. Кормоудом (англ. G. Cormode) и С. Мутукришнаном (англ. S. Muthukrishnan) в 2003 году. Рассмотренный в этом разделе подход позволяет оценить <math>a_{i}</math> при <math>c_j c_t \geq 0 \:\: \forall j</math>. CM Sketch может также быть применен для оценки <math>a_{i}</math> когда существуют <math>c_j 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>.

|proof=Рассмотрим хэш-функцию <math>h_j</math> и счетчик <math>count[j, h_j(i)]</math>, в который записываются обновления для элемента <math>a_i</math>. Так как мы рассматриваем случай для <math>c_t \geq 0 \:\:\forall t</math> и так как может существовать <math>a_kk: h_j(i) = h_j(k), k \neq i</math>, то <math>a_i \leq \hat{a}_i</math>.

Count Sketch включает в себя двумерный массив шириной <math>w</math> и глубиной <math>d</math>: <math>count[1, 1], count[1, 2], \dots, count [d, w]</math>, а также хэш-функции <math>h_1, h_2, \dots, h_d</math> и <math>s_1, s_2, \dots, s_d</math>. В начале работы массив инициализируются инициализируется нулями.

Найдем матожидание <math>E(s_j(i) \:cdot{} count[j, h_j(i)])</math>:

<tex> E(s_j(i) \:cdot{} count[j, h_j(i)]) = a_i \cdot{} E(s_j(i)^2) + \sum_{k=1, k \neq i}^{n} \big(E(I_{h(i)=h(k)}) \cdot{} a_k \cdot{} E(s_j(k)) \cdot{} E(s_j(i)) \big) = a_i \cdot{} E(s_j(i)^2) = a_i. </tex>

<tex> Var(s_j(i) \:cdot{} count[j, h_j(i)]) = E\Big[(s_j(i) \cdot{} count[j, h_j(i)] - a_i)^ 2\Big] </tex>

<tex> = E\Big[\sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k^2 \big)\Big] = E\Big[\sum_{k=1}^{n} \big(I_{i,j,k} \cdot{} a_k^2 \big)\Big] \leq \frac{1}{w} \sum_{k=1, k \neq i}^{n} a_k^2 = \frac{||\mathbf{a}||_2^2}{w}. </tex>

С момента появления Count-Min Sketch и Count Sketch эти структуры данных стали широко использоваться для подсчета статистики, например, для отслеживания популярности контента среди разных групп пользователей. Рассмотрим пример с подсчетом числа просмотров для твита. Отслеживание всех просмотров на разных веб-сайтах результируется в большом потоке данных, которым сложно управлять. Кроме того, ситуация, когда твит наберет большое число просмотров на одной платформе и окажется незамеченным на других, маловероятна, поэтому разработчики могут не волноваться об излишней точности подсчетово больших погрешностях. Использование скетча для каждого отдельного твита занимает ненамного больше места чем само сообщение и метаданные о нем, но при этом позволяет отслеживать, какие платформы привлекают больше всего читателей с хорошей точностью.

Кроме того, скетчи Скетчи также популярны в телекоммуникационных сетях, через узлы которых проходит большое количество трафика, которое не может быть сохранено в явном виде. Сбор статистики о распределении трафика в сети позволяет эффективно управлять ею, снижая загруженность критических узлов.<ref name="use">Graham Cormode, "What is Data Sketching, and Why Should I Care?", 2017</ref>