近似最近傍探索（ANN）は機械学習やデータベースシステムにおいて重要な基礎技術です。大規模なベクトルデータセットから効率的に類似した埋め込みを見つけ出すために広く使われていますが、現代的なANN手法のスケーリング特性の分析ではグリッドベースのアプローチが見落とされてきました。本研究は、マルチプローブグリッドアルゴリズムの性能をデータセットサイズNと次元数dの観点から体系的に特徴づけています。 実験を通じて、GloVe埋め込みファミリーにおいて従来報告されていなかったd方向のスケーリング交差現象を発見しました。この現象では、マルチプローブグリッド検索が次元スケーリング指数をほぼ一定に保つ一方で、グラフベース、ツリーベース、分割ベースの他の手法ではスループットが低下することが明らかになりました。グリッドベース手法の利点は、Nに対する準線形のクエリスケーリングと、競合するANN手法と比較してインデックス作成コストが低いという点にあります。 特筆すべきは、この研究結果がトランスフォーマーアーキテクチャの効率化分析にも応用可能であることです。近年の研究において、自己注意メカニズム（self-attention）がANN操作として形式化されており、ANNアルゴリズムのNおよびdスケーリング特性が、効率的なトランスフォーマー設計のコスト分析を導くことが期待されています。本研究は、インデックス作成コストと次元方向の堅牢性が性能を左右する高次元設定またはリビルド頻度の高い環境において、グリッドベース手法が競争力を持つ可能性を示唆しています。