(57)【要約】【課題】データをそれがもつ時区間あるいは空区間とともに蓄積した履歴データからの検索処理時間を大幅に短縮する。【解決手段】履歴データの蓄積は、データがもつ時区間あるいは空区間を重なりの無い区間領域占有子Ａ，Ｂ，Ｃとそれに付属するデータの組に変換すると共に、区間領域占有子を始端・終端とした部分木Ｔ１〜Ｔ４に分割して管理する。  履歴データの検索は、検索条件として入力された時区間あるいは空区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める時区間あるいは付属するデータを得る。【選択図】  図２
2005196514.tif 000002
【特許請求の範囲】
【請求項１】
人や物の位置、状態などの変化の履歴データを時区間とともに蓄積しておき、検索条件として入力された任意の区間と重なりをもつデータを前記蓄積データ中から検索する履歴データの管理・検索方法であって、
前記履歴データの蓄積は、前記データがもつ時区間を重なりの無い区間領域占有子とそれに付属するデータの組に変換すると共に、該区間領域占有子を始端・終端とした部分木に分割しておき、
前記履歴データの検索は、検索条件として入力された時区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める時区間あるいは付属するデータを得ることを特徴とする履歴データの管理・検索方法。
【請求項２】
人や物の位置、状態などの変化の履歴データを空区間とともに蓄積しておき、検索条件として入力された任意の区間と重なりをもつデータを前記蓄積データ中から検索する履歴データの管理・検索方法であって、
前記履歴データの蓄積は、前記データがもつ空区間を重なりの無い区間領域占有子とそれに付属するデータの組に変換すると共に、該区間領域占有子を始端・終端とした部分木に分割しておき、
前記履歴データの検索は、検索条件として入力された空区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める空区間あるいは付属するデータを得ることを特徴とする履歴データの管理・検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、システムが管理する人や物の位置、状態などの変化の履歴を蓄積しておき、この蓄積データから時区間条件や空区間（空間内の区間）条件に重なりをもつ（条件に合う）データを検索、抽出するための履歴データの管理・検索方法に関する。
【背景技術】
【０００２】
開始時刻と終了時刻の組からなる時区間とともにデータを管理しておき、あるいは空間座標軸上の２点の組からなる空区間とともにデータを管理しておき、それらの蓄積データ中から、入力された任意の１区間と重なりを持つデータを抽出して返す処理の実現方法として、検索条件の始端・終端を、蓄積データの始端・終端と個々に比較することにより、区間の重なりを判定し、重なりをもつデータを目的のデータとして抽出するデータ管理・提供方法が提案されている（例えば、特許文献１参照）。
【０００３】
この方法によるデータ抽出には、例えば、図５に示すように、始端Ｄ１ｓと終端Ｄ１ｅになるデータＤ１、始端Ｄ２ｓと終端Ｄ２ｅになるデータＤ２、…、始端ＤＮｓと終端ＤＮｅになるデータＤＮからなるＮ個の履歴データに対して、始端Ａｓと終端Ａｅになる検索条件に重なりをもつデータを検索する場合、検索条件の始端Ａｓと終端Ａｅを、蓄積データの始端Ｄ１ｓ，Ｄ２ｓ，…，ＤＮｓと個々に比較し、さらに終端Ｄ１ｅ，Ｄ２ｅ，ＤＮｅと個々に比較することにより、重なりの有るデータを抽出する。
【特許文献１】特開平１０−１４３５３１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の検索方法は、個々の蓄積データについて個別に判定を行うため、条件を満たす全ての蓄積データを抽出する処理には、検索に要する時間が長くなり、高速検索が難しくなる。
【０００５】
本発明の目的は、時区間あるいは空区間とともに蓄積した履歴データから検索条件に重なりをもつデータを抽出するための検索処理時間を大幅に短縮できる履歴データの管理・検索方法を提供することにある。
【課題を解決するための手段】
【０００６】
本発明は、前記の課題を解決するため、開始時刻と終了時刻の組からなる時区間とともにデータを管理している場合、あるいは空間座標軸上の２点の組からなる空区間とともにデータを管理している場合、予めそれらを重なりの無い区間領域占有子とそれに付属するデータの組に変換すると共に、区間領域占有子を始端・終端としたＢ木（バランス・ツリー）、２分木等の部分木に分割管理しておき、検索条件として入力された時区間あるいは空区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める時区間、空区間、あるいは付属するデータを得るようにしたもので、以下の方法を特徴とする。
【０００７】
（１）人や物の位置、状態などの変化の履歴データを時区間とともに蓄積しておき、検索条件として入力された任意の区間と重なりをもつデータを前記蓄積データ中から検索する履歴データの管理・検索方法であって、
前記履歴データの蓄積は、前記データがもつ時区間を重なりの無い区間領域占有子とそれに付属するデータの組に変換すると共に、該区間領域占有子を始端・終端とした部分木に分割しておき、
前記履歴データの検索は、検索条件として入力された時区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める時区間あるいは付属するデータを得ることを特徴とする。
【０００８】
（２）人や物の位置、状態などの変化の履歴データを空区間とともに蓄積しておき、検索条件として入力された任意の区間と重なりをもつデータを前記蓄積データ中から検索する履歴データの管理・検索方法であって、
前記履歴データの蓄積は、前記データがもつ空区間を重なりの無い区間領域占有子とそれに付属するデータの組に変換すると共に、該区間領域占有子を始端・終端とした部分木に分割しておき、
前記履歴データの検索は、検索条件として入力された空区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める空区間あるいは付属するデータを得ることを特徴とする。
【発明の効果】
【０００９】
以上のとおり、本発明によれば、開始時刻と終了時刻の組からなる時区間とともにデータを管理している場合、あるいは空間座標軸上の２点の組からなる空区間とともにデータを管理している場合、予めそれらを重なりの無い区間領域占有子に変換して全ての始端・終端をＢ木（バランス・ツリー）等の部分木に分割管理しておき、検索条件として入力された時区間あるいは空区間の始端・終端について、個別に条件を満たす区間領域占有子を検索し、検索結果の共通集合から、求める時区間、空区間、あるいは付属するデータを得るようにしたため、蓄積データ中から、入力された任意の１区間と重なりを持つデータについて従来のように個々に判定することなく、一括して判定できるため、検索処理時間を大幅に短縮できる。
【発明を実施するための最良の形態】
【００１０】
（実施形態１）
本実施形態は、時間軸上でのデータ蓄積およびデータ検索処理方法である。本実施形態によるデータの蓄積および検索処理の実現には、時空間上の領域を管理するために直方体［ｘ１．ｘ２］、［ｙｌ，ｙ２］、［ｚｌ，ｚ２］、［ｔ１，ｔ２］（以下、区間領域占有子と呼ぶ。）を用いる。［ｘ１，ｘ２］、［ｙ１，ｙ２］、［ｚ１，ｚ２］はそれぞれ、Ｘ軸、Ｙ軸、Ｚ軸上の閉空区間、［ｔ１．ｔ２］は時間軸上の閉時区間を表す。
【００１１】
まず、データの蓄積には、蓄積するデータの時区間が相互に重ならないように管理する。このため、新たに蓄積しようとするデータが既に蓄積されているデータと重なりを持つ場合には、重なりがなくなるよう区間領域占有子を分割し、時間軸上に時区間の始端・終端が交互に並ぶようなデータ構造に変換する。
【００１２】
例えば、図１に示すように、始端「３時」と終端「１２時」になる履歴データＤｘが既に蓄積されており、このデータベースに始端「１時」と終端「５時」になるデータＤｙを新たに追加する場合、両データＤｘ，Ｄｙの時区間が重なる「３時」と「５時」で両データをそれぞれ分割し、始端「１時」と終端「３時」の区間領域占有子ＡをもつデータＤAと、始端「３時」と終端「５時」の区間領域占有子ＢをもつデータＤBと、始端「５時」と終端「１２時」の区間領域占有子ＣをもつデータＤCとして蓄積する。
【００１３】
次に、蓄積されたデータについて、時区間の始端・終端を全て集めて、これをＢ木（バランス・ツリー）、２分木等の部分木に分割して管理する。このとき、一組の始端・終端には同一の区間領域占有子を割り当て、これを介して任意の付属するデータの取り出しを可能にする。
【００１４】
例えば、図２の（ａ）に示すように、履歴データとして、区間領域占有子Ａに属するデータ群と、区間領域占有子Ｂに属するデータ群と、区間領域占有子Ｃに属するデータ群が蓄積されている場合、区間領域占有子Ａに属するデータ群の終端Ａｅはそれぞれ「３時」になり、区間領域占有子Ｂに属するデータ群の終端Ｂｓはそれぞれ「３時」になる。この区間領域占有子を基に作成したＢ木構造は、図２の（ｂ）に示すように、節点（ノード）Ｔ1の下位には「３時」を終端Ａｅとし、「１時」を始端Ａｓとする節点Ｔ2をもち、「３時」を始端Ｂｓとし、「５時」を終端Ｂｅとする節点Ｔ3をもつ。同様に、節点Ｔ3の下位には「５時」を終端Ｃｓとし、「１２時」を終端Ｃｅとする節点Ｔ4をもつＢ木構造になる。
【００１５】
以上のようなデータ構造で管理される履歴データに対し、データ検索は、検索条件として１組の始端・終端からなる時区間を与え、それぞれについて条件を満足する区間領域占有子を検索し、両条件を満足するデータの共通集合をとって検索結果とする。
【００１６】
例えば、図３に示すように、始端「３．５時」、終端「７時」とする検索条件によるデータ検索には、始端「３．５時」の条件を満足する端点は「Ｂｅ，Ｃｓ，Ｃｅ」、終端「７時」の条件を満足する端点は「Ａｓ，Ａｅ，Ｂｓ，Ｂｅ，Ｃｓ」になり、両条件を満足する端点「Ｂｅ，Ｃｓ」をもつデータが検索結果として得られる。
【００１７】
なお、求める解が、指定時区間中の空間内の移動領域であれば、図４に例を示すように、検索結果の区間領域占有子から直接和集合をとることにより求められる。求める解がその他のデータである場合は、区間領域占有子に付属するデータを取り出して解とする。
【００１８】
したがって、本実施形態によれば、データ検索には入力された任意の区間と重なりを持つデータについて従来のように個々に判定することなく、一括して判定できるため、検索処理時間を大幅に短縮できる。
【００１９】
（実施形態２）
本実施形態は、空間座標軸上でのデータ蓄積およびデータ検索処理方法である。  本実施形態は、実施形態１と同様に、データの蓄積および検索処理の実現には、空区間上の領域を管理するために区間領域占有子を用い、蓄積するデータの空区間が相互に重ならないように管理する。このため、新たなデータが重なりを持つ場合には、重なりがなくなるよう占有子を分割し、空間座標軸上に空区間の始端・終端が交互に並ぶような構造とする。
【００２０】
そして、空区間の始端・終端を全部集めて、これをＢ木（バランス・ツリー）などで管理する。このとき、一組の始端・終端には同一の区間領域占有子を割り当て、これを介して任意の付属するデータの取り出しを可能にする。
【００２１】
また、検索条件として１組の始端・終端からなる空区間を与え、それぞれについて条件を満足する区間領域占有子を検索し、両検索結果の共通集合をとって検索結果とする。
【００２２】
求める解が、指定空区間中を移動していた時区間であれば、検索結果の区間領域占有子から直接和集合をとることにより求める。求める解がその他のデータである場合は、区間領域占有子に付属するデータを取り出して解とする。
【００２３】
したがって、本実施形態においても、検索処理時間を大幅に短縮できる。
【図面の簡単な説明】
【００２４】
【図１】実施形態における区間領域占有子が重ならないように分割した例。
【図２】実施形態における時区間の始端・終端、および時区間に付属するデータの区間領域占有子を用いた管理データの例。
【図３】実施形態における時区間条件による検索例。
【図４】実施形態における検索結果の区間領域占有子から空間内の移動領域を求めた例。
【図５】区間の重なり判定の説明図（従来）。
【図１】
2005196514.tif 000003
【図２】
2005196514.tif 000004
【図３】
2005196514.tif 000005
【図４】
2005196514.tif 000006
【図５】
2005196514.tif 000007