There has been much research and progress devoted towards algorithms for finding approximate $\ell_p$-Heavy Hitters with parameter $\epsilon$ in the streaming setting (For all 3 of the vanilla, strict turnstile, and general turnstile streaming models).
The scenario is as follows: Suppose that we have a stream of items of the form $\{(i_1, \Delta_1), ... (i_m, \Delta_m)\}$, where $\{i_1, ... , i_m\} \in [n] = \{1, ... , n\}$, all $\Delta_i \in \{ -M, ... , M\} \subseteq \mathbb{R}$, and $m$ is the length of the stream.
We receive the tokens in the stream one at a time, and upon a new token $(i_j, \Delta_j)$, we update a vector $\mathbf{f} \in \mathbb{R}^n$ (Initially the zero vector), with $\mathbf{f}_{i_j} += \Delta_j$.
Now, we don't actually explicitly store the vector $\mathbf{f} \in \mathbb{R}^n$, as $n$ could be so large as to make it infeasible. So the idea is to come up with a data structure that stores a compressed representation of $\mathbf{f}$, say $\mathbf{\hat{f}}$, where the dimension of $\mathbf{\hat{f}}$ is sublinear in $n$, such that we can estimate the summary statistic of $\mathbf{f}$ from $\mathbf{\hat{f}}$ that we are interested in, within some error range $\epsilon \in (0,1)$, and with some probability gaurantee $\delta \in (0,1)$ . Finally, I should add that in most cases we are interested in a 1-pass algorithm, that is, we only get access to the stream once, and cannot 'replay' it. This is more reflective of real life situations where live updates come and go and there is no way to pass over the stream again.
In the approximate $\ell_p$-Heavy Hitters with parameter $\epsilon$ problem, the 'summary statistic' we wish to return is a set $\hat{L}$ such that for all $i \in [n]$ such that $|f_i| \geq \epsilon \| \mathbf{f} \|_p$, then $i \in \hat{L}$. We allow for some false positives, such that $|\hat{L}| \leq c|L|$, where c is a constant and $L$ is the true set of Heavy hitters. Some of the heavy hitter streaming algorithms are randomized, some deterministic.
Some of the more well known methods include the Misra-Gries algorithm, the Count-Min/Count-Median sketch, the Expander sketch and more.
Some links on these methods: https://en.wikipedia.org/wiki/Misra%E2%80%93Gries_summary https://www.sketchingbigdata.org/fall20/lec/notes.pdf - Page 44
https://arxiv.org/pdf/1604.01357.pdf
My question is has there been any investigation or work done looking into returning the lightest elements in a dataset? For instance, we can define it as: approximate $\ell_p$ 'Light' Hitters with parameter $\epsilon$, where we wish to return the indices of all $f_i$ such that $|f_i| < \epsilon \| \mathbf{f} \|_p$, using small space.
This seems to be much harder as, intuitively, if compressing the data, the noise incurred by any element with a smaller frequency will on average be much higher than the noise incurred by a higher frequency element. For example, in the count-sketch, if a low frequency item collides with a high frequency one, the count of the high frequency element will change less relative to its true count than vice versa, simply because it has a higher frequency.
Further, the idea of taking the set difference of the heavy hitters indices and $[n]$ to solve this doesn't exactly work either for 2 reasons:
- We may receive some false positives of items within some small gap less than $\epsilon \| \mathbf{f}\|_p$.
- The idea would be to compute it using small space: so if solving for the heavy hitters problem, that would mean that if we wanted a small set of light elements, we would have to expand our threshold for what constitutes a heavy hitter, and thus use more space than would be ideal. (I.e. keep more 'heavy' hitters).
