\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} \spacing{1.06} \usepackage{graphicx} \newcommand{\handout}[5]{ \noindent \begin{center} \framebox{ \vbox{\vspace{0.25cm} \hbox to 5.78in { {COMS E6998-9:\hspace{0.12cm}Algorithmic Techniques for Massive Data} \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} \newtheorem*{theorem*}{Theorem} \begin{document} \lecture{12 -- More LSH, Data-Dependent Hashing}{Oct 15, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Mingxian Zhong}} \section{Time-space Trade-offs} Below we present a table of LSH algorithms using different space and time. \bigskip \begin{tabular}{|l|l|l|l|l|} \hline Type & Space & Time & Comment & Ref \\ \hline Low space and & $\approx n$ & $n^\sigma$ & $\sigma=2.09/c$ & [Ind'01,Pan'06] \\ \cline{2-5} High query time& $\approx n$ & $n^\sigma$ & $\sigma=O(1/c^2)$ & [AI'06] \\ \hline Medium space and & $n^{1+\rho}$ & $n^\rho$ & $\rho=1/c$ & [IM'98,DIIM'04] \\ \cline{2-5} Medium query time& $n^{1+\rho}$ & $n^\rho$ & $\rho=1/c^2$ & [AI'06] \\ \cline{2-5} & $n^{1+\rho}$ & $n^\rho$ & $\rho\geq 1/c^2$ & [MNP'06,OWZ'11] \\ \cline{2-5} & $n^{1+o(1+1/c^2)}$ & \multicolumn{2}{|l|} {$ \omega(1) $ memory lookup} & [PTW'08,PTW'10] \\ \hline High space and & $n^{4/\epsilon^2}$ & $O(dlogn)$(1 mem lookup) & $c=1+\epsilon$ & [KOR'98,IM'08,Pan'06] \\ \cline{2-5} Low query time & $n^{o(1/\epsilon^2)}$ & \multicolumn{2}{|l|} {$ \omega(1) $ memory lookup} & [AIP'06] \\ \hline \end{tabular} \section{Near-linear Space for $ \{0,1\}^d $} [Indyk'01,PanIgrahy'06] \begin{itemize} \item General idea: Sample a few bucket in the same hash table. \item Setting: \begin{itemize} \item Close: $ r=\dfrac{d}{2c} $ [Note that from last lecture $ P_1=1-\dfrac{r}{d}=1-\dfrac{1}{2c} $] \item Far: $ cr=\dfrac{d}{2} $ [Note that from last lecture $ P_2=1 - \dfrac{cr}{d}=\dfrac{1}{2} $] \end{itemize} \item Algorithm: \begin{itemize} \item Use on hash table with $k=\dfrac{\log n}{\log 1/P_2}=\alpha \ln n$ [Note that since $ P_2=1/2 $ here $ \alpha $ is a constant] \item On query q: \begin{itemize} \item Compute $w=g(p)\in \{0,1\}^k$ \item Define $w'$ such that starting from $w$, flip each $w_j$ with probability $ 1-P_1 $ \item Lookup bucket $ g(w') $ and compute distance to all points there \item Repeat $ R=n^\sigma $ times, stop if found an approximate near neighbor \end{itemize} \end{itemize} \end{itemize} \begin{theorem*} For $\sigma=\Theta(\dfrac{\log c}{c})$, we have \begin{itemize} \item Pr[find an approximate near neighbor]$ \geq 0.1 $ \item Expected runtime: $ O(n^\sigma) $ \end{itemize} \end{theorem*} \begin{proof} Let $p^*$ be the near neighbor, then we know that $\|q-p^*\|\leq r$. Define $ w=g(q), t=\|w-g(p^*)\|_1 $. \begin{claim} $ Pr[t\leq \dfrac{k}{c}]\geq \dfrac{1}{2} $ \end{claim} \begin{proof} Note that $ E[t]=\dfrac{r}{d}k=\dfrac{k}{2c} $. Hence by Markov Inequality, $Pr[t\leq \dfrac{k}{c}]\geq 1-\dfrac{k}{2c}/\dfrac{k}{c}=\dfrac{1}{2}$ \end{proof} \bigskip \begin{claim} $ Pr[w'=g(p)|\|q-p\|_1\geq \dfrac{d}{2}]\leq \dfrac{1}{n} $ \end{claim} \begin{proof} \begin{align*} Pr[\text{Collision}]&\leq (P_1P_2+(1-P_1)(1-P_2))^k\\ &= (P_2(P_1+1-1)+(1-P_1)(1-P_2))^k\\ &= (P_2+(1-P_1)(1-2P_2))^k\\ &\leq P_2^k=1/n \end{align*} \end{proof} \bigskip \begin{claim} $ Pr[w'=g(p^*)|\text{Claim 1}]\geq n^{-\sigma} $ \end{claim} \begin{proof} \begin{align*} Pr[w'=g(p^*)|\text{Claim 1}]&=(1-P_1)^tP_1^{k-t}\\ &\geq (1-(1-\dfrac{1}{2c}))^{k/c} (1-\dfrac{1}{2c})^{k(1-1/c)}\\ &\geq (\dfrac{1}{2c})^{\dfrac{k}{c}}e^{-\dfrac{1}{2c}k}\\ &\geq n^{-\dfrac{\Theta(1)\lg c}{c}}n^{-\dfrac{\alpha}{2c}}\\ &\geq n^{-\sigma} \end{align*} \end{proof} Since if $w'=g(p^*)$ for at least one $w'$, we are guaranteed to output either $p^*$ or an approximate near neighbor, we are done by Claim 3. \end{proof} \section{Beyond LSH} Below we give a contrast of LSH algorithms and other algorithm. \bigskip In Hamming Space \begin{tabular}{|l|l|l|l|l|l|} \hline Type & Space & Time & Comment &$c=2$ & Reference \\ \hline LSH & $n^{1+\rho}$ & $n^\rho$ & $\rho=1/c$&$ \rho=1/2 $ & [IM'98] \\ \cline{2-6} & & & $\rho\geq 1/c$& & [MNP'06,OWZ'11] \\ \hline Non-LSH & $n^{1+\rho}$ & $n^\rho$ & $\rho\approx\frac{1}{2c-1}$&$\rho=1/3$ & [AINR'14,AR'15] \\ \cline{1-6} \end{tabular} \bigskip In Euclidean Space \begin{tabular}{|l|l|l|l|l|l|} \hline Type & Space & Time & Comment &$c=2$ & Reference \\ \hline LSH & $n^{1+\rho}$ & $n^\rho$ & $\rho\approx 1/c^2$&$ \rho=1/4 $ & [AI'06] \\ \cline{2-6} & & & $\rho\geq 1/c^2$& & [MNP'06,OWZ'11] \\ \hline Non-LSH & $n^{1+\rho}$ & $n^\rho$ & $\rho\approx\frac{1}{2c ^2-1}$&$\rho=1/7$ & [AINR'14,AR'15] \\ \cline{1-6} \end{tabular} \section{Data-dependent hashing} [A.-Indyk-Nguyen-Razenshteyn'14,A.-Razenshteyn'15] \begin{itemize} \item General idea: Using a random has function, which is chosen after seeing the given dataset \item Feature: Efficiently computable \item Components: \begin{itemize} \item Nice geometric structure (has better data partition) \item Reduction to such structure (depends on the data) \end{itemize} \item Nice geometric structure: \begin{itemize} \item Like a random dataset on a sphere s.t. random points at distance $ \approx cr $ \item Query: At angle 45' from near-neighbor \end{itemize} \item Alg 1: Hyperplanes[Charikar'02] \begin{itemize} \item We sample unit r uniformly, hash $ p $ into $ sgn $,\\$ Pr[h(p)=h(q)]=1-\alpha/\pi $, where $\alpha$ is the angle between $p$ and $q$ \item $ P_1=3/4,P_2=1/2 $ \item $ \rho\approx 0.42 $ \end{itemize} \item Alg 2: Voronoi[A.-Indyk-Nguyen-Razenshteyn'14] based on [Karger-Motwani-Sudan'94] \begin{itemize} \item Sample $T$ i.i.d. standard $d$-dimensional Gaussians $g_2,g_2,..,g_T$. \item Hash $p$ into $ h(p)=argmax_{1\leq i\leq T}$ \item Note that it is simply Hyperplane LSH when $T=2$ \end{itemize} \item Hyperplane VS Voronoi \begin{itemize} \item Hyperplane with $ k=6 $ hyperplanes , which means we partition space into $ 2^6=64 $ pieces \item Voronoi with $T=2^k=64$ vectors. $\rho=0.18$ \includegraphics{pic1} \item In Hyperplane algorithm we partition into grids while in Voronoi we partition into sphere \end{itemize} \end{itemize} \section{Nearest Neighbor Search: Conclusion} \begin{itemize} \item Approach 1: Via sketches \item Approach 2: Locality Sensitive Hashing \begin{itemize} \item Use Random Space Partitions \item Algorithm with Better Space Bound \item Use Data-dependent hashing \end{itemize} \end{itemize} \end{document}