• indexing
• graphs
• ann
• knn
• approximate knn
• k-nearest neighbors
• similarity search

In the modern era of Big Data the ability to search a given element -called query- in a set of data is fundamental. This search is done via Similarity Search, a paradigm of searching based on a notion of similarity between pairs of objects. With the advent of neural networks, it became possible to produce representations of any kind of object in the form of numerical vectors. Thus, it is possible to perform similarity search by computing distances on vector spaces. This lead us to solving the k-Nearest Neighbors search (kNN) problem. In practice, we solve the Approximate kNN search (ANN).
Many methods have been proposed to face this problem. The most promising class is that of graph-based ANN.
In this work these methods are deeply analyzed and then tested and compared to other class of methods. The reasons of the superiority of these methods and some improvements are investigated.