\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{tikz}
\usetikzlibrary{circuits.logic.US}
\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}

\begin{document}

\newcommand{\slice}[4]{
  \pgfmathparse{0.5*#1+0.5*#2}
  \let\midangle\pgfmathresult

  % slice
  \draw[thick,fill=black!10] (0,0) -- (#1:1) arc (#1:#2:1) -- cycle;

  % outer label
  \node[label=\midangle:#4] at (\midangle:1) {};

}

\lecture{Nearest Neighbor Search (part 2)}{Apr 28,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Bryant Hugo Zhang, Silva Xiaobin Lin, Declan O'Reilly}}

\section{Recap}

\bigskip
Last lecture, we looked at the nearest neighbor search. Today we will look at research from the last decade as well as earlier research.

\bigskip
Last time, we looked at the approximate nearest neighbor search, specifically, that we can solve theoretically and have guarantees, which allows us to compare different algorithms. For a fixed \(c\)-approximate and a fixed threshold \(r\), if we have a guarantee that there is something within distance \(r\), the algorithm will find something that is within a distance of \(cr\).

\bigskip
We looked at the LSH algorithms, that is based upon the locality of hashing functions, where we build \(n^{\rho}\) hash tables, where \(\rho\) depends on how well the space is partitioned. For hamming space we had \(\rho = 1/c\), where the hashes are projected on random bins. For Euclidean space we use a similar \(\rho\) and space/times through we can improve \(\rho \geq 1/c^{2}\) when we move from cells to cells. 

\bigskip
We have
\[ \rho = \frac{\log\frac{1}{p_{1}}}{\log\frac{1}{p_{2}}}\]

\[ p_{1} = \text{Probability that similar pair of points collide}\]
\[ p_{2} = \text{Probability that dissimilar pair of points collide}\]


\section{Euclidean LSH: Hyperplane ($\rho = 1/c$)}

\bigskip
In this case, the vectors are unit-norm vectors. To define the hash functions, we have a circle which is the shape of the hyper-plane, i.e. all the vectors of unit norm. We pick a random direction \(r\) and position the circle with a line perpendicular to the direction \(r\) and going through the center, with +1 on one side and -1 on the other. 

\bigskip
We hash \(p\) into $h(p) = sgn<r,p>$. $Pr[h(p) = h(q)]$ depends on the angle between \(p\) and \(q\) and is $1 - \frac{\alpha}{\pi}$ where $\alpha$ is the angle between \(p\) and \(q\).

\bigskip


\begin{figure}
\centering
\begin{tikzpicture}[x = 2cm, y = 2cm, text height = 1.5ex, text depth = 0.25ex]
\newcounter{a}
\newcounter{b}
\foreach \p/\t in {50/p, 40/, 10/q}
  {
    \setcounter{a}{\value{b}}
    \addtocounter{b}{\p}
    \slice{\thea/100*360}
          {\theb/100*360}
          {\p\%}{\t}
  }
\end{tikzpicture}
\end{figure}

\bigskip
We have $p_{1} = \frac{3}{4}$ and $p_{2} = \frac{1}{2}$ with $p \approx 0.42$

\bigskip
Recall hash function $g = (h_{1}, h_{2}, ..., h_{k})$, now we perform \(k\) such projections on \(k\) random directions.

\bigskip
This algorithm is not one of the most efficient, but it is one of the simplest.

\section{LSH $\approx$ random dimension reductions}

\bigskip
In the hamming space rather than using the full vector, we sample from it, which gives us an approximation to the real hamming distance. This corresponds to the hash function we are using in LSH. The previous Euclidean algorithm is also in a similar vain, where we lower the dimension while trying to maintain distance, with probability \[1 - e^{\frac{-k\epsilon^{2}}{c}}\] 

For nearest neighbors search, this gives us a reduction \[k = O(\log{n})\]

\section{Detour: Fruit Fly Olfactory System (and how it compares to LSH)}

\bigskip
The olfactory system is made up of four layers:
\begin{enumerate}
    \item Odorant receptors $\sim$50 - normalized to release flow to nearest layer
    \item Projection neurons $\sim$50 - random space connections (6/50) to nearest layer
    \item Keyon cells $\sim$2000 - only 51 made it to next layer
    \item Final layer
\end{enumerate}

The random sparse connections from the projection neurons to the Keyon cells is a form of random dimension increasing, but the outermost layer is very sparse. So the paper by \emph{Dasgupta, Stevens, and Navlakha [2018]} suggests that the transformation is similar to Locality-Sensitive Hashing, though of a different kind. The best transformation they suggest is a form of Winner-Take-All (WTA). 

\section{Back to LSH}

\bigskip
In Euclidean space you can define certain hash functions that are data dependent, which have better performance i.e. \[\rho \approx \frac{1}{2c^2-1}\] in the exponent. 

\bigskip
Data dependent LHS has 2 components:
\begin{enumerate}
\item If data is "pseudo-random", we get better LSH partitions
\item Can always reduce any worst case dataset to the "pseudo-random" case (Regularity lemma). Though this is not practical at the moment, i.e. it is theoretical
\end{enumerate}

\section{Data Dependent Hashing}

\bigskip
We choose the random hash function that partitions the space after seeing the data. For part 2, we could build a Voronoi diagram using the data, which partitions the space around each point where each partition contains the space that is closer to the point than any other point. We have smaller partitions where the points are denser. This allows us to build the hash function from the diagram. The problem is that building this diagram is as inefficient as linear nearest neighbors search.







\section{"Pseudo-random" case (Isotropic)}
Ignore the data dependent part, we will assume the following two additional structures:
\begin{enumerate}
    \item Far Pair is near orthogonal @distance cr. This is equivalent to when dataset is random on sphere. Pick two random points on unit sphere: $cr = \sqrt{2}.$ All points are orthogonal to the query.
    \item Close Pairs' distance is $r$.
\end{enumerate}

\begin{lemma}
There exists LSH with \[\rho = \frac{1}{2c^2-1}\] (not data dependent). The Pseudo random case is the best possible, from the isoperimetry argument. We cannot further improve on such $\rho$.
\end{lemma}

\bigskip

\section{Better LSH for Isotropic case}

\begin{figure}
\centering

\begin{tikzpicture}[scale=1.0]

\draw [step=1.0,thin,gray!40] (0,-3) grid (6,3);

\fill[blue] (3,0) circle (2pt) node [black,below left] {$C$};
%
\draw[thick] (3,0) circle(3);
\begin{scope}[>=latex]
\draw[->] (3,0) -- (6,0)  node [midway,fill=white] {$r_1$};
\draw[->] (3,0) -- ++(45:3)  node [midway,sloped,fill=white] {$r_2$};
\draw[->] (3,0) -- ++(-90:3)  node [midway,sloped,fill=white] {$r_3$};
\draw[dotted] (3,0) -- ++(-45:3)  node [midway,sloped, fill=white] {$r_{1-3}$};
\draw[dotted] (3,0) -- ++(22.5:3)  node [midway,sloped, fill=white] {$r_{1-2}$};
\draw[dotted] (3,0) -- ++(157.5:3)  node [midway,sloped, fill=white] {$r_{2-3}$};


\end{scope}

\end{tikzpicture}
\end{figure}

In contrast with Hyperplane LSH, sample \(T\) i.i.d standard d-dimensional Gaussian $r_1,r_2,...,r_{t}$. Hash a point $p$ into $g(p) = argmax_{1\leq i\leq T} <p,r_i>$. (Winner-Take-All)
\begin{enumerate}
    \item We have three partitions, each has a set of points. 
    \item Mathematically speaking, the dot product of such point with $r_i$ is assigned to $r_i$ if the product is the biggest among all $i$.
    \item Geometrically speaking, the half angle line $r_{j-k} $ between $r_j$ and $r_k$ separates the neighboring regions.
    \item This is a better LSH for the isotropic case.
    \item It begins to be very similar to Fruit Fly Olfactory System at least when there is only one winner.
\end{enumerate}

\begin{figure}
\centering
\begin{tikzpicture}[x = 2cm, y = 2cm, text height = 1.5ex, text depth = 0.25ex]
%\newcounter{a}
%\newcounter{b}
\foreach \p/\t in {50/p, 40/, 10/q}
  {
    \setcounter{a}{\value{b}}
    \addtocounter{b}{\p}
    \slice{\thea/100*360}
          {\theb/100*360}
          {\p\%}{\t}
  }
\end{tikzpicture}
\end{figure}

\noindent\textbf{Example:}
\begin{itemize}
    \item When T=2. This is the Hyperplane LSH.
    \item As T gets larger, start to differ from Hyperplane LSH.
\end{itemize}

\section{WTA LSH for Isotropic case}
\textbf{Issue:}
Issue here is mainly two-fold. First, fruit fly can have more than one winner. And what does it mean to have "more than one winner", for example, top 5 percent? And does it have any equivalence in nearest neighbor search? Second, Fruit Fly can be said to only use one hash table. 

\bigskip
\noindent\textbf{Multi-probe LSH:}
Driven by the idea of doing nearest neighbor search using fewer hash tables to reduce space, [Lv-Josephson-Wang-Charikar-Li’07] suggests another nearest neighbor idea called multi-probe LSH. 
For a classic LSH, $p_{1}$ is very small, $\approx {n^{-\rho}}$, hence build ${n^{\rho}}$ iid hash tables. While the pre-processing remains the same, everything is put in one hash table. Every time an element is checked, its nearby bucket will also be looked up as well. 

\bigskip However, we do need to define properly what "nearby" means. Normally starting from $g(p)$,if $g(q) != g(p)$ and $g(q)$ is ruled out, $g_1(q)$ will be the next most likely option and it will be looked at then. After that, $g_2(q)$ subs in once $g_1(q)$ is ruled out. And the logic remains for the rest of the search.

\bigskip
Oftentimes in WT LSH, $g(q),g_1(q)...g_k(q)$ are top k max's. 


\section{Back to LSH: the data-dependent part}
We can reduce any worst-case dataset to the "pseudorandom" case.

\begin{lemma}
Any pointset $P \in R^d$ can be decomposed into clusters, where one cluster is pseudo-random and the rest have smaller diameter. (A form of "regularity lemma")
\end{lemma}



\end{document}
