# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 5 Experiments
### Synthetic Data
#### 5.1.1 Sparse Patterns  
Consider data to be drawn i.i.d. with:  
\[\mathbb{P}(x_{i}^{\mu}=1)=\frac{c}{d}=1-\mathbb{P}(x_{i}^{\mu}=0).\]  
Recall that we have four free parameters: \(c\) the number of one in patterns, \(d\) the dimension of patterns, \(k\) the number of pattern in each class and \(q\) the number of classes.  
Our first two experiments consist of varying \(k\) and afterwards \(q\) while the other parameters are fixed. We choose the parameters \(d=128\) and \(c=8\). Figure 1 depicts the rate at which the highest score is not achieved by the class containing the query vector (we call it the error rate), as a function of \(k\) and for \(q=10\). This function is obviously increasing with \(k\) and presents a high slope for small values of \(k\), emphasizing the critical choice of \(k\) for applications.  
Figure 2 depicts the probability of error as a function of \(q\), for various choices of \(k\). Interestingly, for reasonable values of \(k\) the slope of the curve is not as dramatic as in Figure 1. When adjusting parameters, it seems thus more reasonable to increase the number of classes rather than the number of patterns in each class. This is not a surprising finding as the complexity of the process depends on \(q\), but not on \(k\).  
Given data and their parameters \(c\) and \(d\), a typical designing scenario would consist of finding the best trade-off between \(q\) and \(k\) in order to split the data in the different classes. Figure 3 depicts the error rate as a function of \(k\) when \(n=kq\) is fixed. To obtain these points, we consider \(c=8\), \(d=128\) and \(n=16\),384. There are two interesting facts that are pointed out in this figure. First, we see that the trade-off is not simple as multiple local minima happen. This is not surprising as the decision becomes less precise and promissory, with larger values of \(k\). As a matter of fact, the last point in the curve only claims the correct answer is somewhere in a population of 8192 possible solutions, whereas the first point claims it is one of the 64 possible ones. On the other hand, there is much more memory consumption for the first point where 256 square matrices of dimension 128 are stored, whereas only two of them are used for the last point. Second, the error rate remains of the same order for all tested couples of values \(k\) and \(q\). This is an interesting finding as it emphasizes that the design of a solution is more about complexity vs. precision of the answer--in the sense of obtaining a reduced number of candidates--than it is about error rate.  
Figure 1: Evolution of the error rate as a function of \(k\). The other parameters are \(q=10\), \(d=128\) and \(c=8\).  
Figure 2: Evolution of the error rate as a function of \(q\) and for various values of \(k\). The other parameters are \(d=128\) and \(c=8\).  
Finally, in order to evaluate both the tightness of the bounds obtained in Section 3 and the speed of convergence, we run an experiment in which \(c=\log_{2}(d)\), \(q=2\). We then depict the error rate as a function of \(d\) and when \(k=d^{1.5}\), \(k=d^{2}\) and \(k=d^{2.5}\). The result is depicted in Figure 4. This figure supports the fact that the obtained bound is tight, as illustrated by the curve corresponding to the case \(k=d^{2}\) for which the error rate appears almost constant.  
We ran the same experiments using co-occurrence rules as initially proposed in [7] (instead of adding contributions from distinct messages, we take the maximum). We observed small improvements in every case, even though they were not significant.