# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 5 Experiments
### Real Data  
In this section, we use real data in order to stress the performance of the obtained methods on authentic scenarios. Since we want to stress the interest of using our proposed method instead of classical exhaustive search, we are mainly interested in looking at the error as a function of the complexity. To do so, we modify our method as follows: we compute the scores of each class and order them from largest to smallest. We then look at the rate for which the nearest neighbor is in one of the first \(p\) classes. With \(p=1\), this method boils down to the previous experiments. Larger values of \(p\) allow for more flexible trade-offs of errors versus performance. We call the obtained ratio the recall@1. Considering \(n\) vectors with dimension \(d\), the computational complexity of an exhaustive search is \(dn\) (or \(cn\) for sparse vectors). On the other hand, the proposed method has a two-fold computational cost: first, the cost of computing each score, which is \(d^{2}q\) (or \(c^{2}q\) for sparse vectors), then the cost of exhaustively looking for the nearest neighbor in the selected \(p\) classes, which is \(pkd\) (or \(pck\) for sparse vectors). Note that the cost of ordering the \(q\) obtained scores is negligible. In practice, distinct classes may have a distinct number of elements, as explained later. In this case, complexity is estimated as an average of elementary operations (addition, multiplication, accessing a memory element) performed for each search. When applicable, we also compare the performance of our method with Random Sampling (RS) to build a search tree, the methodology used by PySparNN ([[https://github.com/facebookresearch/pysparnn](https://github.com/facebookresearch/pysparnn)]([https://github.com/facebookresearch/pysparnn](https://github.com/facebookresearch/pysparnn))), or Annoy ([[https://github.com/spotify/annoy](https://github.com/spotify/annoy)]([https://github.com/spotify/annoy](https://github.com/spotify/annoy))). In their method, random sampling of \(r\) elements in the collection of vectors is performed; we call them anchor points. All elements from the collection are then attached to their nearest anchor point. When performing the search, the nearest anchor points are first searched, then an exhaustive computation is performed with corresponding attached elements. Finally, we also look at the performance of a hybrid method in which associative memories are first used to identify which part of the collection should be investigated, then these parts are treated independently using the RS methodology. There are several things that need to be changed in order to accommodate real data. First, for non-sparse data, we center data and then project each obtained vector on the hypersphere with radius one. Then, due to the non-independence of stored patterns, we choose an allocation strategy that greedily assigns each vector to a class, rather than using a completely random allocation. The allocation strategy we use consists of the following: each class is initialized with a random vector drawn without replacement. Then, each remaining vector is assigned to the class that achieves the maximum normalized score. Scores are divided by the number of items \(u\) currently contained in the class, as a normalization criterion. Note that more standard clustering techniques could be used instead. Figure 9 depicts all steps of the proposed method. Figure 8: Evolution of the error rate as a function of \(d\). In this scenario, we choose \(k=d^{\alpha}\) with various values of \(\alpha\) and \(q=2\). We also run some experiments on a binary database. It consists of Santander customer satisfaction sheets associated with a Kaggle contest. There are 76,000 vectors with dimension 369 containing 33 nonzero values on average. In this first experiment, the vectors stored in the database are the ones used to also query it.