(57)【特許請求の範囲】
【請求項１】
事前決定された時間範囲を複数の時間間隔に分割するように構成された時間間隔分割手段と、
現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するように構成された第１索引生成手段と、
現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するように構成された第２索引生成手段とを備え、
前記第２レベル索引は、前記第１レベル索引よりも細かい粒度を有する
ことを特徴とするデータ索引付けシステム。
【請求項２】
前記第１索引生成手段は、各葉ノードが部分空間索引を伴うＢ＋木を用いて、前記時間間隔索引を生成するように構成される
ことを特徴とする請求項１に記載のデータ索引付けシステム。
【請求項３】
前記第１索引生成手段は、Ｒ木を用いて前記部分空間索引を生成するように構成される
ことを特徴とする請求項１に記載のデータ索引付けシステム。
【請求項４】
前記第２索引生成手段は、Ｒ木またはグリッド索引を用いて、レコードレベル索引である前記第２レベル索引を生成するように構成される
ことを特徴とする請求項１に記載のデータ索引付けシステム。
【請求項５】
時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するように構成されたデータ記憶手段を備える
ことを特徴とする請求項１に記載のデータ索引付けシステム。
【請求項６】
前記時間間隔分割手段は、事前決定された時間範囲を、事前知識に基づいて、データが複数の時間間隔内で均一に分布することを確保しつつ、複数の時間間隔に分割するように構成される
ことを特徴とする請求項１に記載のデータ索引付けシステム。
【請求項７】
前記時間間隔分割手段は、各時間間隔についてデータ分割の均一性とデータ層数を計算し、特定の時間間隔のデータ分割の均一性が第１の閾値を上回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を上回る場合には、当該特定の時間間隔をさらに多くの時間間隔に分割し、逆に特定の時間間隔のデータ分割の均一性が第１の閾値を下回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を下回る場合には、当該特定の時間間隔を隣接する時間間隔と結合するように構成される
ことを特徴とする請求項６に記載のデータ索引付けシステム。
【請求項８】
コンピュータが、事前決定された時間範囲を複数の時間間隔に分割するステップと、
コンピュータが、現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するステップと、
コンピュータが、現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するステップとを含み、
前記第２レベル索引は、前記第１レベル索引よりも細かい粒度を有する
ことを特徴とするデータ索引付け方法。
【請求項９】
前記時間間隔索引は、各葉ノードが部分空間索引を伴うＢ＋木を用いて生成される
ことを特徴とする請求項８に記載のデータ索引付け方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はクラウドコンピューティングに関し、特に、データ索引付けシステム、および、データ索引付け方法に関する。
【背景技術】
【０００２】
ＲＦＩＤ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ：無線自動識別）やＧＰＳ（衛星利用測位システム）等の技術の発達に伴い、ＩＯＴ（Ｉｎｔｅｒｎｅｔ  ｏｆ  Ｔｈｉｎｇｓ：モノのインターネット）が急速にかつ広範に適用されるようになってきた。ＩＯＴ環境では検出された数百万ものオブジェクト（モノ）が定期的にデータを生成するため、従来のリレーションデータベースにおいては、不十分なシステムスループットがスケーラビリティ上のボトルネックとなる。
【０００３】
クラウドデータ管理システムは、その高度なスケーラビリティと同時実行性により、ＩＯＴデータ管理の有効な解決法と目されている。クラウドデータ管理システムでは、非行キーの場合はフルテーブルスキャンが必要であるが、行キー内では地点クエリと範囲クエリを効率的に実行することができる。クエリの効率はＭａｐ−Ｒｅｄｕｃｅ技法を利用して改善できるが、クエリの選択速度が低い場合はパフォーマンスが低下する。
【０００４】
典型的なＩＯＴデータは多次元特性を有しており、時間と空間の次元に加えて他の数次元の情報も含む。また、ＩＯＴデータに対するクエリは、時間と空間に基づく多次元クエリであるのが一般的である。そのため、ＩＯＴの適用環境では、高速シグナル次元クエリに加えて、効率的な多次元クエリが提供されるのが望ましい。
【０００５】
ＩＯＴデータのもう一つの特性は、高頻度で更新されることである。ＩＯＴ環境においては、監視対象オブジェクトは特定の時間間隔で新しいデータを定期的に生成するのが典型的であり、データは頻繁に更新される。例えば、監視対象オブジェクト数が多く、データサンプリングが高頻度で行われる場合には、データの同時実行性がきわめて高いため、データ管理システムは高いスループットを持つことが要求される。
【０００６】
現在のところ、クラウドシステムの多次元データ索引付けスキームとしては、多次元データの索引付けおよびクエリ専用のＲＴ−ＣＡＮが提案されている。ＲＴ−ＣＡＮ索引付けスキームは、Ｒ木に基づく２層索引付けスキームであり、複数の属性に対する地点クエリと範囲クエリに対応している。各ストレージノードでは、まずローカルデータに関するＲ木索引が作成され、続いて特定の索引ノード選択ポリシーに基づいて各ローカル索引からいくつかのノードが選択されて、ローカル索引へと配分される。また、クエリ速度を高め、システムのスケーラビリティを確保するために、グローバル索引内においては多次元クエリに対応したカバレージネットワークであるＣＡＮネットワークが採用されているほか、索引ノード選択のために、コストモデルをベースとする適応型の調整ポリシーが使用されている。
【０００７】
具体的には、ＲＴ−ＣＡＮ索引付けスキームは概して、１）クライアントから新たなデータ挿入要求を受信したら、クラウドストレージシステムインタフェースを介して対応するストレージノードを検出し、データをノードに記憶する動作と、２）ストレージノードで生成されたＲ木構造内のローカル索引を更新する動作と、３）更新したローカル索引をグローバル索引に同期化させる動作、とを含む。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、ＲＴ−ＣＡＮスキームは、木のバランスを保つために、データ挿入プロセス中常に、索引ノードに対して分割調整を実行する必要がある（データ挿入が発生する都度、ローカル索引の更新がトリガされ、それによってグローバル索引が影響を受ける）。そのため、特にデータ挿入が高頻度で実行される用途の場合には、索引保守コストが非常に高くなり、システムスループットが大幅に低下する結果となる。よって、このスキームはＩＯＴには適用できない。
【０００９】
従って、ＩＯＴに適応可能で、かつＩＯＴ内において高頻度で更新される多次元データの演算を高スループットで達成することのできる、データ索引付けシステムおよび方法が必要とされている。
【００１０】
本発明によれば、高頻度のデータ更新と効率的なデータクエリの両方に対応できる解決法が提供される。本発明の主要概念は次の２点にある。第一に、ＩＯＴ用途において、監視対象オブジェクトのデータは一旦生成されると変化しない。そして第二に、監視対象オブジェクトの空間的な分布はほとんどの場合均一ではなく、しかも時間の経過に伴って変動する可能性がある。そのため、時間次元のデータを現時間間隔のデータと履歴時間間隔のデータとに分割して、データを異なる時間間隔において異なる粒度で索引付けすることにより、索引の更新数と索引保守コストとを削減することが可能である。さらに、時間と空間におけるデータの分布が不均一になりそうであれば、データを分割することができる。
【課題を解決するための手段】
【００１１】
本発明の第１の態様によれば、データ索引付けシステムが提供される。当該システムは、事前決定された時間範囲を複数の時間間隔に分割するように構成された時間間隔分割手段と、現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するように構成された第１索引生成手段と、現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するように構成された第２索引生成手段とを含む。第２レベル索引は、第１レベル索引よりも細かい粒度を有する。
【００１２】
第１索引生成手段は、各葉ノードが部分空間索引を伴うＢ＋木を用いて、時間間隔索引を生成するように構成されるのが望ましい。
【００１３】
第１索引生成手段は、Ｒ木を用いて部分空間索引を生成するように構成されるのが望ましい。
【００１４】
第２索引生成手段は、Ｒ木またはグリッド索引を用いて、レコードレベル索引である第２レベル索引を生成するように構成されるのが望ましい。
【００１５】
当該システムは、時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するように構成されたデータ記憶手段をさらに含むのが望ましい。
【００１６】
時間間隔分割手段は、事前決定された時間範囲を、事前知識に基づいて、データが複数の時間間隔内で均一に分布することを確保しつつ、複数の時間間隔に分割するように構成されるのが望ましい。
【００１７】
時間間隔分割手段はさらに、各時間間隔についてデータ分割の均一性とデータ層数を計算し、特定の時間間隔のデータ分割の均一性が第１の閾値を上回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を上回る場合には、当該特定の時間間隔をさらに多くの時間間隔に分割し、逆に特定の時間間隔のデータ分割の均一性が第１の閾値を下回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を下回る場合には、当該特定の時間間隔を隣接する時間間隔と結合するように構成されるのが望ましい。
【００１８】
本発明の他の態様によれば、データ索引付け方法が提供される。当該方法は、コンピュータが、事前決定された時間範囲を複数の時間間隔に分割するステップと、コンピュータが、現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するステップと、コンピュータが、現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するステップとを含む。第２レベル索引は、第１レベル索引よりも細かい粒度を有する。
【００１９】
時間間隔索引は、各葉ノードが部分空間索引を伴うＢ＋木を用いて生成されるのが望ましい。
【００２０】
部分空間索引はＲ木を用いて生成されるのが望ましい。
【００２１】
レコードレベル索引である第２レベル索引は、Ｒ木またはグリッド索引を用いて生成されるのが望ましい。
【００２２】
当該方法は、時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するステップをさらに含むのが望ましい。
【００２３】
分割ステップは、データが複数の時間間隔内で均一に分布するように、事前知識に基づいて、事前決定された時間範囲を複数の時間間隔に分割する動作を備えるのが望ましい。
【００２４】
分割ステップはさらに、各時間間隔についてデータ分割の均一性とデータ層数を計算する動作と、特定の時間間隔のデータ分割の均一性が第１の閾値を上回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を上回る場合には、当該特定の時間間隔をさらに多くの時間間隔に分割する動作と、逆に特定の時間間隔のデータ分割の均一性が第１の閾値を下回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を下回る場合には、当該特定の時間間隔を隣接する時間間隔と結合する動作とを備えるのが望ましい。
【発明の効果】
【００３０】
本発明によれば、現在データと履歴データに対して、異なる索引付け粒度で索引を生成することが可能である。これにより、更新が高頻度で行われる場合には、索引保守コストを大幅に削減することができる。さらに、本発明のデータ分割ポリシーによって、ストレージノード内のデータは、物理記憶領域内で均一にかつ互いに隣接するように分布されるので、クエリプロセス中の無効なスキャンを削減させ、クエリ性能を向上させることができる。
【図面の簡単な説明】
【００３１】
本開示の上記および他の特徴は、下記の詳細な説明と以下の図面を併せて参照することでより明らかとなるであろう。
【図１】本発明の第１の実施例によるデータ索引付けシステムのブロック図である。
【図２】本発明の第１の実施例による索引付け構造の概略図である。
【図３】本発明の第２の実施例によるデータ索引付けシステムのブロック図である。
【図４】本発明の一実施例によるデータ記憶手段の動作を示す概略図である。
【図５】本発明の第３の実施例によるデータ索引付け方法のフローチャートである。
【図６】本発明の第４の実施例によるデータクエリ方法のフローチャートである。
【発明を実施するための形態】
【００３２】
本発明の原理と実装は、図面を参照しながら本発明の実施例の下記の説明を読むことによりさらに明らかになるであろう。本発明は下記の実施例に限定されないことに留意されたい。また、煩雑化を避けるため、本発明に無関係な周知の要素については説明を省略する。
【実施例１】
【００３３】
図１は、本発明の第１の実施例によるデータ索引付けシステム１０のブロック図である。図１に示すように、システム１０は、時間間隔分割ユニット１１０と第１索引生成ユニット１２０と第２索引生成ユニット１３０とを含む。以下では、システム１０の個々の手段の動作について詳述する。
【００３４】
時間間隔分割ユニット１１０は、事前決定された時間範囲を複数の時間間隔に分割するように構成されている。ＩＯＴデータの地域的分布は時間の経過に伴い変動するので、時間間隔分割ユニット１１０は時間次元のデータを、以下のようにいくつかの時間間隔（ＴＩＳ：ｔｉｍｅ  ｉｎｔｅｒｖａｌｓ）に分割することができる。
ＴＩＳ＝｛［ｔ１，ｔ２］，［ｔ２，ｔ３］，…，［ｔｉ−１，ｔｉ］，…｝，
ここで、［ｔｉ−１，ｔｉ）は左側が閉鎖され、右側が開放された時間間隔である。これらの時間間隔は、互いに重複しない。言うまでもなく、各時間間隔［ｔｉ−１，ｔｉ）は左側が開放され、右側が閉鎖された時間間隔とすることもできることは当業者には理解されるであろう。
【００３５】
時間間隔分割ユニット１１０は、事前決定された時間範囲を、事前知識に基づいて複数の時間間隔に分割することができる。時間間隔分割ユニット１１０は、データが複数の時間間隔内で均一に分布するように、事前知識に基づいて、事前決定された時間範囲を複数の時間間隔に分割することができる。例えば、移動中の車両を監視するという例示的な用途の場合であれば、分割動作を日単位（つまり、１日を事前決定された時間範囲として使用する）で実行して、日中を短い時間間隔に分割し、夜間を長い時間間隔に分割することが可能である。こうすることで、各時間間隔のデータ数を実質的に同じにすることができる。
【００３６】
時間間隔分割ユニット１１０が事前決定された時間範囲を複数の時間間隔に分割した後、第１索引生成ユニット１２０が現時間間隔内のデータ用の第１レベル索引（低粒度の索引）を生成する。第１レベル索引は、時間間隔索引と部分空間索引とを含む。本実施例においては、第１索引生成ユニット１２０は、様々なデータ構造を用いて、時間間隔用と部分空間用の索引をそれぞれ生成することができる。例えば、第１索引生成ユニット１２０は、Ｂ＋木を用いて時間間隔用の索引を生成し、Ｒ木を用いて部分空間用の索引を生成してもよい。
【００３７】
第２索引生成ユニット１３０は、現時間間隔後の１つの時間間隔において、現時間間隔内のデータ用の第２レベル索引（高粒度の索引）を生成するように構成される。本実施例においては、第２索引生成ユニット１３０は、様々なデータ構造を用いて第２レベル索引を生成することができる。例えば、第２索引生成ユニット１３０は、Ｒ木を用いて第２レベル索引を生成してもよい。
【００３８】
次に、図２を参照して、第１索引生成ユニット１２０と第２索引生成ユニット１３０の例示的動作について説明する。
【００３９】
図２は、本発明の第１の実施例による索引付け構造の概略図である。図２に示すように、索引付け構造の最初の２層はそれぞれ時間間隔索引と部分空間索引である。時間間隔索引と部分空間索引は、現時間間隔内のデータ用の索引（第１レベル索引）である。索引付け構造の第３層は、レコードレベルのグリッド索引、すなわち履歴時間間隔内のデータ用の索引（第２レベル索引）である。
【００４０】
以下では、現時間間隔を［ｔ１、ｔ２）とする。第１索引生成ユニット１２０は、現時間間隔［ｔ１、ｔ２）内のデータ用として、第１レベル索引を作成する（図２の第１層の索引）。ここで、現時間間隔内のすべてのデータは同じ時間間隔索引を有する。さらに、第１索引生成ユニット１２０は、２次元領域をいくつかの相補的で重複する長方形の部分空間に分割する。この分割は、例えばＢｕｃｋｅｔ  ＰＲ  ＫＤ木やＢｕｃｋｅｔ  ＰＲ４分木を用いて実行することができる。これらの長方形の部分空間は、各々１つの記憶領域に対応するようにしてもよい。また、これらの部分空間はＲ木を用いて索引付けしてもよい。このように、分割された部分空間に基づいて、現時間間隔内のデータ用の部分空間索引（図２の第２層の索引）を生成することができる。
【００４１】
次の時間間隔［ｔ２、ｔ３）が到来すると、直前の時間間隔［ｔ１、ｔ２）は履歴時間間隔となり、この時間間隔［ｔ２、ｔ３）が現時間間隔になる。同様に、第１索引生成ユニット１２０は上記のプロセスに従って、この時間間隔［ｔ２、ｔ３）内のデータ用の第１レベル索引を生成する。さらに、第２索引生成ユニット１３０は、履歴時間間隔［ｔ１、ｔ２）内のデータ用の第２レベル索引を作成する（図２の第３層の索引）。また、例えば、１つの領域内のデータクエリを迅速化するために、各領域用としてレコードレベルのローカル索引を生成することも可能である。ローカル索引は、Ｒ木またはグリッド索引の形式とすることができる。
【００４２】
図１を再度参照すると、時間間隔分割ユニット１１０は、分割結果が合理的か否かによって分割ポリシーを動的に調整できるのが望ましい。すなわち、時間間隔分割ユニット１１０は、事前決定された時間範囲を、データが複数の時間間隔内で均一に分布するよう、複数の時間間隔に分割するように構成することができる。
【００４３】
実際には、データは時間次元では単調に増加し、空間次元では特定の領域に固定されるのが一般的である。また、ＩＯＴデータは概して時間と空間において異なる分布パターンを有するので、時間と空間は別個のものと考えることができる。時間次元では、時間はデータの分布パターンに応じていくつかの時間間隔に分割される。ある特定の時間間隔内のデータは、例えばＢｕｃｋｅｔ  ＰＲ  ＫＤ木またはＢｕｃｋｅｔ  ＰＲ４分木を用いて、空間次元内で動的に分割できる。さらに、比較的高密度な空間の場合は、データが部分空間の間で均一に分布するように、複数回にわたって分割してもよい。
【００４４】
時間間隔分割ユニット１１０は、例えば日単位を採用して、毎日のデータを複数の時間間隔に分割（すなわち、１日を複数の時間間隔に分割）してもよい。時間間隔分割ユニット１１０は、以下のプロセス（動的データ分割）を実行することにより、データ分割を最適化するように構成できるのが望ましい。
【００４５】
１）まず、一日のデータレコードの総数Ｎが、特定用途のシナリオに従って推定される。ここでは、各部分空間はＳ個のレコードを含み、各時間間隔内のデータはＲ個の部分空間に均一に分割できると想定する。従って、１日は
【数１】
0005519762.tif 000002
個の時間間隔に分割され、これらはｔ１，ｔ２，…，ｔｋとして表わされる。
【００４６】
２）時間間隔ｔ１，ｔ２，…，ｔｋの各データは、Ｂｕｃｋｅｔ  ＰＲ  ＫＤ木を用いて空間的に分割される。木の深度が記録され、各部分空間のサイズが監視され、各時間間隔における各部分空間内のデータ量の分散が以下の式を用いて計算される。
【数２】
0005519762.tif 000003
ここで、Ｎｉは時間間隔ｔｉにおける部分空間数を表し、ｘｍはｔｉ番目の時間間隔におけるｍ番目の部分空間のサイズを表し、
【数３】
0005519762.tif 000004
は部分空間の平均サイズを表し、Ｄｉはｔｉ番目の時間間隔における部分空間のサイズの分散を表す。最後のＤｉは、時間間隔におけるデータ分割の均一度を反映する数値である。
【００４７】
３）時間間隔内での分割は、分散Ｄｉとデータ分割層数Ｄｅｐｉとに基づいて調整される。具体的には、Ｄｉが閾値を上回る場合、時間間隔におけるデータ分布は均一でないことを示す。また、Ｄｅｐｉが閾値を上回る場合は、時間間隔を短縮する必要があることも同時に示す。従って、時間間隔ｔｉは２つの時間間隔ｔｉ１およびｔｉ２に分割することができる。Ｄｉが閾値を下回る場合、データ分布は比較的均一であることを示す。また、Ｄｅｐｉが閾値を下回る場合は、ｔｉ番目の時間間隔内のデータ量が少なすぎるので、ｔｉ番目の時間間隔を隣接する時間間隔（ｔｉ−１またはｔｉ＋１）と結合できることも同時に示す。
【００４８】
４）時間間隔の分割と領域の分割がある程度の時間にわたって一定である場合には、分割ポリシーを固定して、動的分割を終了することができる。また、システム動作中に、データ分布を継続的に監視し、非均一なデータ分布が検出されたら動的データ分割を再度実行することも可能である。
【００４９】
本実施例によるシステムを使用すれば、索引保守のコストが削減されるので、ＩＯＴ用途における大量データの頻繁な更新に対応することができる。
【実施例２】
【００５０】
図３は、本発明の第２の実施例によるデータ索引付けシステム３０のブロック図である。図３に示すように、システム３０は、時間間隔分割ユニット３１０と第１索引生成ユニット３２０と第２索引生成ユニット３３０とデータ記憶ユニット３４０とを含む。図３の時間間隔分割ユニット３１０、第１索引生成ユニット３２０、第２索引生成ユニット３３０はそれぞれ、図１の時間間隔分割ユニット１１０、第１索引生成ユニット１２０、第２索引生成ユニット１３０と類似している。説明を簡素化するため、以下ではデータ記憶ユニット３４０についてのみ説明する。
【００５１】
データ記憶ユニット３４０は、時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するように構成されている。これにより、クエリプロセス中にスキャンする記憶領域の数が削減されるので、クエリ効率が向上する。
【００５２】
図４は、具体的に本発明の一実施例によるデータ記憶ユニット３４０の動作を示す概略図である。図４に示すように、事前決定された時間範囲はいくつかの時間間隔に分割され、各時間間隔内のデータは２次元空間内で分割されて、いくつかの部分空間を形成する。データ記憶ユニット３４０は、履歴時間間隔［ｔ０、ｔ３）内のデータを領域１と領域２に記憶し、現時間間隔［ｔ３、ｔ４）内のデータを領域ｍに記憶する。これらの記憶領域（領域１，領域２，…，領域ｍ）は物理的に隣接する記憶領域である。
【００５３】
時間と空間において隣接するデータは物理的に隣接する記憶領域に記憶されるため、データクエリにおけるこれらの記憶領域からの読み出しは高速となり、よって以下で（第４の実施例に関連して）詳細に説明するようにクエリ効率が向上する。
【００５４】
本実施例によるシステムを使用すれば、ＩＯＴ用途における大量データの頻繁な更新に対応できほか、ＩＯＴデータクエリプロセス中にスキャンすべき記憶領域の数が削減されるので、クエリ効率が向上する。
【実施例３】
【００５５】
図５は、本発明の第３の実施例によるデータ索引付け方法５０のフローチャートである。図５に示すように、方法５０はステップＳ５１０から開始する。
【００５６】
ステップＳ５２０において、事前決定された時間範囲が複数の時間間隔に分割される。事前決定された時間範囲は、データが複数の時間間隔内で均一に分布するように、事前知識に基づいて複数の時間間隔に分割することができる。分割ポリシーは、分割結果が合理的か否かによって動的に調整できるのが望ましい。
【００５７】
ステップＳ５３０において、現時間間隔内のデータ用として第１レベル索引（低粒度の索引）が生成される。第１レベル索引は、時間間隔索引と部分空間索引とを含む。時間間隔用と部分空間用の索引は、それぞれ様々なデータ構造を用いて生成することができる。例えば、時間間隔用の索引はＢ＋木を用いて生成し、部分空間用の索引はＲ木を用いて生成してもよい。
【００５８】
ステップＳ５４０において、現時間間隔の後の１つの時間間隔内で、現時間間隔内のデータ用の第２レベル索引（高粒度の索引）が生成される。第２レベル索引を生成するためには、例えばＲ木などの様々なデータ構造を用いて生成することができる。
【００５９】
最後に、方法５０はステップＳ５５０で終了する。
【００６０】
本実施例による方法を使用すれば、ＩＯＴ用途における大量データの頻繁な更新に対応できるほか、ＩＯＴデータクエリプロセス中にスキャンすべき記憶領域の数が削減されるので、クエリ効率が向上する。
【実施例４】
【００６１】
図６は、本発明の第４の実施例によるデータクエリ方法６０のフローチャートである。図６に示すように、方法６０はステップＳ６１０から開始する。
【００６２】
ステップＳ６２０において、クエリ対象データは現在データと履歴データのどちらであるかが判定される。
【００６３】
クエリ対象データが現在データの場合は、ステップＳ６３０において、第１レベル索引によってデータがクエリされる。第１レベル索引は、時間間隔索引と部分空間索引とを含む。
【００６４】
クエリ対象データが履歴データの場合は、第２レベル索引によってデータがクエリされる。第２レベル索引は、第１レベル索引よりも細かい粒度を有する。
【００６５】
方法６０においては、時間間隔索引をＢ＋木を用いて生成することができる。Ｂ＋木の各葉ノードは、Ｒ木を用いて生成可能な部分空間索引を伴う。さらに、第２レベル索引はＲ木またはグリッド索引を用いて生成することができる。第２レベル索引はレコードレベルの索引である。
【００６６】
方法６０において実行されるクエリのタイプは、地点クエリ、範囲クエリ、およびＫ最隣接クエリを含むが、これらに限定されるものではない。以下では、これら３タイプのクエリについて詳細に説明する。
・地点クエリ
【００６７】
Ｑ（ｔ，ｌａｔ，ｌｏｎ）は、時間、緯度、経度に関する地点クエリを表わすとする。ユーザがこの地点クエリを開始した後、まずクエリ対象地点が属する時間間隔が、時間間隔索引に基づいて時間ｔから特定される。続いて、クエリ対象地点の行キーが、時間間隔とその地点の緯度・経度の情報とから計算される。最後に、当該行キーに基づいてクエリ要求がクラスタに対して開始され、返された結果がｔ、ｌａｔ、ｌｏｎに基づいてフィルタリングされる。
【００６８】
地点クエリのプロセスは、以下のアルゴリズム１（疑似コード）のように記述できる。具体的には、１番目のコードラインは結果セットを初期化する。２番目のコードラインは、時間間隔索引に基づいて、時間ｔが属する時間間隔のシーケンス番号を計算する。３番目のコードラインは、Ｚ−ｏｒｄｅｒｉｎｇ符号化の計算規則に基づいて、クエリ対象地点のＺ値を取得する。Ｚ値とは、対応するレコードの行キーである。第４のコードラインは、行キーを直接用いて、対応するレコードを取得する。１つの行キーの基礎となるレコードのバージョンは複数あることがあるため、５番目のコードラインは、データの全バージョンをフィルタリングする。最後に、６番目のコードラインが所望結果を返す。
１：ＲＱ  φ／＊  Ｉｎｉｔｉａｌｉｚｅ  ｔｈｅ  ｒｅｓｕｌｔ  ｓｅｔ  ｔｏ  ｅｍｐｔｙ  ｓｅｔ  ＊／
２：Ｔｎ  Ｇｅｔ  Ｔｉｍｅ  Ｉｎｔｅｒｖａｌ  Ｎｏ  （Ｂ−ｔｒｅｅ，ｔ）／＊  Ｇｅｔ  ｔｈｅ  ｔｉｍｅ  ｉｎｔｅｒｖａｌ  ｎｕｍｂｅｒ  ｂｙ  ｔ  ｆｒｏｍ  Ｂ＋ｔｒｅｅ  ｉｎｄｅｘ  ｆｏｒ  ｔｉｍｅ  ｉｎｔｅｒｖａｌｓ  ＊／
３：Ｚ−ｖａｌｕｅ  Ｃｏｍｐｕｔｅ  Ｚ  ｖａｌｕｅ  （Ｔｎ，ｌａｔ，ｌｏｎ）／＊  Ｃｏｍｐｕｔｅ  ｔｈｅ  Ｚ−ｖａｌｕｅ  ＊／
４：Ｒｓ  Ｇｅｔ  Ｒｅｓｕｌｔ  Ｆｒｏｍ  Ｈ  Ｂａｓｅ  （Ｚ−ｖａｌｕｅ）／＊  Ｇｅｔ  ｔｈｅ  ｒｅｃｏｒｄｓ  ｂｙ  ｒｏｗｋｅｙ  ＊／
５：ＲＱ  Ｆｉｌｒｅｒ  Ｒｓ，ｔ，ｌａｔ，ｌｏｎ）／＊  Ｇｅｔ  ｔｈｅ  ｒｅｌａｔｅｄ  ｄａｔａ  ｕｓｉｎｇ  ｒｏｗｋｅｙ  ＊／
６：ｒｅｔｕｒｎ  ＲＱ
アルゴリズム１−地点クエリ
・範囲クエリ
【００６９】
Ｑ（Ｅｔ、Ｅｓ）を範囲クエリとする。ここで、Ｅｔは時間範囲を表し、Ｅｓは空間範囲を表わす。範囲クエリのプロセスは、以下のアルゴリズム２（疑似コード）のように記述できる。具体的には、１番目〜４番目のコードラインは初期化を実行する。５番目のコードラインは、時間間隔索引に基づいて、クエリ対象データが属する時間間隔を判定する。６番目〜７番目のコードラインは、各時間間隔において対応するＲ木索引をクエリすることによって、空間範囲Ｅｓに含まれる領域のリストを取得する。８番目〜１７番目のコードラインは、個々の領域から所望のデータをクエリする。領域範囲がクエリ対象範囲（Ｅｔ、Ｅｓ）のサブセットである場合は、当該領域内の全データが結果内のデータであることを示す。この場合は、領域全体をスキャンして全データが取得される。領域範囲がクエリ対象範囲と重複する場合には、領域範囲とクエリ対象範囲との重複度が決定される。そして、重複度が閾値を上回る場合は、領域全体がスキャンされ、スキャンプロセス中にフィルタリングを実行することによって、所望のデータが取得される。重複度が閾値を上回らない場合は、ローカル索引に基づいて対応するデータの行キーが検出され、その行キーを使用して最終データが取得される。
１：／＊  Ｑ（Ｅｔ，Ｅｓ）  ｉｓ  ｔｈｅ  Ｒａｎｇｅ  ｑｕｅｒｙ，Ｅｔ  ｓｔａｎｄｓ  ｆｏｒ  ｔｈｅ  ｔｉｍｅ  ｒａｎｇｅ，Ｅｓ  ｓｔａｎｄｓ  ｆｏｒ  ＊／
２：ｔｈｅ  ｓｐａｔｉａｌ  ｒａｎｇｅ  ＊／
３：ＲＱ  φ  ／＊  Ｉｎｉｔｉａｌｉｚｅ  ｔｈｅ  ｒｅｓｕｌｔ  ｓｅｔ  ｅｍｐｔｙ  ｓｅｔ  ＊／
４：ＳＱ  φ  ／＊  Ｉｎｉｔｉａｌｉｚｅ  ｔｈｅ  ｒｅｌａｔｅｄ  ｒｅｇｉｏｎ  ｓｅｔ  ｔｏ  ｅｍｐｔｙ  ｓｅｔ  ＊／
５：ＲＴＱ  Ｇｅｔ  Ｒｔｒｅｅ  Ｆｉｌｅ（Ｂ−ｔｒｅｅ，Ｅｔ）  ／＊  Ｇｅｔ  ａｌｌ  ｔｈｅ  Ｒ−ｔｒｅｅ  ｆｉｌｅｓ  ｃｏｎｔａｉｎｅｄ  ｉｎ  Ｅｔ  ＊／
６：ｆｏｒ  ｅａｃｈ  Ｒ−ｔｒｅｅ  ｆｉｌｅ  ＲＴ∈ＲＴＱ  ｄｏ
７：    ＳＱ∪Ｇｅｔ  Ｒｅｇｉｏｎｓ  Ｂｙ  Ｒｔｒｅｅ  Ｆｉｌｅ  （ＲＴ，Ｅｓ）  ／＊  Ｇｅｔ  ａｌｌ  ｔｈｅ  ｒｅｌａｔｅｄ  ｒｅｇｉｏｎｓ  ＊／
８：ｆｏｒ  ｅａｃｈ  ｒｅｇｉｏｎ  Ｒ∈ＳＱ  ｄｏ
９：    ｉｆ  ＡｂｓｔｒａｃｔＲ⊆（Ｅｔ，Ｅｓ）  ／＊  ｉｆ  ｔｈｅ  ｒａｎｇｅ  ｏｆ  ｒｅｇｉｏｎ  Ｒ  ｉｓ  ａ  ｓｕｂｓｅｔ  ｏｆ  ｑｕｅｒｙ  ｒａｎｇｅ  ＊／
１０：    ＲＱ∪Ｓｃａｎ  Ｒｅｇｉｏｎ  （Ｒ）
１１：  ｅｌｓｅ  ｉｆ  ＡｂｓｔｒａｃｔＲ∩（Ｅｔ，Ｅｓ）  ｔｈｅｎ
１２：    ｉｆ  Ｏｖｅｒｌａｐ  （ＡｂｓｔｒａｃｔＲ，（Ｅｔ，Ｅｓ））  ＞  ε  ｔｈｅｎ
１３：      ｆｏｒ  ｅａｃｈ  ｒｅｃｏｒｄ  ｒ∈Ｒ  ｄｏ
１４：          ｉｆ  ｒ∈（Ｅｔ，Ｅｓ）
１５：          ＲＱ∪ｒ
１６：      ｅｌｓｅ
１７：          ＲＱ∪Ｓｃａｎ  Ｗｉｔｈ  Ｒｔｒｅｅ  （Ｒ，Ｅｔ，Ｅｓ）
１８：  ｒｅｔｕｎ  ＲＱ
アルゴリズム２−範囲クエリ
・Ｋ最隣接（ＫＮＮ）クエリ
【００７０】
ＫＮＮ（Ｋ最隣接）クエリは、以下のアルゴリズム３のように記述できる。具体的には、このプロセスは主にクエリ拡張とフィルタリングという２つのステップで構成される。クエリ拡張ステップは、クエリ対象範囲を拡張する。フィルタリングステップは、現在範囲内のデータを計算し、それが要件を満たすかどうかを判定する。
【００７１】
具体的には、１番目〜５番目のコードラインは初期化を実行する。６番目のコードラインは、時間に基づいて、対応するＲ木索引を特定する。７番目〜１４番目のコードラインは、クエリポイントＱとクエリ半径に基づいて、範囲のリストを取得する。各領域について、領域範囲とクエリ半径に基づいて行キーの可能な範囲が特定され、その後、当該行キーの範囲に基づいてデータが取得される。最後に、１５番目のコードラインはクエリ対象範囲を拡張する。
１：／＊Ｑ（ｘ，ｙ，ｔ，ｋ）  ｂｅ  ｔｈｅ  ｐｏｉｎｔ  ｆｏｒ  ｔｈｅ  ｑｕｅｒｙ．  Ｇｅｔ  ｔｈｅ  Ｋ  ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒｓ  ｆｒｏｍ  ｐｏｉｎｔ  ｑ（ｘ，ｙ）  ｉｎ  ｔｉｍｅ  ｉｎｔｅｒｖａｌ  ΔＴ  ＊／
２：ＰＱｒｅｇｉｏｎ  ←  φ  ／＊  ｒｅｌａｔｅｄ  ｒｅｇｉｏｎｓ  ＊／
３：Ｐｑｒｅｓｕｌｔｅ  ←  Ｃｒｅａｔｅ  Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｅ  （ｋ）  ／＊  ｑｕｅｕｅ  ｃａｐａｃｉｔｙ  ｉｓ  ｋ．  ＊／
４：  Ｒｋｓｃａｎｎｅｄ  ←  φ  ／＊  ｓｃａｎｎｅｄ  ｒｏｗｋｅｙ  ＊／
５：ｒａｄｉｕｓ  ←  ｄ  ／＊  ｒａｄｉｕｓ  ｓｉｚｅ  ｆｏｒ  ｓｅａｃｈ：  ｄ  ｅｑｕａｌ  ｗｉｔｈ  ｔｈｅ  ｉｎｔｅｒｖａｌ  ｏｆ  ｔｈｅ  Ｚ−ｏｒｄｅｒｉｎｇ  ＊／  
６：ＲＴ  Ｆｉｌｅ  ←  Ｇｅｔ  Ｒｔｒｅｅ  Ｆｉｌｅ  （Ｂ−ｔｒｅｅ，ｔ）  ／＊  Ｇｅｔ  ｔｈｅ  ｒｅｓｐｏｎｄｉｎｇ  Ｒ−ｔｒｅｅ  ｆｉｌｅ  ａｃｃｏｒｄｉｎｇ  ｔｏ  ｔｉｍｅ  ｔ  ＊／
７：ｗｈｉｌｅ  ｓｉｚｅ  （ＰＱ  ｒｅｓｕｌｔ）＜ｋ
８：  ＰＱ  ｒｅｇｉｏｎ  ←  Ｇｅｔ  Ｒｅｇｉｏｎｓ  Ｂｙ  Ｒｔｒｅｅ  Ｆｉｌｅｓ  （Ｑ，ｒａｄｉｕｓ，ＲＴ  Ｆｉｌｅ）
９：    ｆｏｒ  ｅａｃｈ  Ｒｅｇｉｏｎ  Ｒ∈ＰＱ  ｒｅｇｉｏｎ  ｄｏ
１０：      Ｒｏｗｋｅｙ  Ｒａｎｇｅ  ←  ｃａｃｕｌａｔｅ  Ｚｏｒｄｅｒ  （Ｑ，ｒａｄｉｕｓ，Ｒ）  Ｒｋｓｃａｎｎｅｄ
１１：      ｒｅｓｕｌｔＳｅｔ  ←  ｓｃａｎ  （ｒｏｗｋｅｙ  Ｒａｎｇｅ）
１２：          ｆｏｒ  ｅａｃｈ  ｐｏｉｎｔ  ｐ∈ｒｅｓｕｌｔ  Ｓｅｔ
１３：                  Ｅｎｑｕｅｕｅ（ｐ，ｄｉｓｔａｎｃｅ（ｐ，Ｑ），ＰＱｒｅｓｕｌｔ）
１４：    Ｒｋｓｃａｎｎｅｄ∪Ｒｏｗｋｅｙ  Ｒａｎｇｅ
１５：  ｒａｄｉｕｓ  ←  ｒａｄｉｕｓ＋１００ｄ
アルゴリズム３−ＫＮＮクエリ
【００７２】
本実施例の方法により、ＩＯＴデータのクエリプロセス中にスキャンする記憶領域の数が削減されるので、クエリ効率が向上する。
【００７３】
以上を要約すると、本発明によれば、現在データと履歴データに対して、異なる索引付けレベル（異なる索引付け粒度）で索引を生成することが可能である。これにより、更新が高頻度で行われる場合には、索引保守コストを大幅に削減することができる。さらに、本発明の動的データ分割プロセスによって、ストレージノード内のデータは均一かつ互いに隣接するように分布されるので、クエリプロセス中の無効なスキャンを削減し、クエリ性能を向上させることができる。
【００７４】
本発明の上記の実施例は、ハードウェア、ソフトウェア、またはその組み合わせとして実装できることに留意されたい。例えば、上記の実施例では、データ索引付けシステムとその内部構成要素は、汎用プロセッサ、デジタルシグナルプロセッサ（ＤＳＰ）回路、プログラマブルプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プログラム可能論理回路（ＰＬＤ）等を含むがこれらに限られない様々な装置によって実装することが可能である。
【００７５】
さらに、本明細書で開示した本発明の実施例は、コンピュータプログラム製品上に実装することもできる。このコンピュータプログラム製品は、具体的には、コンピュータプログラム論理が符号化されたコンピュータ可読媒体であって、計算装置上で実行されることで、プロセッサに本発明の実施例による動作（方法）を実行させるコンピュータ可読媒体を含む。本発明のこうした構成は、典型的には、光媒体（例：ＣＤ−ＲＯＭ）、フロッピーディスクもしくはハードディスク等のコンピュータ可読媒体上に設定もしくは符号化されたソフトウェア、コード、その他のデータ構造体、または１つ以上のＲＯＭ、ＲＡＭ、ＰＲＯＭチップ、その他のマイクロコード用媒体上のファームウェア、または１つ以上のモジュール上のダウンロード可能なソフトウェアイメージ、または共有データベースとして提供される。ソフトウェア、ファームウェア等の構成は、計算装置上にインストールすることにより、当該計算装置内の１つ以上のプロセッサを介して、本発明の実施例による解決法を実装することができる。
【００７６】
以上、本発明について好適な実施例を参照して説明してきたが、当業者には、本発明の精神と範囲を逸脱することなく、様々な修正、改変、変更が可能なことは理解されるであろう。従って、本発明の範囲は上記の実施例に限定されず、添付請求項とその同等物によって定義される。
【００７７】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００７８】
（付記１）
事前決定された時間範囲を複数の時間間隔に分割するように構成された時間間隔分割手段と、
現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するように構成された第１索引生成手段と、
現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するように構成された第２索引生成手段とを備え、
前記第２レベル索引は、前記第１レベル索引よりも細かい粒度を有する
ことを特徴とするデータ索引付けシステム。
【００７９】
（付記２）
前記第１索引生成手段は、各葉ノードが部分空間索引を伴うＢ＋木を用いて、前記時間間隔索引を生成するように構成される
ことを特徴とする付記１に記載のデータ索引付けシステム。
【００８０】
（付記３）
前記第１索引生成手段は、Ｒ木を用いて前記部分空間索引を生成するように構成される
ことを特徴とする付記１に記載のデータ索引付けシステム。
【００８１】
（付記４）
前記第２索引生成手段は、Ｒ木またはグリッド索引を用いて、レコードレベル索引である前記第２レベル索引を生成するように構成される
ことを特徴とする付記１に記載のデータ索引付けシステム。
【００８２】
（付記５）
時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するように構成されたデータ記憶手段を備える
ことを特徴とする付記１に記載のデータ索引付けシステム。
【００８３】
（付記６）
前記時間間隔分割手段は、事前決定された時間範囲を、事前知識に基づいて、データが複数の時間間隔内で均一に分布することを確保しつつ、複数の時間間隔に分割するように構成される
ことを特徴とする付記１に記載のデータ索引付けシステム。
【００８４】
（付記７）
前記時間間隔分割手段は、各時間間隔についてデータ分割の均一性とデータ層数を計算し、特定の時間間隔のデータ分割の均一性が第１の閾値を上回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を上回る場合には、当該特定の時間間隔をさらに多くの時間間隔に分割し、逆に特定の時間間隔のデータ分割の均一性が第１の閾値を下回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を下回る場合には、当該特定の時間間隔を隣接する時間間隔と結合するように構成される
ことを特徴とする付記６に記載のデータ索引付けシステム。
【００８５】
（付記８）
事前決定された時間範囲を複数の時間間隔に分割するステップと、
現時間間隔内のデータ用として、時間間隔索引と部分空間索引とを含む第１レベル索引を生成するステップと、
現時間間隔の後の１つの時間間隔内に、現時間間隔内のデータ用として第２レベル索引を生成するステップとを含み、
前記第２レベル索引は、前記第１レベル索引よりも細かい粒度を有する
ことを特徴とするデータ索引付け方法。
【００８６】
（付記９）
前記時間間隔索引は、各葉ノードが部分空間索引を伴うＢ＋木を用いて生成される
ことを特徴とする付記８に記載のデータ索引付け方法。
【００８７】
（付記１０）
前記部分空間索引はＲ木を用いて生成される
ことを特徴とする付記８に記載のデータ索引付け方法。
【００８８】
（付記１１）
レコードレベル索引である前記第２レベル索引は、Ｒ木またはグリッド索引を用いて生成される
ことを特徴とする付記８に記載のデータ索引付け方法。
【００８９】
（付記１２）
時間と空間において隣接するデータを、同じかまたは隣接する記憶領域に記憶するステップを含む
ことを特徴とする付記８に記載のデータ索引付け方法。
【００９０】
（付記１３）
前記分割ステップは、
データが複数の時間間隔内で均一に分布するように、事前知識に基づいて、事前決定された時間範囲を複数の時間間隔に分割する
ことを特徴とする付記８に記載のデータ索引付け方法。
【００９１】
（付記１４）
前記分割ステップは、
各時間間隔についてデータ分割の均一性とデータ層数を計算する動作と、特定の時間間隔のデータ分割の均一性が第１の閾値を上回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を上回る場合には、当該特定の時間間隔をさらに多くの時間間隔に分割する動作と、逆に特定の時間間隔のデータ分割の均一性が第１の閾値を下回り、かつ当該特定の時間間隔のデータ層数が第２の閾値を下回る場合には、当該特定の時間間隔を隣接する時間間隔と結合する
ことを特徴とする付記１３に記載のデータ索引付け方法。
【００９２】
（付記１５）
クエリ対象データが現在データと履歴データのどちらであるかを判定するステップと、
データが現在データの場合は、時間間隔索引と部分空間索引とを含む第１レベル索引によってデータをクエリするステップと、
データが履歴データの場合は、第２レベル索引によってデータをクエリするステップとを含み、
前記第２レベル索引は、前記第１レベル索引よりも細かい粒度を有する。
ことを特徴とするデータクエリ方法。
【００９３】
（付記１６）
前記クエリするステップは、地点クエリ動作、範囲クエリ動作およびＫ最隣接クエリ動作のいずれかを含む
ことを特徴とする付記１５に記載のデータクエリ方法。
【００９４】
（付記１７）
前記時間間隔索引は、各葉ノードが部分空間索引を伴うＢ＋木を用いて生成される
ことを特徴とする付記１５に記載のデータクエリ方法。
【００９５】
（付記１８）
前記部分空間索引はＲ木を用いて生成される
ことを特徴とする付記１５に記載のデータクエリ方法。
【００９６】
（付記１９）
レコードレベル索引である前記第２レベル索引は、Ｒ木またはグリッド索引を用いて生成される
ことを特徴とする付記１５に記載のデータクエリ方法。
【符号の説明】
【００９７】
１１０：時間間隔分割ユニット
１２０：第１索引生成ユニット
１３０：第２索引生成ユニット
３１０：時間間隔分割ユニット
３２０：第１索引生成ユニット
３３０：第２索引生成ユニット
３４０：データ記憶ユニット
【図１】
0005519762.tif 000005
【図２】
0005519762.tif 000006
【図３】
0005519762.tif 000007
【図４】
0005519762.tif 000008
【図５】
0005519762.tif 000009
【図６】
0005519762.tif 000010