\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage[ruled,vlined]{algorithm2e}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{4: Perfect Hashing, Intro to Sketching and Streaming}{Jan 11,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Max Helman, Elena Gribelyuk}}

\section{Perfect Hashing}
\subsection{Background}

Recall that we have a dictionary that when given $S \subset U$ is designed to answer the query "is $x \in S$?". Furthermore, we define: $$n \triangleq |S|$$ $$h: U \to [m]$$ $$C_x = \# y \neq x, y \in S \text{ s.t. } h(x) = h(y)$$ $$C = \sum_{x \in S} C_x$$
We claim that $\mathbb{E}\left[C\right] \leq \frac{n^2}{m}$, which allows us to construct a hash table of size $m = 4n^2$ where the size of each bucket $\leq 1$.

\subsection{Definition}
\begin{theorem}
Perfect hashing can always give us a data structure using $O(n)$ space, $O(1)$ query time, $O(n)$ construction time.
\end{theorem}

\begin{proof}
  To prove the properties of perfect hashing, we combine "standard" hashing with our $4n^2$ solution:
  \begin{figure}[h]
\centering
\includegraphics[width=4.5in]{hashdiagram.png}
\label{fig_sim}
\end{figure}

  We are given $h: U \to [m]$ where $m \approx n$. A potential issue is that some buckets may be large ($> > 1$). We measure their size with: $$n_i \triangleq \text { size of bucket $i$ } = \left|h^{-1}(i) \cap S \right|$$
  From here, we add a second level to the hash table using the quadratic space solution. Our algorithm for perfect hashing is as follows:
  
  \begin{algorithm}[H]
\SetAlgoLined
\KwResult{a data structure using $O(n)$ space, $O(1)$ query time, $O(n)$ construction time}
 Pick some random $h : U \to [m]$ where $m=n$ \\
 \For{$i \in m$}{
  Build a second level hash function using $h_i: U \to \left[4n_i^2\right]$ such that there are no collisions in the second level ($\left[4n_i^2\right]$)
  }

\textbf{return} the two-level hash table
 \caption{Constructing a Table with Perfect Hashing}
\end{algorithm}
  Now, we must analyze this algorithm. Its correctness and consistent $O(1)$ query time are immediate by construction. The algorithm uses $O(n) + O \left(\sum_i n_i^2 \right)$ space, corresponding to the first level table and second level tables respectively.
  \begin{claim}
  $\mathbb{E}\left[\sum_i n_i^2\right] = O \left( n \right)$
  \end{claim}
  \begin{proof}
    $$\mathbb{E}\left[\sum_i n_i^2 \right] \leq 2 \cdot \mathbb{E}\left[C\right]$$
    $$= \mathbb{E} \left[ n_1 + 2C_1 + n_2 + 2C_2 + ... \right]$$
    $$= \mathbb{E} \left[ C + \sum_i n_i \right] = n + \mathbb{E}\left[ C \right]$$
    $$= n + \frac{n^2}{m} = 2n$$
  \end{proof}
  Note that in this proof, we add a factor of $2$ because we have not defined whether we count a single collision as $1$ collision ($x$ collides with $y$) or $2$ collisions ($x$ collides with $y$ and $y$ collides with $x$). We also use the identity $n_1^2 = n_1(n_1 - 1) = n_1 + \binom{n_1}{2}$, where $\binom{n_1}{2}$ represents the number of collisions in bucket $1$.
  
  \begin{observation}
  Space is $O(n)$ in expectation only, but by Markov bounds, we know that it is $O(n)$ with probability $\geq 90\%$. Furthermore, we can repeat the construction $O(1)$ times until we achieve $O(n)$ space.
  \end{observation}
 Therefore, we have proved that perfect hashing will always give us a data structure using $O(n)$ space, $O(1)$ query time, $O(n)$ construction time.
\end{proof}
We remark that in this construction, we used expectation to provide analysis; a result of this is that it is enough to use universal hash functions to achieve these results.

\section{Intro to Sketching and Streaming}
\subsection{Motivation}
Next, we shift to the second topic of this course: sketching and streaming. Suppose we are given a stream of data $x_1, ..., x_m$ as to an algorithm. Our goal will be to store a "sketch" that maintains several key properties of the data such that the size of the sketch is smaller than or equal to the size of the original input data. 

