ベストビンファーストは、超高次元空間における最近傍探索問題の近似解を効率的に見つけるために設計された探索アルゴリズムです。このアルゴリズムは、高次元空間のインデックス作成を可能にするkd木探索アルゴリズムの派生に基づいています。ベストビンファーストは、大部分のクエリに対して最近傍を返し、そうでない場合は非常に近い近傍を返す近似アルゴリズムです。[1]
kdツリーとの違い
- ビンは、クエリ点からの距離が小さい順に検索されます。ビンまでの距離は、その境界上の任意の点からの最小距離として定義されます。これは、優先度キューによって実装されています。[2]
- 最も近い候補を一定数検索して停止します。
- 通常は 2 桁の速度向上が実現します。
参考文献
- ^ Beis, J.; Lowe, DG (1997).高次元空間における近似最近傍探索を用いた形状インデックス作成．コンピュータビジョンとパターン認識に関する会議．プエルトリコ．pp. 1000– 1006．CiteSeerX 10.1.1.23.9493 ．
- ^ 高次元空間における近似最近傍探索を用いた形状インデックス作成、pp. 4-5
