Изменения

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

В любой момент времени может поступить запрос о подсчете некоторой функции от <math>a(t)</math>. Для задачи о приблизительном подсчете числа вхождений нас интересует запрос об оценке значения <math>a_{i}(t)</math> для заданного <math>i</math> в момент времени <math>t</math> (англ. point query).

Для задачи о приблизительном подсчете числа вхождений нас интересует запрос удобства <math>Q(i)t</math> об оценке значения будет опущена и мы будем использовать <math>a_{i}(t)a_i</math> для заданного <math>i</math> в момент времени <math>t</math> (англ. point query)обращения к текущему состоянию вектора.

* он должен оно должно требовать <math>O(polylog \: n)</math> памяти;

'''Count-Min Sketch''' (CM Sketch) это вероятностная структура данных, предложенная Г. Кормоудом (англ. G. Cormode) и С. Мутукришнаном (англ. S. Muthukrishnan) в 2003 году. Рассматриваемый Рассмотренный в данном этом разделе алгоритм подход позволяет оценить <math>a_{i}(t)</math> при <math>c_j \geq 0 \:\: \forall j</math>. CM Sketch может также быть применен для оценки <math>a_{i}(t)</math> когда существуют <math>c_j < 0</math>, а также для алгоритмов оценки скалярного произведения (англ. inner product query) и суммы промежутка величин <math>a_{l}(t), a_{l+1}(t), \dots, a_{lr}(t)</math> (англ. range query)<ref name="smsketch">Graham Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2003</ref>.

'''Обновление.''' При получении из потока пары <math>(i_t, c_t)</math>, т.е. при увеличении величины <math>a_{i_t}(t)</math> на значение <math>c_t</math>, для каждой строки <math>j</math> двумерного массива <math>count</math> мы увеличиваем значение соответствующего счетчика, заданного хэш-функцией <math>h_j</math>:

<math> count[j, h_j(i_t)] \leftarrow count[j, h_j(i_t)] + c_t \:\: \forall j. </math>

'''Ответ на запрос.''' Оценка значения <math>a_{i}(t)</math> подсчитывается как <math>\hat{a}_i = \min_j count[j, h_j(i)]</math><ref name="smsketch">Graham Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2003</ref>.

'''{{Теорема |author=1.''' |statement=Оценка <math>\hat{a}_i</math> удовлетворяет <math>a_i \leq \hat{a}_i \leq a_i(t)</math>, и с вероятностью как минимум <math>1 - \delta</math><math> \hat{a}_i \leq a_i(t) + \varepsilon ||\mathbf{a}||_1. </math>удовлетворяет

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

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

Оценим размер ошибки, накапливающийся в <math> Ecount[j, h_j(i)]</math>. Зададимся индикаторной величиной <math>I_{i,j,k}</math>, равной единице если <math>(i \neq k) = Pr[\land (h_j(a_ii) = h_j(a_kk)] \leq \frac{1}{range(h_j)} = \frac{\varepsilon}{e}, </math>и нулю в противном случае. Так как хэш-функции попарно независимы, получаем

где <math>rangeE(h_j)</math> — размер интервала значенийI_{i, которые может принимать хэш-функция <math>h_j</math>. Обозначим размер ошибкиj, накапливающийся в <math>countk}) = Pr[j, h_j(a_ii) = h_j(k)]</math> как случайную величину <math>X_{i,j} = \sum_leq \frac{k=1}^{nrange(h_j)} I_= \frac{i,j,k\varepsilon}a_k</math>, т.е. <math>count[j, h_j(a_i)] = a_i + X_{ie},j}</math>. В таком случае

где <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>. В таком случае  <math> E(X_{i,j}) = E(\sum_{k=1}^{n} I_{i,j,k}a_k) = \sum_{k=1}^{n} E(I_{i,j,k}a_k) = \sum_{k=1}^{n} a_k E(I_{i,j,k}) = \leq \frac{\varepsilon}{e} \sum_{k=1}^{n} a_k = \frac{\varepsilon}{e} || \mathbf{a} ||_1. </math>

<math>Pr[\hat{a}_i > a_i + \varepsilon ||\mathbf{a}||_1] = Pr[\forall j \: count[j, h_j(a_ii)] > a_i + \varepsilon ||\mathbf{a}||_1] = Pr[\forall j \: a_i + X_{i,j} > a_i + \varepsilon ||\mathbf{a}||_1] = Pr[\forall j \: X_{i,j} > e E(X_{i,j})] </math>

<math>= ^{(1)} Pr[X_{i,1} > e E(X_{i,1}) \times \dots \times X_{i,d} > e E(X_{i,d})] \leq ^{(2)} e^{-d} \leq \delta.,</math>

Последние два перехода вытекают где <math>(1)</math> вытекает из попарной независимости хэш-функций и , а <math>(2)</math> {{---}} из неравенства Маркова соответственно<ref name="smsketch_lecture">Barna Saha, "Algorithmic Techniques for Big Data. Lecture 2"</ref>.}}

