統計情報はどのようにクエリ回答に役立つのか？STINGの仕組みと特徴を解説

統計パラメータを用いたクエリ応答の基本的な流れ

統計パラメータは、トップダウン型のグリッドベースアプローチにおいて、以下のような手順で活用されます。まず、クエリ応答処理を開始する階層構造内のレイヤー（層）を決定します。

この層には通常、少数のセルのみが含まれています。現在の層にある各セルについて、与えられたクエリに対するそのセルの関連性を反映した信頼区間（確率の推定範囲）を計算します。

上位レベルのセルの統計パラメータは、下位レベルのセルのパラメータから容易に算出できます。これらのパラメータには、属性に依存しないパラメータである「カウント（count）」、属性に依存するパラメータである「平均（mean）」「標準偏差（stdev）」「最小値（min）」「最大値（max）」、さらにセル内の属性値が従う分布の種類（正規分布・一様分布・指数分布、あるいは分布が特定できない場合は「なし」）が含まれます。

無関係なセルは以降の検討対象から除外されます。続く下位レベルの処理では、残った関連セルのみが検査されます。この工程は最下層に到達するまで繰り返され、クエリの条件が満たされた時点で、該当する関連セルの領域が結果として返されます。

STINGの主な利点

• クエリに依存しない計算： グリッドベースの計算はクエリ非依存です。各セルに格納された統計データは、クエリとは独立にグリッドセル内データの要約情報を定義しているためです。

• 並列処理と増分更新への対応： グリッド構造は並列処理やインクリメンタル（増分）リフレッシュをサポートしており、大規模データにも柔軟に対応できます。

• 高い処理効率： STINGはデータベースを一度走査するだけでセルの数値パラメータを算出できるため、クラスタ生成の時間計算量はO(n)です（nはオブジェクトの総数）。

• 高速なクエリ処理： 階層構造を構築した後のクエリ処理時間はO(g)です（gは最下位レベルのグリッドセルの総数）。通常、gはnよりも小さい値になります。

留意すべき課題

• 粒度への依存： STINGはマルチ解像度方式によるクラスタ分析を行うため、その品質はグリッド構造の最下層の粒度に左右されます。粒度を細かくすると処理コストが大幅に増加し、逆に最下層が粗すぎるとクラスタ分析の品質が低下する可能性があります。

• 空間的関係が考慮されない： 親セルを構築する際、子セルとその隣接セルとの空間的な関係が考慮されません。その結果、生成されるクラスタの形状は軸に平行（水平・垂直）となり、斜めの境界は検出できません。処理速度は速いものの、クラスタの品質や確からしさが損なわれる場合があります。