\subsection{The Count-Distinct Problem}
Consider the problem of counting distinct elements in a stream of size $m$; in particular, given $x_1, x_2, ..., x_m \in [n] = \{1, 2, ..., n\}$, we want to find the number of values of $[n]$ that appear at least once, i.e. the number of different values $x_i$ present in the stream. This is a well-known problem with numerous applications-- for instance, the elements might represent IP addresses of packets processed by a router or visitors to a website. 

Note that we will analyze the space used by the proposed algorithm to be able to answer the desired question (i.e. the count-distinct question) at the end of the stream. This will be our sole performance measure, as we are currently discounting the time complexity of updating the sketch.

To solve this problem, we can immediately come up with the following relatively-naive, deterministic solutions:
\begin{itemize}
    \item Use a hash table $H$. If $x_i \not \in H$, hash $x_i$ to insert it into the table. The space utilized by this solution is $O(d) \leq O(n)$, where $d = $ number of distinct items in the stream. 
    \item Alternatively, store every $x_i$ in the stream. This will take $O(m\textrm{ log}n)$ space.
\end{itemize}

So, we are led to ask: is it possible to do better? If we aim for an exact, deterministic solution, the answer is no. But, if we allow approximation and randomization, we can achieve a much better space complexity. 

\subsection{The Flajolet-Martin Algorithm}
\begin{theorem}
For $\epsilon < \frac{1}{2}$, $d > \Omega(\frac{1}{\epsilon^2})$. Furthermore, we can achieve $O(\frac{\textrm{log}n}{\epsilon^2})$ space complexity. 
\end{theorem}

We will use the concept of a hash function to reduce the space complexity of our solution to the distinct element counting problem. However, in contrast to previously-used hash functions, we now define a fully random hash function $h: [n] \rightarrow [0,1]$. We now introduce the Flajolet-Martin algorithm.

\begin{algorithm}[H]
\SetAlgoLined
\KwResult{number of distinct elements appearing in the stream}
 $z = 1$\;
 \For{$i \gets 1$ \textbf{to} $m$}{
  $z \gets min\{h(i), z\}$
  }
\textbf{return} $\frac{1}{z} -1$
\caption{Flajolet-Martin}
\end{algorithm}
 
To demonstrate that this algorithm provides the correct result with $\geq$ 90\% probability, we will assert and prove a series of claims. 
\begin{claim} $\mathbb{E}[z] = \frac{1}{d+1}$.\end{claim}
    \begin{proof}
    To see this, we note that $z$ is defined to be the minimum value of $d$ random variables over $[0,1]$. Pick some $a \in [0,1]$ at random. Then, since $h$ maps values in $[n]$ to $[0,1]$ uniformly, it must be that the probability $Pr[a < z] = z$ precisely. Alternatively, we note that the quantity $Pr[a < z]$ also represents the probability that $h(x_m) = min\{h(x_1), h(x_2), ..., h(x_m)\}$. In other words, this is equal to the probability that when we choose $d+1$ random variables uniformly in $[0,1]$, the last chosen value $h(x_m)$ is the smallest. Thus, $Pr[a < z] = \frac{1}{d+1}$. As a result, we conclude that $z = \frac{1}{d+1} \implies \mathbb{E}[z] = \frac{1}{d+1}$, as desired.
    \end{proof}
    
    \begin{observation} We observe that $\mathbb{E}[\frac{1}{z}] \not = \frac{1}{\mathbb{E}[z]}$ in general, suggesting that our estimator $\frac{1}{z} -1$ is biased. So, in order to find upper and lower bounds for our estimate, we will now proceed to assert and prove a concentration bound for $z$. \end{observation} 
    
\begin{claim} For a fixed completely-random hash function $h:[n] \rightarrow [0,1]$, $var_h[z] \leq \frac{2}{d^2}$.\end{claim}
    \begin{proof}
    To compute $var_h[z]$, note that $$var_h[z] = \mathbb{E}[z^2] - \mathbb{E}[z]^2$$ By the result of Claim 5, we know that $\mathbb{E}[z]^2 = \frac{1}{(d+1)^2} > 0$, so $$var[z] = \mathbb{E}[z^2] - \mathbb{E}[z]^2 \leq \mathbb{E}[z^2]$$
    Now, fix an $x \in [0,1]$. Since $h$ is fully random and $h$ takes independent values in the range $[0,1]$ , we see that $$Pr[x < z^2] = Pr[\sqrt{x} < z] = \prod_{i=1}^{d}Pr[\sqrt{x} < h(x_i)] = (1-\sqrt{y})^d$$ Let $f_a(y)$ be the probability density function for $z$ over $[0,1]$, and note that $f_a(y) = 1$ $\forall y \in [0,1]$ since $h$ takes values of $[0,1]$ uniformly. Then, it follows that $$\mathbb{E}[z^2] = Pr[a < z^2] = \int_{0}^{1}Pr[y < z^2] \cdot f_a(y) dy = \int_{0}^{1}(1-\sqrt{y})^d dy = $$ $$-\frac{2(1-\sqrt{y})^{d+1}((d+1)\sqrt{y} +1)}{(d+1)(d+2)}\left(1-2t\right)\bigg|^{1}_{0} = \frac{2}{(d+1)(d+2)} \leq \frac{2}{d^2}$$
    
    \end{proof}

