データ構造における長方形データの表現手法

長方形データとは

多変量の横断的データ(時系列データや反復測定データではないもの)は、一般に「長方形データ」として表現されます。これは、各列が変数(特徴量)を、各行がケースまたはレコードを表す形式のデータです。

1. 点ベースのデータ構造による表現

最初の手法は、長方形データを高次元の点データへマッピングし、グリッドファイル、PR四分木、点四分木、k-d木といった点ベースのデータ構造を利用する方法です。

長方形を四次元の点へ変換する技法には複数の方式があります。例えば、対角にある2つの頂点のx座標・y座標を用いる方法や、1つの頂点の座標と幅・高さを組み合わせる方法などが挙げられます。

ただし、この点ベース表現の欠点は、データの持つ局所性(locality)を十分に活かせないため、記憶効率および空間操作の効率の両面で不利になる点にあります。

2. 線ベースのデータ構造による表現

2番目の手法は、長方形を構成する線分に着目し、PM四分木やPMR四分木などの線ベースのデータ構造によって表現する方法です。

このアプローチの問題点は、個々の線分に対して指定された空間操作が操作の条件を満たさない場合であっても、それらの線分が構成する長方形自体は条件を満たすという不整合が生じうることです。

3. 面積ベースのデータ構造による表現

3番目の手法は、長方形が占有する領域そのものに基づく表現です。MX-CIF四分木やR木(R-Tree)などの手法では、最小外接矩形(minimum bounding box)の階層的なグループ化によって長方形データを組織化します。

MX-CIF四分木では、空間ベースの四分木分割を実装しており、各長方形はそれを囲む最小の四分木ブロックに関連付けられます。一方、R木では、長方形データは階層的にネストされた最小外接矩形へと分割されます。

ただし、R木の欠点は、データの局所性が考慮されていないことにあります。