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