Изменения

Перейти к: навигация, поиск
м
Исправлены опечатки
{{в разработке}}
Задача о '''приблизительном подсчете числа вхождений''': пусть дан некоторый поток данных <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}(t) \leftarrow a_{i_t}(t-1) + c_t, </tex>
<tex> a_{i’}(t) \leftarrow a_{i’}(t-1) \:\:\: \forall i’ \neq i_t. </tex>
В любой момент времени может поступить запрос о подсчете некоторой функции от <math>a(t)</math>. Для задачи о приблизительном подсчете числа вхождений нас интересует запрос об оценке значения <math>a_{i}(t)</math> для заданного <math>i</math> в момент времени <math>t</math> (англ. point query).
[[Файл: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_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>.
'''Структура данных.''' 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> попарно независимых хэш-функций из универсального семейства:
<tex> \hat{a}_i \leq a_i + \varepsilon ||\mathbf{a}||_1. </tex>
|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>.
Оценим размер ошибки, накапливающийся в <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> s_1, s_2, \dots, s_d : \{1, \dots, n\} \rightarrow \{-1, 1\}. </tex>
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>, следующим образом:
<tex> 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). </tex>
 
Схоже с предыдущим доказательством
 
<tex> E(I_{h(i)=h(k)}) \leq \frac{1}{range(h_j)} = \frac{1}{w}. </tex>
Кроме того, очевидно, что
<tex> E(s_j(i)) = 0, \:\:\:\:\: E(s_j(i))^2 = 1. </tex>
Найдем матожидание <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>
Так как в отличие от Count-Min Sketch, Count Sketch может работать при <math>c_t < 0</math>, мы не можем использовать неравенство Маркова. Вместо этого воспользуемся неравенством Чебышёва, для чего подсчитаем дисперсию:
<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[(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] </tex>
<tex> = 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] </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>
Подставим полученную дисперсию в неравенство Чебышёва для <math>k = \sqrt{3}</math>:
== Применение ==
С момента появления Count-Min Sketch и Count Sketch эти структуры данных стали широко использоваться для подсчета статистики, например, для отслеживания популярности контента среди разных групп пользователей. Рассмотрим пример с подсчетом числа просмотров для твита. Отслеживание всех просмотров на разных веб-сайтах результируется в большом потоке данных, которым сложно управлять. Кроме того, ситуация, когда твит наберет большое число просмотров на одной платформе и окажется незамеченным на других, маловероятна, поэтому разработчики могут не волноваться об излишней точности подсчетово больших погрешностях. Использование скетча для каждого отдельного твита занимает ненамного больше места чем само сообщение и метаданные о нем, но при этом позволяет отслеживать, какие платформы привлекают больше всего читателей с хорошей точностью.
Кроме того, скетчи Скетчи также популярны в телекоммуникационных сетях, через узлы которых проходит большое количество трафика, которое не может быть сохранено в явном виде. Сбор статистики о распределении трафика в сети позволяет эффективно управлять ею, снижая загруженность критических узлов.<ref name="use">Graham Cormode, "What is Data Sketching, and Why Should I Care?", 2017</ref>
Описанные выше скетчи также могут быть использованы для решения задачи выявления наиболее часто встречающихся элементов (англ. heavy 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>.
14
правок

Навигация