Algorithm for finding heavy hitters in a weighted stream The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times appear in $\mathcal D$, and no element with frequency lower than $N(\theta-\epsilon)$ belongs to $\mathcal D$. $\epsilon$ and $\theta$ are constant thresholds given as input.

The problem is well studied, with many algorithms developed for it, such as Sticky Sampling, Lossy counting, Batch decrement, and Space Saving. The last two are optimal, in the sense that they require $O(\frac{1}{\epsilon})$ counters and have constant runtime.

I'm looking for an algorithm for a weighted variant of the problem:

Every item in the stream is of a tuple $(id, weight)$, and the goal is the return the elements with the highest weight. All weights are in $(0,1]$.

Formally, a weighted heavy hitters algorithm is required to return all elements whose sum of weights is at least $W\theta$, and no element with weight lower than $W(\theta-\epsilon)$, where $W$ is the sum of weights of the stream elements.


  Are there known (preferably deterministic) algorithms for this problem that use $O(\frac{1}{\epsilon})$ counters and have $O(1)$ runtime?




Batch Decrement and Space Saving does not seem to have a simple generalization to the weighted case, as both maintain a data structure that allows finding the minimum counter in constant time, which might not be doable in the weighted setting.
Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?)
This is probably not the ideal solution, but it's a start.


Weighted Heavy Hitters Algorithm.
Input: $S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$ a weighted stream.

1. Create an unweighted stream $S'=\{\text{id}_j\}_{j=1}^{N'}$ as follows. For every weighted update $(\text{id}_i,\text{weight}_i)$ in $S$, include the unweighted update $\text{id}_i$ in $S'$ independently with probability $\text{weight}_i$.

2. Apply an unweighted heavy hitters algorithm (i.e. Space Saving or Batch Decrement) to $S'$ and output the heavy hitters for $S$.


Clearly this algorithm has $O(1)$ update time. To verify that this algorithm is correct we must prove the following claim.

Claim. With high probability, for every $\text{id}$, the count of $\text{id}$ in $S'$ is close to the sum of the weights of $\text{id}$ in $S$.

Let $w_\text{id}$ be the "true" weight of $\text{id}$ in $S$ and $W_\text{id}$ the weight of $\text{id}$ in $S'$. Let $w=\sum_\text{id} w_\text{id}$ be the total weight of $S$ and $W=\sum_\text{id} W_\text{id}$ be the total weight of $S'$.

Our claim is that $|W_\text{id}-w_\text{id}| \leq \varepsilon w$ for all $\text{id}$ with high probability.

Clearly $\mathbb{E}\left[W_\text{id}\right]=w_\text{id}$. It remains to show concentration bounds. To this end, we use the following result.

Bernstein's Inequality. Let $X_1, \cdots, X_n \in \{0,1\}$ be independent random variables. Then $$\mathbb{P}\left[ \left| \sum_{i=1}^n X_i - \mathbb{E}\left[X_i\right] \right| &gt; t \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{t^2}{t+\sum_{i=1}^n \mathsf{Var}\left[X_i\right]}\right)\right)$$ for all $t &gt; 0$.

Thus  $$\mathbb{P}\left[ \left| W_\text{id}-w_\text{id} \right| &gt; \varepsilon w \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{\varepsilon^2 w^2}{\varepsilon w+w_\text{id}}\right)\right) \leq 2 \cdot \exp\left(-\Omega\left(\varepsilon^2 w\right)\right).$$

Note that if $w_\text{id}=0$, then $W_\text{id}=0$. So we need only consider the $\text{id}$s that appear in the stream. In particular, we can take a union bound over at most $N$ $\text{id}$s:

If $w \geq O\left(\log(N)/\varepsilon^2\right)$, then the weights in $S'$ are close to the weights in $S$ with high probability and the claim is verified.

What about when $w \leq O\left(\log(N)/\varepsilon^2\right)$? Then we can first repeat each weighted update $T$ times. This increases the weight to $Tw$. The good news is that $S'$ is only length $O(Tw)$ and transforming $S$ into $S'$ takes $O(1 + Tw/N)$ (amortized) time per update with high probability. So we just need to find a $T$ with $ O\left(\log(N)/\varepsilon^2\right) \leq Tw \leq O(N)$.