\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{accents} 
\usepackage{tikz}
\usepackage{float}
\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}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\pstar}{{\accentset{\ast}{p}}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{8: Nearest Neighbor Search}{Feb 4,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Sixuan Wang, Grisha Temchenko}}


\section{Reminder: Dimension reduction  }
Last time we talked about dimension reduction, in particular we stated a foundational lemma called Johnson–Lindenstrauss lemma. What it shows is that there exists a distribution over $\phi$, which maps d-dimensional euclidean space into k-dimensional euclidean space, where we usually think of k is being much smaller than d.The property is that for any $x$ and $y$, we have:
\[ Pr[\Vert\phi(x) - \phi(y)\Vert] = (1 \pm \epsilon) \Vert x - y\Vert \geq 1 - e^{-\frac{\epsilon^{2}k}{9}}\]
Importantly, there is no dependency on the original dimension here. When we care about some end points, for example, if we take $k = D(\frac{\log{n}}{\epsilon^{2}})$, then we have:\\
\[ Pr[\Vert\phi(x) - \phi(y)\Vert] \geq 1 - \frac {1}{n^3}\]
As a result, we can embed endpoints in $\mathbb{R}^d$ into $\mathbb{R}^k$, preserving the distances up to $1 \pm \epsilon$, where $k$ is only $O(\frac{\log(n)}{\epsilon^{2}})$.\\

\section{Nearest Neighbor Search}
\begin{definition}
Giving $D$, which is a data set of points, $D \subset \mathbb{R}^d$, $\mid D \mid = n, q \subset \mathbb{R}^d$, so that we can find the closest $p^{*} \subset D$ .
\textbf{Note:}"Closest" $p$ here means
\[argmin_{p\in D}\Vert q - p \Vert\]
\end{definition}

\noindent \textbf{Motivation:} Look at high dimension key when d is high, so it's the high dimensional case. To illustrate, say we are in domain of images and there are two images which are of 20 * 20 pixels. How do we compare these two images?\\
One way to declare whether these two images are similar or not is by mapping them into a vector, let's say a 400 dimensional vector where each coordinate corresponds to some pixel in the image.\\
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\textwidth]{s8.png}\\
\caption{The visualization of how two images mapping into two vectors.}
\end{figure}

It's reasonable to say that the distance between these two vectors represents some dissimilarity measure between images. The smaller the distance, the more similar the images are. It's the fundamental method of representation and there are more fancy ways to do a representation of images. One popular way today is that we'll take an image fit into a big black box, which is known as neural network, it gives a representation which is a vector whose dimension is the number of neurons we have in penultimate level.\\

What we are thinking here is not about how to do the representation, we are more from the perspective that if we are done the representation already, how do we solve the problem of finding the nearest neighbor quickly.\\

\noindent \textbf{Performance measure of NNS:}\\
\noindent  -  Space\\
\noindent  -  Query time\\

\noindent \textbf{Solution 0:} just iterate over all points and calculate the distance. Pick the point with minimal distance.\\
\noindent  -  Space: $O(n \cdot d)$\\
\noindent  -  Query time: $O(n \cdot d)$\\
The space complexity here is good though we do want to improve query time.\\

