<p>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.</p>

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

<p><i>1.</i> 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$.</p>

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

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

<p><b>Claim.</b> 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$.</p>

<p>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'$.</p>

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

<p>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.</p>

<p><b>Bernstein's Inequality.</b> 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$.</p>

<p>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).$$</p>

<p>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:</p>

<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2015-09-17T22:53:04.433Z
I think Misra-Gries, Lossy Counting, and Space Saving are essentially deterministic. A hash function can be used to speed up the update time, but if you are fine with $1/\theta$ update time, then you don't need it. I might be missing something.
Sasho Nikolov
CC BY-SA 3.0
2015-09-17T22:59:12.770Z
I guess this is the Las Vegas/Monte Carlo distinction. Randomness is used for speed, but not correctness.
Thomas Steinke
CC BY-SA 3.0
2015-09-18T03:34:41.123Z
Sasho: I think you really mean $1/\varepsilon$ and not $1/\theta$. In any case, even without randomization (i.e. no hashing), you can get $\log(1/\varepsilon)$ update time using an augmented balanced BST.

Also, Thomas: how do you know whether to repeat $T$ times? You don't know all weights a priori, right? My impression from "algorithm is required to return all elements whose sum of weights is at least ..." of OP is that the same item can be updated multiple times.
Jelani Nelson
CC BY-SA 3.0
2015-09-18T04:11:30.450Z
@JelaniNelson Right. How to pick the right $T$ is unclear, as it must be done at the start and requires a rough estimate of the total weight $w$. I'm not sure how to solve this problem.
Thomas Steinke
CC BY-SA 3.0
2015-09-17T15:38:15.093Z
2015-09-17T15:51:17.507Z
2015-09-17T15:51:17.507Z
Thomas Steinke
<p>If you allow randomization, the <a href="https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf?attachauth=ANoY7cp1a_5Uj5QbLdZ74SjRCuZ5Dw62HtahmsyZDDniMswKBNfZQzrikZOMiXGSTbYxZtqv7Xn2jKGQfNsNsVzx1Wzk0HUSsAzTBnmqiWMCBlGjZJN_v8c-00DQD7CEc2PqBt5aFH7g4shvr6OD4D97eIUySQ-RD0-bAUxft8VLI1l5jH1nUrcLLdsuB81xlhh4T4smDfJYuElJ7KLIdwbAiZkMMryFMg%3D%3D&amp;attredirects=0" rel="nofollow">CountMin</a> (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM shows that with a sketch of size $O(\varepsilon^{-1}\log 1/\delta)$ you can compute a $\tilde{w}_i$ so that $\tilde{w_i} \geq w_i$ always, and $\tilde{w}_i \leq w_i + \varepsilon W$ with probability at least $1-\delta$. Now you can set $\delta &lt; 1/3m$, where $m$ is the length of the stream, so that $\tilde{w}_i$ are accurate for all $i$ you encounter in the stream. As you process the stream, in addition to the sketch at any point you maintain the set $S$ of those $i$ with the $1/\theta$ largest $\tilde{w}_i$. At the end you output the $i$ which have $\tilde{w}_i$ at least $\theta W$ (notice all of them have to be in $S$). The details are a bit more complicated if the weights can be negative, check the paper.</p>

<p>This algorithm can be derandomized using <a href="http://www.cse.iitk.ac.in/users/sganguly/crprecis-escape.pdf" rel="nofollow">CR-precis</a> in place of the CM sketch, but the dependence on $1/\varepsilon$ becomes quadratic, and additional log factors are lost. For a short analysis, you can also check <a href="https://polylogblog.wordpress.com/2009/09/22/bite-sized-streams-cr-precis/" rel="nofollow">Andrew McGregor's blog post</a>. Once again, with additional work, this can be made to work with negative weights too.</p>

CC BY-SA 3.0
2015-09-18T03:25:58.780Z
CM sketch will have worse space than OP desired. Also, for CR Precis, you can do better and it's not any harder. The following is in my RANDOM'12 paper with Huy and David (or just see Section 3 of these lecture notes: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec4.pdf).

The idea is simple. A matrix $\Pi\in\mathbb{R}^{m\times n}$ is said to be $\varepsilon$-incoherent if its columns $\Pi_i$ have unit Euclidean norm, and for $i\neq j$ we have $|\langle \Pi_i, \Pi_j \rangle| < \varepsilon$. The sketch of $x$ will be $\Pi x$. We estimate $x_i$ as $\langle \Pi_i, \Pi x\rangle$.
Jelani Nelson
CC BY-SA 3.0
2015-09-18T03:28:34.203Z
Now note the estimate is $\sum_j x_j \langle \Pi_i, \Pi_j\rangle = x_i + \sum_{i\neq j}x_j \langle \Pi_i, \Pi_j\rangle = x_i \pm \varepsilon \|x\|_1$.

Now the question is just how small can you make $m$, the sketch size. A code with distance $1-\varepsilon$, block length $t$, and alphabet size $q$ implies an incoherent matrix with $m = qt$ (see lecture notes above). A random code can thus be taken with $q = O(1/\varepsilon)$ and $t = O(q\log n)$, giving $m = O(\varepsilon^{-2}\log n)$. Or you can use Reed-Solomon codes, giving $q=t= O(\varepsilon^{-1}\log n/(\log\log n+\log(1/\varepsilon)))$.
Jelani Nelson
CC BY-SA 3.0
2015-09-18T03:30:01.893Z
Using either code is better than the bound in CR-Precis (though they morally did what I just said above but used the wrong code).
Jelani Nelson
CC BY-SA 3.0
2015-09-18T04:27:58.303Z
@JelaniNelson Thanks Jelani, this makes sense, and gives a much better idea about what's happening. I assume this is the best deterministic algorithm you know for heavy hitters with weights (but still increments only)? I agree none of this is as good as what OP asked for.
Sasho Nikolov
CC BY-SA 3.0
2015-09-18T08:46:59.757Z
Thanks Sasho ! I've also thought of CMS, but I don't like the memory overhead. It works better to run SS using a skip list of values in the Frequent data structure. This uses $\epsilon^{-1}$ counters with insertions taking $O(\log\epsilon^{-1})$. I'm trying to get to constant run time, while still having $O(\epsilon^{-1})$ counters. I seem to have a method that uses $2\epsilon^{-1}$ counters with $O(1)$ amortized run time, but with $O(\epsilon^{-1})$ time at worst case, which is not something I can afford.
R B
CC BY-SA 3.0
2015-09-18T17:22:10.137Z
Sasho: $m$ was space in machine words. Misra-Gries etc. use $O(1/\varepsilon)$ words, whereas the dependence on above is $1/\varepsilon^2$. In fact is known that any deterministic linear sketch for $\ell_1$ heavy hitters working when there are both deletions and insertions must have $m = \Omega(1/\varepsilon^2)$ rows. Also, the update time isn't great; it's $\Omega(t) = \Omega(1/\varepsilon)$, since there are $t$ non-zeroes per column of $\Pi$ using codes. It's known that an incoherent matrix cannot have column sparsity better than $\Omega(\varepsilon^{-1}\log n / \log(m/\log n))$.
Jelani Nelson
CC BY-SA 3.0
2015-09-19T01:09:53.927Z
@JelaniNelson I am not sure if Misra-Gries works with arbitrary nonnegative weights? At least I could not quite get the analysis to work. But I guess Space Saving does work fine with non-negative weights.
Sasho Nikolov
CC BY-SA 3.0
2015-09-20T01:57:40.910Z
The Misra-Gries analysis works for arbitrary nonnegative rational weights. Let's say weights are integers first (rational follows by scaling denominators). Consider the following scenario: there are $\sum_i x_i$ folks in a room with $x_i$ people voting for presidential candidate $i$. We make them form as many groups of size $k+1$ as possible such that no two people in the same group like the same candidate. Then we kill everyone who joined a group. Any candidate with > $1/(k+1)$ fraction of votes still has voters left alive. Exactly this process is what Misra-Gries with $k$ counters simulates.
Jelani Nelson
CC BY-SA 3.0
2015-09-17T23:18:39.043Z
2015-09-18T03:25:18.810Z
2015-09-18T03:25:18.810Z
Sasho Nikolov
<p>I think <a href="https://arxiv.org/abs/1705.07001" rel="nofollow noreferrer">"A High-Performance Algorithm for Identifying Frequent Items in Data Streams" by Anderson, et al.</a> shows an answer, though the weights are integral, not real.</p>

CC BY-SA 3.0
2017-06-21T03:19:14.203Z
2017-06-21T03:19:14.203Z
jbapple
<p>The problem of finding <a href="https://en.wikipedia.org/wiki/Streaming_algorithm#Heavy_hitters">heavy hitters</a> 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.</p>

<p>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.</p>

<p>I'm looking for an algorithm for a weighted variant of the problem:</p>

<p>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]$.</p>

