[2505.20274] Probabilistic Kernel Function for Fast Angle Testing

Computer Science > Machine Learning arXiv:2505.20274 (cs) [Submitted on 26 May 2025 (v1), last revised 1 Mar 2026 (this version, v3)] Title:Probabilistic Kernel Function for Fast Angle Testing Authors:Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa View a PDF of the paper titled Probabilistic Kernel Function for Fast Angle Testing, by Kejing Lu and 2 other authors View PDF HTML (experimental) Abstract:In this paper, we study the angle testing problem in the context of similarity search in high-dimensional Euclidean spaces and propose two projection-based probabilistic kernel functions, one designed for angle comparison and the other for angle thresholding. Unlike existing approaches that rely on random projection vectors drawn from Gaussian distributions, our approach leverages reference angles and adopts a deterministic structure for the projection vectors. Notably, our kernel functions do not require asymptotic assumptions, such as the number of projection vectors tending to infinity, and can be theoretically and experimentally shown to outperform Gaussian-distribution-based kernel functions. We apply the proposed kernel function to Approximate Nearest Neighbor Search (ANNS) and demonstrate that our approach achieves a 2.5x--3x higher query-per-second (QPS) throughput compared to the widely-used graph-based search algorithm HNSW. Comments: Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Databases (cs.DB); Da...