5

$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful. Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful. $F_1$ counting, or ...


5

A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.) One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\...


3

You can do $O(\log \frac n\epsilon)$ space if you only want an approximation. The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set Lowerbound (which you can find, e.g., in the Arora-Barak book). So you pick a target $y$ and observe whether $h(x_i)$ holds for any $i$. If the sequence is diverse, ...


3

I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?" The answer is that the data structures you have outlined are not sufficient by ...


2

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number. Building block: sampling without arbitrary precision arithmetic Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$). Then one ...


2

A graphical user interface that contains more than a few tens of components would be very confusing for the user. This means that, whatever data structure is used, it doesn't have to scale to large instances. The user is unlikely to generate more than a couple of mouse-clicks per second, so whatever data structure is used, it doesn't even have to be ...


2

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


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


1

Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.


1

The problem with your counterexample is that the type you presented is not a valid instance of ArrowApply as far as I can tell. You didn't present what the implementation of app but the only one I could come up with (where you use the input stream function once and then discard it) doesn't satisfy the 2nd and 3rd ArrowApply laws. What definition of app did ...


1

The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$. It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there. For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.


Only top voted, non community-wiki answers of a minimum length are eligible