(57)【要約】【課題】本発明は、データベースに格納される移動軌跡データを検索対象として、直観的な記述方法に従って制約条件を与えて移動軌跡データの検索を行うことができるようにするとともに、形状が似ている移動軌跡データの検索を行うことができるようにすることを目的とする。【解決手段】複雑な形状を持つ線分である移動規制データの検索を可能にするために、検索対象となる移動軌跡データの各移動軌跡点の属する領域の情報を分割された区画を使って記録するとともに、その移動軌跡データの通過する分割区画の通過順序の情報を記録するインデックスを生成する。そして、線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件が与えられると、その検索条件で指定される領域に一致する分割区画を特定し、インデックスを用いて、その検索条件を充足する移動軌跡データを検索する。【選択図】　　　　　図１
2004118293.tif 000002
【特許請求の範囲】
【請求項１】
データベースに格納される移動軌跡データの検索に用いられて、移動軌跡データの属する領域の情報と通過順序の情報とについて記録するインデックスを生成する移動軌跡データ検索用インデックス生成装置であって、
移動軌跡データの存在する空間に対応付けられる区画を分割することで、移動軌跡点の属する領域の登録先となる分割区画を生成する手段と、
移動軌跡点が与えられる場合に、その移動軌跡点の属する上記分割区画を特定して、その特定した分割区画に対応付けて設けられる配列の末尾に、その移動軌跡点に関する情報へのポインタを登録する手段と、
上記特定した分割区画と、移動軌跡データの通過する上記分割区画の識別情報を記録するリンクリストの末尾の分割区画とが異なる場合に、該リンクリストの末尾に、その特定した分割区画の識別情報を登録する手段とを備えることを、
特徴とする移動軌跡データ検索用インデックス生成装置。
【請求項２】
請求項１記載の移動軌跡データ検索用インデックス生成装置において、
上記配列の長さが規定以上となる場合に、その配列を持つ上記分割領域を分割することで階層的な構造を持つ分割区画を生成するとともに、それに応じて上記リンクリストを生成しなおす手段を備えることを、
特徴とする移動軌跡データ検索用インデックス生成装置。
【請求項３】
データベースに格納される移動軌跡データを検索する移動軌跡データ検索装置であって、
検索対象となる移動軌跡データの各移動軌跡点の属する領域の情報を分割された区画を使って記録するとともに、その移動軌跡データの通過する該分割区画の通過順序の情報を記録するインデックスを保持する手段と、
線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件を入力する手段と、
上記インデックスを用いて、上記検索条件を充足する移動軌跡データを検索する手段とを備えることを、
特徴とする移動軌跡データ検索装置。
【請求項４】
請求項３記載の移動軌跡データ検索装置において、
上記分割区画が階層的に構成される場合にあって、上記検索条件で指定される領域が上記分割区画に一致しない場合には、その領域を含む最小の上記分割区画を特定する手段を備え、
上記検索する手段は、上記インデックスを用いて、上記最小の分割区画で指定領域が置き換えられた上記検索条件を充足する移動軌跡データを検索して、その中から上記検索条件を充足する移動軌跡データを検索することを、
特徴とする移動軌跡データ検索装置。
【請求項５】
請求項３又は４記載の移動軌跡データ検索装置において、
上記検索する手段は、上記検索条件で時刻条件が指定される場合には、上記検索条件を充足するものとして検索した移動軌跡データの中から、その時刻条件を充足するものを検索することを、
特徴とする移動軌跡データ検索装置。
【請求項６】
データベースに格納される移動軌跡データの検索に用いられて、移動軌跡データの属する領域の情報と通過順序の情報とについて記録するインデックスを生成してメモリ域に保持させる移動軌跡データ検索用インデックス生成方法であって、
移動軌跡データの存在する空間に対応付けられる区画を分割することで、移動軌跡点の属する領域の登録先となる分割区画を生成する過程と、
移動軌跡点が与えられる場合に、その移動軌跡点の属する上記分割区画を特定して、その特定した分割区画に対応付けて設けられる配列の末尾に、その移動軌跡点に関する情報へのポインタを登録する過程と、
上記特定した分割区画と、移動軌跡データの通過する上記分割区画の識別情報を記録するリンクリストの末尾の分割区画とが異なる場合に、該リンクリストの末尾に、その特定した分割区画の識別情報を登録する過程とを備えることを、
特徴とする移動軌跡データ検索用インデックス生成方法。
【請求項７】
請求項６記載の移動軌跡データ検索用インデックス生成方法において、
上記配列の長さが規定以上となる場合に、その配列を持つ上記分割領域を分割することで階層的な構造を持つ分割区画を生成するとともに、それに応じて上記リンクリストを生成しなおす過程を備えることを、
特徴とする移動軌跡データ検索用インデックス生成方法。
【請求項８】
データベースに格納される移動軌跡データを検索する移動軌跡データ検索方法であって、
線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件を入力する過程と、
メモリ域に保持されて、検索対象となる移動軌跡データの各移動軌跡点の属する領域の情報を分割された区画を使って記録するとともに、その移動軌跡データの通過する該分割区画の通過順序の情報を記録するインデックスを用いて、上記検索条件を充足する移動軌跡データを検索する過程とを備えることを、
特徴とする移動軌跡データ検索方法。
【請求項９】
請求項８記載の移動軌跡データ検索方法において、
上記分割区画が階層的に構成される場合にあって、上記検索条件で指定される領域が上記分割区画に一致しない場合には、その領域を含む最小の上記分割区画を特定する過程を備え、
上記検索する過程では、上記インデックスを用いて、上記最小の分割区画で指定領域が置き換えられた上記検索条件を充足する移動軌跡データを検索して、その中から上記検索条件を充足する移動軌跡データを検索することを、
特徴とする移動軌跡データ検索方法。
【請求項１０】
請求項８又は９記載の移動軌跡データ検索方法において、
上記検索する過程では、上記検索条件で時刻条件が指定される場合には、上記検索条件を充足するものとして検索した移動軌跡データの中から、その時刻条件を充足するものを検索することを、
特徴とする移動軌跡データ検索方法。
【請求項１１】
データベースに格納される移動軌跡データの検索に用いられて、移動軌跡データの属する領域の情報と通過順序の情報とについて記録するインデックスを生成する移動軌跡データ検索用インデックス生成装置の実現に用いられる移動軌跡データ検索用インデックス生成プログラムであって、
移動軌跡データの存在する空間に対応付けられる区画を分割することで、移動軌跡点の属する領域の登録先となる分割区画を生成する手段と、
移動軌跡点が与えられる場合に、その移動軌跡点の属する上記分割区画を特定して、その特定した分割区画に対応付けて設けられる配列の末尾に、その移動軌跡点に関する情報へのポインタを登録する手段と、
上記特定した分割区画と、移動軌跡データの通過する上記分割区画の識別情報を記録するリンクリストの末尾の分割区画とが異なる場合に、該リンクリストの末尾に、その特定した分割区画の識別情報を登録する手段として、コンピュータを機能させるための移動軌跡データ検索用インデックス生成プログラム。
【請求項１２】
請求項１１記載の移動軌跡データ検索用インデックス生成プログラムにおいて、
さらに、上記配列の長さが規定以上となる場合に、その配列を持つ上記分割領域を分割することで階層的な構造を持つ分割区画を生成するとともに、それに応じて上記リンクリストを生成しなおす手段として、コンピュータを機能させるためのプログラムを含むことを、
特徴とする移動軌跡データ検索用インデックス生成プログラム。
【請求項１３】
データベースに格納される移動軌跡データを検索する移動軌跡データ検索装置の実現に用いられる移動軌跡データ検索プログラムであって、
線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件を入力する手段と、
検索対象となる移動軌跡データの各移動軌跡点の属する領域の情報を分割された区画を使って記録するとともに、その移動軌跡データの通過する該分割区画の通過順序の情報を記録するインデックスを用いて、上記検索条件を充足する移動軌跡データを検索する手段として、コンピュータを機能させるための移動軌跡データ検索プログラム。
【請求項１４】
請求項１３記載の移動軌跡データ検索プログラムにおいて、
さらに、上記分割区画が階層的に構成される場合にあって、上記検索条件で指定される領域が上記分割区画に一致しない場合には、その領域を含む最小の上記分割区画を特定する手段として、コンピュータを機能させるためのプログラムを含み、
かつ、上記検索する手段は、上記インデックスを用いて、上記最小の分割区画で指定領域が置き換えられた上記検索条件を充足する移動軌跡データを検索して、その中から上記検索条件を充足する移動軌跡データを検索することを、
特徴とする移動軌跡データ検索プログラム。
【請求項１５】
請求項１３又は１４記載の移動軌跡データ検索プログラムにおいて、
上記検索する手段は、上記検索条件で時刻条件が指定される場合には、上記検索条件を充足するものとして検索した移動軌跡データの中から、その時刻条件を充足するものを検索することを、
特徴とする移動軌跡データ検索プログラム。
【請求項１６】
請求項１１又は１２記載の移動軌跡データ検索用インデックス生成プログラムを記録した記録媒体。
【請求項１７】
請求項１３ないし１５のいずれか１項に記載の移動軌跡データ検索プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベースに格納される移動軌跡データの検索に用いられるインデックスを生成する移動軌跡データ検索用インデックス生成装置及びその方法と、そのインデックスを用いて、データベースに格納される移動軌跡データの中から検索条件を充足するものを検索する移動軌跡データ検索装置及びその方法と、その移動軌跡データ検索用インデックス生成装置の実現に用いられる移動軌跡データ検索用インデックス生成プログラム及びそのプログラムを記録した記録媒体と、その移動軌跡データ検索装置の実現に用いられる移動軌跡データ検索プログラム及びそのプログラムを記録した記録媒体とに関する。
【０００２】
ナビゲーションシステムや、人物の位置を管理するシステムや、人物の移動軌跡から嗜好情報を読み取るシステムなどといったような様々なシステムで、移動物体の移動軌跡データを検索することが要求されている。その他にも、様々なシステムで、時間軸に沿って値の変化するデータ（広義の移動軌跡データ）を検索することが要求されている。
【０００３】
これから、このような移動軌跡データの検索を実現する技術を構築していく必要がある。
【０００４】
【従来の技術】
本発明に関連する先行技術として、時系列データベースシステム、時空間データベースシステム、ナビゲーションシステムがある。
【０００５】
〔１〕時系列データベースシステム（例えば、特許文献１参照）
株価や為替に類する経済的指標値、降水量や気温、湿度に類する気候に関する測定値、人口や就業率、出生率に類する社会的指標値といったような、時間軸に沿って変化する可能性のある値を、一定周期あるいは不定期に計測したデータを一般に時系列データという。
【０００６】
時系列データから周期性、規則性を発見し、未来の値の変化を予測する技術の開発がこれまでに行われている。この技術開発の中で、時系列データを蓄積し、条件に合致する時系列データを検索する機能を持つ時系列データベースシステムが開発されている。
【０００７】
従来の時系列データベースシステムは、時間変化に伴うデータの値の増減変化の特徴を検索条件として与えて、その検索条件に合致するデータを検索する機能を有する。
【０００８】
移動するユーザについて記述する移動軌跡データは、各時刻に対応するユーザの座標情報を記録したものであるから、時系列データの一種である。
【０００９】
しかし、移動軌跡データは空間上の線分としての性質を持つことから、時間軸に対する値の増減変化を指定する検索方法のみでは、検索能力が十分ではない。幾何学的な線分の形状の変化や、線分周辺の別の図形との関係の変化についても条件として与え、その条件に合致するデータを取得する機能が必要である。
【００１０】
しかしながら、既存の時系列データベースシステムは、この機能を有していない。
【００１１】
〔２〕時空間データベースシステム（例えば、特許文献２参照）
空間上の図形を、図形間の関係や図形の形状を条件として与えることで検索することができる機能を有するデータベースシステムとして、空間データベースシステムと時空間データベースシステムとがある。これらのデータベースシステムは、ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ）の基盤技術としても用いられている。
【００１２】
蓄積するデータとしては、標高や河川や道路や建築物などに類する静的な地理学的なデータと、人口分布や職業分布や植生や降雨量などに類する場所に依存した動的に変動するデータとがある。
【００１３】
静的なデータと動的なデータとを組み合わせて分析することで、特定の地域にのみ見られる特有のデータパターンを発見したり、複数の分布図間に存在する図形的な関連性を発見することが可能である。
【００１４】
例えば、植生分布、降雨量、崖崩れの発生区域の３つの分布図について、図形上での比較を行うことで、崖崩れが頻出する地点の近傍では年間降雨量が平均より多く、なおかつ植生分布図では樹木のない区域にある、などといった関係を発見するケースがこれにあたる。
【００１５】
従来の時空間データベースシステムでは、図形として面積あるいは体積を持つ図形間の関係を計算することができる。
【００１６】
しかし、面積あるいは体積を持つ図形間の関係計算は、一般に極めて膨大なコストを要する。このため、時空間データベースシステムで扱われるデータは、関係の演算に時間を要しても影響がない程度にデータの更新が少ない、いわゆる静的なデータである必要があった。
【００１７】
これに対して、移動軌跡データはセンサ情報の一種であり、リアルタイムにデータが追加される性質を持つ。したがって、移動軌跡データベースは、動的に増加するデータに対しても十分に高速にデータを検索できる能力が必要である。
【００１８】
しかしながら、既存の時空間データベースシステムは、この機能を有していない。
【００１９】
〔３〕ナビゲーションシステム（例えば、特許文献３参照）
地図上の複数の点を指定し、指定した順序で通過する経路を検索できるシステムとして、カーナビゲーションシステム、パーソナルナビゲーションシステムがある。
【００２０】
ナビゲーションシステムではデータとして、道路の形状、長さ、接続情報を保有し、カーナビゲーションシステムではさらに渋滞、工事、通行規制に関する情報を保有しており、複数のデータを複合的に用いてユーザの条件を満たす最適な経路を探す。
【００２１】
しかしながら、ナビゲーションシステムの検索対象は二点間を結ぶ経路としての静的な道路データであり、形状が不定でリアルタイムにデータが追加される移動軌跡データを検索対象とすることはできない。
【００２２】
【特許文献１】
特開平６−９６２３４号公報
【特許文献２】
特開平７−９３３３８号公報
【特許文献３】
特開平９−１７８４９９号公報
【非特許文献１】
Ｍ．Ｅｇｅｎｈｏｆｅｒ，Ｅ．Ｃｌｅｍｅｎｔｉｎｉ，ａｎｄ　Ｐ．ｄｉ　Ｆｅｌｉｃｅ：　Ｔｏｐｏｌｏｇｉｃａｌ　Ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　Ｒｅｇｉｏｎｓ　ｗｉｔｈ　Ｈｏｌｅｓ，Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｇｅｏｇｒａｐｈｉｃａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，Ｖｏｌ．８，Ｎｏ．２，ｐｐ．１２９−１４２（１９９４）．
【００２３】
【発明が解決しようとする課題】
以上説明したように、従来の技術では、次の２つの要求を満たすことができない。
【００２４】
すなわち、向きのある複雑な形状を持つ線分である移動軌跡データに対して、直観的な記述方法に従って空間的および時間的な制約条件を与えて検索を行うことができない。
【００２５】
そして、サンプルとして与えた移動軌跡データに空間上での形状が似ている移動軌跡データをデータベースから検索することができない。
【００２６】
本発明はかかる事情に鑑みてなされたものであって、データベースに格納される複雑な形状を持つ線分である移動軌跡データを検索対象として、直観的な記述方法に従って制約条件を与えて移動軌跡データの検索を行うことができるようにするとともに、形状が似ている移動軌跡データの検索を行うことができるようにする新たな移動軌跡データ検索技術の提供を目的とする。
【００２７】
【課題を解決するための手段】
この目的を達成するために、本発明では、（１）データベースに格納される移動軌跡データの検索に用いられるインデックスを生成してメモリ域（半導体メモリやハードディスクなどのようなメモリ域）に保持させる移動軌跡データ検索用インデックス生成装置と、（２）そのメモリ域に保持されるインデックスを用いて、データベースに格納される移動軌跡データの中から検索条件を充足するものを検索する移動軌跡データ検索装置とを用意する。
【００２８】
〔１〕本発明の移動軌跡データ検索用インデックス生成装置の構成
本発明の移動軌跡データ検索用インデックス生成装置は、検索対象となる移動軌跡データの属する領域の情報と通過順序の情報とについて記録するインデックスを生成する処理を行うものであって、▲１▼移動軌跡データの存在する空間に対応付けられる区画を分割することで、移動軌跡点の属する領域の登録先となる分割区画を生成する手段と、▲２▼移動軌跡点が与えられる場合に、その移動軌跡点の属する分割区画を特定して、その特定した分割区画に対応付けて設けられる配列の末尾に、その移動軌跡点に関する情報へのポインタを登録する手段と、▲３▼特定した分割区画と、移動軌跡データの通過する分割区画の識別情報を記録するリンクリストの末尾の分割区画とが異なる場合に、リンクリストの末尾に、その特定した分割区画の識別情報を登録する手段と、▲４▼分割区画に対応付けて設けられる配列の長さが規定以上となる場合に、その配列を持つ分割領域を分割することで階層的な構造を持つ分割区画を生成するとともに、それに応じてリンクリストを生成しなおす手段とを備えるように構成する。
【００２９】
以上の各処理手段はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどの記録媒体に記録して提供することができる。
【００３０】
〔２〕本発明の移動軌跡データ検索装置の構成
本発明の移動軌跡データ検索装置は、データベースに格納される移動軌跡データを検索する処理を行うものであって、▲１▼検索対象となる移動軌跡データの各移動軌跡点の属する領域の情報を分割された区画を使って記録するとともに、その移動軌跡データの通過する分割区画の通過順序の情報を記録するインデックスを保持する手段と、▲２▼線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件を入力する手段と、▲３▼インデックスを用いて、検索条件を充足する移動軌跡データを検索する手段と、▲４▼分割区画が階層的に構成される場合にあって、検索条件で指定される領域が分割区画に一致しない場合には、その領域を含む最小の分割区画を特定する手段とを備えるように構成する。
【００３１】
このように構成されるときにあって、検索する手段は、分割区画が階層的に構成される場合にあって、検索条件で指定される領域が分割区画に一致しない場合には、先ず最初に、特定された最小の分割区画で指定領域が置き換えられた検索条件を充足する移動軌跡データを検索対象として、インデックスを用いて検索を行い、続いて、その中から本来の検索条件を充足する移動軌跡データを検索するように処理する。
【００３２】
そして、検索する手段は、検索条件で時刻条件が指定される場合には、検索条件を充足するものとして検索した移動軌跡データの中から、その時刻条件を充足するものを検索するように処理する。
【００３３】
以上の各処理手段（但し、保持する手段を除く）についてはコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどの記録媒体に記録して提供することができる。
【００３４】
〔３〕本発明により実現される移動軌跡データの検索処理
このように構成される本発明では、先ず最初に、本発明の移動軌跡データ検索用インデックス生成装置が動作して、移動軌跡データの存在する空間に対応付けられる区画を分割することで、移動軌跡点の属する領域の登録先となる分割区画を生成する。
【００３５】
続いて、移動軌跡点が与えられると、その移動軌跡点の属する分割区画を特定して、その特定した分割区画に対応付けて設けられる配列の末尾に、その移動軌跡点に関する情報へのポインタを登録し、さらに、その特定した分割区画と、リンクリスト（移動軌跡データの通過した分割区画の識別情報の時系列データが記録されている）の末尾に記録されている分割区画とが異なる場合には、リンクリストの末尾に、その特定した分割区画の識別情報を登録する。
【００３６】
そして、分割区画に対応付けて設けられる配列の長さが規定以上となる場合には、その配列を持つ分割領域を分割することで階層的な構造を持つ分割区画を生成するとともに、それに応じてリンクリストを生成しなおす。
【００３７】
このようにして、本発明の移動軌跡データ検索用インデックス生成装置の処理により、移動軌跡データが通過する分割区画とその通過順序とについて記述するインデックスが生成されることになる。
【００３８】
このインデックスの生成を受けて、移動軌跡データの検索要求が発行されると、本発明の移動軌跡データ検索装置が動作して、線分と領域との幾何学的な関係について記述する検索言語で記述された検索条件が与えられと、それを入力する。
【００３９】
続いて、入力した検索条件で指定される領域に一致する分割区画を特定し、その一致する分割区画が存在しない場合には、入力した検索条件で指定される領域を含む最小の分割区画を特定する。
【００４０】
そして、入力した検索条件で指定される領域に一致する分割区画を特定できた場合には、インデックスを用いた検索が可能であるので、インデックスを用いて、検索条件を充足する移動軌跡データを検索する。
【００４１】
このとき、検索条件で時刻条件が指定される場合には、さらに、その時刻条件を充足するものを検索することで、最終的な検索結果となる移動軌跡データを検索する。
【００４２】
一方、入力した検索条件で指定される領域に一致する分割区画を特定できない場合には、インデックスを用いた検索が不可能であるので、検索条件で指定される領域をその領域を含む最小の分割区画で置き換えることでインデックスの使用を可能にして、インデックスを用いて、その置き換えた検索条件を充足する移動軌跡データの検索を行い、その中から本来の検索条件を充足する移動軌跡データを検索する。
【００４３】
このとき、検索条件で時刻条件が指定される場合には、さらに、その時刻条件を充足するものを検索することで、最終的な検索結果となる移動軌跡データを検索する。
【００４４】
このようにして、本発明では、線分と領域との幾何学的な関係について記述する検索言語で指定される検索条件を充足する移動軌跡データを検索できるようにするためのインデックスを生成して、それを用いて検索条件を充足する移動軌跡データを検索することから、線分と領域との幾何学的な関係について記述する検索言語を使って検索条件を指定できるようになるとともに、向きのある複雑な形状を持つ線分である移動軌跡データを検索できるようになる。
【００４５】
これにより、本発明によれば、直観的な記述方法に従って制約条件を与えて移動軌跡データの検索を行うことができるようになるとともに、形状が似ている移動軌跡データの検索を行うことができるようになる。
【００４６】
なお、検索の結果として得られる答えに含まれるものは、データベースに格納されている（１本の）移動軌跡データの全体であったり、その一部分である。場合によっては、データベース中では１本の移動軌跡データであっても、答えとしては、その移動軌跡データの複数の部分が切り出されて答えとされる場合もある。
【００４７】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００４８】
図１に、本発明を具備するデータベースシステム１の全体構成を図示する。
【００４９】
この図に示すように、本発明のデータベースシステム１は、入力部１０と、データ管理部１１と、検索部１２と、蓄積部１３とから構成される。
【００５０】
入力部１０は、外部から受け取ったテキスト情報が移動軌跡データであるのか問い合わせ記述であるのかを判断して、移動軌跡データであった場合には、データを整形してデータ管理部１１へ送信し、問い合わせ記述であった場合には、問い合わせ内容を解析して検索部１２へその解析結果を送信する。
【００５１】
データ管理部１１は、入力部１０から受け取ったデータに対してインデックスを作成する。インデックスはデータ管理部１１で保持され、移動軌跡データは蓄積部１３に送信される。
【００５２】
蓄積部１３は、外部から受信した移動軌跡データをハードディスク等の物理記憶デバイスに記録し、外部から要求のあった移動軌跡データを物理記憶デバイスから読み出して要求元に送信し、外部から指示された移動軌跡データの削除またはデータの置き換えを行う機能を有する。
【００５３】
検索部１２は、入力部１０から受け取った問い合わせに対し、データ管理部１１に問い合わせてインデックスを利用して問い合わせの条件を満たすデータの候補を選び、次に蓄積部１３から候補となるデータを取得し、その中から実際に条件を満たすデータだけを選んで外部に検索結果として送信する機能を有する。
【００５４】
〔１〕本発明で扱う移動軌跡データ
次に、本発明のデータベースシステム１で扱う移動軌跡データについて述べる。
【００５５】
空間上を移動する物体の移動軌跡を、物体の識別子と時刻と空間上の座標（点データ）との組として記録したものを移動軌跡データと呼ぶ。
【００５６】
移動軌跡データは、一般には連続でない時系列に沿った離散的な点データ列である。移動軌跡データに含まれる点データ列を点データの時刻順に結んだものは、空間上では有限の長さを持ち向きがある線分になる。
【００５７】
図２に、移動軌跡データの一例を図示する。この図に示すように、移動軌跡データの各点は、時刻ｔと、座標（ｘ，ｙ）と、個々の移動軌跡データに対してシステムが割り振る識別子ｕとの組で表される。
【００５８】
〔２〕検索部１２で扱うことのできる条件記述式
次に、検索部１２で扱うことのできる条件記述式について述べる。
【００５９】
空間上の図形を検索する方法として、空間上の別の図形との間の位相幾何学的関係を用いる方法が従来より利用されている。
【００６０】
閉領域（空間内にある境界を持ち、内部に穴のない連続な領域）間の位相幾何学的関係を記述する方法として、領域Ｒの境界∂Ｒと、領域の内部Ｒ°（閉領域のうち境界を含まない開領域）と、領域の外部Ｒ−　（空間内の領域Ｒに含まれない部分）との関係を表す行列式を用いる方法（例えば、非特許文献１参照）がある。
【００６１】
例えば、図３（ａ）に示す関係行列式Ｔ０（Ｒ１，Ｒ２）は、図３（ｂ）のように表される。ここで、“φ”は共通部分が空である（存在しない）ことを意味し、“¬φ”は共通部分があることを意味する。
【００６２】
本発明のデータベースシステム１ではこれを拡張して、空間上のひとつの閉領域Ｒと有向線分Ｌとの関係を、領域の内部Ｒ°／領域の境界∂Ｒ／領域の外部Ｒ−　と、線分の始点∂０　Ｌ／線分の終点∂１　Ｌ／線分の内部Ｌ°（始点と終点以外の線分上の点）との３×３の行列で表し、検索条件に指定できるようにする。
【００６３】
例えば、図４（ａ）に示す関係行列式Ｔ（Ｒ１，Ｌ）は図４（ｂ）のように表される。ここで、“φ”は共通部分が空である（存在しない）ことを意味し、“¬φ”は共通部分があることを意味する。
【００６４】
図５に示すように、二次元空間Ｒ２　では、閉領域Ｒと有向線分Ｌとの関係の可能な組み合わせは２６種類である。図６に、この２６種類の関係行列式を図示する。
【００６５】
しかし、この２６種類の関係は、次のＣＯＮＮＥＣＴ演算を利用すると、基本となる７種類の関係の組み合わせで記述できることになる。
【００６６】
ＣＯＮＮＥＣＴ演算＊は、領域Ｒと二つの有向線分Ｌ，　Ｌ’　があり、「∂１　Ｌ＝∂０　Ｌ’　」という関係があるときに限り、Ｔ（Ｒ１，Ｌ）とＴ（Ｒ１，Ｌ’）との二つの関係の間に定義できて、「Ｔ（Ｒ１，Ｌ）＊Ｔ（Ｒ１，Ｌ’）」は図７に示すように定義される。
【００６７】
図８に、このＣＯＮＮＥＣＴ演算の例を示す。例えば、図中に示す（ａ）と（ｂ）のケースでは、同じ領域Ｒ１　に対して二つの有向線分Ｌ１，Ｌ２　がそれぞれ別の関係を持ち、「∂１　Ｌ１　＝∂０　Ｌ２　」であるときに、「Ｔ（Ｒ１，Ｌ１）＊Ｔ（Ｒ１，Ｌ２）」という演算を計算できる。そして、図中に示す（ｄ）と（ｅ）のケースでも、同じ領域Ｒ１　に対して二つの有向線分Ｌ４，Ｌ５　がそれぞれ別の関係を持ち、「∂１　Ｌ４　＝∂０　Ｌ５　」であるときに、「Ｔ（Ｒ１，Ｌ４）＊Ｔ（Ｒ１，Ｌ５）」という演算を計算できる。
【００６８】
前述したように、図６に示す２６種類の関係行列式は、ＣＯＮＮＥＣＴ演算を利用すると、基本となる７種類の関係の組み合わせで記述できることになる。
【００６９】
図９に、この基本となる７種類の関係を図示する。この基本となる７種類の関係とＣＯＮＮＥＣＴ演算とを用いることで、２６種類すべての関係を表すことができる。
【００７０】
図１０に、その組み合わせの例を示す。図中のＴＩ　〜ＴＸＸＶＩは、図６の各関係を表す行列式に対応する。
【００７１】
このように、閉領域と有向線分との関係は、基本となる７種類の関係行列式とＣＯＮＮＥＣＴ演算とを用いて記述することができるのである。
【００７２】
このようにして、本発明のデータベースシステム１への問い合わせは、次の形式で記述されることになる。
【００７３】
＜Ｌ＞＝Ｑ（Ｒ，Ｅ０　＊Ｅ１　＊　．．．＊Ｅｎ　）
但し、＜Ｌ＞は線分Ｌの集合
この式は、領域Ｒと関係Ｅ０　＊Ｅ１　＊．．．．＊Ｅｎ　を持つ線分Ｌの集合＜Ｌ＞を求める問い合わせである。
【００７４】
複数の領域との関係式は、線分と各領域との関係行列式の列で表すことができる。例えば、二つの領域Ｒ１，Ｒ２　が存在し、Ｒ１　の境界上から出発してＲ２　の境界上に終点があるような関係は、次のように表される。
【００７５】
Ｔ１（Ｒ１，Ｒ２，Ｌ）＝〈Ｔ０（Ｒ１，Ｌ１），　Ｔ０（Ｒ２，Ｌ２）〉＝〈ＥＤ　，　ＥＥ　〉
但し、Ｒ１　°∩Ｒ２　°＝“φ”、Ｌ１　∪Ｌ２　＝Ｌ、∂１　Ｌ１　＝∂０　Ｌ２　とする。
【００７６】
この式は、線分Ｌがまず領域Ｒ１　とＥＤ　の関係を持ち（なおかつ他のすべての領域との間にＥＦ　の関係を持ち）、その直後にＲ２　との間にＥＥ　の関係を持つという関係を表している。
【００７７】
複数の領域に対する関係問い合わせも、領域がひとつの場合と同様にして、次のように記述する。但し、各Ｅｉ　は複数のＥｊ　をＣＯＮＮＥＣＴ演算で結合したものでもよい。
【００７８】
＜Ｌ＞＝Ｑ（（Ｒ１，Ｅ０），（Ｒ２，Ｅ１），　．．．　，（Ｒｎ　，　Ｅｎ　））
この条件式Ｑに加えて、時刻に関する次の条件記述を与えることができる。なお、∂０　Ｌの時刻をｔＳ　、∂１　Ｌの時刻をｔＥ　、移動軌跡データ上の任意の１点の時刻をｔｉ　と表記している。
【００７９】
（イ）独立時間指定Ｐ
Ｑとは無関係に、移動軌跡データの含まれる時区間や時刻を指定する。「ｔＥ　−ｔＳ　＜２．０（分）」や、「８：００ＰＭ＜ｔＥ　＜９：００ＰＭ」や、「１１：００ＡＭ＝ｔｉ　」などという記述がこれにあたる。これらは、例えば、
＜Ｌ＞＝Ｑ∩Ｐ０　∩Ｐ１　．．．
のようにＡＮＤ条件として記述する。
【００８０】
（ロ）従属時間指定Ｓ
Ｑの各関係行列と領域との組に対して時区間や時刻を指定する。例えば、
＜Ｌ＞＝Ｑ（（Ｒ１，Ｅ０，〔ｔＥ　＝６：００ＰＭ〕），（Ｒ２，Ｅ１））
のように記述する。この例は、「線分がＲ１　とＥ０　の関係を持つとき、その部分移動軌跡データの終点の時刻が１６：００ＰＭである。その後、Ｒ２　とＥ１　の関係を持つ」という条件を表している。
【００８１】
〔３〕データ管理部１１でのインデックス生成処理
次に、データ管理部１１により実行されるインデックス生成処理について述べる。
【００８２】
データベースの管理者によって決められた定数Ｈ，Ｗ，ｍ，ｎ，θがあるものとする。また、移動軌跡データの各ポイントはｐ＝（ｕ，ｔ，ｘ，ｙ）（ここで、ｕは軌跡のＩＤ、ｔは時刻、ｘ，ｙはポイントの位置）で表され、各移動軌跡データの各ポイントが１つずつデータベースに追加されるものとする。
【００８３】
ポイントｐがデータベースに追加されるためにデータ管理部１１に送られてきたとき、データ管理部１１は、次の手順（（ｉ）〜（ｖ））でインデックスを作成する。
【００８４】
但し、追加されるｐは、同じＩＤｕを持つポイント群の中で、常に最後尾（ｐの時刻が他のポイント群の中で最後）になっているものとする。
【００８５】
（ｉ）インデックスの頂点τ０　が存在しない場合には、図１１に示すように、頂点τ０　を作成し、ｐの位置（ｘ，ｙ）に対応付けられる位置を中心とした縦Ｈ×ｎ、横Ｗ×ｍのサイズの矩形を生成する。さらに、この矩形を縦ｎ分割、横ｍ分割し、これらの分割された各分割矩形をＲｅｃ（τ０，ｉ，ｊ）で表す。
【００８６】
この分割矩形Ｒｅｃ（τ０，ｉ，ｊ）が移動軌跡データを構成する各ポイントの位置する領域に対応付けられることになる。
【００８７】
ここで、Ｒｅｃ（τ０，０，０）は便宜上もっとも左上の分割矩形を指すものとし、右下の分割矩形をＲｅｃ（τ０，（ｍ−１），（ｎ−１））で表す。また、τ０　はインデックスの頂点が親ノードであることを表している。
【００８８】
（ｉｉ）ｐの座標（ｘ，ｙ）を含む分割矩形Ｒｅｃ（τ０，ｉ，ｊ）を探す。
【００８９】
後述するように、分割矩形Ｒｅｃ（τ０，ｉ，ｊ）に閾値θを超える数のポイントが登録される場合には、検索性能が劣化するのを防止するために、その分割矩形Ｒｅｃ（τ０，ｉ，ｊ）をｎ×ｍの分割形態で分割することになるので、子ノードセットを持つことになる。
【００９０】
これから、探した出した分割矩形が子ノードセットを持つ場合には、子ノードの中からさらに対応する分割矩形Ｒｅｃ（Ｒｅｃ（τ０，ｉ，ｊ），ｉ’　，ｊ’　）を探す。同様にして子ノードを探索していって、子ノードを持たない分割矩形に到達するまで再帰的に探す。最後に見つかった分割矩形をＲとする。
【００９１】
（ｉｉｉ）探索した分割矩形Ｒに対応付けられる配列の末尾にｐを加える。
【００９２】
具体的には、ｐの情報は蓄積部１３に格納することになるので、配列の末尾には、その格納先のアドレスを加えることになる。図１１では、分割矩形Ｒｅｃ（τ０，３，２）に対応付けられた配列の末尾にｐを加える例を示している。
【００９３】
このとき、配列の長さが閾値θ以上となる場合には、後述する（ｉｖ）を実行する。一方、そうでない場合には、ｐについてリンクリスト（移動軌跡データの分割矩形の通過順序を記録するもの）を作成する。
【００９４】
リンクリストの作成手順は次の通り（▲１▼〜▲３▼）である。
【００９５】
▲１▼ｐと同じＩＤｕを持つポイントで、時刻値が直前のポイントｐ’　を探す。もしｐ’　が存在していなければ、リンクリストのトップノードを新たに作成して、ｐが所属する分割矩形Ｒをリンクリストのトップに追加して終了する。
【００９６】
▲２▼ｐ’　が存在する場合、ｐ’　の所属するＲ’　とｐの所属するＲとが「Ｒ＝Ｒ’　」であるならば、同じ分割矩形内での移動であるので何も行わずに終了する。そうでなければ次に進む。
【００９７】
▲３▼リンクリストの末尾にＲを追加する。Ｒに親ノードＲｐ　がある場合には、「Ｒｐ　＝Ｒ’　」かどうかを調べる。「Ｒｐ　＝Ｒ’　」であれば処理を終了する。そうでなければ、Ｒ’　の親ノードＲ’　ｐ　について同様に「Ｒｐ　＝Ｒ’　ｐ　」であるかどうかを調べる。これを再帰的に繰り返し、親ノードがなくなるまで繰り返す。
【００９８】
この▲１▼〜▲３▼の作成手順に従って、最終的には、図１２に示すように、ＩＤｕのポイント列（移動軌跡データ）の先頭から順番に、分割矩形の階層レベル毎にその移動軌跡データが通過した分割矩形を並べて作ったリンクリストと、τ０　をトップノードとした分割矩形の階層関係について記述するツリーとが生成される。リンクリストは、ＩＤが同じｐ群に対してひとつだけ存在する。
【００９９】
（ｉｖ）分割矩形Ｒの配列の長さが閾値θ以上となる場合には、多数のポイントが登録されることで検索性能が劣化することになるので、図１３に示すように、分割矩形Ｒを親ノードとして、Ｒを縦ｎ分割、横ｍ分割し、これらをそれぞれＲｅｃ（Ｒ，　ｉ，　ｊ）としてすべてＲの子ノードとする。さらに、Ｒの配列に含まれているすべての点ｐを各子ノードに再配置して、Ｒの配列はクリアする。
【０１００】
（ｖ）分割矩形Ｒを分割した場合には、再配置された各ノードについて、リンクリストを生成しなおす。
【０１０１】
図１４及び図１５に、以上に説明したインデックス作成処理の処理フローを図示する。
【０１０２】
ここで、図１４に示す処理フローが骨格となる処理フローであり、図１５に示す処理フローは、図１４に示す処理フローのステップ１８で実行するリンクリストの作成処理の詳細な処理を示す。
【０１０３】
以上に説明したインデックスの作成処理では、インデックスの頂点τ０　を作成する際に、分割矩形を予めｎ×ｍ個作成するという方法を用いているが、規定のサイズの矩形を中央に１つだけ作成するようにして、必要に応じて、頂点τ０　に含まれる分割矩形を増やしていくという方法を用いることも可能である。この方法を用いると、メモリを節約できるようになる。
【０１０４】
〔４〕検索部１２での移動軌跡データ検索処理
次に、検索部１２により実行される移動軌跡データの検索処理について述べる。
【０１０５】
検索部１２は、入力部１０から移動軌跡データの検索の問い合わせがあると、データ管理部１１により生成されたインデックスを用いて検索を行う。
【０１０６】
前述したように、検索式は、
＜Ｌ＞＝Ｑ（（Ｒ１，Ｅ０），（Ｒ２，Ｅ１），　．．．　，（Ｒｎ　，　Ｅｎ　））
のような表記で、線分Ｌの集合＜Ｌ＞を求める問い合わせとして入力される。
【０１０７】
このとき指定されるＲとしては、先ず最初に、指定されるＲがインデックス用に作られた各分割矩形に等しいケースについて述べ、そうでないケースについては後述することにする。なお、以下の文中のＥＡ　，　ＥＢ　などは、それぞれ図９のＥＡ　，　ＥＢ　などに対応する。
【０１０８】
検索対象となる移動軌跡データは離散的なポイント列であるため、実際のクエリでは「矩形の境界上」に厳密にポイントが一致するケースはほとんどない。そのため、前述のＥＡ　からＥＧ　のうち、境界部分に始点か終点のある問い合わせについては、これを厳密に満たすような移動軌跡データを検索しても、全く答が得られない可能性が高い。
【０１０９】
これから、実用上は基本要素であるＥＡ　からＥＧ　までを組み合わせた、図１６に示す５つの関係を問い合わせに用いる。
【０１１０】
すなわち、実用上は、
2004118293.tif 000003
という５つの関係を問い合わせに用いれば足りる。
【０１１１】
次に、これらの問い合わせに対する答えを検索する方法について説明する。
【０１１２】
（Ｉ）Ｅｎｔｅｒ：
問い合わせ式がＱ（（Ｒ，Ｅｅｎｔｅｒ　））の場合、先ず最初に、Ｒを通る移動軌跡データをインデックスを使って探す。次に、各移動軌跡データのリンクリストを使って、Ｒの直前に別の分割矩形Ｒ’　を通っているかどうかを調べる（Ｒがリンクリストの先頭でない限りは、Ｒの直前にＲの四方のいずれかの分割矩形を通っている）。Ｒ’　が存在する場合は、その移動軌跡データを答えとして返す。
【０１１３】
（ＩＩ）Ｅｘｉｔ　：
問い合わせ式がＱ（（Ｒ，Ｅｅｘｉｔ））の場合、先ず最初に、Ｒを通る移動軌跡データをインデックスを使って探す。次に、各移動軌跡データのリンクリストを使って、Ｒの直後に別の分割矩形Ｒ’　を通っているかどうかを調べる（Ｒがリンクリストの末尾でない限りは、Ｒの直後にＲの四方のいずれかの分割矩形を通っている）。Ｒ’　が存在する場合は、その移動軌跡データを答えとして返す、
（ＩＩＩ）Ｒｅｔｕｒｎ　：
問い合わせ式がＱ（（Ｒ，Ｅｒｅｔｕｒｎ））の場合、先ず最初に、Ｒを通る移動軌跡データをインデックスを使って探す。次に、各移動軌跡データのリンクリストを使って、Ｒから順番にリンクをたどり、またＲに戻るようなルートがリンクリスト上にあるかどうかを調べる。もしそのようなルートが存在すれば、その移動軌跡データを答えとして返す。
【０１１４】
（ＩＶ）　Ｃｒｏｓｓ：
問い合わせ式がＱ（（Ｒ，Ｅｃｒｏｓｓ　））の場合、先ず最初に、ＲについてＥｅｎｔｅｒ　の条件を調べ、その後、さらにＥｅｘｉｔのケースについて調べる。両方を満たす移動軌跡データを答えとして返す。
【０１１５】
（Ｖ）Ｐａｔｈ　：
問い合わせ式がＱ（（Ｒ１，Ｒ２，Ｅｐａｔｈ））の場合、先ず最初に、Ｒ１　を通る移動軌跡データをインデックスを使って探す。次に、各移動軌跡データのリンクリストを使って、Ｒ１　から順番にリンクをたどりＲ２　にたどり着くようなルートがあるかどうかを調べる。もしそのルートが存在すれば、その移動軌跡データを答えとして返す。
【０１１６】
以上の処理によつて得られた答えの中から、条件式に含まれている時刻に関する条件を調べる、検索部１２は、最終的に時刻条件も満たす移動軌跡データだけを答えとして返す。
【０１１７】
次に、検索式で指定される領域Ｒがインデックスのために作られた各分割矩形と一致しない場合の検索方法について述べる。
【０１１８】
（Ａ）検索式で指定されるＲがτ０　よりも大きい（インデックスが対象としている範囲を超えている）場合には、インデックスを使用することができないので、移動軌跡データすべてについて与えられた条件を直接調べることで、検索式を充足する移動軌跡データを検索する。
【０１１９】
（Ｂ）検索式で指定されるＲがインデックスの分割矩形階層の最下層の分割矩形のいずれかに完全に含まれる場合には、次のように計算する。
【０１２０】
（Ｂ−１）Ｅｎｔｅｒ／Ｅｘｉｔ　／Ｒｅｔｕｒｎ　／Ｃｒｏｓｓの場合：
Ｒが含まれる最下層の分割矩形をＲ’　とすると、先ず最初に、インデックスを使って、Ｒ’　を通過する移動軌跡データを探す。その後に、リンクリストを使わず、それぞれの移動軌跡データについて条件のチェックを行う。
【０１２１】
（Ｂ−２）Ｐａｔｈ　の場合：
Ｒ１　が含まれる最下層の分割矩形をＲ１’、Ｒ２　が含まれる最下層の分割矩形をＲ２’とすると、先ず最初に、インデックスを使って、Ｒ１’を通った後にＲ２’を通る移動軌跡データを調べ、その後に、リンクリストを使わず、Ｑ（（Ｒ１，Ｒ２，Ｅｐａｔｈ））を満たすかどうかを調べる。
【０１２２】
（Ｃ）検索式で指定されるＲがインデックス分割矩形階層の最下層の分割矩形のいずれにも完全には含まれない場合には、Ｒを含むインデックス中の最小の分割矩形を使って、リンクリストを調べた後、インデックスを使わずに、検索式を充足する移動軌跡データを検索する。その調べ方については、Ｒが最下層の分割矩形に完全に含まれる場合と同様である。
【０１２３】
リンクリストは、特にＰａｔｈ　を含むクエリを計算する上で有効である。例えば、Ｒ１，　．．．　，Ｒｎ　を順番に通過していくような多数の分割矩形を含むＰａｔｈ　クエリでは、リンクリストをたどり、移動軌跡がＲ１　からＲｎ　まで順番に通過しているかどうかを簡単に調べることができる。
【０１２４】
図１７ないし図２１に、以上に説明した移動軌跡データ検索処理の処理フローを図示する。
【０１２５】
ここで、図１７及び図１８の処理フローが骨格となる処理フローであり、図１９及び図２０の処理フローは、図１７及び図１８の処理フローのステップ２３／ステップ３０で実行する移動軌跡データの検索処理の詳細な処理を示し、図２１の処理フローは、図１７及び図１８の処理フローのステップ３４で実行する移動軌跡データの検索処理の詳細な処理を示す。
【０１２６】
図１７及び図１８の処理フローについて簡単に説明するならば、ステップ２１，２２で、インデックスの最上位層の分割矩形（分割元となった矩形）と検索式で指定される領域Ｒの大きさを比較して、一致する場合には、図１９及び図２０の処理フローに従って、上述した（Ｂ）と同様の手順に従い、インデックス（リンクリストを含む）を使って、検索式を充足する移動軌跡データを検索する。
【０１２７】
そして、インデックスの最上位層の分割矩形（分割元となった矩形）と検索式で指定される領域Ｒの大きさとが一致しない場合には、ステップ２５で、検索式で指定される領域Ｒの方が大きいのか否かを判断して、検索式で指定される領域Ｒの方が大きい場合には、インデックスを用いることができないので、上述した（Ａ）で説明したように、インデックスを使わずに、検索式を充足する移動軌跡データを検索する。
【０１２８】
一方、ステップ２５で、検索式で指定される領域Ｒの方が小さい場合には、ステップ２８〜ステップ３３の処理を繰り返していくことで、インデックスの１つ下位層の分割矩形と検索式で指定される領域Ｒの大きさとが一致するのか否かを判断して、一致する場合には、図１９及び図２０の処理フローに従って、上述した（Ｂ）と同様の手順に従い、インデックス（リンクリストを含む）を使って、検索式を充足する移動軌跡データを検索する。
【０１２９】
そして、ステップ２８〜ステップ３３の処理を繰り返していくことで、最終的に、検索式で指定される領域Ｒの大きさとインデックスの分割矩形とが一致しないことを判断するときには、検索式で指定される領域Ｒを含む最小の分割矩形Ｒ’　を特定して、ステップ３４で、図２１の処理フローに従って、その分割矩形Ｒ’　が検索式で指定されたものとして扱って、インデックスを使って検索を行い、ステップ３５で、その検索した移動軌跡データの中から、インデックスを使わずに検索式を充足するものを検索する。
【０１３０】
すなわち、上述した（Ｃ）と同様の手順に従い、検索式で指定される領域Ｒを含む最小の分割矩形Ｒ’　を特定すると、その分割矩形Ｒ’　が検索式で指定されたものとして扱って、インデックスを使って検索を行い、その後、その検索した移動軌跡データの中から、インデックスを使わずに検索式を充足するものを検索するのである。
【０１３１】
ここで、図２１の処理フローで、Ｅｎｔｅｒ／Ｅｘｉｔ　／Ｒｅｔｕｒｎ　／Ｃｒｏｓｓに分けて検索を行わないのは、最小の分割矩形Ｒ’　についてそのような条件を充足したとしても、検索式で指定される領域Ｒについてそのような条件を充足しているとは限らないからである。
【０１３２】
なお、いずれの検索ルートを通る場合にも、最終的な検索結果は、検索式で指定される時刻条件を充足するものを検索することで得ることになる。
【０１３３】
以上説明した実施形態例では、移動軌跡データとして２次元平面上のデータを扱っているが、本発明では、３次元空間上あるいはそれ以上の多次元空間内の移動軌跡データに対してもそのまま適用できるものである。この場合、移動軌跡データの各ポイントの座標を表すデータの個数がｎ次元空間内のデータである場合にはｎ個になる。
【０１３４】
また、本発明の取り扱う移動軌跡データは、移動する物体の移動軌跡データに限られるものではなく、複数のパラメータが連動して時間軸に沿って変化するような移動軌跡データに対してもそのまま適用できるものである。例えば、学生の身長、体重、胸囲、座高の４パラメータを各年に測定したケースでは、これらの４パラメータを軸とする四次元空間内の移動軌跡データとして扱うことができる。
【０１３５】
【発明の効果】
空間上を移動する物体の移動軌跡などを、物体の識別子と時刻と空間上の座標（点データ）との組として記録したものを移動軌跡データと呼ぶ。
【０１３６】
移動軌跡データは、一般には連続でない時系列に沿った離散的な点データ列である。移動軌跡データに含まれる点データ列を点データの時刻順に結んだものは、空間上では有限の長さを持ち向きがある線分になる。このような移動軌跡データを蓄積し検索する機能を有するデータベースシステムを、移動軌跡データベースシステムと呼ぶ。
【０１３７】
本発明では、このような移動軌跡データベースシステムに対して、空間上の複数の領域と移動軌跡データとの間の位相幾何学的な関係を検索条件として指定すると、移動軌跡データベースシステムが予め蓄積している移動軌跡データの通過するグリッドの順序を検出して作成するグリッドリンクと呼ぶインデックスを利用することで、指定された検索条件を満たす移動軌跡データを高速に検索することを実現する。
【図面の簡単な説明】
【図１】本発明を具備するデータベースシステムの全体構成図である。
【図２】移動軌跡データの一例を示す図である。
【図３】閉領域間の位相幾何学的関係を記述する行列式の説明図である。
【図４】閉領域と有向線分との間の位相幾何学的関係を記述する行列式の説明図である。
【図５】閉領域と有向線分との関係の説明図である。
【図６】閉領域と有向線分との間の位相幾何学的関係を記述する行列式の説明図である。
【図７】ＣＯＮＮＥＣＴ演算の説明図である。
【図８】ＣＯＮＮＥＣＴ演算の説明図である。
【図９】基本となる関係行列の説明図である。
【図１０】基本となる関係行列とＣＯＮＮＥＣＴ演算とにより導出される関係行列の説明図である。
【図１１】インデックスの説明図である。
【図１２】リンクリストの説明図である。
【図１３】矩形分割処理の説明図である。
【図１４】データ管理部の実行する処理フローである。
【図１５】データ管理部の実行する処理フローである。
【図１６】実用上で基本となる閉領域と有向線分との関係の説明図である。
【図１７】検索部の実行する処理フローである。
【図１８】検索部の実行する処理フローである。
【図１９】検索部の実行する処理フローである。
【図２０】検索部の実行する処理フローである。
【図２１】検索部の実行する処理フローである。
【符号の説明】
１　　データベースシステム
１０　入力部
１１　データ管理部
１２　検索部
１３　蓄積部
【図１】
2004118293.tif 000004
【図２】
2004118293.tif 000005
【図３】
2004118293.tif 000006
【図４】
2004118293.tif 000007
【図５】
2004118293.tif 000008
【図６】
2004118293.tif 000009
【図７】
2004118293.tif 000010
【図８】
2004118293.tif 000011
【図９】
2004118293.tif 000012
【図１０】
2004118293.tif 000013
【図１１】
2004118293.tif 000014
【図１２】
2004118293.tif 000015
【図１３】
2004118293.tif 000016
【図１４】
2004118293.tif 000017
【図１５】
2004118293.tif 000018
【図１６】
2004118293.tif 000019
【図１７】
2004118293.tif 000020
【図１８】
2004118293.tif 000021
【図１９】
2004118293.tif 000022
【図２０】
2004118293.tif 000023
【図２１】
2004118293.tif 000024