Как я могу определить ширину и глубину наброска мин-эскиз?
Ширина (количество сегментов) и глубина (количество хеш-функций) эскиза 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, которые хранятся в эскизе. Чем больше элементов, тем больше ошибка и вероятность ошибки. Что будет подходящей функцией для создания исходного эскиза?