(57)【要約】  時空間領域に対応付けられる時系列データを管理する時空間データ管理システムであって、プログラムを実行するプロセッサと、前記プログラムを格納するメモリと、前記時系列データを格納する複数の記憶装置とを備え、前記プロセッサは、前記時空間領域を時間及び空間で分割して、複数の時空間分割領域を生成し、前記時空間分割領域の時間及び空間の近傍性を考慮して、前記複数の時空間分割領域の各々を一意に識別するための、一次元の整数値で表現される識別子を割り当て、前記割り当てられた識別子を用いて定められた範囲の時空間データについて、前記複数の記憶装置への配置を決定する。
2014073081.tif 000002
【特許請求の範囲】
【請求項１】
時空間領域に対応付けられる時系列データを管理する時空間データ管理システムであって、
プログラムを実行するプロセッサと、前記プログラムを格納するメモリと、前記時系列データを格納する複数の記憶装置とを備え、
前記プロセッサは、
前記時空間領域を時間及び空間で分割して、複数の時空間分割領域を生成し、
前記時空間分割領域の時間及び空間の近傍性を考慮して、前記複数の時空間分割領域の各々を一意に識別するための、一次元の整数値で表現される識別子を割り当て、
前記割り当てられた識別子を用いて定められた範囲の時空間データについて、前記複数の記憶装置への配置を決定することを特徴とする時空間データ管理システム。
【請求項２】
請求項１に記載の時空間データ管理システムであって、
前記プロセッサは、前記決定された時空間データの配置に従って時空間データを記憶装置間で移行する際、前記時空間データの形式を変更することを特徴とする時空間データ管理システム。
【請求項３】
請求項２に記載の時空間データ管理システムであって、
前記プロセッサは、
時間及び空間が近い時空間データが一つの時空間分割領域に含まれるように、前記識別子を前記時空間データに割り当て、
同一の前記識別子が割り当てられた時空間データ毎に、前記時空間データの形式を変更することを特徴とする時空間データ管理システム。
【請求項４】
請求項１に記載の時空間データ管理システムであって、
前記プロセッサは、前記割り当てられた識別子を用いて、前記時空間データの格納場所を特定し、
前記特定された格納場所毎に前記時空間データを検索し、
前記検索の結果を結合することを特徴とする時空間データ管理システム。
【請求項５】
請求項１に記載の時空間データ管理システムであって、
前記プロセッサは、前記時空間データの登録処理の頻度、前記時空間データの検索処理の頻度及び前記時空間分割領域に含まれるデータ量の少なくとも一つに基づいて、前記時空間領域の分割を動的に変更することを特徴とする時空間データ管理システム。
【請求項６】
請求項１に記載の時空間データ管理システムであって、
前記プロセッサは、前記決定された時空間データの配置に従って時空間データを記憶装置間で移行する際、時間及び空間において連続的に変化する値を表す時空間データの時系列変化を近似して、前記時空間データを圧縮することを特徴とする時空間データ管理システム。
【請求項７】
請求項６に記載の時空間データ管理システムであって、
前記プロセッサは、圧縮前後のデータの誤差及び圧縮率の少なくとも一つに従って、前記時空間データの圧縮を制御することを特徴とする時空間データ管理システム。
【請求項８】
請求項６に記載の時空間データ管理システムであって、
前記プロセッサは、前記時空間データの連続性を考慮して、前記記憶装置に格納されていない点を補間することを特徴とする時空間データ管理システム。
【請求項９】
請求項１に記載の時空間データ管理システムであって、
前記プロセッサは、前記記憶装置に格納されている時空間データの中から、指定する時空間領域のデータを時系列に表示するためのデータを生成することを特徴とする時空間データ管理システム。
【請求項１０】
時空間領域に対応付けられる時系列データを管理するために時空間データ管理システムで実行される時空間データ管理方法であって、
前記時空間データ管理システムは、プログラムを実行するプロセッサと、前記プログラムを格納するメモリと、前記時系列データを格納する複数の記憶装置とを有し、
前記方法は、
前記プロセッサが、前記時空間領域を時間及び空間で分割して、複数の時空間分割領域を生成するステップと、
前記プロセッサが、前記時空間分割領域の時間及び空間の近傍性を考慮して、前記複数の時空間分割領域の各々を一意に識別するための、一次元の整数値で表現される識別子を割り当てるステップと、
前記プロセッサが、前記割り当てられた識別子を用いて定められた範囲の時空間データについて、前記複数の記憶装置への配置を決定するステップとを含むことを特徴とする時空間データ管理方法。
【請求項１１】
時空間領域に対応付けられる時系列データを管理する計算機システムを下記の手段として機能させるためのプログラムであって、
前記計算機システムは、プログラムを実行するプロセッサと、前記プログラムを格納するメモリと、前記時系列データを格納する複数の記憶装置とを有し、
前記プログラムは、
前記時空間領域を時間及び空間で分割して、複数の時空間分割領域を生成する手段と、
前記時空間分割領域の時間及び空間の近傍性を考慮して、前記複数の時空間分割領域の各々を一意に識別するための、一次元の整数値で表現される識別子を割り当てる手段と、
前記割り当てられた識別子を用いて定められた範囲の時空間データについて、前記複数の記憶装置への配置を決定する手段とを含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間及び空間に対応付けられる時空間におけるデータを管理する時空間データ管理システムに関する。
【背景技術】
【０００２】
近年の計測、通信技術の発達により、位置及び時刻の情報（時空間情報）を含むセンシングデータが安価かつ大量に取得可能になり、これらを活用した新たなサービスが生まれつつある。例えば、タクシーの位置及び時刻の情報から交通流を把握する技術が開発されている。【０００３】
これらのリアルタイムなサービスは、情報が古くなると、その価値が下がる。このため、位置及び時刻の情報を含むデータを高速に収集し、解析し、再配信することが求められる。【０００４】
これらの処理の中で、ハードディスクドライブのＩ／Ｏを必要とする、収集データのデータベースへの格納及び検索処理がボトルネックとなる。時空間情報のデータベースへの格納及び検索を高速化するために、いくつかの技術が開発されている。例えば、近年、揮発性半導体による主記憶装置上にデータベースを構築することによって処理を高速化する方法が注目されている。しかし、実際には、半導体メモリの現在の集積技術の制限から、一個の６４ビットＣＰＵに搭載される主記憶装置としての半導体メモリは、数十ＧＢ程度である。【０００５】
また、特許文献１では、揮発性半導体による主記憶装置及び不揮発性のハードディスクドライブを用いることによって、高速な主記憶装置上に記録できないデータを、低速だが大容量のハードディスクドライブに格納する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００９−３２０１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述した特許文献１に記載された技術を、時間に従って連続的に変化する大量の時空間データに適用する場合、以下の問題がある。【０００８】
まず、記憶装置間で分散して格納した時空間データを検索する場合、複数のデータベースに跨って検索をするので、検索性能が悪化する問題がある。また、複数の記憶装置で同一の形式でデータを格納する必要があるため、記憶装置ごとに最適な格納形式を用いることができないという問題がある。【０００９】
本発明は、時空間データのリアルタイムに利用可能とすることを目的とする。
【課題を解決するための手段】
【００１０】
本願において開示される発明の代表的な一例は以下の通りである。すなわち、時空間領域に対応付けられる時系列データを管理する時空間データ管理システムであって、プログラムを実行するプロセッサと、前記プログラムを格納するメモリと、前記時系列データを格納する複数の記憶装置とを備え、前記プロセッサは、前記時空間領域を時間及び空間で分割して、複数の時空間分割領域を生成し、前記時空間分割領域の時間及び空間の近傍性を考慮して、前記複数の時空間分割領域の各々を一意に識別するための、一次元の整数値で表現される識別子を割り当て、前記割り当てられた識別子を用いて定められた範囲の時空間データについて、前記複数の記憶装置への配置を決定する。
【発明の効果】
【００１１】
本発明の代表的な実施例によると、時空間データのリアルタイム性を損わずに、データの格納及び検索を高速化することができる。【００１２】
前述した以外の課題、構成及び効果は、以下の実施例の説明により明らかにされる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【図２】本発明の第１の実施例の時空間データ登録部によって実行されるデータ登録処理のフローチャートである。
【図３】本発明の第１の実施例の時空間データ移行部によって実行されるデータ移行処理のフローチャートである。
【図４】本発明の第１の実施例の時空間データ検索部によって実行される検索処理のフローチャートである。
【図５】本発明の第１の実施例の主記憶検索部によって実行される検索処理のフローチャートである。
【図６】本発明の第１の実施例の二次記憶検索部によって実行される検索処理のフローチャートである。
【図７】本発明の第１の実施例の二次記憶検索部による処理の概念を説明する図である。
【図８】本発明の第１の実施例の時空間ＩＤ計算処理のフローチャートである。
【図９】本発明の第１の実施例の代表的な登録前データの一例を説明する図である。
【図１０】本発明の第１の実施例の時空間展開データの一例を説明する図である。
【図１１】本発明の第１の実施例の時空間ＩＤ管理データの一例を説明する図である。
【図１２】本発明の第１の実施例の時空間管理データの一例を説明する図である。
【図１３】本発明の第１の実施例の時空間圧縮データの一例を説明する図である。
【図１４】本発明の第１の実施例のデータ移行条件の一例を説明する図である。
【図１５Ａ】本発明の第１の実施例の時空間ＩＤの概念を説明する図である。
【図１５Ｂ】本発明の第１の実施例の時空間ＩＤの概念を説明する図である。
【図１６Ａ】本発明の第１の実施例の時空間ＩＤグリッドの動的な変更の具体例を説明する図である。
【図１６Ｂ】本発明の第１の実施例の時空間ＩＤグリッドの動的な変更の具体例を説明する図である。
【図１７】本発明の第２の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【図１８Ａ】本発明の第２の実施例の軌跡圧縮方法の概念を説明する図である。
【図１８Ｂ】本発明の第２の実施例の軌跡圧縮方法の概念を説明する図である。
【図１９Ａ】本発明の第２の実施例の移動軌跡補間方法の概念を説明する図である。
【図１９Ｂ】本発明の第２の実施例の移動軌跡補間方法の概念を説明する図である。
【図２０】本発明の第２の実施例の代表的な移動軌跡圧縮補間パラメータの例を示す。
【図２１】本発明の第２の実施例の時空間データ移行部によって実行されるデータ移行処理のフローチャートである。
【図２２】本発明の第２の実施例の移動軌跡圧縮処理のフローチャートである。
【図２３】本発明の第２の実施例の移動軌跡グループ圧縮処理のフローチャートである。
【図２４】本発明の第２の実施例の二次記憶検索部によって実行される検索処理のフローチャートである。
【図２５】本発明の第２の実施例の移動軌跡補間処理のフローチャートである。
【図２６】本発明の第３の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【図２７】本発明の第３の実施例の時空間データ可視化部が生成する画面の一例を説明する図である。
【図２８】本発明の第３の実施例の時空間データ可視化部が生成する画面の他の一例を説明する図である。
【発明を実施するための形態】
【００１４】
＜第１の実施例＞
以下、本発明の第１の実施例を、図面を参照して説明する。
【００１５】
図１は、第１の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【００１６】
本実施例の時空間データ管理システムは、中央処理装置１００、二次記憶装置１１０、主記憶装置１２０、入力装置１４０及び出力装置１５０を有し、これらの構成がバスで接続された計算機である。
【００１７】
中央処理装置１００は、主記憶装置１２０に格納されたプログラムを実行するプロセッサである。
【００１８】
二次記憶装置１１０は、例えば、磁気記憶装置、フラッシュメモリ等の不揮発性の記憶装置であり、プログラム実行時に中央処理装置１００によって使用されるデータを格納する。具体的には、二次記憶装置１１０は、時空間圧縮データ１１１及び二次記憶時空間索引データ１１２を格納する。
【００１９】
時空間圧縮データ１１１は、図１３に示すように、時空間ＩＤ及び時系列データを含み、例えば、表形式の時空間テーブルによって構成される。時空間テーブルは、必要に応じて属性値の最小値及び／又は最大値を含んでもよい。時空間圧縮データ１１１は、時空間データのスキーマも含む。時空間データのスキーマは、図３に示すように、列名及びデータ型を含む。
【００２０】
二次記憶時空間索引データ１１２及び主記憶時空間索引データ１２４は、時空間ＩＤをキーとして時空間展開データ、時空間圧縮データ（レコード番号やレコードの格納アドレス）を検索するための索引であり、例えば、Ｂ−Ｔｒｅｅインデックスを用いることができる。ここで時空間索引データ１２４を主記憶装置内に置くことによって、二次記憶装置内の時空間圧縮データ１１１の検索を高速化することもできる。
【００２１】
主記憶装置１２０は、例えば、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような高速かつ揮発性の記憶装置であり、オペレーティングシステム（ＯＳ）及びアプリケーションプログラムを格納する。中央処理装置１００が、オペレーティングシステムを実行することによって、計算機の基本機能が実現され、アプリケーションプログラムを実行することによって、計算機が提供する機能が実現される。
【００２２】
主記憶装置１２０は、二次記憶装置１１０と比べ、アクセス速度が速いので、頻繁にアクセスされるデータを配置するのに適する。一方、主記憶装置１２０は、二次記憶装置１１０と比べ、小容量なので、大量のデータを格納することができない。このため、本実施例では、時空間データ移行部１３４が、主記憶装置１２０に格納された時空間データを、二次記憶装置１１０に移行する（図３参照）。さらに、時空間データ検索部１３３が、主記憶装置１２０及び二次記憶装置１１０に格納された時空間データをシームレスに検索する（図４参照）。
【００２３】
具体的には、主記憶装置１２０は、時空間管理データ１２１、時空間展開データ１２３、主記憶時空間索引データ１２４を格納する。また、主記憶装置１２０は、時空間データ管理部１３０を実装するためのプログラムを格納する。時空間データ管理部１３０は、時空間管理データ作成部１３１、時空間データ登録部１３２、時空間データ検索部１３３及び時空間データ移行部１３４を含む。
【００２４】
時空間管理データ１２１は、時空間展開データ１２３及び時空間圧縮データ１１１を管理するためのデータであって、その詳細は図１１に示す。
【００２５】
時空間展開データ１２３は、図１３に示すように、時空間ＩＤ及び時系列データを含み、例えば、表形式の時空間テーブルによって構成される。時空間テーブルは、必要に応じて属性値の最小値及び属性値の最大値を含んでもよい。時空間展開データ１２３は、時空間データのスキーマも含む。時空間データのスキーマは、列名及びデータ型を含む。
【００２６】
時空間データ管理部１３０は、時空間圧縮データ１１１及び時空間展開データ１２３を管理する（例えば、データベースマネジメントシステムである）。時空間管理データ作成部１３１は、入力された時空間管理データから時空間管理データ１２１を作成する。時空間データ登録部１３２は、入力された時空間データから時空間展開データ１２３を作成する。
【００２７】
時空間データ検索部１３３は、時空間圧縮データ１１１及び時空間展開データ１２３を参照して、検索処理（概略判定、詳細判定）を実行する。
【００２８】
時空間データ移行部１３４は、時空間展開データ１２３に格納されているデータを時空間圧縮データ１１１に移行する。
【００２９】
なお、二次記憶装置１１０が、中央処理装置１００によって実行されるプログラムを格納してもよい。この場合、プログラムは、二次記憶装置１１０から読み出され、主記憶装置１２０にロードされて、中央処理装置１００によって実行される。
【００３０】
入力装置１４０は、キーボード、マウスなどのユーザインターフェースである。出力装置１５０は、ディスプレイ装置、プリンタなどのユーザインターフェースである。
【００３１】
なお、時空間データ管理システムが、ネットワークに接続し、他の装置との通信を制御する通信インターフェースを有してもよい。この場合、時空間データ管理システムが通信インターフェースを介して端末と接続されており、該端末が入力装置１４０及び出力装置１５０を有し、時空間データ管理システムは、端末からの要求に従って時空間データを処理し、処理結果を端末に出力する。
【００３２】
時空間データ管理システムは、物理的に一つの計算機上に構築されても、物理的には一つ又は複数の計算機上に構成された論理区画上に構築されてもよい。
【００３３】
なお、中央処理装置１００によって実行されるプログラムは、不揮発性の記憶媒体又はネットワークを介して計算機に提供される。このため、計算機は、記憶媒体（ＣＤ−ＲＯＭ、フラッシュメモリ等）を読み込むインターフェースを備えるとよい。
【００３４】
図２は、第１の実施例の時空間データ登録部１３２によって実行されるデータ登録処理のフローチャートである。
【００３５】
本実施例では、リアルタイムでＧＰＳなどによって収集される人や物の時空間データを、時空間に基づいた一塊のデータとして本システムに最終的に登録するために、主記憶上に時空間の属性を考慮したＩＤを付与し、データを登録する。本処理で主記憶装置１２０上に一時的に記録することによって、リアルタイムに大量に収集される時空間データを高速に登録及び検索をすることが可能となる。このため、リアルタイム性が要求されるアプリケーションが検索を要求した場合、検索結果をリアルタイムに返すことが可能となる。検索処理に関しては、図４に示す。
【００３６】
時空間データ登録部１３２によって実行される処理の具体的な流れを以下に示す。
【００３７】
まず、登録前データ読み込み部２０１が、登録前データ２００を読み込む。登録前データ２００は、ｃｓｖなどのファイル形式のデータでも、データベースに格納されているデータでもよい。代表的な時空間データの例は、図９を用いて後述する。
【００３８】
次に、登録用時空間ＩＤ付きデータ作成部２０２が、時空間管理データ１２１を用いて時空間の属性を考慮したＩＤを発行し、登録用時空間データ２０３を生成する。時空間のＩＤの発行方法は、図８を用いて後述する。
【００３９】
その後、展開データ登録部２０６は、生成された登録用時空間データ２０３を時空間展開データ１２３に登録する。また、主記憶時空間索引データ作成部２０４は、生成された登録用時空間データ２０３から主記憶時空間索引データ１２４を作成する。さらに、時空間ＩＤ管理データ作成部２０８は、時空間ＩＤ管理データ１２２を作成する。時空間ＩＤ管理データ１２２は、時空間ＩＤが表す時空間データの時刻区間、空間区間及び格納場所の情報である。なお、既に登録されている時空間ＩＤは重複して登録をしない。時空間ＩＤ管理データ１２２の例は、図１１を用いて後述する。
【００４０】
展開データ登録部２０６で作成された時空間展開データ１２３は、主記憶装置１２０のテーブルに格納されるので、時空間ＩＤ管理データ１２２に含まれる格納場所は当該テーブルの格納場所を表す記号が格納される。
【００４１】
なお、前述した処理は繰り返し実行される。つまり、前述の処理が終了した後、まだ登録が終了していないデータがある場合、登録前データ読み込み部２０１がデータを読み込み、その後の処理を実行する。また、登録前データが未だ到着していない場合、登録前データ読み込み部２０１は、データが到着するまで待機する。
【００４２】
図３は、第１の実施例の時空間データ移行部１３４によって実行されるデータ移行処理のフローチャートである。
【００４３】
時空間データ移行部１３４は、主記憶装置１２０上に時空間展開データ１２３として登録されているデータを二次記憶装置１１０上に圧縮して登録する処理を実行する。この処理によって、小容量の主記憶装置１２０上の容量が一杯になることを防ぐ。このため、時空間データ移行部１３４は、データ移行条件判定部３０１、移行データ検索部３０２、データ型変更部３０３、二次記憶時空間索引データ作成部３０５、圧縮データ登録部３０６、時空間ＩＤ管理データ作成部３０７及びデータ移行成否判定部３０８を含む。
【００４４】
時空間データ移行部１３４によって実行される処理の具体的な流れを以下に示す。
【００４５】
データ移行条件判定部３０１は、データ移行条件１２５を参照し、主記憶装置１２０に格納された時空間展開データ１２３から二次記憶装置１１０に移行すべき時空間ＩＤがあるかを判定する。データ移行条件１２５の例は、図１４を用いて後述する。
【００４６】
データ移行条件判定部３０１が移行する時空間ＩＤを決定した後、移行データ検索部３０２が、該当する時空間ＩＤを含む時空間展開データ１２３を検索する。主記憶装置１２０上で移行データ検索部３０２が実行する展開データ検索処理は、主記憶検索部４０３が実行する展開データ検索処理と同じであり、図５を用いて後述する。
【００４７】
その後、データ型変更部３０３は、検索されたデータの型を変更して、一つのレコードに同じオブジェクトの同じ時空間ＩＤを持つデータを圧縮した圧縮データ３０４を作成する。圧縮データの例は、図１３を用いて後述する。
【００４８】
その後、圧縮データ登録部３０６は、生成された圧縮データ３０４を時空間圧縮データ１１１に登録する。また、二次記憶時空間索引データ作成部３０５は、生成された圧縮データ３０４から二次記憶時空間索引データ１１２を作成する。さらに、時空間ＩＤ管理データ作成部３０７は、生成された圧縮データ３０４から時空間ＩＤ管理データ１２２を作成する。時空間ＩＤ管理データ１２２は、時空間ＩＤが表す時空間データの時刻区間、空間区間及び格納場所の情報である。なお、登録しようとする時空間ＩＤは、既に時空間データ登録部１３２で時空間展開データ１２３を登録する際に、同じ時空間ＩＤが登録されているので、この時空間ＩＤを含むレコードを削除してから登録する。時空間データ移行部１３４によって作成された時空間圧縮データ１１１は、二次記憶装置１１０のテーブルに格納されるので、時空間ＩＤ管理データ１２２に含まれる格納場所は当該テーブルの格納場所を表す記号が格納される。
【００４９】
データ移行成否判定部３０８は、圧縮データ３０４を作成してから、二次記憶時空間索引データ１１２、時空間圧縮データ１１１及び時空間ＩＤ管理データ１２２の更新が全て正常に行われているかを判定する。
【００５０】
データ移行成否判定部３０８で移行が正常に終了していると判定された場合、コミット部３０９は、移行データ検索部３０２で検索された主記憶上の時空間展開データ１２３を削除する。一方、データ移行成否判定部３０８で移行が正常に終了していないと判定された場合、二次記憶時空間索引データ１１２、時空間圧縮データ１１１及び時空間ＩＤ管理データ１２２を更新の前の状態に戻す。
【００５１】
これらの処理は繰り返し実行される。つまり、前述した処理が終了したら、データ移行条件判定部３０１が移行すべきデータがあるかを判定する。また、移行条件を満たしていない場合、データ移行条件判定部３０１は移行条件が真になるまで待機する。
【００５２】
図４は、第１の実施例の時空間データ検索部１３３によって実行される検索処理のフローチャートである。
【００５３】
時空間データ検索部１３３は、主記憶装置１２０と二次記憶装置１１０とに異なる形式で格納されているデータをシームレスに検索する。
【００５４】
データ位置検索部４０１は、時空間データ検索条件４００及び時空間ＩＤ管理データ１２２によって、検索する記憶領域を決定する。具体的には、検索対象の時空間を時空間ＩＤ管理データ１２２と比較することによって、検索対象の時空間を特定する時空間ＩＤを抽出する。図１１に示す例を用いると、時空間データ検索条件４００が（２≦時刻＜４  ａｎｄ  （１．２，１．０）≦空間＜（３．０、２．０））である場合、検索対象の時空間領域は、時空間ＩＤ｛２２，２３，３２，３３｝で特定される時空間領域に含まれている。このとき、各時空間ＩＤのデータが格納されている場所が分かる。この場合、時空間ＩＤ｛２２，２３｝のデータの格納場所は”ｍｅｍ＿ｔａｂｌｅ”であるので、このデータは主記憶装置１２０に格納されている。また、時空間ＩＤ｛３２，３３｝のデータの格納場所は”ｄｉｓｋ＿ｔａｂｌｅ”であるので、このデータは二次記憶装置１１０に格納されている。
【００５５】
以上の結果から、各格納場所について検索対象である時空間ＩＤ及び検索条件を求めた結果を、主記憶検索条件４０２及び二次記憶検索条件４０５とする。前述した例では、主記憶検索条件４０２は（時空間ＩＤ｛２２，２３｝，２≦時刻＜３  ａｎｄ  （１．２，  １．０）≦空間＜（３．０、２．０））となる。二次記憶検索条件４０５は（時空間ＩＤ｛３２，３３｝，３≦時刻＜４  ａｎｄ  （１．２，１．０）≦空間＜（３．０、２．０））となる。
【００５６】
その後、主記憶検索部４０３は、主記憶検索条件４０２を用いて、時空間展開データ１２３及び主記憶時空間索引データ１２４を検索し、主記憶検索結果４０４を出力する。また、二次記憶検索部４０６は、二次記憶検索条件４０５を用いて、時空間圧縮データ１１１及び二次記憶時空間索引データ１１２を検索し、二次記憶検索結果４０７を出力する。主記憶検索部４０３によって実行される処理の詳細は図５を用いて後述し、二次記憶検索部４０６によって実行される処理の詳細は図６を用いて後述する。
【００５７】
その後、検索結果マージ部４０８は、主記憶検索結果４０４及び二次記憶検索結果４０７を結合する。ここで、結合の際に、検索結果を時空間ＩＤ（又は、他の値）でソートしてもよい。検索結果はマージ検索結果４０９として出力される。
【００５８】
ここでは、説明と簡単にするため、空間データ及び空間検索要求は矩形であり、ｘ，ｙの最小値と最大値のペアで表現できる形式で説明するが、空間の表現方法は一般的なポリゴン形式でもよい。なお、空間条件が矩形以外のポリゴンである場合、例えば、ポリゴンを内包する外接矩形で検索し、検索結果がポリゴンに含まれるかを判定し、検索結果を求めればよい。また、このことは本特許の他の空間データにも同じである。
【００５９】
図５は、第１の実施例の主記憶検索部４０３によって実行される検索処理のフローチャートである。
【００６０】
主記憶検索部４０３は、主記憶検索条件４０２を用いて主記憶装置１２０に格納された時空間展開データ１２３を検索した結果を返す処理を行う。
【００６１】
まず、クエリ文生成部５００は、主記憶検索条件４０２を用いてクエリ文５０１を生成する。主記憶検索条件４０２では、時空間ＩＤ、時刻、空間及びオブジェクトＩＤの少なくとも一つが検索キーとなる。また、時空間展開データ１２３が他の属性情報を格納している場合、当該属性情報を検索キーとしてもよい。
【００６２】
クエリ文実行部５０２は、生成されたクエリ文５０１及び主記憶時空間索引データ１２４を用いて、検索クエリに該当するレコードを時空間展開データ１２３から取得して、主記憶検索結果４０４として出力する。
【００６３】
図６は、第１の実施例の二次記憶検索部４０６によって実行される検索処理のフローチャートである。
【００６４】
二次記憶検索部４０６は、二次記憶検索条件４０５を用いて二次記憶装置１１０に格納された時空間圧縮データ１１１を検索した結果を返す処理を行う。
【００６５】
また、二次記憶装置１１０では時空間データが圧縮されているので、図７に示すように、時空間ＩＤ及びオブジェクトＩＤを検索キーとした概略判定を実行した後、圧縮されたレコード内から二次記憶検索条件４０５に一致するデータを詳細判定を実行する２段階の検索処理を行う。
【００６６】
二次記憶検索条件４０５では、時空間ＩＤ、時刻、空間及びオブジェクトＩＤの少なくとも一つが検索キーとなる。ただし、二次記憶検索条件４０５は、データ位置検索部４０１がデータの格納位置を検索するために用いた時空間ＩＤをそのまま含んでいる。また、時空間圧縮データ１１１が他の属性情報を格納している場合、当該属性情報も検索キーとしてもよい。
【００６７】
クエリ文生成部６００は、二次記憶検索条件４０５を用いてクエリ文６０１を生成する。二次記憶検索処理では、最初に時空間ＩＤ及びオブジェクトＩＤを検索キーとした概略判定を実行するので、クエリ文生成部６００は時空間ＩＤ及びオブジェクトＩＤを用いてクエリ文６０１を作成する。
【００６８】
概略判定部６０２は、クエリ文６０１及び二次記憶時空間索引データ１１２を用いて、検索クエリに該当するレコードを時空間圧縮データ１１１から取得して、結果候補６０３として出力する。
【００６９】
詳細判定部６０４は、結果候補６０３が二次記憶検索条件４０５に一致するかを判定する。詳細判定部６０４は、概略判定部６０２では用いられなかった詳細な検索条件（すなわち、時刻範囲、空間範囲、属性範囲）を用いて判定をする。詳細判定部６０４は、二次記憶検索条件４０５に一致すると判定したデータを、二次記憶検索結果４０７として出力する。
【００７０】
図８は、第１の実施例の時空間ＩＤ計算処理のフローチャートである。
【００７１】
まず、処理２００１では、登録前データ２００に含まれる時刻ｔ、座標（ｘ，ｙ）を取得する。その後、処理２００２において、この登録前データ２００の時間軸の分割番号ｔｉｄを計算する。分割番号ｔｉｄは、この登録前データが時間軸方向で原点（開始時刻）からで何番目の時空間分割領域に含まれるかを示す。
【００７２】
さらに、処理２００３において、登録前データ２００のｘ軸の分割番号ｘｉｄを計算する。分割番号ｘｉｄは、この登録前データが時ｘ軸方向で原点（ｘ軸上の最小値）から何番目の時空間分割領域に含まれるかを示す。さらに、処理２００４においてこの登録前データ２００のｙ軸の分割番号ｙｉｄを計算する。分割番号ｙｉｄは、この登録前データが時ｙ軸方向で原点（ｙ軸上の最小値）から何番目の時空間分割領域に含まれるかを示す。
【００７３】
処理２００１〜２００４において、ＴＭＩＮは時間軸上の開始時刻であり、ｔｗは時間軸上の分割幅である。また、ＸＭＩＮはｘ軸上の最小値であり、ｘｗはｘ軸上の分割幅である。また、ＹＭＩＮはｙ軸上の最小値であり、ｙｗはｙ軸上の分割幅である。
【００７４】
次に、処理２００５において、ｔｉｄを指定ビット数Ｎｂｔで、２進数［ｔｉｄ］２で表現し、処理２００６において、ｘｉｄを指定ビット数Ｎｂｘで、２進数［ｘｉｄ］２で表現し、処理２００７において、ｙｉｄを指定ビット数Ｎｂｙで、２進数［ｙｉｄ］２で表現する。なお、［  ］ｎはｎ進数で表示された整数値を表す。
【００７５】
その後、処理２００８において、Ｎｂビットの時空間ＩＤを、上位Ｎｂｔビットと、下位（Ｎｂ−Ｎｂｔ）ビットとに分け、上位ビットには［ｔｉｄ］２を、下位ビットには［ｙｉｄ］２と［ｘｉｄ］２を上位ビットから順に並べた［ｓｔｉｄ］２を生成する。
【００７６】
最後に、処理２００９において［ｓｔｉｄ］２を１０進数に変換して、ｓｔｉｄを算出する。
【００７７】
図９は、第１の実施例の代表的な登録前データ２００の一例を説明する図である。
【００７８】
時空間データは、時間及び空間の値を持つデータである。具体的には、図９に示すように、登録前の時空間データの一つのレコードに、時間の値、空間の値及び属性値（例えば、オブジェクトＩＤ）を含む。図９は、空間が二次元の時空間データを例示するが、あらゆる次元が対象となる。また、時空間データは、時間及び空間と関係のデータとして属性値を含んでもよい。属性値としては、加速度、心拍等のオブジェクトの状態を示すものがある。
【００７９】
図１０は、第１の実施例の時空間展開データ１２３の一例を説明する図である。
【００８０】
時空間展開データ１２３は、登録用時空間データ２０３をそのままの形式で登録したもので、両データの形式は同じである。
【００８１】
登録用時空間データ２０３は、登録前データ２００の各レコードに時空間ＩＤが付与されたデータである。これによって、各データが時間及び空間に関連付けられた、より大きな単位にクラスタリングされる。つまり、時間的及び空間的に近いデータには同じ時空間ＩＤが付与されており、時空間ＩＤを用いて索引データを後に作成することが容易にできる。時空間展開データ１２３のデータ形式は、図１０に示すように、一つのレコードに時空間ＩＤ、時刻の値、空間の値及び属性値（例えば、オブジェクトＩＤ）を含む。
【００８２】
図１１は、第１の実施例の時空間ＩＤ管理データ１２２の一例を説明する図である。
【００８３】
時空間ＩＤ管理データ１２２は、時空間ＩＤが付与されたデータが含まれる時間区間及び空間区間、及び、該データの格納場所を管理するためのデータである。具体的には、各レコードは、時空間ＩＤ、開始時間、終了時間、開始位置、終了位置及び格納場所を含む。
【００８４】
ここでは、登録用時空間データ２０３に含まれる時空間ＩＤの中で、既に時空間ＩＤ管理データに登録されていない時空間ＩＤが表す時刻及び空間の端点を求め、時空間データが登録される格納場所及び求められた時刻及び空間の端点を時空間ＩＤ管理データ１２２に登録する。なお、時空間ＩＤから、開始時間、終了時間、開始位置及び終了位置を求める際に、時空間ＩＤ作成処理（図８）と同じ処理を実行すればよい。
【００８５】
図１２は、第１の実施例の時空間管理データ１２１の一例を説明する図である。
【００８６】
時空間管理データ１２１は、管理パラメータ及び値を含む。
【００８７】
管理パラメータのうち、「時空間ＩＤビット数」は、時空間ＩＤが表現される整数値のビット数である。また、「空間次元」は、時空間データが置かれる時空間が二次元のｘｙ平面であれば「２」、三次元のｘｙｚ空間であれば「３」である。
【００８８】
時空間管理データ１２１から、時空間ＩＤの空間ビット数（空間の各軸の分割数を表すために必要な最小のビット数）及び時間ビット数を求めることができる。例えば、図１２に示す時空間管理データ１２１では、ｘ軸方向に４分割なのでｘ軸で２ビット、ｙ軸方向に４分割なのでｙ軸で２ビットとなり、空間ビット数は合計４ビットである。時間ビット数は、時空間ＩＤビット数から空間ビット数を減じた値で、図１２に示す時空間管理データ１２１の例では、４ビットである。
【００８９】
時空間管理データ１２１は、時空間データ管理システムが稼働する際に設定されている必要がある。時空間管理データ１２１は、ＣＳＶ形式などのファイルで入力されても、ＣＵＩ又はＧＵＩを用いてインタラクティブに入力されてもよい。また、時空間データ管理システムに予めデフォルト値を設定して、ユーザが入力しない場合はデフォルト値を用いてもよい。
【００９０】
また、検索及び格納の履歴より、時空間管理データ１２１で管理している時空間領域の分割幅を動的に変更し、検索効率及び／又は格納効率を向上することもできる。例えば、一つの検索条件で検索される時空間領域を纏めて一つの時空間ＩＤを付与してもよい。一つの時空間ＩＤに纏めることによって、時空間ＩＤの総数が減し、検索効率が向上する。
【００９１】
また、稀にしか検索されない時空間領域を纏めて一つの時空間ＩＤを付与してもよい。検索される確率が低い時空間領域を一つの時空間ＩＤに纏めても、当該部分の検索効率への影響は小さいが、時空間ＩＤの数が減るため全体の検索効率が向上する。
【００９２】
また、分割幅を動的に変更した場合、既に格納されているデータを新しい時空間管理データ１２１に従って付与された新しい時空間分割領域に従って再格納し、時空間ＩＤ管理データ１２２を更新してもよい。なお、過去の時空間データはそのままにしてもよい。再格納した場合は元の時空間データを消去する。
【００９３】
このような時空間ＩＤの動的変更は、時空間ＩＤ管理データ１２２によって管理されているため可能となる。動的な時空間ＩＤの変更の例は、図１６を用いて後述する。
【００９４】
図１３は、第１の実施例の時空間圧縮データ１１１の一例を説明する図である。
【００９５】
時空間圧縮データ１１１は、時空間ＩＤ、オブジェクトＩＤ及び時系列データを含む。時系列データは、時空間展開データ１２３において、同じオブジェクトＩＤ及び同じ時空間ＩＤが付与されたデータを全て一つに纏めたものである。このとき、時系列データは、時刻、ｘ座標及びｙ座標の組（ｔ１，ｘ１，ｙ１）で構成され、時刻順に並べられる。また、時系列データで、同じｘ座標、ｙ座標の組が続いた場合、同値圧縮によって、その間のデータのサイズを削減してもよい。また、時空間以外の属性情報（ｃ１、ｃ２）が含まれる場合、時空間情報の後に属性情報を置くことによって（ｔ１，ｘ１，ｙ１，ｃ１１，ｃ２１）、属性情報を同じレコードに格納することができる。
【００９６】
図１４は、第１の実施例のデータ移行条件１２５の一例を説明する図である。
【００９７】
データ移行条件１２５は、時空間データ移行部１３４において主記憶装置１２０に格納された時空間展開データ１２３を、二次記憶装置１１０に格納する時空間圧縮データ１１１に変換する際に使用される条件である。データ移行条件１２５は、ＣＳＶ形式などのファイルで入力されても、ＣＵＩ又はＧＵＩを用いてインタラクティブに入力されてもよい。データ移行条件１２５は、データ移行ルール、容量、時間、移行元、移行先、移行元データ型、移行先データ型を含む。
【００９８】
データ移行ルールには、主記憶装置１２０に格納された時空間展開データ１２３を、１１０に格納する時空間圧縮データ１１１に変換するための基本ルールが設定される。例えば、データ移行ルールは、容量及び時間がある。データ移行ルールで容量が選択された場合、主記憶装置１２０に格納される時空間展開データ１２３のデータ量が、容量の項目に設定されている容量（ｍ１）以上である場合、データ量がｍ１以下になるまで変換をすることを定める。
【００９９】
この時、時間の項目の値は移行ルールには用いられない。また、容量を、絶対容量によって定義しても、使用可能容量の割合によって定義してもよい。割合によって定義した場合、展開データのデータ量が全使用可能容量のｍ１％以上である場合、ｍ１％以下になるまで変換をすることを定める。
【０１００】
また、移行ルールが時間である場合、時間ｔ１ごとに展開データに記憶されている時間ｔ１分だけ移行することを定める。この時、容量の値は移行ルールには用いられない。
【０１０１】
移行元及び移行先の項目は、データの移行元と移行先のテーブルを特定し、移行元データ及び移行先データにアクセスするために用いられる。移行元及び移行先には、例えば、ＤＢ名、Ｔａｂｌｅ名、Ｕｓｅｒ名、などを用いることができる。
【０１０２】
移行元データ型及び移行先データ型の項目は、データが格納されている形式である。本実施例は最も単純な構成として、主記憶上の展開データから二次記憶上の圧縮データへの変換を例にしているので、移行元データ型のＴｙｐｅ１は「展開型」であり、移行先データ型のＴｙｐｅ２は「圧縮型」である。
【０１０３】
データ移行条件１２５の項目を変更することによって所望のデータの変換及び移行をすることができる。例えば、主記憶装置１２０に格納された時空間展開データから二次記憶装置１１０に格納される時空間展開データへの移行や、主記憶装置１２０に格納された時空間展開データから主記憶装置１２０上で時空間圧縮データを作成し、作成された時空間圧縮データを二次記憶装置１１０に格納するデータ移行も可能である。
【０１０４】
また、データの変換及び移行は、主記憶装置１２０に格納されている時空間展開データの中で、古い時刻の（小さい時空間ＩＤが付与されている）データから移行するとよい。これは、時空間データ管理システムには、リアルタイムのデータを高速に処理することが求められており、新しいデータを、検索処理が高速な主記憶上になるべく長く残したいためである。
【０１０５】
また、空間的距離が近い時空間データに、近い時空間ＩＤを付与するように、Ｚｏｒｄｅｒを用いて時空間ＩＤが作成されている。このため、小さい時空間ＩＤの時空間データから順に移行することによって、空間的に近い時空間データを二次記憶装置１１０において近い記憶領域に配置することができる。これによって、空間的に近いため一つの検索クエリで検索される可能性が高いデータが近い記憶領域に配置され、Ｉ／Ｏ処理がボトルネックになりやすい記憶装置（例えば、ハードディスクドライブ）を二次記憶装置１１０に用いた場合でも、高速に検索することができる。
【０１０６】
なお、移行ルールを別に設けることによって、古いデータから移行する以外の移行方法も可能である。例えば、頻繁に検索されている時空間ＩＤを主記憶装置１２０に残してもよい。また、注目したい時間帯及び／又は空間領域を予め指定又は動的に指定して、それらの時間帯及び／又は空間領域を含む時空間ＩＤのデータを主記憶装置１２０に残してもよい。例えば、日中の時間帯や、首都圏だけに注目したい場合などである。また、これらのルールは、複数同時に適用することも可能である。例えば、日中の首都圏だけを主記憶装置１２０に残すが、それでもデータ量がｍ１％となった場合、日中の首都圏データから古いデータを移行してもよい。
【０１０７】
図１５Ａ及び図１５Ｂは、第１の実施例の時空間ＩＤの概念を説明する図である。
【０１０８】
ここでは、説明を簡単にするため、空間が二次元＋時間（一次元）の時空間について説明するが、ｎ次元空間へ拡張することができる。
【０１０９】
時空間ＩＤは、時間及び空間の属性を持つデータを、近い時間及び近い空間で纏めて扱うための識別子である。そのため、図１５Ａに示すように、時空間領域を直方体で分割する。分割する際に、まず時間軸方向で切断して、時刻ＩＤ（ｔ１、ｔ２、ｔ３、ｔ４）を割り当てる。次に、図１５Ｂに示すように、同一時間帯においては空間的距離が近いデータに近い値が付与されるように、時空間ＩＤを定める。時空間ＩＤを計算するための具体的な処理は、図８を用いて後述する。。例えば、空間平面をＺｏｒｄｅｒを用いて分割することができる。なお、Ｚｏｒｄｅｒは、空間平面を空間的な距離が近い順に辿る空間充填線の一手法であり、ヒルベルト線など他の空間充填線を利用してもよい。
【０１１０】
このように時空間ＩＤを用いることによって、時空間的な近さを一次元で簡単に管理することができる。このため、本実施例で行う時空間ＩＤを用いたデータの移行及びデータの圧縮において、空間的に近いデータを簡単に纏めて操作することができる。また、時空間的に近接していて、一緒に検索される可能性が高いデータをできるだけ同じ場所に配置し、検索効率を上げることができる。
【０１１１】
図１６Ａ及び図１６Ｂは、第１の実施例の時空間グリッドの動的な変更の具体例を説明する図である。図１６Ａは時間方向の結合及び分割の例を示し、図１６Ｂは空間方向の結合及び分割の例を示す。
【０１１２】
この時空間グリッドの動的な変更は、登録処理の頻度、検索処理の頻度及び前記時空間分割領域に含まれるデータ量の少なくとも一つに基づいて実行される。例えば、登録処理の頻度が高い時空間グリッドを複数の時空間グリッドに分割してもよい。また、検索処理の頻度が高い時空間グリッドを複数の時空間グリッドに分割してもよい。さらに、時空間グリッドに含まれるデータ量が多い場合、複数の時空間グリッドに分割してもよい。
【０１１３】
図１６Ａに示す例では、時間帯ｔ３、ｔ４の結合し、時間分割幅を２倍にする。結合された時空間グリッドには、小さい方の時間ＩＤ（ｔ３）を付与するとよい。また、逆に、時間帯ｔ３、ｔ４を分割することができる。時間方向の結合は、時間帯ｔ３、ｔ４が一緒に検索されることが多い場合などに有効である。
【０１１４】
図１６Ｂに示す例では、四つの時空間グリッドを結合し、空間分割幅を２倍にする。結合された時空間グリッドには、最小の空間ＩＤを付与するとよい。また、逆に、時空間グリッドを空間方向で分割することができる。空間方向の分割は、空間検索範囲が予め想定された検索範囲より大きい場合などに有効である。
【０１１５】
以上に説明した時間方向及び空間方向の結合及び分割は、繰り返し実行してもよい。つまり、２倍２倍と領域を拡張してもよく、１／２倍１／２倍と領域を縮小してもよい。
【０１１６】
本実施例では空間ＩＤ、時間ＩＤとも整数値を用いるので、時間及び空間のＩＤが０より小さくならないように、最初の時空間の分割幅を十分小さく設定するとよい。
【０１１７】
以上に説明したように、第１の実施例では、二次記憶装置に格納する前の主記憶装置に格納されるデータを検索することができ、時空間データのリアルタイム性を損わずに、データの格納及び検索を高速化することができる。
【０１１８】
また、データ移行条件に一致するデータを主記憶装置から二次記憶装置へ移動するので、主記憶装置の高速性と二次記憶装置の大容量性を生かしつつ、複数の記憶装置をまたがる検索を減らすことができる。特に、時空間ＩＤ毎にデータを移動するので、時間的及び空間的に近いデータは同じ記憶装置に格納され、多くの場合、一つの記憶装置内を検索すればよくなる。
【０１１９】
また、時空間ＩＤ毎に時空間データを纏めて、主記憶装置から二次記憶装置へデータを移行するので、主記憶装置及び二次記憶装置の特性に適した格納形式でデータを格納することができ、データの格納効率及び検索効率を向上することができる。
【０１２０】
また、検索時に、時空間データの格納場所を特定し、特定された格納場所毎に時空間データを検索し、検索結果を結合するので、複数の記憶装置間を跨って時空間データを検索することができる。
【０１２１】
また、時空間グリッドを動的に変更することによって、時空間データが特定の時空間グリッドに偏ることを防ぎ、検索を高速化することができる。
【０１２２】
＜第２の実施例＞
以下に、本発明の第２の実施例の構成について説明する。
【０１２３】
第２の実施例は、第１の実施例の構成に加え、時空間の軌跡データの圧縮及び解凍を実行することを特徴とする。これによって、人や車の移動データのような、連続的かつ滑らかなデータのデータ量を少なくして、データの格納及び検索の効率を向上することができる。また、解凍する時間幅を指定することによって、ユーザが求める時間幅でデータを返すことが可能となる。
【０１２４】
図１７は、第２の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【０１２５】
本実施例の時空間データ管理システムは、移動軌跡圧縮補間パラメータ１２６、移動軌跡データ圧縮部１３５及び移動軌跡データ解凍部１３６を有する。また、移動軌跡の圧縮及び補間をするので、時空間データ移行部１３４及び二次記憶検索部４０６の処理が、第１の実施例と異なる。なお、第１の実施例の時空間データ管理システムと同じ構成には、同じ符号を付し、説明を省略する。
【０１２６】
移動軌跡圧縮補間パラメータ１２６は、図２０を用いて後述する。移動軌跡データ圧縮部１３５は、移動軌跡データを圧縮する。移動軌跡データ圧縮部１３５が実行する軌跡圧縮方法は、図１８Ａ及び図１８Ｂを用いて後述する。移動軌跡データ解凍部１３６は、移動軌跡データを補間する。移動軌跡データ解凍部１３６が実行する軌跡補間方法は、図１９Ａ及び図１９Ｂを用いて後述する。
【０１２７】
図１８Ａ及び図１８Ｂは、第２の実施例の軌跡圧縮方法の概念を説明する図であり、図１８Ａは元の軌跡点を示し、図１８Ｂは圧縮後の軌跡点を示す。
【０１２８】
なお、説明を分かりやすくするため近似線を直線で示しているが、近似線は２次以上の関数を用いた多項式でもよい。
【０１２９】
図１８Ａに示すように、始点と終点とを近似線で結ぶ。近似線は移動軌跡圧縮補間パラメータ１２６の軌跡圧縮ルールに従って生成される。次に、始点と終点との間の全ての点について近似線との誤差を計算し、計算された誤差と移動軌跡圧縮補間パラメータ１２６の圧縮精度とを比較することによって、近似線が軌跡点群を十分に表現しているかを判定する。その結果、誤差が大きく、近似線が軌跡点群を十分に表現していない場合、誤差が最も大きかった点を圧縮点に追加する。
【０１３０】
圧縮点を追加すると、図１８Ｂに示すように、始点及び終点以外の点を含む圧縮点群が作成される。圧縮点を追加する処理は、近似線がこの軌跡点群を十分に表現するまで再帰的に実行される。
【０１３１】
軌跡圧縮によってデータ量を減少させることができ、データの格納効率及び検索効率を向上することができる。軌跡圧縮は、特に、軌跡点が直線上に並んでいる場合等に有効である。
【０１３２】
図１９Ａ及び図１９Ｂは、第２の実施例の移動軌跡補間方法の概念を説明する図であり、図１９Ａは圧縮後の軌跡点を示し、図１９Ｂは補間後の軌跡点を示す。
【０１３３】
図１９Ａに示す例では、圧縮後の三つの軌跡点がある。この三つの軌跡点を含む時空間領域が検索された場合、三つの圧縮点を返してもよいが、圧縮点間を補間した点を返してもよい。例えば、移動軌跡圧縮補間パラメータ１２６の補間頻度Ｈｚ１が２Ｈｚである場合、圧縮時に用いた近似線で圧縮点間を結び、その近似線上を時空間において０．５秒進んだ毎に補間点を求めることができる。これにより、移動軌跡圧縮処理によって減らしたデータ量をユーザが望む細かさまで補間することができる。移動軌跡補間処理の詳細は、図２５を用いて後述する。
【０１３４】
図２０は、第２の実施例の代表的な移動軌跡圧縮補間パラメータ１２６の例を示す。
【０１３５】
移動軌跡圧縮補間パラメータ１２６は、軌跡圧縮ルール、軌跡圧縮下限ルール、圧縮率、圧縮精度及び補間頻度を含む。軌跡圧縮ルールは、近似線を生成する方法を定め、例えば、圧縮なし、一次関数、二次関数を選択可能である。軌跡圧縮下限ルールは、圧縮処理を終了するための条件の種類を定め、例えば、圧縮率、圧縮精度を選択可能である。圧縮率及び圧縮精度は、圧縮処理を終了するための条件となる、具体的な値である。補間精度は、補間点を設定する間隔を定める。
【０１３６】
移動軌跡圧縮補間パラメータ１２６は、ＣＳＶ形式などのファイルで入力されても、ＣＵＩ又はＧＵＩを用いてインタラクティブに入力されてもよい。また、時空間データ管理システムに予めデフォルト値を設定して、ユーザが入力しない場合はデフォルト値を用いてもよい。
【０１３７】
図２１は、第２の実施例の時空間データ移行部１３４によって実行されるデータ移行処理のフローチャートである。
【０１３８】
第１の実施例では、同じ時空間ＩＤを持つデータを圧縮した圧縮データ３０４を登録したが、第２の実施例では、軌跡圧縮部１７００が圧縮データ３０４から移動軌跡を圧縮した軌跡圧縮データ１７０１を生成し、軌跡圧縮データを登録する点が特徴である。なお、第１の実施例と同じ構成には、同じ符号を付し、説明を省略する。
【０１３９】
軌跡圧縮部１７００は、移動軌跡圧縮補間パラメータ１２６を参照して、パラメータに従って軌跡を圧縮し、軌跡圧縮データ１７０１を生成する。軌跡圧縮処理は、図２２を用いて後述する。
【０１４０】
その後、圧縮データ登録部３０６は、生成された軌跡圧縮データ１７０１を時空間圧縮データ１１１に登録する。また、二次記憶時空間索引データ作成部３０５は、生成された軌跡圧縮データ１７０１から二次記憶時空間索引データ１１２を作成する。さらに、時空間ＩＤ管理データ作成部３０７は、軌跡圧縮データ１７０１から時空間ＩＤ管理データ１２２を作成する。
【０１４１】
図２２は、第２の実施例の移動軌跡圧縮処理のフローチャートである。
【０１４２】
まず、処理２３００で圧縮データ３０４を読み込む。処理２３０１で移動軌跡圧縮補間パラメータ１２６を読み込む。処理２３０２で軌跡の始点及び終点を軌跡圧縮データに登録する。処理２３０４で移動軌跡グループ圧縮処理を引数（１、Ｎ）で呼び出す。ここで、Ｎは圧縮データの軌跡点の総数である。
【０１４３】
図２３は、第２の実施例の移動軌跡グループ圧縮処理のフローチャートである。
【０１４４】
移動軌跡グループ圧縮処理は、引数（ｉｓｔ，ｉｅｎｄ）が入力されると、ｉｓｔからｉｅｎｄの間の軌跡点を圧縮する。まず、処理２４００では、軌跡点ｉｓｔ及び軌跡点ｉｅｎｄを近似線で結んだ場合、ｉｓｔ＜ｉ＜ｉｅｎｄを満たす軌跡点ｉの各々と近似線との誤差（距離）が、移動軌跡圧縮補間パラメータ１２６に設定されている圧縮精度より小さいかを判定する。
【０１４５】
判定が真であれば、移動軌跡グループ圧縮処理を終了する。一方、判定が偽であれば、処理２４０１において、ｉｓｔ＜ｉ＜ｉｅｎｄを満たす軌跡点ｉのうち、誤差の最大値を与える軌跡点ｉｍａｘを求め、軌跡点ｉｍａｘを軌跡圧縮データに登録する。処理２４０２において、移動軌跡グループ圧縮処理２３０２を引数（ｉｓｔ、ｉｍａｘ）で呼び出す。さらに、処理２４０３において、移動軌跡グループ圧縮処理２３０２を引数（ｉｍａｘ、ｉｅｎｄ）で呼び出す。その後、移動軌跡グループ圧縮処理を終了する。
【０１４６】
なお、説明を簡単にするため、軌跡圧縮ルールが一次関数（近似線が直線）であり、圧縮点だけを記録する例を説明したが、軌跡圧縮ルールが二次以上の関数である場合、当該関数で表される近似線を生成すればよい。この場合、軌跡圧縮データについて、時刻及び空間の情報、及び、多項式の係数（ｔ１，ｘ１，ｙ１，ｃ１１，ｃ２１）を記録すればよい。また、軌跡圧縮ルールが圧縮無しの場合、圧縮は行わない。
【０１４７】
また、図２３に示す移動軌跡グループ圧縮処理では、軌跡圧縮下限ルールに圧縮精度を指定した例を示したが、圧縮率を指定した場合、元の軌跡点の数と圧縮後の軌跡点の数との比が圧縮率Ｃｍｐ１以下になるように引数を設定し、移動軌跡グループ圧縮処理を実行する。
【０１４８】
図２４は、第２の実施例の二次記憶検索部４０６によって実行される検索処理のフローチャートである。
【０１４９】
第１の実施例では、概略判定及び詳細判定を実行して、二次記憶装置１１０に格納されている時空間圧縮データを、そのまま検索したが、第２の実施例では、移動軌跡を補間してデータを補う処理を行う点が特徴である。なお、第１の実施例と同じ構成には、同じ符号を付し、説明を省略する。
【０１５０】
移動軌跡補間部１８０１は、詳細判定部６０４から出力された詳細判定結果１８００を読み込み、移動軌跡圧縮補間パラメータ１２６の軌跡圧縮ルール及び補間頻度に従って、データを補間し、補間された結果を二次記憶検索結果４０７として出力する。移動軌跡補間処理の詳細は、図２５を用いて後述する。
【０１５１】
図２５は、第２の実施例の移動軌跡補間処理のフローチャートである。
【０１５２】
処理２５００では、詳細判定結果１８００を読み込む。処理２５０１では、移動軌跡圧縮補間パラメータ１２６を読み込む。処理２５０２では、パラメータｎを初期値１に設定し、詳細判定結果１８００の中で最も古い時刻のデータを選択する。処理２５０３では、ｎ番の圧縮点及びｎ＋１番の圧縮点を選択する。処理２５０４では、移動軌跡圧縮補間パラメータ１２６の軌跡圧縮ルールに従って、ｎ番の圧縮点間とｎ＋１番の圧縮点との間の近似線を求める。
【０１５３】
処理２５０５では、求められた近似線上で補間頻度Ｈｚ１に従って補間点を求める。処理２５０６では、全ての圧縮点間の処理が終わったかを判定する。全ての圧縮点間の処理が終わったら、移動軌跡補間処理を終了する。一方、一部の圧縮点間の処理が終わっていなければ、処理２５０７でｎに１を加え、処理２５０３に戻る。
【０１５４】
以上に説明したように、第２の実施例では、時空間データを間引くデータ圧縮処理によってデータ量を削減した後、主記憶装置から二次記憶装置へデータを移行するので、データの格納効率及び検索効率を向上することができる。
【０１５５】
また、圧縮率、圧縮精度によって圧縮処理を制御するので、ユーザが望む程度の圧縮をすることができる。
【０１５６】
また、圧縮されたデータを補間するので、ユーザが望む粒度でデータを提示することができる。
【０１５７】
＜第３の実施例＞
以下に、本発明の第３の実施例の構成について説明する。
【０１５８】
第３の実施例は、第１の実施例の構成に加え、時空間の軌跡データを可視化することを特徴とする。
【０１５９】
図２６は、第３の実施例の時空間データ管理システムのハードウェア構成を示すブロック図である。
【０１６０】
本実施例の時空間データ管理システムは、時空間データ可視化部１３７を有する。なお、第３の実施例の時空間データ管理システムと同じ構成には、同じ符号を付し、説明を省略する。
【０１６１】
図２７は、第３の実施例の時空間データ可視化部１３７が生成する画面２７０５の一例を説明する図である。図２７に示す画面２７０５は、時空間のデータをディスプレイ等の出力装置１５０にリアルタイムに表示する。
【０１６２】
図２７に示す画面は、地図、衛星写真、航空写真、ストリートビュー等の背景を表示するパネル２７００の上にオブジェクト２７０１の位置を表示する。また、パネル２７００上には、時刻２７０２を表示する。パネル２７００に表示される時刻はタイムスライダー２７０３を用いて変更するこができる。また、パネル２７００はマウス、タッチパネル等の操作によって拡大、縮小、移動、回転ができるとよい。
【０１６３】
さらに、ボタン２７０４の操作によってリアルタイムモードに切り替えることが可能であり、リアルタイムモードは、本実施例の時空間データ管理システムに含まれる最新のデータを表示する。このとき、タイムスライダーのバーは動的に現在時刻を示す場所に移動する。
【０１６４】
図２８は、第３の実施例の時空間データ可視化部１３７が生成する画面２８０５の他の一例を説明する図である。図２８に示す画面２８０５は、補間された時空間データをディスプレイ等の出力装置１５０に表示する。
【０１６５】
図２８に示す画面例は、図２７に示す画面例と異なり、表示する時間幅を、マウス、タッチパネル等の操作によって変更することができる。時間幅が変更されると、スクロールバー２８０３上のスライダの幅が変化し、時刻範囲２８０２の表示も変わる。
【０１６６】
また、表示時刻範囲内の一つのオブジェクトの複数のデータを表示し、矢印２８０６で移動の方向を表示してもよい。このとき、実データの表示２８０１と補間されたデータの表示２８０７の態様を変えることによって、ユーザがデータの種類を確認できるようにしてもよい。このとき、表示切り替えボタン２８０８の操作によって、実データ、補間データを表示するかを選択可能としてもよい。
【０１６７】
さらに、ボタン２８０４の操作によってリアルタイムモードに切り替えることが可能でもよい。
【０１６８】
以上に説明したように、第３の実施例では、時空間データを分かりやすくユーザに提示することができる。
【０１６９】
以上に説明した第１から第３の実施例では、時空間データを格納する領域を一つの主記憶装置１２０及び一つの二次記憶装置１１０の各々に設けたが、本発明は、この構成に限定されたものではなく、主記憶装置１２０上の記憶領域及び／又は二次記憶装置上の記憶領域が複数であるなど、いかなる構成でもよい。また、各実施例では、二つの記憶領域間でデータを移行するが、三つ以上の記憶領域間で多段階的にデータを移行してもよい。また、各実施例では、一方向にデータを移行する例を説明したが、一般的なキャッシュ技術のように、検索頻度が高い時空間データを主記憶装置１２０に格納してもよい。
【０１７０】
以上、本発明を添付の図面を参照して詳細に説明したが、本発明はこのような具体的構成に限定されるものではなく、添付した請求の範囲の趣旨内における様々な変更及び同等の構成を含むものである。
【図１】
2014073081.tif 000003
【図２】
2014073081.tif 000004
【図３】
2014073081.tif 000005
【図４】
2014073081.tif 000006
【図５】
2014073081.tif 000007
【図６】
2014073081.tif 000008
【図７】
2014073081.tif 000009
【図８】
2014073081.tif 000010
【図９】
2014073081.tif 000011
【図１０】
2014073081.tif 000012
【図１１】
2014073081.tif 000013
【図１２】
2014073081.tif 000014
【図１３】
2014073081.tif 000015
【図１４】
2014073081.tif 000016
【図１５Ａ】
2014073081.tif 000017
【図１５Ｂ】
2014073081.tif 000018
【図１６Ａ】
2014073081.tif 000019
【図１６Ｂ】
2014073081.tif 000020
【図１７】
2014073081.tif 000021
【図１８Ａ】
2014073081.tif 000022
【図１８Ｂ】
2014073081.tif 000023
【図１９Ａ】
2014073081.tif 000024
【図１９Ｂ】
2014073081.tif 000025
【図２０】
2014073081.tif 000026
【図２１】
2014073081.tif 000027
【図２２】
2014073081.tif 000028
【図２３】
2014073081.tif 000029
【図２４】
2014073081.tif 000030
【図２５】
2014073081.tif 000031
【図２６】
2014073081.tif 000032
【図２７】
2014073081.tif 000033
【図２８】
2014073081.tif 000034
【国際調査報告】
2014073081.tif 000035
2014073081.tif 000036