<p>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.</p>

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

<hr>

<p>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.</p>

CC BY-SA 3.0
2015-09-17T13:05:41.000Z
Is the only problem with batch decrement and space saving the lack of constant update time? And is $\log(1/\varepsilon)$ update time too slow?
Thomas Steinke
CC BY-SA 3.0
2015-09-17T13:33:05.500Z
@Thomas - correct. Converting SS into $\log(1 / \epsilon)$ time for the weighted case is relatively simple using a skip list of values rather than a simple list.
R B
<ds.algorithms><reference-request><online-algorithms><data-streams><streaming-algorithms>
Algorithm for finding heavy hitters in a weighted stream
R B
# Algorithm for finding heavy hitters in a weighted stream

(Asked by: username_0 on 2015-09-17)

The problem of finding [heavy hitters](https://en.wikipedia.org/wiki/Streaming_algorithm#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.

**Tags:** ds.algorithms, reference-request, online-algorithms, data-streams, streaming-algorithms
> **Comments:**
> **username_1**: Is the only problem with batch decrement and space saving the lack of constant update time? And is $\log(1/\varepsilon)$ update time too slow?  
> **username_0**: @Thomas - correct. Converting SS into $\log(1 / \epsilon)$ time for the weighted case is relatively simple using a skip list of values rather than a simple list.  

---

## 3 answers

### Answer by username_1 on 2015-09-17. Score: 2

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| > 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 > 0$.

Thus $$\mathbb{P}\left[ \left| W\_\text{id}-w\_\text{id} \right| > \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)$.

> **Comments:**
> **username_2**: I think Misra-Gries, Lossy Counting, and Space Saving are essentially deterministic. A hash function can be used to speed up the update time, but if you are fine with $1/\theta$ update time, then you don't need it. I might be missing something.  
> **username_1**: I guess this is the Las Vegas/Monte Carlo distinction. Randomness is used for speed, but not correctness.  
> **username_3**: Sasho: I think you really mean $1/\varepsilon$ and not $1/\theta$. In any case, even without randomization (i.e. no hashing), you can get $\log(1/\varepsilon)$ update time using an augmented balanced BST.  Also, Thomas: how do you know whether to repeat $T$ times? You don't know all weights a priori, right? My impression from "algorithm is required to return all elements whose sum of weights is at least ..." of OP is that the same item can be updated multiple times.  
> **username_1**: @JelaniNelson Right. How to pick the right $T$ is unclear, as it must be done at the start and requires a rough estimate of the total weight $w$. I'm not sure how to solve this problem.  

---

### Answer by username_2 on 2015-09-17. Score: 2

If you allow randomization, the [CountMin](https://7797b024-a-62cb3a1a-s-sites.googlegroups.com/site/countminsketch/cm-latin.pdf?attachauth=ANoY7cp1a_5Uj5QbLdZ74SjRCuZ5Dw62HtahmsyZDDniMswKBNfZQzrikZOMiXGSTbYxZtqv7Xn2jKGQfNsNsVzx1Wzk0HUSsAzTBnmqiWMCBlGjZJN_v8c-00DQD7CEc2PqBt5aFH7g4shvr6OD4D97eIUySQ-RD0-bAUxft8VLI1l5jH1nUrcLLdsuB81xlhh4T4smDfJYuElJ7KLIdwbAiZkMMryFMg%3D%3D&attredirects=0) (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM shows that with a sketch of size $O(\varepsilon^{-1}\log 1/\delta)$ you can compute a $\tilde{w}\_i$ so that $\tilde{w\_i} \geq w\_i$ always, and $\tilde{w}\_i \leq w\_i + \varepsilon W$ with probability at least $1-\delta$. Now you can set $\delta < 1/3m$, where $m$ is the length of the stream, so that $\tilde{w}\_i$ are accurate for all $i$ you encounter in the stream. As you process the stream, in addition to the sketch at any point you maintain the set $S$ of those $i$ with the $1/\theta$ largest $\tilde{w}\_i$. At the end you output the $i$ which have $\tilde{w}\_i$ at least $\theta W$ (notice all of them have to be in $S$). The details are a bit more complicated if the weights can be negative, check the paper.

This algorithm can be derandomized using [CR-precis](http://www.cse.iitk.ac.in/users/sganguly/crprecis-escape.pdf) in place of the CM sketch, but the dependence on $1/\varepsilon$ becomes quadratic, and additional log factors are lost. For a short analysis, you can also check [Andrew McGregor's blog post](https://polylogblog.wordpress.com/2009/09/22/bite-sized-streams-cr-precis/). Once again, with additional work, this can be made to work with negative weights too.

> **Comments:**
> **username_3**: CM sketch will have worse space than OP desired. Also, for CR Precis, you can do better and it's not any harder. The following is in my RANDOM'12 paper with Huy and David (or just see Section 3 of these lecture notes: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec4.pdf).  The idea is simple. A matrix $\Pi\in\mathbb{R}^{m\times n}$ is said to be $\varepsilon$-incoherent if its columns $\Pi_i$ have unit Euclidean norm, and for $i\neq j$ we have $|\langle \Pi_i, \Pi_j \rangle| < \varepsilon$. The sketch of $x$ will be $\Pi x$. We estimate $x_i$ as $\langle \Pi_i, \Pi x\rangle$.  
> **username_3**: Now note the estimate is $\sum_j x_j \langle \Pi_i, \Pi_j\rangle = x_i + \sum_{i\neq j}x_j \langle \Pi_i, \Pi_j\rangle = x_i \pm \varepsilon \|x\|_1$.  Now the question is just how small can you make $m$, the sketch size. A code with distance $1-\varepsilon$, block length $t$, and alphabet size $q$ implies an incoherent matrix with $m = qt$ (see lecture notes above). A random code can thus be taken with $q = O(1/\varepsilon)$ and $t = O(q\log n)$, giving $m = O(\varepsilon^{-2}\log n)$. Or you can use Reed-Solomon codes, giving $q=t= O(\varepsilon^{-1}\log n/(\log\log n+\log(1/\varepsilon)))$.  
> **username_3**: Using either code is better than the bound in CR-Precis (though they morally did what I just said above but used the wrong code).  
> **username_2**: @JelaniNelson Thanks Jelani, this makes sense, and gives a much better idea about what's happening. I assume this is the best deterministic algorithm you know for heavy hitters with weights (but still increments only)? I agree none of this is as good as what OP asked for.  
> **username_0**: Thanks Sasho ! I've also thought of CMS, but I don't like the memory overhead. It works better to run SS using a skip list of values in the Frequent data structure. This uses $\epsilon^{-1}$ counters with insertions taking $O(\log\epsilon^{-1})$. I'm trying to get to constant run time, while still having $O(\epsilon^{-1})$ counters. I seem to have a method that uses $2\epsilon^{-1}$ counters with $O(1)$ amortized run time, but with $O(\epsilon^{-1})$ time at worst case, which is not something I can afford.  
> **username_3**: Sasho: $m$ was space in machine words. Misra-Gries etc. use $O(1/\varepsilon)$ words, whereas the dependence on above is $1/\varepsilon^2$. In fact is known that any deterministic linear sketch for $\ell_1$ heavy hitters working when there are both deletions and insertions must have $m = \Omega(1/\varepsilon^2)$ rows. Also, the update time isn't great; it's $\Omega(t) = \Omega(1/\varepsilon)$, since there are $t$ non-zeroes per column of $\Pi$ using codes. It's known that an incoherent matrix cannot have column sparsity better than $\Omega(\varepsilon^{-1}\log n / \log(m/\log n))$.  
> **username_2**: @JelaniNelson I am not sure if Misra-Gries works with arbitrary nonnegative weights? At least I could not quite get the analysis to work. But I guess Space Saving does work fine with non-negative weights.  
> **username_3**: The Misra-Gries analysis works for arbitrary nonnegative rational weights. Let's say weights are integers first (rational follows by scaling denominators). Consider the following scenario: there are $\sum_i x_i$ folks in a room with $x_i$ people voting for presidential candidate $i$. We make them form as many groups of size $k+1$ as possible such that no two people in the same group like the same candidate. Then we kill everyone who joined a group. Any candidate with > $1/(k+1)$ fraction of votes still has voters left alive. Exactly this process is what Misra-Gries with $k$ counters simulates.  

---

### Answer by username_4 on 2017-06-21. Score: 0

I think ["A High-Performance Algorithm for Identifying Frequent Items in Data Streams" by Anderson, et al.](https://arxiv.org/abs/1705.07001) shows an answer, though the weights are integral, not real.


---

