Изменения

Перейти к: навигация, поиск

Приблизительный подсчет числа вхождений

140 байт добавлено, 21:48, 21 января 2022
добавлены ссылки на другие страницы
'''Count-Min Sketch''' (CM Sketch) {{---}} это вероятностная структура данных, предложенная Г. Кормоудом (англ. G. Cormode) и С. Мутукришнаном (англ. S. Muthukrishnan) в 2003 году. Рассмотренный в этом разделе подход позволяет оценить <math>a_{i}</math> при <math>c_t \geq 0 \:\: \forall j</math>. CM Sketch может также быть применен для оценки <math>a_{i}</math> когда существуют <math>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> h_1, h_2, \dots, h_d : \{1, \dots, n\} \rightarrow \{1, \dots, w\}. </tex>
<tex>=^{(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,</tex>
где <math>(1)</math> вытекает из попарной независимости хэш-функций, а <math>(2)</math> {{---}} из [[Неравенство Маркова|неравенства Маркова]]<ref name="smsketch_lecture">Barna Saha, "Algorithmic Techniques for Big Data. Lecture 2"</ref>.
}}
Анонимный участник

Навигация