$. (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}