But, we ask if this a good enough bound for us? Unfortunately, this result does not rule out the possibility that $z =0$, which is problematic. However, it is possible to get a $1 \pm \epsilon$ factor approximation by running $k = O(\frac{1}{\epsilon^2})$ Flajolet-Martin algorithms for independently and identically distributed random variables. To achieve a $1 \pm \epsilon$ approximation, we present the Bottom-$k$ algorithm in the following section. 

\subsection{The Bottom-$k$ Algorithm}

The Bottom-$k$ Algorithm yields a $1 \pm \epsilon$ approximation for the number of distinct elements seen.
 
 \begin{algorithm}[H]
\SetAlgoLined
\KwResult{number of distinct elements appearing in the stream}
 $z_1,...,z_k = 1$\;
 \For{item $i$ in stream}{
  Compute $h(i)$\;
  Maintain $z_1 < z_2 < ... < z_k$ smallest $k$ hash values seen in stream
  }
\textbf{return} $\frac{k}{z_k}$
\caption{Bottom-$k$}
\end{algorithm}

We now want to prove $\hat{d} = \frac{k}{z_k}$ is within $1 \pm \epsilon$ of $d$ with $\geq 90\%$ probability.

\begin{claim}
    $Pr \left[ \hat{d} > d \cdot (1 + \epsilon) \right] \leq 0.05$ for $k = O \left( \frac{1}{\epsilon^2} \right)$. We can prove the other direction similarly.
\end{claim}

\begin{proof}
$\hat{\delta} > \delta \cdot (1 + \epsilon) \iff \frac{k}{z_k} < \delta \cdot (1 + \epsilon)$\\
\indent \indent \indent \indent \indent \indent $\iff z_k < \frac{k}{\delta \cdot (1 + \epsilon)}$ \\
\indent \indent \indent \indent \indent \indent $\iff \exists$ at least $k$ items in stream whose hash function values $< \frac{k}{\delta \cdot (1 + \epsilon)}$ \\
Now, we define $\pi = Pr \left[\text{choose $d$ random variables } \in [0,1] \text{ such that at least $k$ of them $< \frac{k}{\delta \cdot (1 + \epsilon)}$} \right]$. We define $x_i$ as the indicator random variable of the $i$th distinct item meeting the condition $h(i) < \frac{k}{\delta \cdot (1 + \epsilon)}$. Now, we see:
$$\mathbb{E}\left[ x_i \right] = Pr \left[ h(i) < \frac{k}{\delta \cdot (1 + \epsilon)} \right]$$
$$Var \left( x_i \right) \leq \mathbb{E} \left[ x_i^2 \right] \leq \frac{k}{\delta \cdot (1 + \epsilon)} < \frac{k}{\delta}$$
$$\mathbb{E} \left[ \sum_i x_i \right] = \delta \cdot \frac{k}{\delta \cdot (1 + \epsilon)} = \frac{k}{1 + \epsilon}$$
Of particular interest is the expectation of the sums, which leads to the result:
$$Var \left( \sum_i x_i \right) = \delta \cdot var \left( x_i \right) = k$$
This allows us to use Chebyshev's inequality to prove our bound:
$$Pr \left[ \sum_i x_i - \frac{k}{1 + \epsilon} > 20k \right] \leq \frac{1}{20} = 0.05$$
$$\sum_i x_i > \frac{k}{1 + \epsilon} + \sqrt{20k}$$
We observe that $\frac{k}{1 + \epsilon} + \sqrt{20k}$ for $k = c \cdot \frac{1}{\epsilon^2}$ and large enough $c$.
$$\iff \pi \left[ \sum_i x_i > k \right] \leq 0.05$$
\end{proof}

\section{Acknowledgements}
In producing this document, we referenced the lecture notes, as well as the scribe notes from lecture 4 of the 2017 Advanced Algorithms course, as provided on the current course website.

\end{document}
