Изменения
Исправлены формулы
Рассмотрим постановку задачи о потоке данных. Пусть дан вектор <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</math> и будем обновлять вектор <math>a</math> следующим образом:
<mathtex> a_{i_t}(t) \leftarrow a_{i_t}(t-1) + c_t, </mathtex>
<mathtex> a_{i’}(t) \leftarrow a_{i’}(t-1) \:\:\: \forall i’ \neq i_t. </mathtex>
В любой момент времени может поступить запрос о подсчете некоторой функции от <math>a(t)</math>. Для задачи о приблизительном подсчете числа вхождений нас интересует запрос об оценке значения <math>a_{i}(t)</math> для заданного <math>i</math> в момент времени <math>t</math> (англ. point query).
'''Структура данных.''' 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> попарно независимых хэш-функций из универсального семейства:
<mathtex> h_1, h_2, \dots, h_d : \{1, \dots, n\} \rightarrow \{1, \dots, w\}. </mathtex>
В начале работы массив инициализируется нулями.
'''Обновление.''' При получении из потока пары <math>(i_t, c_t)</math>, т.е. при увеличении величины <math>a_{i_t}</math> на значение <math>c_t</math>, для каждой строки <math>j</math> двумерного массива <math>count</math> мы увеличиваем значение соответствующего счетчика, заданного хэш-функцией <math>h_j</math>:
<mathtex> count[j, h_j(i_t)] \leftarrow count[j, h_j(i_t)] + c_t \:\: \forall j. </mathtex>
Данная процедура описывается на рис. 1.
|author=1
|statement=
Оценка <mathtex>\hat{a}_i</mathtex> удовлетворяет <mathtex>a_i \leq \hat{a}_i</mathtex>, и с вероятностью как минимум <mathtex>1 - \delta</mathtex> удовлетворяет
<mathtex> \hat{a}_i \leq a_i + \varepsilon ||\mathbf{a}||_1. </mathtex>
|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_k: h_j(i) = h_j(k), k \neq i</math>, то <math>a_i \leq \hat{a}_i</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> и нулю в противном случае. Так как хэш-функции попарно независимы, получаем
<mathtex> E(I_{i,j,k}) = Pr[h_j(i) = h_j(k)] \leq \frac{1}{range(h_j)} = \frac{\varepsilon}{e}, </mathtex>
где <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>. В таком случае
<mathtex> 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. </mathtex>
Наконец, докажем что <math>Pr[\hat{a}_i > a_i + \varepsilon ||\mathbf{a}||_1]</math> не превышает <math>\delta</math>, из чего следует, что <math>Pr[\hat{a}_i \leq a_i + \varepsilon ||\mathbf{a}||_1] > 1 - \delta</math>.
<mathtex>Pr[\hat{a}_i > a_i + \varepsilon ||\mathbf{a}||_1] = Pr[\forall j \: count[j, h_j(i)] > 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})] </mathtex>
<mathtex>=^{(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,</mathtex>
где <math>(1)</math> вытекает из попарной независимости хэш-функций, а <math>(2)</math> {{---}} из неравенства Маркова<ref name="smsketch_lecture">Barna Saha, "Algorithmic Techniques for Big Data. Lecture 2"</ref>.
'''Структура данных.''' Пусть <math>h_1, h_2, \dots, h_d</math> и <math>s_1, s_2, \dots, s_d</math> — это наборы хэш-функций, принадлежащие универсальному семейству и удовлетворяющие
<mathtex> h_1, h_2, \dots, h_d : \{1, \dots, n\} \rightarrow \{1, \dots, w\}, </mathtex>
<mathtex> s_1, s_2, \dots, s_d : \{1, \dots, n\} \rightarrow \{-1, 1\}. </mathtex>
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>(i_t, c_t)</math>, для каждой строки <math>j</math> двумерного массива <math>count</math> мы обновляем значение соответствующего счетчика, заданного хэш-функцией <math>h_j</math>, следующим образом:
<mathtex> count[j, h_j(i_t)] \leftarrow count[j, h_j(i_t)] + c_t \cdot{} s_j(i_t) \: \forall j. </mathtex>
'''Ответ на запрос.''' Оценка значения <math>a_{i}</math> подсчитывается как
{{Теорема
|author=2
|statement=Оценка значения <mathtex>a_{i}</mathtex> полученная с помощью Count Sketch удовлетворяет
<mathtex> a_{i} - \sqrt{\frac{3}{R}} ||\mathbf{a}||_2 \leq \hat{a}_i \leq a_{i} + \sqrt{\frac{3}{R}} ||\mathbf{a}||_2. </mathtex>
|proof=Воспользуемся схемой доказательства, сходной с той, что была использована для Count-Min Sketch. С учетом коллизий хэш-функций получаем значение, хранимое в счетчике <math>count[j, h_j(i)]</math>:
<mathtex> count[j, h_j(i)] = \sum_{k=1}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k \cdot{} s_j(k)\big) = a_i \cdot{} s_j(i) + \sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k \cdot{} s_j(k)\big), </mathtex>
из чего следует, что
<mathtex> s_j(i) \cdot{} count[j, h_j(i)] = a_i \cdot{} s_j(i)^2 + \sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k \cdot{} s_j(k) \cdot{} s_j(i) \big). </mathtex>
Схоже с предыдущим доказательством
<mathtex> E(I_{h(i)=h(k)}) \leq \frac{1}{range(h_j)} = \frac{1}{w}. </mathtex>
Кроме того, очевидно, что
<mathtex> E(s_j(i)) = 0, </math> <math> \:\:\:\:\: E(s_j(i))^2 = 1. </mathtex>
Найдем матожидание <math>E(s_j(i) \:count[j, h_j(i)])</math>:
<mathtex> E(s_j(i) \: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. </mathtex>
Так как в отличие от Count-Min Sketch, Count Sketch может работать при <math>c_t < 0</math>, мы не можем использовать неравенство Маркова. Вместо этого воспользуемся неравенством Чебышёва, для чего подсчитаем дисперсию:
<mathtex> Var(s_j(i) \:count[j, h_j(i)]) = E\Big[(s_j(i) \cdot{} count[j, h_j(i)] - a_i)^ 2\Big] </mathtex>
<mathtex> = E\Big[(a_i \cdot{} s_j(i)^2 + \sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k \cdot{} s_j(k) \cdot{} s_j(i) \big) - a_i) ^ 2\Big] </mathtex>
<mathtex> = E\Big[\Big(\sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)} \cdot{} a_k \cdot{} s_j(k) \cdot{} s_j(i) \big)\Big) ^ 2\Big] </mathtex>
<mathtex> = E\Big[\sum_{k=1, k \neq i}^{n} \big(I_{h(i)=h(k)}^2 \cdot{} a_k^2 \cdot{} s_j(k)^2 \cdot{} s_j(i) ^2\big) + \sum_{k \neq i, l \neq i} \big(I_{h(i)=h(k)} \cdot{} I_{h(i)=h(l)} \cdot{} a_k \cdot{} a_l \cdot{} s_j(k) \cdot{} s_j(l) \cdot{} s_j(i) ^2\big)\Big] </mathtex>
<mathtex> = E\Big[\sum_{k=1, k \neq i}^{n} \big(I_{h(i)=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}. </mathtex>
Подставим полученную дисперсию в неравенство Чебышёва для <math>k = \sqrt{3}</math>:
<mathtex> Pr\Big[(s_j(i) \cdot{} count[j, h_j(i)] - a_i) > \sqrt{\frac{3}{w}}||\mathbf{a}||_2\Big] < \frac{1}{3}. </mathtex><ref name="ssketch_lecture">Anshumali Shrivastava, "Probabilistic Algorithms and Data Structure. Lecture 10"</ref>
}}
