提出新型确定性核函数，加速高维空间角度搜索
Probabilistic Kernel Function for Fast Angle Testing
- 用参考角度构建确定性投影向量，替代随机高斯投影
- 在角度比较和阈值检测上均超越传统方法，实测查询速度提升2.5至3倍
- 适合需要高速相似性搜索的工程场景，如大规模向量检索
本文研究高维欧氏空间中的相似性搜索角度测试问题，提出两种基于投影的概率核函数，分别用于角度比较与角度阈值判断。与依赖高斯分布随机投影向量的现有方法不同，本方法利用参考角度，采用确定性结构设计投影向量。显著优势在于无需渐近假设（如投影向量数量趋于无穷），理论与实验均表明其性能优于基于高斯分布的核函数。将该核函数应用于近似最近邻搜索（ANNS），实验显示相较广泛应用的图基算法HNSW，查询每秒吞吐量（QPS）提升2.5至3倍。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。