Indyk, P. and Xu, H. (2023). Worst-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations. In Advances in Neural Information Processing Systems 36, pp. 66239–66256. DOI 10.52202/075280-2891
Key takeaways
Read in full (NOTE-910). For DiskANN’s “slow preprocessing” graph (each point linked to the points that survive α-pruning of all other points, naively O(n³) time), greedy search from any start with no backtracking reaches a ((α+1)/(α−1) + ε)-approximate nearest neighbour in O(log_α(∆/((α−1)ε))) steps, each costing O((4α)^d log ∆) for doubling dimension d and aspect ratio ∆; the ratio is tight and the dependence on ∆ cannot be replaced by log n. For DiskANN with its practical “fast preprocessing”, HNSW, NSG and seven other graph indexes, the paper constructs two-dimensional point sets (constant doubling dimension) on which, in experiments with the authors’ code at the authors’ recommended parameters, the search queue must hold about 10% of the points before recall@5 becomes non-zero or the approximation ratio becomes reasonable. The linear lower bounds are empirical, for one query per constructed instance, with an informal Ω(n/R) argument for fast-preprocessing DiskANN; no theorem bounds HNSW or NSG.
Why this is here
CLAIM-310, with LIT-1103 and LIT-1098: proves a guarantee only for the slow-preprocessing DiskANN graph, at about cubic build cost. For HNSW, NSG and the fast DiskANN build, linear-time behaviour is shown on constructed instances, not proved; the authors cannot prove guarantees for them.