Примерный алгоритм подсчета

Алгоритм приближенного подсчета позволяет подсчитывать большое количество событий, используя небольшой объем памяти. Изобретенный в 1977 году Робертом Моррисом из Bell Labs , он использует вероятностные методы для увеличения счетчика . Он был полностью проанализирован в начале 1980-х годов Филиппом Флажоле из INRIA Rocquencourt, который придумал название « приблизительный подсчет » и во многом способствовал его признанию среди исследовательского сообщества. Сосредоточив внимание на высоком качестве аппроксимации и низкой вероятности неудачи, Нельсон и Ю показали, что очень небольшая модификация счетчика Морриса является асимптотически оптимальной среди всех алгоритмов для решения этой задачи. ^[1] Алгоритм считается одним из предшественников потоковых алгоритмов , и более общая проблема определения частотных моментов потока данных была центральной в этой области.

Теория работы [ править ]

Используя алгоритм Морриса, счетчик представляет собой « оценку порядка величины » фактического подсчета. Приближение является математически несмещенным .

Для увеличения счетчика используется псевдослучайное событие, то есть приращение является вероятностным событием. Для экономии места сохраняется только показатель степени. Например, в системе счисления 2 счетчик может оценить счет как 1, 2, 4, 8, 16, 32 и все степени двойки . Требование к памяти состоит в том, чтобы просто хранить экспоненту .

Например, для увеличения от 4 до 8 будет сгенерировано псевдослучайное число, так что вероятность увеличения счетчика равна 0,25. В противном случае счетчик остается на уровне 4.

В таблице ниже показаны некоторые возможные значения счетчика:

Сохраненное двоичное значение счетчика	Приближение	Диапазон возможных значений фактического количества	Ожидание (достаточно большое n, равномерное распределение)
0	1	0 или начальное значение	0
1	2	1 или более	2
10	4	2 или более	6
11	8	3 или более	14
100	16	4 или более	30
101	32	5 или более	62

Если счетчик имеет значение 101, что соответствует показателю степени 5 (десятичный эквивалент 101), то расчетное значение равно $2^{5}$ , или 32. Существует довольно низкая вероятность того, что фактическое количество событий приращения составило 5 ( ${\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}$ ). Фактическое количество событий приращения, вероятно, будет «около 32», но оно может быть сколь угодно большим (с уменьшением вероятности фактического количества событий выше 39).

Выбор значений счетчика [ править ]

Хотя использование степеней 2 в качестве значений счетчика эффективно использует память, произвольные значения имеют тенденцию создавать динамический диапазон ошибок, и меньшие значения будут иметь больший коэффициент ошибок, чем большие значения. Другие методы выбора значений счетчика учитывают такие параметры, как доступность памяти, желаемый коэффициент ошибок или диапазон счета, чтобы обеспечить оптимальный набор значений. ^[2]

Однако если несколько счетчиков имеют одинаковые значения, значения оптимизируются в соответствии со счетчиком с наибольшим диапазоном счета и обеспечивают неоптимальную точность для счетчиков меньшего размера. Смягчение достигается за счет поддержки сегментов независимой счетчиковой оценки. ^[3] которые ограничивают эффект большего счетчика другими счетчиками в сегменте.

Алгоритм [ править ]

Алгоритм можно реализовать вручную. При увеличении счетчика подбросьте монету столько раз, сколько соответствует текущему значению счетчика. Если каждый раз выпадает орел, увеличьте счетчик. В противном случае не увеличивайте его.

Этого можно легко добиться на компьютере. Позволять $c$ быть текущим значением счетчика. Создание $c$ псевдослучайные биты и используя логическое И всех этих битов, добавьте результат в счетчик. Поскольку результат был нулевым, если любой из этих псевдослучайных битов равен нулю, достигалась вероятность приращения $2^{-c}$ . Эта процедура выполняется каждый раз, когда поступает запрос на увеличение счетчика.

Приложения [ править ]

Алгоритм полезен при проверке больших потоков данных на наличие шаблонов. Это особенно полезно в приложениях сжатия данных , распознавания изображений и звука и других искусственного интеллекта приложениях .

См. также [ править ]

Гиперлоглог

Ссылки [ править ]

^ Нельсон, Джелани; Ю, Хуачэн (2020). «Оптимальные границы для приближенного подсчета». arXiv : 2010.02116 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Цидон, Эрез, Иддо Ханниэль и Исаак Кесласси. «Оценщикам также нужны общие ценности, чтобы расти вместе». ИНФОКОМ, 2012 г. Труды IEEE. ИИЭР, 2012.
^ Эйнцигер, Г.; Феллман, Б.; Касснер, Ю. (апрель 2015 г.). «Независимые счетчики оценок». Конференция IEEE по компьютерным коммуникациям (INFOCOM) 2015 . стр. 2560–2568. дои : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0 . S2CID 15673730 .

Источники [ править ]

Моррис Р. Подсчет большого количества событий в маленьких регистрах . Сообщения ACM 21, 10 (1978), 840–842.
Флажоле, П. Приблизительный подсчет: подробный анализ . БИТ 25, (1985), 113–134 [1]
Фукс М., Ли К.К., Продингер Х. Приблизительный подсчет по методу Пуассона-Лапласа-Меллина [2]

[ny2020-1] Нельсон, Джелани; Ю, Хуачэн (2020). «Оптимальные границы для приближенного подсчета». arXiv : 2010.02116 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[2] Цидон, Эрез, Иддо Ханниэль и Исаак Кесласси. «Оценщикам также нужны общие ценности, чтобы расти вместе». ИНФОКОМ, 2012 г. Труды IEEE. ИИЭР, 2012.

[3] Эйнцигер, Г.; Феллман, Б.; Касснер, Ю. (апрель 2015 г.). «Независимые счетчики оценок». Конференция IEEE по компьютерным коммуникациям (INFOCOM) 2015 . стр. 2560–2568. дои : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0 . S2CID 15673730 .

[1]

[2]

[3]