14
правок
Изменения
м
Добавлены категории и примечания
Простым решением задачи может быть хранение вектора <math>a</math> в явном виде. Однако при больших <math>n</math> этот подход становится невыгодным из-за большего количества памяти, требуемого для хранения вектора <math>a</math>. Хорошее решение данной задачи должно обладать следующими свойствами:
* он должен требовать <math>O(polylog \: n)</math> памяти;* обновление <math>a</math> и обработка запросов должны выполняться быстро и быть достаточно точными<ref name="smsketch">Graham Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2003</ref>.
Ниже рассмотрены две структуры данных, позволяющие решить задачу о приблизительном подсчете числа вхождений, которые соответствуют этим требованиям.
[[Файл:cm_sketch.png|thumb|500px| Рисунок 1 — Процедура обновления Count-Min Sketch.]]
'''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_{l}(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>.
'''Структура данных.''' 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> попарно независимых хэш-функций из универсального семейства:
Данная процедура описывается на рис. 1.
'''Ответ на запрос.''' Оценка значения <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>.
'''Теорема 1.''' Оценка <math>\hat{a}_i</math> удовлетворяет <math>\hat{a}_i \leq a_i(t)</math>, и с вероятностью как минимум <math>1 - \delta</math>
<math>= Pr[X_{i,1} > e E(X_{i,1}) \times \dots \times X_{i,d} > e E(X_{i,d})] \leq e^{-d} \leq \delta.</math>
Последние два перехода вытекают из попарной независимости хэш-функций и неравенства Маркова соответственно<ref name="smsketch_lecture">Barna Saha, "Algorithmic Techniques for Big Data. Lecture 2"</ref>.
== Count Sketch ==
'''Ответ на запрос.''' Оценка значения <math>a_{i}(t)</math> подсчитывается как
<math>\hat{a}_i = median_j \{count[j, h_j(i)] \cdot{} s_j(i_t) \}</math><ref name="ssketch">Moses Charikar, Kevin Chen, Martin Farach-Colton, "Finding Frequent Items in Data Streams", 2002</ref>.
'''Теорема.''' Оценка значения <math>a_{i}(t)</math> полученная с помощью Count Sketch удовлетворяет
Подставим полученную дисперсию в неравенство Чебышёва для <math>k = \sqrt{3}</math>:
<math> Pr\Big[Error > \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 эти структуры данных стали широко использоваться для подсчета статистики, например, для отслеживания популярности контента среди разных групп пользователей. Рассмотрим пример с подсчетом числа просмотров для твита. Отслеживание всех просмотров на разных веб-сайтах результируется в большом потоке данных, которым сложно управлять. Кроме того, ситуация, когда твит наберет большое число просмотров на одной платформе и окажется незамеченным на других маловероятна, поэтому разработчики могут не волноваться об излишней точности подсчетов. Использование скетча для каждого отдельного твита занимает ненамного больше места чем само сообщение и метаданные о нем, но при этом позволяет отслеживать, какие платформы привлекают больше всего читателей с хорошей точностью.
Кроме того, скетчи также популярны в телекоммуникационных сетях, через узлы которых проходит большое количество трафика, которое не может быть сохранено в явном виде. Сбор статистики о распределении трафика в сети позволяет эффективно управлять ею, снижая загруженность критических узлов.<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>. == См. также == * [[Хеш-таблица]]* [[Универсальное семейство хеш-функций]]* [[Анализ социальных сетей]] == Примечания == <references/>
== Источники информации ==
* Anshumali Shrivastava, "Probabilistic Algorithms and Data Structure. Lecture 10" [https://www.cs.rice.edu/~as143/COMP480_580_Spring19/scribe/S10.pdf]
* Graham Cormode, "What is Data Sketching, and Why Should I Care?", 2017 [http://dimacs.rutgers.edu/~graham/pubs/papers/cacm-sketch.pdf]
[[Категория:Алгоритмы и структуры данных]][[Категория:Потоковые алгоритмы]]
