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

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring '20)} \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}
\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\begin{document}

\lecture{3: Dictionary via Hashing, Perfect Hashing}{Jan 28,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Benjamin Most, Sian Lee Kitt}}

\section{Background}

We have some fixed universe (a large set of numbers) [\textit{U}]=$\{1,2,...,U\}$.\newline

\noindent\textbf{Problem:} Given some subset $S\subset U$, with $|S|=m$, and some $x\in U$, report if $x\in S$.\newline

Last class, we discussed non-hashing solutions to this problem, including storing the entirety of $S$, using a Binary Search Tree, and using a bit array to store whether or not a value $x\in U$ is in $S$.

In this lecture, we discuss how to solve this problem using hashing.\newline

\noindent
\textbf{Background terms/notation:}

Collisions occur when our hash functions maps two elements into the same cell.

The expression $[k]$ for some integer $k$ refers to the set $\{1,2,...,k\}$.

\begin{center}
\includegraphics[scale=0.5]{circles.png}
\end{center}

As displayed in the image above, we will consider hash functions mapping from $[U]$ to $[n]$. If $U > n \cdot m$ for some number $m$, then $\exists i\in [n]$ such that $|h^{-1}(i)|>m$, where $h$ is our hash function.

\section{Hashing}

There are multiple ways we could solve the problem explained above using hashing.

\subsection{Knuth's Solution}

Knuth suggests the hash function $$h(x) = \floor{ \{\frac{\sqrt{5}-1}{2}x)\}n}$$

where the curly brackets denote taking the fractional part of the expression they contain.

Because it is deterministic, this hash function would perform better in some cases than in others, and in some scenarios it might lead to a high number of collisions.

\subsection{Solution 1: Random Function}

For every possible input $x$, we could randomly select the value of $h(x)$ and avoid all collisions. In this case, the average query time would be the expected value for the number of collisions we will get on computing the hash of $x$, which we denote as $C_x$. Therefore,