\noindent \textbf{Solution 1: d = 1}\\
\noindent \textbf{Algorithm:} Sort all points in $D$ and at the query $q$, we do binary search.\\
\noindent  -  Space: $O(n)$\\
\noindent  -  Query time: $O(\log {n})$
\subsection{Voronoi diagram}
\noindent \textbf{Solution 2: d = 2}\\
\noindent \textbf{Voronoi diagram:} \\
We can try to partition the entire space according to what is the right answer for that part of space. For example, giving these five points, which are part of the data set. In the diagram, the central part is for all queries which the answer is the central point, the other part acts in the similar way. We have:
\[size = O(n)\]
That means the number of lines and points in the diagram is n. What we can do is what is called point location, which says that when given such diagram and a query $q$, we can efficiently determine which part we fall into.\\
\noindent  -  Space: $O(n \log(n)$\\
\noindent  -  Query time: $O(\log {n})$\\

\textbf{Doubt 1: Does Voronoi diagram still perform well when we have $d \gg 2$?}\\
\begin{claim}
No. Note we have:
Voronoi diagram size = $n\lfloor \frac {d}{2}\rfloor$.
\end{claim}
This means if the dimension is relatively high, Voronoi diagram's size grows exponentially faster in dimension. This kind of dependence, generally speaking, exponential dependence on the dimension is what is called course of dimensionality.

\begin{theorem}
If we can solve NNS in dimension $d = (\log^2(n))$ with $O(1)$ pre-processing time and space and query time $n^{0.99}$, then SETH (strong exponential time hypothesis) is false.
\end{theorem}
That is, we can't solve a general CNF formula on variables in time $\ll 2^n$.


\section{Approximate NNS in high dimensions}
What SETH means for us is that we don't really hope to solve Nearest Neighbor Search in polynomial space and linear time. Instead we will use an approximation.

\begin{definition}
($r$-near neighbor):
Given $r > 0$, and a data set $D \subset \R^d$, build data structure
such that given query $q \in R^d$, report any $p \in D$ such that $||q-p|| \le r$
\end{definition}
This a "threshold" version of NNR in a sense: we report only points within certain radius $r$.

\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}

\begin{figure}[H]
\centering
\begin{tikzpicture}
% circles
\draw[cyan] (2,2) circle (1cm);
\draw[magenta] (2,2) circle (2cm);
% black points
\filldraw[fill=blue] (2,2) circle (0.05cm) node[anchor=west] {$q$};
\filldraw[fill=black] (2.5,1.8) circle (0.05cm);
\filldraw[fill=black] (1.6,1.6) circle (0.05cm);
\filldraw[fill=black] (2.3,1.4) circle (0.05cm);
% gray points
\draw[gray] (0.7,1.4) circle (0.05cm);
\draw[gray] (0.4,1.2) circle (0.05cm);
\draw[gray] (2.4,3.2) circle (0.05cm);
\draw[gray] (1.9,0.3) circle (0.05cm);
\draw[gray] (3.4,1.2) circle (0.05cm);
% radius
\draw[thick,cyan,->] (2,2) -- (1.92,2.99) node[anchor=north east] {$r$};
\draw[thick,magenta,->] (2,2) -- (0.26,3) node[anchor=north east] {$c \cdot r$};
\end{tikzpicture}
\caption{Because there are points within radius $r$, any of the black or grey points can be reported, even though only one of the points is the closest. If there were not black points within the radius $r$, c-ANN may or may not report the gray points.}
\label{fig:cANNfig}
\end{figure}

We can think about approximations $1 \pm \varepsilon$, but we can also think about higher approximations. 

\noindent
\textbf{Remarks:}
\begin{enumerate}
    \item There exists a formal reduction from approximate \textit{nearest} neighbor to approximate \textit{near} neighbor. 
        We do not formally define the approximate nearest neighbor, but roughly, if there exists a closest point at distance $r$ it reports a point at distance $c \cdot r$
        (as opposed to a fixed threshold).
        
        It turns out we can do a reduction from the \textit{nearest} neighbor to the \textit{near} neighbor. Roughly the idea is to guess a threshold $r$, or enumerate all possible thresholds, and build a data structure for all possible $r$.
        In practice we usually know the threshold that we care about.
        
    \item Usually, the algorithms for ANN can be modified to report a set $L \subset D$ such that:
        \begin{itemize}
            \item if $p \in D$ is $||p-q|| \le r$, then $p \in L$
            \item if $||p - q|| \ge c\cdot r$, then $p \not\in L$
        \end{itemize}
    
    \item Randomized algorithms report $p$ with probability at least 90\% per point if there exists $\pstar$ (in definition \ref{cappoxnn} the first case)
    
\end{enumerate}

So in c-ANN we are trying to improve over naive space $O(nd)$ and query time $O(nd)$.

