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