Range reporting とは

計算幾何学およびデータベース理論では、範囲報告クエリはクエリに合致する点のリストを求める。クエリは、ジオメトリシェイプで指定されることが多く、一致する必要があるすべてのポイントを含み、範囲と呼ばれます。範囲レポートは、範囲内のポイントに関する他の種類の集計情報を返す範囲検索の特殊なケースです。
範囲報告クエリは、クエリに効率的に応答できる点の集合からデータ構造を構築することによって、しばしば処理されます。データセットのサイズnの関数として測定された範囲報告クエリの最悪の出力サイズはそれ自体である可能性があるので、範囲報告データ構造に関する多くの研究では、出力時間に敏感なアルゴリズムが調査され、クエリ時間が分析されるnと報告されたポイントの数(しばしばkと表される)の両方の点で
たとえば、クエリ範囲が区間である1次元(数値)データの場合、範囲レポートクエリはソートされた配列にデータを格納することで処理できます。この構造では、バイナリ検索を使用してクエリ間隔の開始点に最も近い点を見つけ出し、その点から配列をスキャンして、その区間のすべての点をリストすることができます。このデータ構造を格納すると、O(n)(線形)空間が使用され、クエリごとに時刻O(log n + k)のクエリが処理されます。