Как я могу определить ширину и глубину наброска мин-эскиз?

Ширина (количество сегментов) и глубина (количество хеш-функций) эскиза Count-Min определяют точность полученной оценки частоты.

Из статьи 2005 года оригинальных авторов Count-Min:

Параметры w и d могут быть выбраны путем установки w=⌈e/ε⌉ и d=⌈ln1/δ⌉, где ошибка в ответе на запрос находится в пределах коэффициента ε с вероятностью δ.

Из этого, как описано выше:

w=⌈e/error⌉

d=⌈ln(1/(1−certainty))⌉

Из статьи 2011 года оригинальных авторов Count-Min:

Предположим, что мы хотим погрешность не более 0,1 (от суммы всех частот) с вероятностью 99,9. Тогда мы хотим 2/w=1/1000, мы устанавливаем w=2000, и (1/2)^d=0,001, то есть d=log0.001/log0.5 ≤ 10.

в результате чего:

w=⌈2/error⌉

d=⌈ln(1−certainty)/ln(1/2)⌉

И все же ошибка должна зависеть от общего количества элементов N, которые хранятся в эскизе. Чем больше элементов, тем больше ошибка и вероятность ошибки. Что будет подходящей функцией для создания исходного эскиза?

0 ответов

Другие вопросы по тегам