# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 3 Search Problems with Sparse Patterns  
In this section, we will treat the situation where we try to find a pattern that is closest to some input pattern and all the patterns are binary and sparse. To be more precise, assume that we are given nsparse vectors or patterns \(x^{\mu},\mu=1,\ldots,n\) with \(x^{\mu}\in\{0,1\}^{d}\) for some (large) \(d\). Assume that the \((x^{\mu})\) are random and i.i.d. and have i.i.d. coordinates such that:  
\[\mathbb{P}(x^{\mu}_{i}=1)=\frac{c}{d}=1-\mathbb{P}(x^{\mu}_{i}=0)\]  
for all \(i=1,\ldots,d\) and all \(\mu=1,\ldots,n\). To describe a sparse situation, we will assume \(c\) depends on \(d\), such that \(c/d\to 0\) as \(c\) and \(d\) become large. We will even need this convergence to be fast enough. Moreover, we will always assume that there is an \(x^{\mu}\) such that the query pattern \(x^{0}\) has a macroscopically large overlap with \(x^{\mu}\), hence that \(\sum_{l=1}^{d}x^{0}_{l}x^{\mu}_{l}\) is of order \(c\). We will begin with the situation that \(x^{0}=x^{\mu}\) for an index \(\mu\). The situation where \(x^{0}\) is a perturbed version of \(x^{\mu}\) is then similar. The algorithm proposed in [7] proposes to partition the patterns into equal-sized classes \(\mathcal{X}^{1},\ldots\mathcal{X}^{q}\), with \(|\mathcal{X}^{i}|=k\) for all \(i=1,\ldots q\). Thus, \(n=kq\). Afterwards, one computes the score:  
\[s(\mathcal{X}^{i},x^{0})=\sum_{\mu:x^{\mu}\in\mathcal{X}^{i},l,m=1}x^{0}_{l}x ^{\mu}_{m}x^{\mu}_{l}x^{\mu}_{m}\]  
for each of these classes and takes the class \(\mathcal{X}^{i}\) with the highest score. Then, on this class, one performs exhaustive search. We will analyze under which condition on the parameters this algorithm works well and when it is effective. To this end, we will show the following theorem. Theorem 3.1: _Assume that the query pattern is equal to one of the patterns in the database. The algorithm described above works asymptotically correctly, i.e., with an error probability that converges to zero and is efficient, i.e., requires less computations than exhaustive search, if:_  
1. \(d\ll k\ll d^{2}\)_, i.e.,_ \(\frac{k}{d}\to 0\) _and_ \(\frac{k}{d}\to\infty\)_,_
2. \(c\ll d\) _and_ \(c\ll\left(\frac{d^{2}}{k^{3}}\right)^{\frac{1}{6}}\)__
3. _and_ \(qe^{-\frac{1}{3}\frac{d^{2}}{k}}\to 0\)_._  
Proof: To facilitate notation, assume that \(x^{0}=x^{1}\) (which is of course unknown to the algorithm), that \(x^{1}\in\mathcal{X}^{1}\) and that \(x^{1}_{i}=1\) for the first \(\mathcal{C}\) indices \(i\) and that \(x^{1}_{i}=0\) for the others. Note that for any \(\varepsilon>0\), with high probability (when \(c\) and \(d\) become large), we are able to assume that \(\frac{\mathcal{C}}{d}\in\left(\frac{\mathcal{C}}{d}(1-\varepsilon),\frac{ \mathcal{C}}{d}(1+\varepsilon)\right)\). Then, for any \(i\), we have \(s(\mathcal{X}^{i},x^{0})=\sum_{\mu:x^{\mu}\in\mathcal{X}^{i}}\sum_{l,m=1}^{ \mathcal{C}}x^{\mu}_{l}x^{\mu}_{m}\) and in particular:  
\[s(\mathcal{X}^{1},x^{0})=\mathcal{C}^{2}+\sum_{ \begin{subarray}{c}\mu:x^{\mu} \in\mathcal{X}^{1}\\ \mu\
eq 1\end{subarray} }\sum_{l,m=1}^{\mathcal{C}}x^{\mu}_{l}x^{\mu}_{m}.\]We now want to show that for a certain range of parameters \(n,k\) and \(d\), this algorithm works reliably, i.e., we want to show that:  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{0})) \to 0\qquad\text{as}\quad d\to\infty.\]  
Now, since, \(c\) and \(\tilde{c}\) are close together when divided by \(d\), we will replace \(\tilde{c}\) by \(c\) everywhere without changing the proof. Trivially,  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{0} ))\leq q\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\]  
and we just need to bound the probability on the right-hand side. Taking \(X_{\mu}\) to be i.i.d.