\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage{bbm}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{algorithm}
\usepackage{accents}
\usepackage{algpseudocode}
\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{\olrk}[1]{\ifx\nursymbol#1\else\!\!\mskip4.5mu plus 0.5mu\left(\mskip0.5mu plus0.5mu #1\mskip1.5mu plus0.5mu \right)\fi}
\newcommand{\elrk}[1]{\ifx\nursymbol#1\else\!\!\mskip4.5mu plus0.5mu\left[\mskip0.5mu plus0.5mu #1\mskip1.5mu plus0.5mu \right]\fi}
\newcommand{\clrk}[1]{\ifx\nursymbol#1\else\!\!\mskip4.5mu plus0.5mu\left\{\mskip0.5mu plus0.5mu #1\mskip1.5mu plus0.5mu \right\}\fi}

\newcommand{\floor}[1]{\ensuremath{\left\lfloor #1\right\rfloor}}
\newcommand{\ceil}[1]{\ensuremath{\left\lceil #1\right\rceil}}
\newcommand{\Angle}[1]{\ensuremath{\left\langle #1\right\rangle}}
\newcommand{\abs}[1]{\ensuremath{\left\lvert #1 \right\rvert}}
\newcommand{\norm}[1]{\ensuremath{\left\|#1\right\|}}
\newcommand{\concat}{\ensuremath{\|}}

\newcommand{\probname}{Pr}
\newcommand{\expectationname}{\ensuremath{\mathbb{E}}}
\newcommand{\supportname}{Supp}
\newcommand{\prob}[1]{\ensuremath{\operatorname{\probname}\elrk{#1}}}
\newcommand{\probsub}[2]{\ensuremath{\operatorname{\probname}_{#1}\elrk{#2}}}
\newcommand{\condprob}[2]{\ensuremath{\prob{#1\,\left|\,#2\vphantom{#1}\right.}}}
\newcommand{\condprobsub}[3]{\ensuremath{\probsub{#1}{#2\,\left|\,#3\vphantom{#1}\right.}}}
\newcommand{\expect}[1]{\ensuremath{\operatorname{\expectationname}\elrk{#1}}}
\newcommand{\expsub}[2]{\ensuremath{\operatorname{\expectationname}_{#1}\elrk{#2}}}
\newcommand{\condexp}[2]{\ensuremath{\expect{#1\,\left|\,#2\vphantom{#1}\right.}}}
\newcommand{\condexpsub}[3]{\ensuremath{\expsub{#1}{#2\,\left|\,#3\vphantom{#1}\right.}}}

\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{problem}[theorem]{Problem}

\newcommand\xor{\oplus}
\newcommand{\E}{{\mathbb E}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\pstar}{{\accentset{\ast}{p}}}
\DeclareMathOperator{\var}{Var}

\begin{document}
\tikzset{every picture/.style={line width=0.75pt}}

\lecture{9: Nearest Neighbor Search: Locality Sensitive Hashing}{Feb 09, 2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Haoran Pu, Rodolfo Raimundo}}

\section{Review: Lecture 8}
Last time we discussed the problem of Nearest Neighbor Search using as a foundation for our possible solutions the Johnson-Lindenstrauss lemma from Lecture 7. \\
We then started discussing solutions for the c-ANN problem as described below:
\begin{definition}\label{cappoxnn}
[c-approximation of r-near neighbor, c-ANN]:
Given $c>1, r>0$, data set $D \subset \R^d, n = |D|$, build a data structure 
on $D$ such that it can answer given $q \in \R^d$:
\begin{itemize}
    \item if there exists $\pstar \in D$ such that $||\pstar - q|| \le r$,
        then report $p \in D$ such that $||p - q|| \le c\cdot r$
        
        (in case of randomized algorithms, $p$ is reported with probability at least 90\% per point)
    \item if doesn't exist $\pstar \in D$ such that $||\pstar - q|| \le r$,
        then may or may not report anything
\end{itemize}
\end{definition}
\noindent After a solution adopting dimension reduction, we concluded that in some cases it is enough to use a sketching map instead of a proper dimension reducing map\footnote{Scribe 8: Section 3}. We then followed with a solution using sketching for $\ell_1$ and the Hamming space\footnote{Scribe 8: Section 4}. 

\section{Solution 1: KOR Theorem and Sketching}
As described in the \textbf{Section 1}, last time we stated a theorem that could lead us to a possible solution of the c-ANN problem using sketching. Now, we will prove the theorem and better define the solution. We should first recall the Kushilevitz-Ostrovsky-Rabani Theorem: 
\begin{theorem}\label{cappoxnn}
[Kushilevitz-Ostrovsky-Rabani]:
Fix $d \geq 1$ and $c = 1+O(\varepsilon)$. Then, there exists $\theta > 0$ such that $\forall r\geq 1$ there exists a distribution $\varphi$ over $\{0,1\}^d$ defined as $\varphi: \{0, 1\}^d \to \{0, 1\}^k$, with $k = O(\frac{\log n}{\varepsilon^2})$ such that:
\begin{itemize}
    \item if $\norm{p-q}\leq r$ then $\prob{\norm{\varphi(p)-\varphi(q)}\leq \theta k}\geq 1 - \frac{1}{n^3}$
    \item if $\norm{p-q}> cr$ then $\prob{\norm{\varphi(p)-\varphi(q)}> \theta k }\geq 1 - \frac{1}{n^3}$
\end{itemize}
\end{theorem}
\noindent As one should notice, the distribution $\varphi$ acts like a dimension reduction mapping for a scale $r$.\\
We can now proceed with the proof of the theorem as follows:
\begin{proof}
First, we should define $\varphi$ as transformation in the given space, thus we will have that $\varphi$ takes the following form: 
$$\varphi(p) = 
\begin{bmatrix}
	\cdots & u_1 & \cdots \\
	\cdots & u_2 & \cdots \\
	\vdots & \vdots & \vdots \\
	\cdots & u_d & \cdots \\
\end{bmatrix} 
\cdot
\begin{bmatrix}
	p_1 \\
	p_2 \\
	\vdots \\
	p_d
\end{bmatrix} $$
The matrix $M$ is defined such that for each $u_i$ we have that $\prob{u_i=1}=\alpha=\frac{1}{2r}$ and we have that the size of the matrix $M$ of the transformation is $d*k$ with $d$ and $k$ as defined previously.\\
We should also remember that since we defined the mapping in $\{0,1\}^d$, we have that all operations are in the Galois Field with modulo 2 ($\mathbb{F}_2$), hence, the sum operation behaves similarly to Exclusive OR ($\xor$).\\
Taking these properties into account, we can proceed with our proof. \\
For a vector $p$ and a matrix $M$ as defined above with $v_i=(u^i_1, u^i_2, \dots ,u^u_d)$\footnote{For the purpose of simplification, we will be dropping the superscript on $u^i$, since the operations are analogous in every column of $M$.}, we have:
$$\varphi (p) = (v_1 \cdot p, v_1 \cdot p, \dots, v_k \cdot p)$$ 
Now, for another vector $q$, since we have that $(+)\equiv (\xor)$, we have: 
$$\norm{\varphi (p)-\varphi (q)}= \sum_{i=1}^k\mathbbm{1}[v_i\cdot p \neq v_i \cdot q] $$
We can then take the expectation of such variables to prove our theorem. 
\begin{flalign*}
    \begin{aligned}
        \expect{\norm{\varphi (p)-\varphi (q)}} &= \expect{\sum_{i=1}^k\mathbbm{1}[v_i\cdot p \neq v_i \cdot q]}\\
        &=k*\prob{v_i \cdot p \neq v_i \cdot q}
    \end{aligned}
\end{flalign*}
Further, we have: 
\begin{flalign*}
    \begin{aligned}
        \prob{v_i \cdot p \neq v_i \cdot q}&=\probsub{u}{u\cdot p \neq u\cdot q}\\
        &=\probsub{u}{\xor^d_{i=1} u_i\cdot p_i \neq \xor^d_{i=1} u_i\cdot q_i}\\
        &=\probsub{u}{\xor^d_{i=1} u_i \cdot (p_i\xor q_i)\neq 0}
    \end{aligned}
\end{flalign*}
Since the operation Exclusive OR depends only on the coordinate, we have that the number of iterations of $i$ in which $(p_i\xor q_i) = 1$ is $\norm{p-q}$. Now, since we have established that each $u_i = 1$ with probability $\frac{1}{2r}$, we can then define the distribution of $u_i$ as follows:
\begin{itemize}
    \item $u_i \in \{0,1\}$ with probability $\frac{1}{r}=2\alpha$.
    \item $u_1 = 0$ with probability $1-2\alpha$
\end{itemize}
Therefore, $u_1=1$ with probability $\alpha$ as defined previously, further, we have:
\begin{flalign*}
    \begin{aligned}
        \probsub{u}{\xor^d_{i=1} u_i \cdot (p_i\xor q_i)\neq 0} &= 1 - \probsub{u}{\xor^d_{i=1} u_i \cdot (p_i\xor q_i)= 0}\\
        &= 1-(1-2\alpha)^{\norm{p-q}}-(1-(1-2\alpha)^{\norm{p-q}})*\frac{1}{2}\\
        &= \frac{1}{2} (1-(1-2\alpha)^{\norm{p-q}})
    \end{aligned}
\end{flalign*}
Now, we can look back at the cases described in the KOR Theorem: 
\begin{enumerate}
    \item if $\norm{p-1}\leq r$, for $(1-x)\approx e^{-x}$ for small $x$, we will have:
    \begin{flalign*}
        \begin{aligned}
            \prob{u\cdot p \neq u\cdot q} &\leq \frac{1}{2}\Bigg (1-\Big (1-\frac{2}{2r}\Big )^r\Bigg )\\
            &=\frac{1}{2}(1-e^{-1})\\
            &= \frac{1}{2} - \frac{1}{2e}
        \end{aligned}
    \end{flalign*}
    \item if $\norm{p-1}> cr$, for $c=1+\varepsilon$, we will have:
    \begin{flalign*}
        \begin{aligned}
            \prob{u\cdot p \neq u\cdot q} &\leq \frac{1}{2}\Bigg (1-\Big (1-\frac{2}{2r}\Big )^{r*(1+\varepsilon)}\Bigg )\\
            &=\frac{1}{2}(1-e^{-1-\varepsilon})\\
            &=\frac{1}{2}(1-e^{-1}(1-\varepsilon))\\
            &= \frac{1}{2} - \frac{1}{2e} + \varepsilon * \frac{1}{2e}
        \end{aligned}
    \end{flalign*}
\end{enumerate}
We can now use the Chernoff Bound on each case, hence we will have:
\begin{enumerate}
    \item $$\norm{\varphi(p)-\varphi(q)}\leq \frac{1}{2}-\frac{1}{2e}+\frac{\varepsilon}{4e}$$
    \item $$\norm{\varphi(p)-\varphi(q)}\leq \frac{1}{2}-\frac{2}{2e}+\frac{\varepsilon}{2e}-\frac{\varepsilon}{5e}$$
\end{enumerate}
With probability $\sigma \geq 1-\frac{1}{n^3}$. Thus, we have concluded our proof.
\end{proof}
As a result of our proof, we then arrive in the following corollary: 
\begin{corollary}
There is a solution for a $(1+\varepsilon)-ANN$ in $\{0,1\}^d$ using space $O(n*k)=O(n*\frac{\log n}{\varepsilon^2})$ and query time $O(d*k) + O(n*\frac{\log n}{\varepsilon^2})$.
\end{corollary}

\section{Solution 2: Compare Query Sketch \& Dataset Sketch}

The issue for \textbf{Sol 1} is that the query time contains term $O(n\ln(n))$, which is bad. And here we are trying to reduce the n term.

\tikzset{every picture/.style={line width=0.75pt}} 
\begin{center}
    \begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
    
%Shape: Rectangle [id:dp35880230902770394] 
\draw   (38,130) -- (186.33,130) -- (186.33,150.2) -- (38,150.2) -- cycle ;
%Shape: Rectangle [id:dp5625710618621473] 
\draw   (38,40) -- (186.33,40) -- (186.33,60.2) -- (38,60.2) -- cycle ;
%Shape: Rectangle [id:dp9888501010583863] 
\draw   (38,70) -- (186.33,70) -- (186.33,90.2) -- (38,90.2) -- cycle ;
%Shape: Rectangle [id:dp6221777968333626] 
\draw   (38,100) -- (186.33,100) -- (186.33,120.2) -- (38,120.2) -- cycle ;
%Shape: Rectangle [id:dp26152122117805576] 
\draw  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,draw opacity=1 ] (219.33,40) -- (289.33,40) -- (289.33,60.2) -- (219.33,60.2) -- cycle ;
%Shape: Rectangle [id:dp43926414811352554] 
\draw  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,draw opacity=1 ] (219.33,71) -- (289.33,71) -- (289.33,91.2) -- (219.33,91.2) -- cycle ;
%Shape: Rectangle [id:dp3580125278846855] 
\draw  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,draw opacity=1 ] (219.33,100) -- (289.33,100) -- (289.33,120.2) -- (219.33,120.2) -- cycle ;
%Shape: Rectangle [id:dp3044670390837747] 
\draw  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,draw opacity=1 ] (219.33,130) -- (289.33,130) -- (289.33,150.2) -- (219.33,150.2) -- cycle ;
%Straight Lines [id:da8388646699776303] 
\draw    (185.8,50.2) -- (217.8,50.2) ;
\draw [shift={(219.8,50.2)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da496871096666168] 
\draw    (185.8,81.2) -- (217.8,81.2) ;
\draw [shift={(219.8,81.2)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da45525568755537305] 
\draw    (185.8,111.2) -- (217.8,111.2) ;
\draw [shift={(219.8,111.2)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da4068216676641989] 
\draw    (185.8,141.2) -- (217.8,141.2) ;
\draw [shift={(219.8,141.2)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp4342012541156466] 
\draw  [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ] (328.33,41) -- (398.33,41) -- (398.33,61.2) -- (328.33,61.2) -- cycle ;
%Straight Lines [id:da589478919559711] 
\draw    (308.8,51.2) -- (308.8,140.2) ;
%Straight Lines [id:da540338311537143] 
\draw    (308.8,51.2) -- (325.8,51.2) ;
\draw [shift={(327.8,51.2)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7524047469416941] 
\draw    (308.8,140.2) -- (291.8,140.2) ;
\draw [shift={(289.8,140.2)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da5163236172244872] 
\draw    (308.8,51.2) -- (291.8,51.2) ;
\draw [shift={(289.8,51.2)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da4950429636369924] 
\draw    (308.8,80.2) -- (291.8,80.2) ;
\draw [shift={(289.8,80.2)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da5949165595591102] 
\draw    (308.8,110.2) -- (291.8,110.2) ;
\draw [shift={(289.8,110.2)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp3720424182933546] 
\draw  [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ] (430.33,40) -- (571.2,40) -- (571.2,60.2) -- (430.33,60.2) -- cycle ;
%Straight Lines [id:da9377340389016537] 
\draw    (430.2,50.2) -- (400.2,50.2) ;
\draw [shift={(398.2,50.2)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (40,75) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle p_{2}$};
% Text Node
\draw (40,105) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle p_{3}$};
% Text Node
\draw (40,45) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle p_{1}$};
% Text Node
\draw (40,135) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle p_{4}$};
% Text Node
\draw (247,155) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle \vdots $};
% Text Node
\draw (104,155) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle \vdots $};
% Text Node
\draw (219.33,132) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle S( p_{4})$};
% Text Node
\draw (219.33,42) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle S( p_{1})$};
% Text Node
\draw (219.33,102) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle S( p_{3})$};
% Text Node
\draw (219.33,72) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle S( p_{2})$};
% Text Node
\draw (328.33,43) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle S( q)$};
% Text Node
\draw (433,45) node [anchor=north west][inner sep=0.75pt]   [align=left] {$\displaystyle q$};


\end{tikzpicture}
\end{center}

\begin{assumption}
The sketch is $\{0, 1\}^k$, which has $2^k$ distinct values. This can be achieved by doing the sketch in \textbf{sol 1}.

\end{assumption}
\noindent The key trick here is the sketch itself can be a pointer of an address for the sketch. This means, if we just store all the possible answers in the address, upon computing the query sketch, we have $O(1)$ retrieval time and therefore preventing the $n$ term. Here is an diagram showing the sketch-address trick.

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,249); %set diagram left start at 0, and has height of 249

%Shape: Rectangle [id:dp39752075306391355] 
\draw   (180,131) -- (200,131) -- (200,151) -- (180,151) -- cycle ;
%Shape: Rectangle [id:dp8273674737581529] 
\draw   (200,131) -- (220,131) -- (220,151) -- (200,151) -- cycle ;
%Shape: Rectangle [id:dp8405600544547991] 
\draw   (220,131) -- (240,131) -- (240,151) -- (220,151) -- cycle ;
%Shape: Rectangle [id:dp22294015361074715] 
\draw   (240,131) -- (260,131) -- (260,151) -- (240,151) -- cycle ;
%Shape: Rectangle [id:dp12313917690704135] 
\draw   (260,131) -- (280,131) -- (280,151) -- (260,151) -- cycle ;
%Shape: Rectangle [id:dp8346258815984622] 
\draw   (310,131) -- (330,131) -- (330,151) -- (310,151) -- cycle ;
%Shape: Rectangle [id:dp20728705539269265] 
\draw   (330,131) -- (350,131) -- (350,151) -- (330,151) -- cycle ;
%Shape: Rectangle [id:dp8905339256174423] 
\draw   (350,131) -- (370,131) -- (370,151) -- (350,151) -- cycle ;
%Shape: Rectangle [id:dp21832977284581445] 
\draw   (370,131) -- (390,131) -- (390,151) -- (370,151) -- cycle ;
%Shape: Rectangle [id:dp5701568452274961] 
\draw   (390,131) -- (410,131) -- (410,151) -- (390,151) -- cycle ;
%Shape: Rectangle [id:dp43546753303696617] 
\draw   (178,50) -- (280,50) -- (280,77) -- (178,77) -- cycle ;
%Straight Lines [id:da5256142733028948] 
\draw    (230,80) -- (230,108) ;
\draw [shift={(230,110)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (192,120.5) node [anchor=east] [inner sep=0.75pt]   [align=left] {0};
% Text Node
\draw (213,120.5) node [anchor=east] [inner sep=0.75pt]   [align=left] {1};
% Text Node
\draw (236,120.5) node [anchor=east] [inner sep=0.75pt]   [align=left] {10};
% Text Node
\draw (257,120.5) node [anchor=east] [inner sep=0.75pt]   [align=left] {11};
% Text Node
\draw (284,121.5) node [anchor=east] [inner sep=0.75pt]   [align=left] {100};
% Text Node
\draw (193,54.4) node [anchor=north west][inner sep=0.75pt]    {$\phi ( q) =10$};
% Text Node
\draw (284,132.4) node [anchor=north west][inner sep=0.75pt]    {$\cdot \cdot \cdot $};


\end{tikzpicture}

\noindent And here the algorithm becomes:

\begin{algorithm} \caption{Sketch Algorithm}
\begin{algorithmic}[1]
\Require $\phi :\{0, 1\}^d \rightarrow \{0, 1\}^k $ created by \textbf{Sol 1}, , a $n\times \{0, 1\}^d$ dataset $D$, a $2^k$ length array $A$ and a query $q\in \{0, 1\}^d$. By J-L theorem, $k\in O(\frac{\ln(n)}{\epsilon^2})$ 


\For{\texttt{$x\in D$}}
        \State \texttt{compute $\phi(x)$ and store it to address $\sigma$ if it is an answer for query  sketch $\sigma$}
\EndFor

\State compute query sketch $\phi(q)$ 

\Return $A[\phi(q)]$

\end{algorithmic}
\end{algorithm}


\subsection{Sketch Algorithm Space \& Query Time Analysis}

Space complexity is based one the size of the array $A$: $2^k=2^{O(\frac{\ln(n)}{\epsilon^2})}=n^{O(1/\epsilon^2)}$. This means, if one wants to have better approximate (lower $\epsilon$), the space complexity will be higher degree polynomial ($\epsilon=0.05$ will give $O(n^{400})$).\\
Query Time: Since retrieving answer is $O(1)$, most works are done for computing $\phi(q)$, which is $O(dk)=O(\frac{d\ln(n)}{\epsilon^2})$, please note that here we do eliminate the n term from \textbf{Sol 1}.


\section{Solution 3: Locality Sensitivity Hashing (LSH) algorithm}

The issue of \textbf{Sol 2} is that eventually the space will be a higher order polynomial of $n$, which makes the storage cost too large to be considered practical. The core idea is to sacrifice some query time (still under linear) while keeping space close linear as well. And this can be achieved by the application of Locality Sensitivity Hashing (LSH). Such hashing function has the property that, if two points are closed in their space, then the hash of those two points shall have high probability under the same bucket and vice versa. Here is an example show the expected behavior of locality sensitive hashing function.

\begin{center}
    \begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,249); %set diagram left start at 0, and has height of 249

%Flowchart: Connector [id:dp6527120420190524] 
\draw   (180,125) .. controls (180,105.67) and (213.58,90) .. (255,90) .. controls (296.42,90) and (330,105.67) .. (330,125) .. controls (330,144.33) and (296.42,160) .. (255,160) .. controls (213.58,160) and (180,144.33) .. (180,125) -- cycle ;
%Shape: Rectangle [id:dp25637567488473567] 
\draw   (420,60) -- (440,60) -- (440,80) -- (420,80) -- cycle ;
%Shape: Rectangle [id:dp4935709309807592] 
\draw   (420,80) -- (440,80) -- (440,100) -- (420,100) -- cycle ;
%Shape: Rectangle [id:dp9177349330269706] 
\draw   (420,100) -- (440,100) -- (440,120) -- (420,120) -- cycle ;
%Shape: Rectangle [id:dp7657233484224073] 
\draw   (420,120) -- (440,120) -- (440,140) -- (420,140) -- cycle ;
%Shape: Rectangle [id:dp9827073841029044] 
\draw   (420,140) -- (440,140) -- (440,160) -- (420,160) -- cycle ;
%Shape: Rectangle [id:dp8281373882565799] 
\draw   (420,160) -- (440,160) -- (440,180) -- (420,180) -- cycle ;
%Shape: Circle [id:dp8217447509499918] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (200,115) .. controls (200,112.24) and (202.24,110) .. (205,110) .. controls (207.76,110) and (210,112.24) .. (210,115) .. controls (210,117.76) and (207.76,120) .. (205,120) .. controls (202.24,120) and (200,117.76) .. (200,115) -- cycle ;
%Shape: Circle [id:dp4271690884830095] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (267,115) .. controls (267,112.24) and (269.24,110) .. (272,110) .. controls (274.76,110) and (277,112.24) .. (277,115) .. controls (277,117.76) and (274.76,120) .. (272,120) .. controls (269.24,120) and (267,117.76) .. (267,115) -- cycle ;
%Shape: Circle [id:dp8992388574787] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (280,145) .. controls (280,142.24) and (282.24,140) .. (285,140) .. controls (287.76,140) and (290,142.24) .. (290,145) .. controls (290,147.76) and (287.76,150) .. (285,150) .. controls (282.24,150) and (280,147.76) .. (280,145) -- cycle ;
%Shape: Circle [id:dp9543251680473293] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (290,135) .. controls (290,132.24) and (292.24,130) .. (295,130) .. controls (297.76,130) and (300,132.24) .. (300,135) .. controls (300,137.76) and (297.76,140) .. (295,140) .. controls (292.24,140) and (290,137.76) .. (290,135) -- cycle ;
%Shape: Circle [id:dp8182870864877636] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (210,105) .. controls (210,102.24) and (212.24,100) .. (215,100) .. controls (217.76,100) and (220,102.24) .. (220,105) .. controls (220,107.76) and (217.76,110) .. (215,110) .. controls (212.24,110) and (210,107.76) .. (210,105) -- cycle ;
%Shape: Circle [id:dp25692404134683344] 
\draw  [draw opacity=0][fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (230,145) .. controls (230,142.24) and (232.24,140) .. (235,140) .. controls (237.76,140) and (240,142.24) .. (240,145) .. controls (240,147.76) and (237.76,150) .. (235,150) .. controls (232.24,150) and (230,147.76) .. (230,145) -- cycle ;
%Straight Lines [id:da4293892266732604] 
\draw    (220,105) -- (418.04,66.38) ;
\draw [shift={(420,66)}, rotate = 528.97] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da07647854430881318] 
\draw    (210,115) -- (416.04,75.38) ;
\draw [shift={(418,75)}, rotate = 529.11] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7925439140001058] 
\draw    (277,115) -- (417,108.1) ;
\draw [shift={(419,108)}, rotate = 537.1800000000001] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da39833667101027137] 
\draw    (240,145) -- (417.02,168.73) ;
\draw [shift={(419,169)}, rotate = 187.64] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6496943892242539] 
\draw    (285,145) -- (416,150.91) ;
\draw [shift={(418,151)}, rotate = 182.58] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da902105800894613] 
\draw    (300,135) -- (417.01,145.82) ;
\draw [shift={(419,146)}, rotate = 185.28] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;




\end{tikzpicture}
\end{center}


\begin{definition}
Fix $r,c>0$, family $\mathcal{H}$ of $h:\mathbb{R}^d\rightarrow U$ ,where $U$ is countable set, is called $(r, cr, P_1, P_2)$-LSH if $\forall p,q\in \mathbb{R}^d, ||p-q||\le r\Rightarrow P(h(p)=h(q))\ge P_1$, and $||p-q||\ge  cr\Rightarrow P(h(p)=h(q))\le P_2$
\end{definition}

\noindent The understanding of this algorithm is quite similar with K-Mean  problem where the differences are 1): U is independent of dataset D, and 2): unlike K matters in K-Mean problem, we don't care about the cardinally of $U$. And the algorithm becomes:

\begin{algorithm} \caption{LSH Algorithm}
\begin{algorithmic}[1]
\Require A $(r, cr, P_1, P_2)$-LSH hash function $h$,  a dictionary data structure $V$, and query $q$

\For{\texttt{$x\in D$}}
        \State \texttt{Prepossess h(x) and store it in $V$}
\EndFor

\For{\texttt{$p\in V(h(q))$}}
        \State \texttt{compute $||p-q||$ and return $p$ if $||p-q||\le cr$}
\EndFor
\end{algorithmic}
\end{algorithm}

\noindent In future lecture we will show such algorithm has query time $O(n^\rho)\le O(n^1)$ and space close to $O(n)$


\subsection{$(r, cr, 1, \frac{1}{n})$ - LSH Correctness \& Performance Analysis}

Here lets do some best case scenario and use the best LSH we can imagine to see the upper bound of the performance. Since $||p-q||\le r \implies P(h(p)=h(q))=1$, the bucket must have the correct answer if such answer exists. And for expectation, we will compute its expectation, since the data is in dim $d$:

$$\E(\sum\limits_{x\in V(h(q))}Query(x))\le d\E(\sum\limits_{i=1}^nQ(x)I(x\in V(h(q))))\le d\times n\times cP_2\in O(d)$$

\noindent Here $Query(\cdot)$ means query for entire vector, $Q(\cdot)$ means query for one coordinate, and $c$ is computation constant  between two numbers.

\subsection{Impossibility of $(r, cr, 1, \frac{1}{n})$ - LSH}

TL;DR: if exists, $P_1=1$ will enforce $h$ has only one bucket, which contradicts the $P_2$ requirement.\\
Although the performance analysis is promising, such thing is over optimistic and just mathematically impossible. Here is a gist of how such thing cannot be possible in $\mathbb{R}^1$. (You can alter interval $(a-r, a+r)$ into volume in higher dimensions to show the generic impossibility as well) 

\begin{claim}
  LSH - $(r, cr, 1, \frac{1}{n})$ does not exist for $\mathbb{R}^1$
\end{claim}
  
\begin{proof}
We will prove it by contradiction and assume such thing exists.

Fix value $a$ and $r$, we know: $\forall x\in (a-r, a+r), h(x)=h(a)$.

By using induction, this implies, for any natural number $n\in \mathbb{N}$, if $x\in (a-nr, a+nr)$, then $h(a)=h(x)$.

Recall Archimedes theorem, for any $m>0$, there exists $n\in N$ such that $n \ge 
\frac{m-a}{r}$.

This means, $\forall x\in \mathbb{R}^1$, there exists a natural number $n\in \mathbb{N}$ such that 

$x\in (a-nr, a+nr)$ and so $h(x)=h(a)$.

This means we have only one bucket and therefore 

$\forall x$ such that if  $||x-a||\ge cr$, $P(h(x)=h(a))=1> \frac{1}{n}$ for $n>1$.

This contradicts the assumption that 
$||x-a||\ge cr$, $P(h(x)=h(a))\le P_2 = \frac{1}{n}$.

Given the contradiction, we hereby show our assumption is false and therefore such thing 

does not exist.

\end{proof}

\noindent And such impossibility implies $P_1$ must be strictly less than 1, which will be discussed in next lecture.

\end{document}