6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Thomas supports Monica Sep 17 '15 at 13:05
  • $\begingroup$ @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. $\endgroup$ – R B Sep 17 '15 at 13:33
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 17 '15 at 22:53
  • $\begingroup$ I guess this is the Las Vegas/Monte Carlo distinction. Randomness is used for speed, but not correctness. $\endgroup$ – Thomas supports Monica Sep 17 '15 at 22:59
  • $\begingroup$ 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. $\endgroup$ – Jelani Nelson Sep 18 '15 at 3:34
  • $\begingroup$ @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. $\endgroup$ – Thomas supports Monica Sep 18 '15 at 4:11
2
$\begingroup$

If you allow randomization, the CountMin (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 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. Once again, with additional work, this can be made to work with negative weights too.

$\endgroup$
  • 2
    $\begingroup$ 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: 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$. $\endgroup$ – Jelani Nelson Sep 18 '15 at 3:25
  • 2
    $\begingroup$ 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)))$. $\endgroup$ – Jelani Nelson Sep 18 '15 at 3:28
  • $\begingroup$ 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). $\endgroup$ – Jelani Nelson Sep 18 '15 at 3:30
  • $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 18 '15 at 4:27
  • $\begingroup$ 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. $\endgroup$ – R B Sep 18 '15 at 8:46
0
$\begingroup$

I think "A High-Performance Algorithm for Identifying Frequent Items in Data Streams" by Anderson, et al. shows an answer, though the weights are integral, not real.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.