'''Count Sketch''' — вероятностная структура данных, предложенная М. Чарикаром (англ. M. Charikar), К. Ченом (англ. K. Chen) и М. Фара-Колтоном (англ. M. Farach-Colton) в 2002 году. В отличие от Count-Min Sketch, эта структура данных позволяет оценивать <math>a_{i}(t)</math> даже для отрицательных <math>c_jc_t</math>.

<math> s_1, s_2, \dots, s_d : \{1, \dots, n\} \rightarrow \{+-1, -1\}. </math>

'''Обновление.''' При получении из потока пары <math>(i_t, c_t)</math>, для каждой строки <math>j</math> двумерного массива <math>count</math> мы обновляем значение соответствующего счетчика, заданного хэш-функцией <math>h_j</math>, следующим образом: <math> count[j, h_j(i_t)] \leftarrow count[j, h_j(i_t)] + c_t \cdot{} s_j(i_t) \: \forall j. </math>

'''Ответ на запрос.''' Оценка значения <math>a_{i}(t)</math> подсчитывается как

<math>\hat{a}_i = median_j \{count[j, h_j(i)] \cdot{} s_j(i_ti) \}</math><ref name="ssketch">Moses Charikar, Kevin Chen, Martin Farach-Colton, "Finding Frequent Items in Data Streams", 2002</ref>.

'''{{Теорема.''' |author=2|statement=Оценка значения <math>a_{i}(t)</math> полученная с помощью Count Sketch удовлетворяет

<math> a_{i}(t) - \sqrt{\frac{3}{R}} ||\mathbf{a}||_2 \leq \hat{a}_i \leq a_{i}(t) + \sqrt{\frac{3}{R}} ||\mathbf{a}||_2. </math>

'''Доказательство.''' |proof=Воспользуемся схемой доказательства, сходной с той, что была использована для Count-Min Sketch. С учетом коллизий хэш-функций получаем значение, хранимое в счетчике <math>count[j, h_j(a_ii)]</math>:

<math> count[j, h_j(a_ii)] = \sum_{k=1}^{n} \big(I_{h(i,j,)=h(k)} \cdot{} a_k \cdot{} s_j(a_kk)\big) = a_i(t) \cdot{} s_j(a_i(t)i) + \sum_{k=1, k \neq i}^{n} \big(I_{h(i,j,)=h(k)} \cdot{} a_k \cdot{} s_j(a_kk)\big), </math>

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

<math> E(I_{h(i,j,)=h(k)}) = \leq \frac{1}{range(h_j)} = \frac{1}{w}. </math>

<math> E(s_j(a_i(ti)) = 0, </math>

<math> E(s_j(a_i(ti))^2 = 1. </math>

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

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

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

<math> = E\Big[(a_i(t) \cdot{} s_j(a_i(t)i)^2 + \sum_{k=1, k \neq i}^{n} \big(I_{h(i,j,)=h(k)} \cdot{} a_k \cdot{} s_j(a_kk) \cdot{} s_j(a_i(t)i) \big) - a_i(t)) ^ 2\Big] </math>

<math> = E\Big[\Big(\sum_{k=1, k \neq i}^{n} \big(I_{h(i,j,)=h(k)} \cdot{} a_k \cdot{} s_j(a_kk) \cdot{} s_j(a_i(t)i) \big)\Big) ^ 2\Big] </math>

<math> = E\Big[\sum_{k=1, k \neq i}^{n} \big(I_{h(i,j,)=h(k)}^2 \cdot{} a_k^2 \cdot{} s_j(a_kk)^2 \cdot{} s_j(a_i(t)i) ^2\big) + \sum_{k \neq i, l \neq i} \big(I_{h(i,j,)=h(k)} \cdot{} I_{h(i,j,)=h(l)} \cdot{} a_k \cdot{} a_l \cdot{} s_j(a_kk) \cdot{} s_j(a_ll) \cdot{} s_j(a_i(t)i) ^2\big)\Big] </math>

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

<math> Pr\Big[Error (s_j(i) \cdot{} count[j, h_j(i)] - a_i) > \sqrt{\frac{3}{w}}||\mathbf{a}||_2\Big] < \frac{1}{3}. </math><ref name="ssketch_lecture">Anshumali Shrivastava, "Probabilistic Algorithms and Data Structure. Lecture 10"</ref>}}

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

Описанные выше скетчи также могут быть использованы для решения задачи выявления наиболее часто встречающихся элементов (англ. Heavy Hittersheavy hitters). Это может быть актуально, например, для поисковых систем, таких как Google. Подробное описание решения этой задачи с помощью Count-Min Sketch и Count Sketch описано в оригинальных статьях<ref name="smsketch">Graham Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2003</ref><ref name="ssketch">Moses Charikar, Kevin Chen, Martin Farach-Colton, "Finding Frequent Items in Data Streams", 2002</ref>.