# Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism

**Authors:** Zhen Peng, Minjia Zhang, Kai Li, Ruoming Jin, Bin Ren  
**arXiv:** [2201.13007](https://arxiv.org/abs/2201.13007)  
**Date:** 2022-01-31  
**Summary page:** https://www.summarizepaper.com/en/paper/2201.13007v1/

## Key points

- Nearest Neighbor Search (NNS) is important in data science and AI applications for managing high-dimensional vector data.
- Similarity graphs have emerged as successful algorithms for fast NNS.
- Challenges exist in maximizing the performance of similarity graph algorithms, especially in large-scale and high-recall scenarios.
- The authors propose a parallel similarity search algorithm called Speed-ANN that exploits hidden intra-query parallelism and memory hierarchy to improve search efficiency.
- Speed-ANN achieves shorter query latency compared to NSG and HNSW, outperforming highly optimized GPU implementations as well.
- Speed-ANN exhibits good scalability with increasing hardware resources (such as CPU cores) and graph sizes.
- Speed-ANN is a promising solution for low latency and high accuracy nearest neighbor search in managing high dimensional vector data.

## Summary

Nearest Neighbor Search (NNS) has become increasingly important in data science and AI applications due to its role in managing high-dimensional vector data. This interest has been fueled by the success of neural embedding, where deep learning models transform unstructured data into semantically correlated feature vectors for tasks like recommending popular items. Among the various methods for fast NNS, similarity graphs have emerged as one of the most successful algorithmic trends. Popular similarity graph algorithms such as NSG and HNSW employ best-first traversal along underlying graph indices to search for near neighbors. However, maximizing the performance of these algorithms is challenging, especially in large-scale and high-recall scenarios. In this work, the authors provide an in-depth examination of the challenges faced by state-of-the-art similarity search algorithms, particularly in leveraging multi-core processors to improve search efficiency. The authors also explore whether similarity graph search can be made more robust by allowing multiple walkers to simultaneously advance the search frontier, deviating from strict order maintenance. Based on their insights, they propose a parallel similarity search algorithm called Speed-ANN. This algorithm exploits hidden intra-query parallelism and memory hierarchy to enable similarity search to take advantage of multiple CPU cores, significantly accelerating search speed while maintaining high accuracy. To evaluate Speed-ANN's performance, the authors conduct experiments on a wide range of datasets with varying sizes (ranging from million to billion data points). The results demonstrate that Speed-ANN achieves shorter query latency compared to NSG and HNSW. Moreover, with multicore support, Speed-ANN outperforms highly optimized GPU implementations in terms of search latency and exhibits good scalability with increasing hardware resources (such as CPU cores) and graph sizes. Overall, this study presents Speed-ANN as a novel approach for low latency and high accuracy nearest neighbor search. By leveraging intra query parallelism and memory hierarchy on multi core processors, Speed ANN offers significant improvements over existing similarity search algorithms making it a promising solution for managing high dimensional vector data in data science and AI applications.