# Tag Info

## Hot answers tagged streaming

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

2

This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $... 1 Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced. 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