空間インデックス

空間インデックス（くうかんインデックス、英: spatial index）は、空間データベース（オブジェクト群の空間上の位置などの情報を格納するデータベース）での空間クエリの最適化に使われる。空間データベース以外のデータベースで使うインデックスでは、2点間の距離や複数の地点が問題のエリアにあるかといったクエリに効率的に対応できない。

主な手法

主な空間インデックス手法としては、次のようなものがある。

• グリッド
• Z階数曲線
• 四分木
• 八分木
• UB-tree
• R木: 空間データのインデックスに最適なデータ構造。最小外接矩形 (MBR) を使ってオブジェクト（図形、直線、点など）をグループ化する。オブジェクトを追加する場合、サイズの増大が最小となるMBRに追加する。
• kd木

グリッド

グリッド (grid) は、多様体や2次元表面を一連の小さな形状（セル）で充填し、セル単位に識別子を付け、インデックスに利用する。グリッドの形状には様々なものがあり、矩形、三角形、メッシュ、六角形、ひし形などのセルがある。地球全体の表面を覆うようなグリッドはグローバルグリッド (global grid) と呼ぶ。メッシュと呼ぶこともある。

種類

正方形または矩形のグリッドは、直交座標（緯度と経度）との変換が容易であるため、よく使われる。グリッドは経線や緯線に沿って配置されるとは限らない。例えば、地域メッシュ、マースデンスクエア、World Meteorological Organization squares、c-squaresなどは緯線と経線に沿っているが、UTMや各国のグリッド（例えば 平面直角座標系やBritish national grid reference system）はそうではない。一般にこれらのグリッドは2種類に分類できる。1つは経線と緯線に沿って分割するもの（等角）で、各領域の面積は等しくない（高緯度ほど面積が小さくなる）。もう1つは面積が一定になるようにするもので（等積）、一辺の長さが等しいが、緯度や経度の変化は等しくない。

最も有名な三角形グリッドは、1980年代初期に Geoffrey Dutton が開発した "Quaternary Triangular Mesh" (QTM) である。1999年、これに基づいた "A Hierarchical Coordinate System for Geoprocessing and Cartography" という論文が発表された。マイクロソフトのエンカルタにある回転する地球儀はこの成果に基づいている。

それ以外の形状のグリッドについては Sahr et al. (2003) の論文が詳しい。

一般に、三角形や六角形のグリッドは極付近も連続的にカバーし、なるべく等面積になるようにするために生み出された。矩形グリッドでは極付近が常に問題になる。

グリッドによる空間インデックス

グリッドベースの空間インデックスは、まずオブジェクトを適切な位置に置き、そのオブジェクトの識別子と対応するグリッドセルの識別子を結びつけたインデックスを生成し、高速アクセスを可能にする。これは「空間駆動型」またはデータ独立型手法の例だが、逆の「データ駆動型」またはデータ依存型手法は Rigaux et al. (2002) で論じられている。グリッドベースの空間インデックスの利点は、インデックスの構造を先に作成でき、データはそのインデックス構造を変化させることなく後から随時追加できる点である。実際、様々な種類のデータに共通のグリッドを使ってインデックスを付けていた場合、それらインデックスは様々なソースから集めてマージ可能である。一方、データ駆動型構造のR木などは、データ量と検索速度は効率的だが既存のデータとインデックス構造が密接に結びついていることが多い。

このような空間インデックスはデジタルデータに限ったものではない。例えば、地図帳の地名索引はページ番号とそのページの地図内の矩形グリッド番号で示される。これも空間インデックスの一例である。

関連項目

• 地域メッシュ
• ジオコーディング

参考文献

• Indexing the Sky - Clive Page - Grid indexes for astronomy