最近傍検索

地理情報システムで頻繁に遭遇するクエリタイプは、空間内の特定の点に最も近いk個の隣接オブジェクトを見つけることです。このようなクエリを処理するには、位置情報や範囲クエリとは大幅に異なる検索アルゴリズムが必要です。本論文では、特定の点に最も近い隣接オブジェクトを見つけるための効率的な分枝限界Rツリー走査アルゴリズムを提示し、その後、k個の最も近い隣接オブジェクトを見つけるように一般化します。また、楽観的および悲観的な検索順序戦略およびプルーニングのためのメトリクスについても議論します。最後に、私たちのアルゴリズムの実装を使用して得られた複数の実験の結果を示し、メトリクスの挙動とアルゴリズムのスケーラビリティを検討します。