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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

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

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: