\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm, mathtools, tikz}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\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}}
\newcommand\norm[1]{\left\lVert#1\right\rVert}

\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\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}
\newtheorem{remarks}{Remarks}

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

\begin{document}

\lecture{10: Locality Sensitive Hashing, Graphs}{Feb 11,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Rishav (rk3142), Arjun (aa4664)}}

\section{Overview of Lecture}

Today's lecture is a continuation of our discussion in nearest neighbour search. We will finish the topic, discussing about Local Sensitive Hashing for Hamming Space and then move to graphs.

\section{$c$-ANN for Hamming Space}

Family $\mathcal{H}$ of $h: \{0,1\}^d \xrightarrow{}U$ is a $(r,cr, P_1,P_2)-LSH$ if: $\forall p,q \in \{0, 1\}^d$:
\[
\norm{p-q}_1 \leq r \implies Pr_h[h(p)=h(q)] \geq P_1
\]

\[
\norm{p-q}_1 > cr \implies Pr_h[h(p)=h(q)] < P_2
\]

\begin{fact}
    If $P_{2} < 1, \text{then } P_{1} < 1.$
\end{fact}

The above fact is an example of an isoperimetric statement (and
stronger, more quantative statements are known).

\begin{theorem}
    If there exists $(r,cr,P_1,P_2)$-LSH, then we can solve \textbf{C-ANN} (C-Approximate Nearest Neighbour) with the following parameters:
    \begin{enumerate}
        \item \textbf{Space}: O(nd + \begin{math} {n^\frac{1+\rho}{P_1}}\end{math})
        \item \textbf{Query Time}: O(\begin{math}n^\frac{\rho}{P_1}\end{math}).d.[1 + time to compute h(q)]
    \end{enumerate}
    Where $\rho = \frac{\text{log}\frac{1}{P_1}}{\text{log}\frac{1}{P_2}}$  $\in (0,1)$. $\rho \longrightarrow$ Ratio of the exponents of the probabilities.
\end{theorem}


\begin{observation}
    Let us fix $k \in \mathcal{N}$ and define a new hash function $g(p) = \langle h_1(p), h_2(p), \dots, h_k(p) \rangle$ where $h_1, \ldots h_k \in \mathcal{H}$ iid. $g : \{0,1\}^d \rightarrow U^k$. Then g(p) is defined as follows:
\end{observation}
\[
    g(p) = h_1(p) \cdot h_2(p) \cdot \dots, h_k(p) \in U^k; \text{ where . denotes concatenation}
\]
The above is an LSH with parameters $(r, cr, P_1^k, P_2^k)$. If p, q are close:
\[
    Pr[h_i(p) = h_i(q)] = P_1
\]
\[
    Pr_g[g(p) = g(q)] = \prod_{i=1}^{k} Pr[h_i(p) = h_i(q)]
\]
\[
    Pr_g[g(p) = g(q)] =  P_1^k
\]
    
\textbf{Algorithm}
\begin{enumerate}
    \item \textbf{Preprocessing}: Build a dictionary data structure on points g(p), p $\in$ D(Dataset)
    \item \textbf{Query q}: Compute g(q)
    \begin{enumerate}
        \item Retrieve all points p $\in$ D such that g(p) - g(q), using dictionary data structure
        \item Enumerate through n until find a point p with $\norm{q-p} \leq cr$.
    \end{enumerate}
    \item \textbf{Performance Analysis}
    \begin{enumerate}
        \item \textbf{Space}: dictionary is stored on n points $\longrightarrow$ O(n) [O(nd) to store original points]
        \item \textbf{Query Time}: Time to compute g(q) + time taken to compute distance calculations in the bucket.
    \end{enumerate}

    $$\E[\text{\# distance calculations}] \leq 1 + E[\text{\# distance calculation to points } p \in D: \norm{p-q} \geq cr \text{ and } h(p) = h(q)]$$ \\
    $$\leq 1 + n \cdot P_r[g(p)=g(q)][|| p-q || \geq cr]$$ \\
    By LSH property
    $$\leq 1 + n*P_2^k$$ \\

\end{enumerate}

\textit{Proof.} Assuming there exists $p^*$ at a distance $\leq r$ from q. We will find an ANN. To ensure this algorithm is correct, we need to show that $p^*$ will be in the bucket. That is:
\[
  P_r[\text{algorithm outputs a cr-nearest-neighbor}] \geq P_r[p^*) = g(q)] \geq P_1^k
\]
If we set k to be sufficiently large, then $P_1^k$ will be small. The probability of correctness could be very small. To improve the probability of success, we will repeat the above process  L times (each with a fresh function g) where L is:
\[
    L=\frac{10}{P_1^k}
\]
\\
$\textbf{Space}: O(Ln + nd)$
\\
$\textbf{Query Time}: O(L\cdot (1 + n\cdot P_2^k + [\text{Time to compute g(q)]}))$

\[
P_{r}[success] \geq [(1 - P_1^k)^L] \approx 1 - \exp^{\left(\frac{-10}{ P_1^k} \cdot P_1^k\right)} \geq 0.9
\]
  

The value of L depends purely on k. In order to minimize the Query time, we need to set k such that:
\[
    P_2^k = \frac{1}{n}
\]

\[
    k = \ceil{\frac{log n}{log \frac{1}{P_2}}}
\]

\begin{remarks}
    Note: k has to be an integer, so we add a ceil to the above equation.
\end{remarks}

\begin{equation}
    L = O\left(\frac{1}{ P_1^k}\right) \\
      = O\left(\frac{1}{ P_2^{\left(k \cdot  \frac{\text{log}\frac{1}{P_1}}{\text{log}\frac{1}{P_2}}\right)}}\right) \\
      = O( n^ \rho)
\end{equation}
   
\begin{observation}
    The query time is always sub-linear in n as long as we can get $P_1 > P_2.$
\end{observation}

\subsection*{LSH family for $\{0,1\}^d$, IM' 98}

We can construct an LSH for Hamming space $\{0, 1\}^d$. Define $h(p) = P_j$ where $j$ is random (\textit{picked} before seeing the data). Hash function $g$ is usually a concatenation of \textit{primitive} functions. That is, $g(p) = \langle h_1(p), h_2(p), \dots, h_k(p) \rangle$. Then, $g(p)$ is just a projection on $k$ random bits and

\begin{align*}
    Pr[h(p) = h(q)] &= 1 - \frac{Ham(p,q)}{d} \\
    P_1 &= 1 - \frac{r}{d}  \approx e^{-r/d} \\ 
    P_2 &= 1 - \frac{cr}{d} \approx e^{-cr/d}
\end{align*}

Hence,
\begin{align*}
    \rho = \frac{\log(1/P_1)}{\log\left(1/P_2\right)} = \frac{r/d}{cr/d} = \frac{1}{c}
\end{align*}

\begin{corollary}
    C-ANN for a Hamming space $\{0, 1\}^d$ has \\
    \textbf{Space}: O(nd + $n^{(1+\frac{1}{c})}$) \\
    \textbf{Query Time}: O($n^\frac{1}{c} \dot d$) \\
\end{corollary}

\begin{example}
    For c = 2, \\
    \textbf{Space}: O($n^{1.5}$) \\
    \textbf{Query Time}: O($\sqrt{n}d$) \\
    Thus, the 2-approximation of ANN on Hamming Space can be solved in $\sqrt{n}$ time.
\end{example}

\begin{remarks}
Can we do better? Is there any better way to partition the Hamming space so that we have better properties.
No we can't do so, as mentioned in the below theorem.
\end{remarks}

\begin{theorem}[MNP '06, OWZ '10]

The best possible cases:
    \[
        \text{For the Hamming space}, \rho \geq \frac{1}{c}
    \]

    \[
        \text{For the Euclidean space } l_2, \rho \leq \frac{1}{c^2}
    \]
\end{theorem}

\begin{remarks}
    It is possible to beat these lower bounds by considering data-dependent LSH($\approx$ Perfect Hashing)
\end{remarks}

\begin{remarks}
    We can trade-off space vs query time to obtain:\\
    \textbf{Space}: $n^{(1+\rho_u)}$ \\
    \textbf{Query Time}: $n^\rho_q$
    \begin{enumerate}
        \item It is possible to push the query time to be close to a constant, but then the space will increase.
        \item It is possible to obtain a linear space. Then $\rho_u$ = 0 and Query time will be sub-linear. Eg. $\rho_u$ = 0, then $\rho_q$ $<$ 1.
    \end{enumerate}

\end{remarks}

\section{Graphs}

In this section we will be seeing algorithms which are exact,i.e., neither random nor approximate. We will talk about the Max-Flow problem. It illustrates a number of techniques which are applicable for Graph Algorithms.

Consider, G:(V,E,C), where V is the number of vertices, E is the number of edges, C is Capacity. We will assume $\forall c_e \in C \geq 0$. Example:
\newline

\begin{tikzpicture}[node distance={30mm},main/.style = {draw, circle}] 
\node[main] (1)  {s};
\node[main] (2) [right of=1] {2};
\node[main] (3) [below right of=2] {t}; 
\node[main] (4) [below of=1] {3};
\node[main] (5) [right of=4] {4}; 
\draw[->] (1) -- node[midway, above] {2/2} (2) ;
\draw[->] (2) -- node[midway, above] {1/5} (3);
\draw[->] (2) -- node[midway, left] {1/3} (5);
\draw[->] (1) -- node[midway, right] {1/5} (4);
\draw[->] (4) -- node[midway, above] {1/6} (5);
\draw[->] (5) -- node[midway, above] {2/2} (3);
\end{tikzpicture}

The numerator in the weights denote the unit that flows from one node to another. Fix source(s) and destination(t). f is a flow vector $f \in \mathbb{R}_t^m$ , m $\rightarrow$ number of edges, n $\rightarrow$ number of nodes, such that:
\begin{enumerate}
    \item $f_e \geq 0, \forall e\in E$ 
    \item $f_e \leq C_e, \forall e \in E$
    \item Flow conservation; A flow that satisfies the below equation is called a valid flow.
\end{enumerate}

\[
\sum_{(u,v)\in E}f_{(u,v)} - \sum_{(v,u) \in E}f_{(v,u)} = 0 \;\; ; \;\; \forall v\neq s,t
\]

\begin{example}
    f = all 0's is a valid flow.
\end{example}

\textbf{Max-Flow Problem: Find f maximizing flow shipped from s to t:}
\begin{equation}
    |f| = \sum_{(s,u)\in E}f_{(s,u)} - \sum_{(u,s) \in E}f_{(u,s)} = \sum_{(t,u)\in E}f_{(t,u)} - \sum_{(u,t) \in E}f_{(u,t)}
\end{equation}

We can prove $|f| = \sum_{(t,u)\in E}f_{(t,u)} - \sum_{(u,t) \in E}f_{(u,t)}$ for any flow by summing up all flow contribution constraints for $v \neq s,t$; $\forall edge (u,v)$ not incident on s,t will cancel out.

\subsection*{Other types of flow}
\begin{definition}
Path Flow: A particular type of flow which is a path. For example: There is a path from node s to node t in the figure below.

\end{definition}
\begin{tikzpicture}[node distance={40mm},main/.style = {draw, circle}] 
\node[main] (1)  {s};
\node[main] (2) [right of=1] {t};
\draw[->] (1) to [out=135,in=90,looseness=1.5] (2);
\end{tikzpicture} 

\begin{definition}
Cycle Flow: A particular type of flow that starts from a node and comes back into that node.
\end{definition}

We can say that, any flow that doesn't split or combine is either a path flow or a cycle flow. 

\begin{tikzpicture}[node distance={15mm},main/.style = {draw, circle}] 
\node[main] (1)  {1};
\node[main] (2) [below right of=1] {2};
\node[main] (3) [below left of=2] {3};
\node[main] (4) [above left of=3] {4};
\draw[->] (1) -- (2);
\draw[->] (2) -- (3);
\draw[->] (3) -- (4);
\draw[->] (4) -- (1);
\end{tikzpicture} 

\begin{theorem}
    Any valid flow f can be decomposed into a set of path flows $f_{p_1}, f_{p_2} \dots f_{p_k}$ and cycle flows  $f_{c_1}, f_{c_2} \dots f_{c_l}$ s.t.
    \[
    f = f_{p_1}, f_{p_2} \dots f_{p_k} + f_{c_1}, f_{c_2} \dots f_{c_l};\;\; k+l \leq m
    \]
\end{theorem}

\begin{example}
    Refer to the following image which shows the path flows from s to t.
\end{example}
\begin{figure}[htp]
  \centering
  \includegraphics[height=30mm]{IMG-0537.jpg}
\end{figure}

In the \textbf{next class}, we shall prove this theorem and will study Ford-Fulkerson algorithm.
\end{document}
