Let $h: U \to \{0, \dots, M-1\}$ be a universal hash function.
Let $C$ be a counter of size $M$, initially $C[i] = 0$ for $i \in \{0, \dots, M-1\}$
Define $\operatorname{update}(x): C[h(x)] = C[h(x)] +1$, increase $C[h(x)]$ by one.
Define $\operatorname{query(x)} \Rightarrow x \rightarrow C[h(x)]$, returns $C[h(x)]$.
After $n$ queries, let us denote $a(x)$ as the true number of occurrences of $x$.
What is the best estimate of $\mathbb{P}(\operatorname{query}(x)>a(x)+ \epsilon \cdot n)$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Welcome to MSE. This question looks as copied from homework. It will probably be closed unless you show some effort on your part. Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress etc $\endgroup$– leonbloyCommented Nov 28, 2021 at 17:51
-
$\begingroup$ I recently knew about how we can use approximate algorithms to solve problems fast. I started self studying from this source: cs.columbia.edu/~andoni/s17_advanced/algorithms/mainSpace/files In the first lecture, they started with the problem of counting: cs.columbia.edu/~andoni/s17_advanced/algorithms/mainSpace/files/… I have just rephrased the questions from 1.0.2 and 1.03, the solution is already here but I could not understand. $\endgroup$– IlyaCommented Nov 28, 2021 at 18:55
-
$\begingroup$ The same problem is addressed here in Chapeter2 (Counting Problems): sketchingbigdata.org/fall20/lec/notes.pdf Maybe I need some preparation in other topics, it would be great in someone could guide me to where I can start $\endgroup$– IlyaCommented Nov 28, 2021 at 18:58
Add a comment
|