時間属性を持つ空間データ管理方式の研究

点击翻译按钮获取中文摘要

近年、空間データを対象としたデータ構造によりデータの存続期間を含めた情報(以下、時空間データと呼ぶ)を管理するためのデータ管理手法が提案されている。特に、時間と空間の両方の区間を指定したデータ検索が可能なデータ管理として木構造を応用した方式がいくつか提案されている。これらは、その方式により以下の3種類に分類できる。(1)最新のデータだけでなく、過去のある時刻でのデータセットに対し、データ構造を作成し、保存しておく。すなわち、重要と考えられる時刻のデータセットに対応するデータ構造をすべて保存しておく方法である。(2)空間位置によりデータ分類を行い、時間属性はキ-属性としない。すなわち、時刻t=0以降のすべてのデータを単一の空間データ構造で管理し、空間検索により求まった結果のデータに対して、時間属性による選択処理を行う。(3)データの更新によるデータ構造の変化の差分を保持することにより、過去の状態へのアクセスを可能にする。本研究で提案したデータ構造は、基本的には(3)の差分を保持する方式である。(3)に属する方式として、Driscollらは、1次元のデータを対象としてデータ構造を提案しており、筆者らも、これまでに、その方式の多次元2分木構造への拡張方式を提案した。しかし、これらの方式では、木構造の平衡化が困難であり、データの分布が変化するような環境においては、管理・検索効率が悪化する場合がある。そこで、多次元完全平衡木であるMD木に(3)のコンセプトを適用する。すなわち、木構造の変化を保存することにより、各時刻におけるデータの管理とアクセスを可能にする。しかも、どの時点においては、木は完全にバランスしており、さらに、MD木の良好な性質であるメモリ効率が66.6%以上という性質も保持している。データの時系列的な変化を保存するために必要な記憶容量は、最新の状態のみを保持する構造に要するメモリ量をC(N)とした場合、k・C(N)(kは定数で、k≦5/2、Nはデータ総数。)であるという性質をもつ。本データ構造を、Persistent MD-tree(以下、PMD木と略す。)と呼ぶ。PMD木は、時空間データに対する完全平衡木による管理構造である。現在、理論的な考察を終え、種々のデータにより、性能変化についての実験の準備を進めている。