Instance-based Approximation Guarantees for Graph-based Nearest Neighbor Search

Nearest Neighbor Search (NNS) in high-dimensional point sets is an important building block in many application areas, including pattern recognition, machine learning, planning, data mining, and computational geometry. Graph-based approaches that offer approximate NNS (ANNS) are ubiquitously used for these applications, and a variety of suitable graph structures have been proposed for this purpose. However, these approaches do not come with a priori approximation guarantees, often not even in low dimensions. Thus, there may be query points for which the distance to the returned ANN is significantly larger than the distance to the true NN. A common way to assess the quality of graph-based search and to compare different variants is the evaluation of query point samples. However, since the space of potential query points is infinite, it is likely that the samples will give biased results and that critical points will be missed. To systematically evaluate the ANNS quality of a given graph structure, we propose an algorithm that identifies the query point with the worst ratio r between ANN distance and true NN distance. This ratio provides a tight instance-based approximation guarantee. Our algorithm relies on a new geometric data structure called search-path diagram. In our experiments on established base graphs, we demonstrate that sampling based evaluation heavily underestimates r, while our method provides a robust quality assessment.