\begin{equation}
\begin{split}
\mathbb{E}_{n}[C_x]& = \mathbb{E}_{n}[\#\text{ of }y\in S, y\not=x,h(y)=h(x)]\\
&=\mathbb{E}_n[\sum_{\substack{y\in S \\ y\neq x}} \mathbbm{1}[h(y)=h(x)]]\\
&\leq m \cdot \frac{1}{n}
\end{split}
\end{equation}

So $\mathbb{E}[\text{query time}]=O(1)$ as long as $n\geq m$.

\subsection{Solution 2: Less random}

\textbf{Definition:} $H$ family of $h:[U]\rightarrow[n]$ is \underline{universal} if:
$$\forall x \not = y, \underset{h\in H}{Pr}[h(x)=h(y)]=\frac{1}{n}.$$\newline

\noindent
\textbf{Example:} The family containing all hash functions is universal.\newline

\noindent
\textbf{Fact:} There exists a universal hash function family $H$ such that $lg|H|=O(lg\text{ }U)$.\newline

\noindent\textbf{Definition:} $H$ is $\alpha$-almost-universal for $\alpha\geq 1$ if:
$$\underset{h\in H}{Pr}[h(x)=h(y)]\leq \frac{\alpha}{n}$$.\newline

\noindent
\textbf{Example} [Dietzfelbinger et al., '97]:\newline

$\forall a\in [U],$
$h_{a}(x)=\floor{(a\cdot x) \% U)/n}.$

$H=\{h_a,a\in U\text{ odd}\}$.\newline

\noindent
\textbf{Fact:} $H$ is 2-almost-universal. This is equivalent to:

$$\forall x\not = y \in [U], \underset{a\in U\text{ odd}}{Pr}[h_{a}(x)=h_{a}(y)] \leq 
\frac{2}{n}$$



\section{Perfect Hashing}
The goal of perfect hashing is to have zero collisions.\\
We want O(1) query time. Define:\\
\begin{equation}
    C \triangleq \sum_{x \in S} C_x
\end{equation}

Zero collision count, C = 0, means that every bucket has at most one element. 

\subsection{Achieving a Zero Collision Count}

We have that:

\begin{equation}
    \mathbb{E} [C] = \mathbb{E} [\sum_{x \in S} C_x] \leq \frac{m^2}{n}
\end{equation}
Recall: $\mathbb{E} [C_x] \leq m/n $.\\~\\

\noindent
If we fix $n = 4m^2$, then

\begin{align*}
    & \mathbb{E} [C] \leq \frac{1}{4}.\\
    & \text{By Markov bound } Pr [C > \frac{3}{4}] \leq \frac{1}{3}\\
    & \text{With a probability} \geq \frac{2}{3}, C \leq \frac{3}{4}\\
    & \text{but since C} \in \mathbb{Z} \text{ then } C = 0.
\end{align*}
\\~\\

\subsection{Solution 3}

The algorithm is as follows:\\
\begin{align*}
    & \text{At preprocessing, given input S, pick h randomly}\\
    & \text{If C = 0, done.}\\
    & \text{Else, try again.}
\end{align*}
Query time: $O(1)$ deterministically\\
Space: $O(m^2$) \\~

\subsection{Solution 4: (Perfect Hashing)}

We have two levels of hash functions: $h: [U] \rightarrow [n]$ (1st level)\\
$h_i: [U] \rightarrow [n_i]$ (2nd level) where $i \in [n] $ and $ 1 \leq n_i \leq m$ \\~\\

For Solution 4, we will use a two-level hashing system, with a goal of having no collisions in our 2nd-level arrays.

Our first-level hash function, $h$, will take elements of $[U]$ as input and return an output in $[n]$. We will have use an array $A$ of length $n$, with $n$ pointers to subarrays $A_1, A_2,...,A_n$.

Our second-level hash functions, $h_1,h_2,...,h_n$, will take an element of $[U]$ as input and return an element of $[n_i]$, where $n_i$ is the length of subarray $A_i$. With this two-level hashing scheme, we can use $h$ to find which subarray to access, then use the appropriate $h_i$ to find the value we seek within that subarray, with no collisions in the subarrays giving us perfect hashing.

\includegraphics[scale=0.5]{img1.png}

\begin{align*}
    & \text{Pick h:[U] $\rightarrow$ [n] }\\
    & \text{Let $s_i$ = number of elements x $\in$ S s.t. $h(x) = i$}\\
    & \text{$n_i \triangleq 4s_i^2$}\\
    & \text{At preprocessing for each  $i \in [n]$,} \\
    & \text {if $\exists$ collisions in $A_i$, resample $h_i$ until there are no collisions.}\\
    & \text{(With probability $\geq \frac{2}{3}$ there would be no collisions.)}\\
    & \text{Once there are no collisions for $i$, move on to $i+1$}
\end{align*}

\noindent
Query time: $O(1) + O(1) \implies O(1)$. $O(1)$ for first level hashing and $O(1)$ for second level hashing since there are no collisions.  This is deterministic.\\

\noindent
Space: $O(1) + O(n) + O(n) + O(\sum_{i \in [n]} n_i) = O(n) + O(\sum_{i \in [n]} s_i^2)$ where the hash function requires space $O(1)$, the first-level array requires space $O(n)$, and each $h_i$ requires space $O(1)$ (so all $h_i$ functions require space $O(n)$). The $O(\sum_{i \in [n]} s_i^2)$ term refers to the sum of the space required by each subarray.

Note that we approximate $n=m$.\newline

\noindent
\textbf{Claim}: $\mathbb{E} [ \sum_{i} s_i^2] = O(m)$.
\begin{proof}

    \begin{align*}
        & \mathbb{E}[\sum_i s_i^2] = \mathbb{E} [\sum_{i=1}^{n} S_i (S_i -1)] + \mathbb{E} [\sum_i S_i]\\
        & (\text{where $s_i (s_i -1)$ is the number of collisions in bucket $i$})\\
        & = \mathbb{E}[C] + m\\
        & \leq \frac{m^2}{n} + m \\
        & \leq O(m) \text{ as long as $n = \Omega(m)$}
    \end{align*}
  
\end{proof}

\noindent
So $\mathbb{E}[space] = O(m)$. \\
By Markov, space $\leq O(m)$ with probability $ \geq \frac{1}{2}$.

\section{Consistent Hashing}
Consider a scenario in which we have m objects, n servers (similar to buckets) where n is much smaller than n (n $\ll$ m). \\

\noindent
$\mathbb{E}[C_x] \leq \frac{m}{n}$. where $C_x =$ objects per server. \\
$\mathbb{E}[x \in S \text{(Server) s.t. } h(x) = i] \leq \frac{m}{n} \forall i \in [n]$.\\

But servers cannot last forever. Say we want to rebalance the network with new servers. We need to move a bunch of items to a new server.

For example: $h: [U] \rightarrow [n]$, $h':[U] \rightarrow [n+1]$.

Items will completely reshuffle, and about $~ 1 - \frac{1}{n}$ of the total items will be moved. 

The goal is to have no collisions in the second level array. If size of second level using $4m^2$, then no collisions. 



\end{document}
