Probabilistic Kernel Function for Fast Angle Testing
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908857513541632 |
|---|---|
| author | Lu, Kejing Xiao, Chuan Ishikawa, Yoshiharu |
| author_facet | Lu, Kejing Xiao, Chuan Ishikawa, Yoshiharu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probabilistic Kernel Function for Fast Angle Testing Lu, Kejing Xiao, Chuan Ishikawa, Yoshiharu Machine Learning Artificial Intelligence Computer Vision and Pattern Recognition Databases Data Structures and Algorithms 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. |
| title | Probabilistic Kernel Function for Fast Angle Testing |
| topic | Machine Learning Artificial Intelligence Computer Vision and Pattern Recognition Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.20274 |