Скажем, вы смотрите на трафик для профилей Facebook. У вас есть миллиарды хитов. Вы хотите узнать, к каким профилям обращаются чаще всего. Вы можете вести подсчет для каждого профиля, но тогда у вас будет очень большое количество отсчетов, подавляющее большинство которых будет бессмысленным.
При подсчете с потерями вы периодически удаляете элементы с очень малым количеством из таблицы. Профили, к которым чаще всего обращаются, почти никогда не будут иметь низкое количество, и если они это сделают, они вряд ли останутся там надолго.
Алгоритм в основном включает в себя группирование входных данных в блоки или блоки и подсчет внутри каждого блока. Затем вы уменьшаете число для каждого элемента на единицу, сбрасывая все элементы, количество которых уменьшается до нуля.
Наиболее часто посещаемые профили попадут на ваш счет и останутся там. Любые профили, которые не попадают очень часто, упадут до нуля через несколько блоков, и вам больше не придется их отслеживать.
Обратите внимание, что окончательные результаты зависят от порядка, придавая больший вес подсчетам, обработанным последним. В некоторых случаях это имеет смысл и является преимуществом, а не недостатком. (Если вы хотите узнать, какие профили наиболее популярны в настоящее время , вы хотите оценить доступы сегодня больше, чем доступы в прошлом месяце.)
В алгоритм внесено множество уточнений. Но основная идея заключается в том, чтобы находить сильных нападающих без необходимости отслеживать каждый элемент, периодически очищать счетчики от любых элементов, которые, по-видимому, не являются сильными нападающими на основании данных.