This paper addresses the challenge of leveraging GPUs for similarity search, particularly in handling high-dimensional data such as images and videos. The authors propose an optimized $k$-selection algorithm that operates at up to 55% of theoretical peak performance, enabling an $8.5 \times$ faster nearest neighbor implementation compared to prior GPU state-of-the-art. They apply this algorithm to various similarity search scenarios, including brute-force, approximate, and compressed-domain search using product quantization. The results show significant improvements over existing methods, achieving high accuracy in constructing $k$-NN graphs on large datasets. The paper also includes a detailed analysis of GPU architecture and discusses the challenges of similarity search on GPUs. The authors' approach is open-sourced for reproducibility and comparison.This paper addresses the challenge of leveraging GPUs for similarity search, particularly in handling high-dimensional data such as images and videos. The authors propose an optimized $k$-selection algorithm that operates at up to 55% of theoretical peak performance, enabling an $8.5 \times$ faster nearest neighbor implementation compared to prior GPU state-of-the-art. They apply this algorithm to various similarity search scenarios, including brute-force, approximate, and compressed-domain search using product quantization. The results show significant improvements over existing methods, achieving high accuracy in constructing $k$-NN graphs on large datasets. The paper also includes a detailed analysis of GPU architecture and discusses the challenges of similarity search on GPUs. The authors' approach is open-sourced for reproducibility and comparison.