\subsection{Solution \#1 for c-ANN}

First idea is to use the previously seen dimensional reduction (Johnson–Lindenstrauss).

\begin{algorithm}[H]
\caption{c-ANN using dimensional reduction}
\SetAlgoLined
 Pick $\varphi: \R^d \to \R^k$ at random, $k = O(\frac{\log n}{\varepsilon^2})$ \\
 Store $\varphi(p)$ for all $p \in D$ \\
 \textbf{At query $q$}: 
 \begin{itemize}
     \item Compute $||\varphi(p) - \varphi(q)||$ for all $p \in D$
     \item Return the closest $p$
 \end{itemize}
\end{algorithm}

Even though we still iterate over all points, we reduced the size of the data set to $k$ dimensions, so now the computation is less expensive.
It's not as important that we reduced the space, but it is important is that we somehow compressed the information about every point, so now computing the distances is faster.

New \textbf{space}: $O(nk) = O(n \frac{\log n}{\varepsilon^2})$

New query \textbf{time}: $ O(dk) + O(nk) = O(n \frac{\log n}{\varepsilon^2}) $

(Approximate $c = 1 + \varepsilon$, assuming $n >> d$)

\textbf{Correctness analysis}: 
Using Corollary of Johnson–Lindenstrauss on points $D \bigcup \{q\}$ it implies that distances between $p \in D$ and $q$ are preserved up to $(1+ \varepsilon)$ factor with probability at least $1 - 1/N \ge 1 - 1/n$ for $k = O(\frac{\log N}{\varepsilon^2}) = O(\frac{\log n}{\varepsilon^2})$, where $N = n+1$.

A crucial aspect is that $\varphi$ is \textit{oblivious}, meaning that $\varphi$ does not depend on the actual points. We pick the function $\varphi$ without looking at any data sets. It is important because when we pick $\varphi$ we don't know any queries yet.

Another way to look at how this algorithm works is that there exists some $\varphi$ that mapped our original space and metric into something that is lower complexity, such that $\varphi$ is defined on the entire metric and for all $p, q$ have the distance between $\varphi(p)$ and $\varphi(q)$ approximately the same as the distance between $p$ and $q$ with probability at least $1 - 1/n^3$.
In case of Johnson–Lindenstrauss it maps $\R^d$ to lower dimensional $\R^k$, nearly preserving the distances:
$ \varphi: (\R^d, \ell_2) \to (\R^k, \ell_2) $.

It is enough to use a sketching map instead of dimension reducing map. For example, for $\ell_1$ we saw that we can't do dimension reduction, but we don't need to. Instead, we can do something different.

\section{Sketching for $\ell_1$}
\begin{theorem}
There exists a distribution over $\varphi$ such that $\varphi: \R^d \to \R^k$ and estimator algorithm $E: \R^k \times \R^k \to \{0,1\}$, and for all $x, y \in \R^d$:
\begin{itemize}
    \item if $||x - y|| \le r$ then $E(\varphi(x), \varphi(y)) = 0$
    \item if $||x - y|| \ge (1+\varepsilon)r$ then $E(\varphi(x), \varphi(y)) = 1$
\end{itemize}
with probability at least $1 - \delta$, $k = O(\frac{\log 1/\delta}{\varepsilon^2})$
\end{theorem}
(Proof is left for the next homework)

\subsection{Hamming space}

Consider $\{0, 1\}^d$ with $\ell_1$ distance, which is called the Hamming space. All vector coordinates in this space are either 0 or 1. The distance between two vectors in this space is the number of different coordinates.

\begin{theorem}
Fix $d, r \ge 1$, approximation $1+\varepsilon$.
There exists a distribution $\varphi: \{0, 1\}^d \to \{0, 1\}^k, k = O(\frac{\log n}{\varepsilon^2})$ such that:
\begin{itemize}
    \item if $||x-y|| < r$ then $||\varphi(x) - \varphi(y)|| \le \tau k$
    \item if $||x-y|| \ge (1+\varepsilon)r$ then $||\varphi(x) - \varphi(y)|| > (\tau + \frac{\varepsilon}{9}) k$
\end{itemize}
where $\tau$ is a universal constant.
\end{theorem}

(Proof in the next lecture)

This can be seen almost like a dimension reduction from $d$ dimensions to $k$, but with particular scale $r$. This implies $(1+\varepsilon)$-ANN for Hamming space with the same parameters as Solution \#1 for $\ell_2$.


\end{document}
