提出网格法在高维近邻搜索中的缩放规律，证明其性能更稳定。
Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions
- 用多探针网格法系统分析数据量与维度对搜索效率的影响。
- 在高维下保持稳定性能，吞吐量随维度增长下降更慢。
- 适合索引成本敏感或维度高的场景，如Transformer优化。
基于网格的近似最近邻（ANN）搜索方法长期未被纳入现代缩放分析。本文系统研究了多探针网格算法在数据集规模 $N$ 和维度 $d$ 两个维度上的表现。实验发现，在 GloVe 嵌入族中存在此前未报告的 $d$-缩放交叉现象：多探针网格搜索的维度缩放指数近似恒定，而图、树和分治类方法的吞吐量随维度上升显著下降。该方法具有近线性的查询复杂度 $O(N)$，且索引开销低于现有 ANN 方法。结果表明，网格类方法在重建频繁或高维场景中具备竞争力，尤其在索引成本和维度鲁棒性决定性能的场景。更广泛地，近期研究将自注意力形式化为 ANN 操作，因此此类算法的 $N$ 与 $d$ 缩放特性可指导高效 Transformer 架构的成本分析。代码已公开于：https://github.com/weiz345/MultiProbeANN。
原文摘要 · Abstract (English)
Grid-based approaches to approximate nearest neighbor (ANN) search have been absent from modern scaling analyses. We present a systematic characterization of a multiprobe grid algorithm with respect to dataset size $N$ and dimensionality $d$. Our experiments reveal a previously unreported $d$-scaling crossover on the GloVe embedding family, in which multiprobe grid search maintains an approximately constant dimensional scaling exponent while other graph-, tree-, and partitioning-based methods exhibit degrading throughput. The advantage comes with near-linear query scaling in $N$, but also with lower indexing cost than competing ANN methods. Our results suggest that grid-based methods such as multiprobe grid may be competitive in rebuild-heavy or high-dimensional settings where indexing cost and dimensional robustness dictate performance. More broadly, recent work has formalized self-attention as an ANN operation. Thus, the $N$- and $d$-scaling properties of ANN algorithms may guide cost analysis of efficient transformer architectures. Code is available at: https://github.com/weiz345/MultiProbeANN.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。