Find the Heavy Hitters using the Lossy Count with Forgetting factor algorithm1.
Keep track of the most frequent item(set)s in a data stream and apply a forgetting factor to discard previous frequent items that do not often appear anymore. This is an approximation algorithm designed to work with a limited amount of memory rather than accounting for every possible solution (thus using an unbounded memory footprint). Any hashable type can be passed as input, hence tuples or frozensets can also be monitored.
Considering a data stream where
n elements were observed so far, the Lossy Count algorithm has the following properties:
All item(set)s whose true frequency exceeds
support * nare output. There are no false negatives;
No item(set) whose true frequency is less than
(support - epsilon) * nis outputted;
Estimated frequencies are less than the true frequencies by at most
epsilon * n.
support (float) – defaults to
The support threshold used to determine if an item is frequent. The value of
supportmust be in \([0, 1]\). Elements whose frequency is higher than
supporttimes the number of observations seen so far are outputted.
epsilon (float) – defaults to
Error parameter to control the accuracy-memory tradeoff. The value of
epsilonmust be in \((0, 1]\) and typically
support. The smaller the
epsilon, the more accurate the estimates will be, but the count sketch will have an increased memory footprint.
alpha (float) – defaults to
Forgetting factor applied to the frequency estimates to reduce the impact of old items. The value of
alphamust be in \((0, 1]\).
>>> import random >>> import string >>> from river import sketch >>> rng = random.Random(42) >>> hh = sketch.HeavyHitters()
We will feed the counter with printable ASCII characters:
>>> for _ in range(10_000): ... hh = hh.update(rng.choice(string.printable))
We can retrieve estimates of the
n top elements and their frequencies. Let's try
>>> hh.most_common(3) [(',', 122.099142...), ('[', 116.049510...), ('W', 115.013402...)]
We can also access estimates of individual elements:
>>> hh['A'] 99.483575...
Unobserved elements are handled just fine:
>>> hh[(1, 2, 3)] 0.0
Veloso, B., Tabassum, S., Martins, C., Espanha, R., Azevedo, R., & Gama, J. (2020). Interconnect bypass fraud detection: a case study. Annals of Telecommunications, 75(9), 583-596. ↩