Probabilistic Kernel Function For Fast Angle Testing

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keylu2025probabilistic

Related papers

• Kernel Density Estimation Through Density Constrained Near Neighbor Search (2020)5.84
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• DEANN: Speeding Up Kernel-density Estimation Using Approximate Nearest Neighbor Search (2021)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• Efficient Data-aware Distance Comparison Operations For High-dimensional Approximate Nearest Neighbor Search (2024)5.24
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19
• 2-bit Random Projections, Nonlinear Estimators, And Approximate Near Neighbor Search (2016)0.00
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00