(57)【要約】      （修正有）【課題】より効率的な新しい区間索引付け方法を提供すること。【解決手段】仮想構成区間（ＶＣＩ）と呼ばれる新しい概念を導入し、各述語区間は、１つまたは複数のこの構成区間に分解される。このＶＣＩは述語区間を厳密に被覆する。すなわち、述語区間によって被覆されるすべてのアトリビュート値は、少なくとも１つの分解ＶＣＩによっても被覆され、その逆も成り立つ。各構成区間は、一意のＩＤまたは区間座標と、１組の端点を有する。構成区間は、それを分解に使用する述語区間がシステムに追加されたとき、活動化されると考えられる。次に述語ＩＤが、分解ＶＣＩに関連付けられたＩＤリストに挿入される。高速探索を容易にするため、ビットマップ・ベクトルが、あるイベント値を被覆するＶＣＩの活動化を示すのに使用される。【選択図】図２
2005108221.tif 000002
【特許請求の範囲】
【請求項１】
クエリ索引を維持し使用するための方法であって、前記クエリ索引内のクエリが述語区間を有し、前記方法が、
仮想構成区間のグループを定義するステップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するステップとを含む方法。
【請求項２】
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、
仮想構成区間の前記グループは一定の長さをもち、
前記述語区間は一定の長さをもたない、請求項１に記載の方法。
【請求項３】
仮想構成区間の前記グループ内の前記述語区間のロケーションを述語ＩＤビットマップ・ベクトルを用いて維持するステップをさらに含む、請求項１に記載の方法。
【請求項４】
仮想構成区間の前記グループを定義する前記処理が、仮想構成区間のグループ内のすべての仮想構成区間を同じアトリビュート値で開始させるステップと、仮想構成区間の前記グループ内の前記仮想構成区間を異なるアトリビュート値で終了させるステップとを含む、請求項１に記載の方法。
【請求項５】
前記クエリ索引内の前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項１に記載の方法。
【請求項６】
前記述語区間を前記仮想構成区間に挿入する前記処理が、前記述語区間を同じサイズの仮想構成区間に挿入するステップを含む、請求項１に記載の方法。
【請求項７】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記挿入処理が、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを含む、請求項１に記載の方法。
【請求項８】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項１に記載の方法。
【請求項９】
クエリ索引を維持し使用するための方法であって、前記クエリ索引内のクエリが述語区間を有し、前記方法が、
仮想構成区間のグループを定義するステップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するステップとを含み、
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、
仮想構成区間の前記グループは一定の長さをもち、
前記述語区間は一定の長さをもたない方法。
【請求項１０】
仮想構成区間の前記グループ内の前記述語区間のロケーションを述語ＩＤビットマップ・ベクトルを用いて維持するステップをさらに含む、請求項９に記載の方法。
【請求項１１】
仮想構成区間の前記グループを定義する前記処理が、仮想構成区間のグループ内のすべての仮想構成区間を同じアトリビュート値で開始させるステップと、仮想構成区間の前記グループ内の前記仮想構成区間を異なるアトリビュート値で終了させるステップとを含む、請求項９に記載の方法。
【請求項１２】
前記クエリ索引内の前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項９に記載の方法。
【請求項１３】
前記述語区間を前記仮想構成区間に挿入する前記処理が、前記述語区間を同じサイズの仮想構成区間に挿入するステップを含む、請求項９に記載の方法。
【請求項１４】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記挿入処理が、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを含む、請求項９に記載の方法。
【請求項１５】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項９に記載の方法。
【請求項１６】
クエリ索引を維持し使用するための方法であって、前記クエリ索引内のクエリが述語区間を有し、前記方法が、
仮想構成区間のグループを定義するステップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するステップとを含み、
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、
仮想構成区間の前記グループの各々が、イベント値の固有のグループを被覆し、前記述語区間を挿入する前記ステップが、前記述語区間だけを対応するイベント値を有する前記構成区間に挿入するステップを含む方法。
【請求項１７】
仮想構成区間の前記グループ内の前記述語区間のロケーションを述語ＩＤビットマップ・ベクトルを用いて維持するステップをさらに含む、請求項１６に記載の方法。
【請求項１８】
仮想構成区間の前記グループを定義する前記処理が、仮想構成区間のグループ内のすべての仮想構成区間を同じアトリビュート値で開始させるステップと、仮想構成区間の前記グループ内の前記仮想構成区間を異なるアトリビュート値で終了させるステップとを含む、請求項１６に記載の方法。
【請求項１９】
前記クエリ索引内の前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項１６に記載の方法。
【請求項２０】
前記述語区間を前記仮想構成区間に挿入する前記処理が、前記述語区間を同じサイズの仮想構成区間に挿入するステップを含む、請求項１６に記載の方法。
【請求項２１】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記挿入処理が、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを含む、請求項１６に記載の方法。
【請求項２２】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項１６に記載の方法。
【請求項２３】
クエリ索引を維持し使用するための方法であって、前記クエリ索引内のクエリが述語区間を有し、前記方法が、
仮想構成区間のグループを定義するステップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するステップとを含み、
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、仮想構成区間の前記グループの各々が、イベント値の固有のグループを被覆し、
前記述語区間を挿入する前記ステップが、前記述語区間だけを対応するイベント値を有する前記構成区間に挿入するステップを含み、
前記定義処理が、前記述語区間でアトリビュートが取り得る最小値と最大値の間にある仮想構成区間だけを定義する方法。
【請求項２４】
仮想構成区間の前記グループ内の前記述語区間のロケーションを述語ＩＤビットマップ・ベクトルを用いて維持するステップをさらに含む、請求項２３に記載の方法。
【請求項２５】
仮想構成区間の前記グループを定義する前記処理が、仮想構成区間のグループ内のすべての仮想構成区間を同じアトリビュート値で開始させるステップと、仮想構成区間の前記グループ内の前記仮想構成区間を異なるアトリビュート値で終了させるステップとを含む、請求項２３に記載の方法。
【請求項２６】
前記クエリ索引内の前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項２３に記載の方法。
【請求項２７】
前記述語区間を前記仮想構成区間に挿入する前記処理が、前記述語区間を同じサイズの仮想構成区間に挿入するステップを含む、請求項２３に記載の方法。
【請求項２８】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記挿入処理が、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを含む、請求項２３に記載の方法。
【請求項２９】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項２３に記載の方法。
【請求項３０】
クエリ索引を維持し使用するように適合されたサービスであって、前記クエリ索引内のクエリが述語区間を有し、前記サービスが、
仮想構成区間のグループを定義するステップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するステップとを含み、
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、
仮想構成区間の前記グループの各々が、イベント値の固有のグループを被覆し、前記述語区間を挿入する前記ステップが、前記述語区間だけを対応するイベント値を有する前記構成区間に挿入するステップを含むサービス。
【請求項３１】
仮想構成区間の前記グループ内の前記述語区間のロケーションを述語ＩＤビットマップ・ベクトルを用いて維持するステップをさらに含む、請求項３０に記載のサービス。
【請求項３２】
仮想構成区間の前記グループを定義する前記処理が、仮想構成区間のグループ内のすべての仮想構成区間を同じアトリビュート値で開始させるステップと、仮想構成区間の前記グループ内の前記仮想構成区間を異なるアトリビュート値で終了させるステップとを含む、請求項３０に記載のサービス。
【請求項３３】
前記クエリ索引内の前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項３０に記載のサービス。
【請求項３４】
前記述語区間を前記仮想構成区間に挿入する前記処理が、前記述語区間を同じサイズの仮想構成区間に挿入するステップを含む、請求項３０に記載のサービス。
【請求項３５】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記挿入処理が、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを含む、請求項３０に記載のサービス。
【請求項３６】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項３０に記載のサービス。
【請求項３７】
クエリ索引を維持し使用するためのシステムであって、前記クエリ索引内のクエリが述語区間を有し、前記システムが、
仮想構成区間のグループを定義する複数のビットマップと、
前記述語区間の各々を前記仮想構成区間の前記グループの少なくとも１つに挿入するように適合された述語挿入ハンドラとを含み、
仮想構成区間の前記グループの各々が、複数の述語区間を保持するように適合され、
仮想構成区間の前記グループの各々が、イベント値の固有のグループを被覆し、前記述語区間を挿入する前記ステップが、前記述語区間だけを対応するイベント値を有する前記構成区間に挿入するステップを含むシステム。
【請求項３８】
仮想構成区間の前記グループ内の前記述語区間のロケーションを維持するように適合された述語ＩＤビットマップ・ベクトルをさらに含む、請求項３７に記載のシステム。
【請求項３９】
仮想構成区間のグループ内のすべての仮想構成区間が、同じアトリビュート値で開始し、異なるアトリビュート値で終了する、請求項３７に記載のシステム。
【請求項４０】
前記仮想構成区間の前記グループのすべてが、サイズの異なる仮想構成区間からなる同じパターンを有する、請求項３７に記載のシステム。
【請求項４１】
前記述語挿入ハンドラが、前記述語区間を同じサイズの仮想構成区間に挿入する、請求項３７に記載のシステム。
【請求項４２】
述語区間が前記仮想構成区間のどれよりも大きい場合、前記述語挿入ハンドラが、
前記述語区間の最初の部分を利用可能な最大の仮想構成区間に挿入するステップであって、前記述語区間の余った長さが残余述語区間を構成するステップと、
前記残余述語区間を同じ長さの仮想構成区間に挿入するステップとを実行する、請求項３７に記載のシステム。
【請求項４３】
複数の述語区間の同じイベント値が仮想構成区間内の同じイベント値に挿入されるように、前記述語区間のイベント値を前記仮想構成区間の同じイベント値と整列させる、請求項３７に記載のシステム。
【請求項４４】
請求項１ないし２９のいずれか一項に記載の方法の各ステップをコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下に、継続クエリ（continual query）、ルール、プロファイル、および購読を索引付けするための方法を開示する。継続クエリ、ルール、プロファイル、または購読は、少なくとも１つの区間述語（intervalpredicate）を含むことができる。詳細には、与えられたイベント、条件、または発行に一致するクエリ、ルール、プロファイル、および購読を速やかに識別するための、区間述語索引付け方法（intervalpredicate indexing method）が開示される。
【背景技術】
【０００２】
本発明ならびに本発明の様々な特徴および有利な詳細について、添付の図面に図示され、以下の説明で詳述される非限定的な実施形態を参照しながらより詳しく説明する。図面に示される形体が必ずしも実寸に比例して描かれていないことに留意されたい。周知の構成要素および処理技法についての説明は、本発明が徒らに不明瞭にならないよう省略してある。本明細書で用いる例は、本発明を実施できる方法をより良く理解できるようにすること、さらに当業者が本発明を実施できるようにすることを意図しているに過ぎない。したがって、それらの例が本発明の範囲を限定すると解釈してはならない。
【０００３】
大規模分散環境におけるコンテンツ・ベースの発行／購読システム、継続クエリ、プロファイル・ベースのアプリケーション、ルール・ベースの監視システム、およびその他の情報配布サービスが、ワールド・ワイド・ウェブ（ＷＷＷ）の出現によって実現可能となり普及した。そのようなシステムおよびアプリケーションのユーザは、ウェブを介して簡単に、セットアップを行うことができ、またはプロバイダにサービスの提供を申し込むことができる。これらの購読、継続クエリ、プロファイル、およびルールは、１組のアトリビュートに関する述語として通常は表現される。各述語は、アトリビュート、演算子、および値を含む。述語は、ユーザによって表現される条件、指定、または制約を表す。述語は、多数の受け取ったイベント、条件、または発行をふるい分け、ユーザの関心または指定に合致するものだけをユーザに通知するために使用される。
【０００４】
大規模な継続クエリ、コンテンツ・ベースの発行／購読、またはプロファイル・ベースのアプリケーションを支援するのに最も重要な構成要素の１つは、イベントと述語との高速照合である。多数のイベントが、短期間のうちに発生することがあり得る。各イベントは、おそらく数１０万あるいは数１００万もの膨大な数の述語と照合しなければならない。そのため、効率的なイベント照合システムが必要になる。通常は、メイン・メモリ・ベースの述語索引が必要とされる。顧客の関心／制約は断続的にシステムに追加され、あるいはシステムから削除されるので、この索引は、述語の動的挿入および削除を支援しなければならない。探索計算量（search complexity）およびストレージ・コストは、最小にしなければならない。その上、述語は、区間などの不等式節を含むことがある。区間述語は、等式述語（equalitypredicate）と異なり、動的挿入および削除が行われると索引付けが著しく困難になる。
【０００５】
次の質問に効率的に答えるため、区間述語索引が使用される。「集合Ｑ＝｛Ｉ１，Ｉ２，．．．，Ｉｎ｝に属する述語区間（predicate interval）のうち、あるデータ点を被覆する述語区間はどれか？」ここで、Ｉ１，Ｉ２，．．．，Ｉｎは、［４，５］、［２，１９］、［２４，２３０］、または［−，８］などの述語区間であり、クエリ、ルール、プロファイル、または購読によって指定される。これらの述語区間は、ユーザが関心のあるデータ値の範囲を表す。課題は、クエリ、ルール、または購読に関する効率的な区間索引を維持することによって、与えられたデータが満足する、または一致するすべてのクエリまたはルールを効率的に見つけることである。区間索引付けの分野には、いくつかのシステムが存在する。しかし、その大多数は、大規模な動的環境におけるイベントの高速照合に関して効率的ではない。区分木および区間木（Ｈ．サメット（Samet）、空間データ構造の設計および解析（Designand Analysis of Spatial Data Structure）、アディソン−ウェズリー（Addison-Wesley）、１９９０年）が、静的環境では一般によく機能するが、区間を動的に追加または削除する必要がある場合には適当ではない。最初は長方形などの空間物体を取り扱うために設計されたＲ木（Ａ．グットマン（Guttman）、「Ｒ木：空間探索のための動的索引構造（R-trees:A dynamic index structure for spatial searching）」、ＡＣＭ  ＳＩＧＭＯＤ会報（Proceedings ofthe ACM SIGMOD）、１９８４年）を、区間を索引付けするのに使用することができる。しかし、区間どうしのオーバラップが大きい場合、探索時間は著しく低下する。ＩＢＳ木（Ｅ．ハンソン（Hanson）他、「データベース・ルール・システムのための述語照合アルゴリズム（Apredicate matching algorithm for database rule systems）」、ＡＣＭ  ＳＩＧＭＯＤ会報、１９９０年）、およびＩＳリスト（Ｅ．ハンソン他、「区間スキップ・リストを用いた稼動データベースのための選択述語索引付け（Seletionpredicate indexing for active databases using interval skip lists）」、情報システム（InformationSystems）、２１（３）、２６９〜２９８ページ、１９９６年）が、区間索引付けのために設計された。大多数のその他の動的探索木では、探索時間はＯ（ｌｏｇ（ｎ））であり、ストレージ・コストはＯ（ｎｌｏｇ（ｎ））である。ただし、ｎは述語区間の総数である。さらに、Ｏ（ｌｏｇ（ｎ））の探索時間を達成するには、挿入または削除の後で、索引構造の複雑な「調整」が必要になる。索引構造を再バランスさせるには調整が必要である。索引の調整は、挿入／削除の時間計算量（timecomplexity）を増大させる。より重要なのは、調整を行うことによって、実用時にアルゴリズムの信頼性のある実施が難しくなることである。
【非特許文献１】Ｈ．サメット（Samet）、空間データ構造の設計および解析（Designand Analysis of Spatial Data Structure）、アディソン−ウェズリー（Addison-Wesley）、１９９０年
【非特許文献２】Ａ．グットマン（Guttman）、「Ｒ木：空間探索のための動的索引構造（R-trees:A dynamic index structure for spatial searching）」、ＡＣＭ  ＳＩＧＭＯＤ会報（Proceedings ofthe ACM SIGMOD）、１９８４年
【非特許文献３】Ｅ．ハンソン（Hanson）他、「データベース・ルール・システムのための述語照合アルゴリズム（Apredicate matching algorithm for database rule systems）」、ＡＣＭ  ＳＩＧＭＯＤ会報、１９９０年
【非特許文献４】Ｅ．ハンソン他、「区間スキップ・リストを用いた稼動データベースのための選択述語索引付け（Seletion predicate indexing for active databases using interval skiplists）」、情報システム（Information Systems）、２１（３）、２６９〜２９８ページ、１９９６年
【発明の開示】
【発明が解決しようとする課題】
【０００６】
そのため、より効率的な新しい区間索引付け方法に対する必要性が認められる。
【課題を解決するための手段】
【０００７】
本発明は、仮想構成区間（ＶＣＩ：virtual construct interval）と呼ばれる新しい概念を導入し、各述語区間は、１つまたは複数のこの構成区間に分解される。このＶＣＩは述語区間を厳密に被覆する。すなわち、述語区間によって被覆されるすべてのアトリビュート値は、少なくとも１つの分解ＶＣＩによっても被覆され、その逆も成り立つ。各構成区間は、一意のＩＤまたは区間座標（intervalcoordinate）と、１組の端点を有する。構成区間は、それを分解に使用する述語区間がシステムに追加されたとき、活動化されると考えられる。次に述語ＩＤが、分解ＶＣＩに関連付けられたＩＤリストに挿入される。高速探索を容易にするため、ビットマップ・ベクトルが、あるイベント値を被覆するＶＣＩの活動化を示すのに使用される。難しいのは、述語分解（predicatedecomposition）を簡潔にする適切な１組の構成区間を見つけることであり、より重要で難しいのは、効率的なビットマップ索引を構築することである。各構成区間はアトリビュート値の僅かな範囲を被覆するに過ぎないので、本発明もビットマップ・クリッピング（bitmapclipping）を用いて、不必要なビットマップの保存を削減する。ビットマップ・クリッピングを容易にするため、本発明は、被覆セグメント（coveringsegment）の概念を導入する。被覆セグメントの外部のビット位置が取り除かれる。
【０００８】
本発明は、効率的な継続クエリ／ルール監視を支援して、多数のクエリ、ルール、または購読の高速照合を可能にする。本発明は、探索時間計算量と、クエリ／ルール索引を維持するためのストレージ要件の両面で効率的である。挿入および削除も非常に効率的になる。あるデータ点を被覆するすべての述語区間を見つけるための探索時間計算量はＯ（１）であり、その時点で維持されている述語区間の数とは独立である。ストレージ要件はＯ（ｎ）であり、その時点で維持されている述語区間の数に比例する。挿入時間もＯ（１）である。
【発明を実施するための最良の形態】
【０００９】
本発明は一般に、効率的なクエリ／ルールの索引付けに関し、各クエリまたはルールは、１つまたは複数の区間述語を含むことができる。具体的には、効率的な区間述語索引付け方式が開示される。そのような区間述語索引は、次のような質問に効率的に答えるのに使用される。「集合Ｑ＝｛Ｉ１，Ｉ２，．．．，Ｉｎ｝に属する述語区間のうち、あるデータ点を被覆する述語区間はどれか？」ここで、Ｉ１，Ｉ２，．．．，Ｉｎは、［４，５］、（２，１９）、（２４，２３０）、または（−，＊）などの述語区間であり、クエリまたはルールによって指定される。これらの述語区間は、ユーザが関心のあるデータ値の範囲を表す。課題は、クエリまたはルールに関する効率的な索引を維持することによって、与えられたデータが満足する、または一致するすべてのクエリまたはルールを効率的に見つけることである。本発明は、効率的な継続クエリ／ルール監視を支援して、多数のクエリまたはルールのリアルタイム監視を可能にする。本発明は、探索時間計算量と、クエリ／ルール索引を維持するためのストレージ要件の両面で効率的である。あるデータ点を被覆するすべての述語区間を見つけるための探索時間計算量はＯ（１）であり、その時点で維持されている述語区間の数とは独立である。ストレージ要件はＯ（ｎ）であり、その時点で維持されている述語区間の数に比例する。
【００１０】
図１は、分散システム環境のブロック図であり、様々なタイプのサービス・プロバイダ１０４、１０５、データ・ソース１０２、１０３、およびクライアント１００、１０１が、通信ネットワーク１０６を介して相互接続されている。通信ネットワーク１０６は、インターネットまたは無線ネットワークとすることができる。発行／購読、継続クエリ監視、イベント監視、またはルール監視など、様々なタイプのサービスを、ネットワーク上でクライアントに提供することができる。サービス・プロバイダは、この好ましい実施形態に開示される本発明を利用して、分散環境内の１つまたは複数のデータ・ソース１０２、１０３から到来するデータまたはイベントを監視し、管理する。データ・ソースは、温度センサ、交通センサ、株価データ・ストリーム、小売店売上データ・ストリーム、その他とすることができる。クライアント１００、１０１は、パーソナル・コンピュータ、セル電話、従来型電話、または携帯情報端末など、信号を受信できる任意の装置とすることができる。
【００１１】
図２は、この好ましい実施形態に開示される本発明を実施するシステムのブロック図である。コンピュータ・システム２３０には、ＣＰＵ２３３、ディスク２３２、およびメイン・メモリ２３１が少なくとも含まれる。ディスク２３２およびメイン・メモリ２３１には、様々なソフトウェア・プログラムが含まれ、その１つが本発明のロジックを実施する。開示される区間索引付け方法２１０を実施するプログラムは、述語挿入ハンドラ（predicate insertion handler）２１１（図５で詳細に説明する）、イベント照合ハンドラ（eventmatching handler）２１２（図６で詳細に説明する）、述語削除ハンドラ（predicate deletion handler）２１３（図７で詳細に説明する）、およびユーザ・アカウント・マネージャ（useraccount manager）２１４を少なくとも含む。ユーザ・アカウント・マネージャ２１４は、ユーザの購読、およびその他のアカウント管理タスクを維持する。区間索引付け方法のメイン・ロジックは、述語挿入ハンドラ２１１、述語削除ハンドラ２１３、およびイベント照合ハンドラ２１２を含み、それらについては以下でより詳しく説明する。システムへの入力は、ユーザ関心事２０１およびイベント値２０２である。ユーザ関心事は、購読、継続クエリ、およびルールの中で区間述語の形式で表現される。イベント値は、センサの感知データ、または発行元のコンテンツである。システムの出力２０３は、一致した購読、クエリ、またはルールである。
【００１２】
図３は、１つまたは複数の区間述語の存在下でイベント照合を実行する問題を示した一例である。述語区間３１１〜３１９が、左端点から右端点まで水平に引かれている。イベント照合問題は、イベント値の所で垂直線を引くことによって解くことができる。例えば、２本の垂直線３０１、３０２が、ａｉおよびａｊの所で引かれている。一致区間は、これらの垂直線と交差する区間である。例えば、｛ｑ１，ｑ３，ｑ７，ｑ９｝は、ａｉに一致する述語区間の集合であり、｛ｑ２，ｑ４，ｑ６，ｑ８，ｑ９｝は、ａｊに一致する述語区間の集合である。
【００１３】
あるイベント値の垂直線と交差するこれらの述語区間を速やかに識別することは非常に難しい。区間索引の助けを借りない場合、線形探索によってイベント照合を実行しなければならない。すなわち、各イベントがすべての述語区間と比較される。この方法は、述語区間の数が多い場合は特に、受け入れ難いほど低速な処理となることがある。
【００１４】
開示される区間索引付け方法は、図３に示されたアイデアを費用対効果の高い方式で実施する試みである。簡単にするため、述語区間の端点は整数であると仮定する。しかし、アトリビュートは、整数データ型とすることも、非整数データ型とすることもできる。非整数の端点を最も近い整数まで広げられることは、当業者には理解されよう。１組の仮想構成区間ＶＣＩが、アトリビュートの整数値で事前定義される。各ＶＣＩは、一意のＩＤまたは座標、および特定の端点を有する。このＶＣＩは述語区間を分解するのに用いられる。分割ＶＣＩは述語区間を厳密に被覆する。すなわち、述語区間によって被覆される任意のアトリビュート値は、少なくとも１つの分解ＶＣＩによっても被覆され、その逆も成り立つ。
【００１５】
各整数値について、本発明は、その値を被覆するあるＶＣＩの活動化を示すのに、ビットマップ・ベクトルを使用する。各ビットマップ・ベクトルは、全部でＮ＝ＲＬビットを含む。ただし、Ｒはアトリビュートが取り得る整数値の総数である。各ＶＣＩに関連づけて、述語ＩＤリストが維持される。本発明は、そのようなＩＤリストを維持するのに、ヘッダ・ポインタの配列を使用する。
【００１６】
図４は、１組の単純構成区間（ＳＣＩ：simple constructinterval）の一例である。ＳＣＩの場合、一定のＬの下で、ＶＣＩが整数値毎に事前定義される。これらのＶＣＩは、１からＬの範囲の連続的な長さを有する。ＶＣＩｃ：［ａ，ｂ］のＩＤは、ｃ＝（ａ−ａ０）Ｌ＋（ｂ−ａ）−１として計算することができる。ただし、ｃはＩＤ、［ａ，ｂ］は区間である。図４では、Ｌ＝４であり、ＩＤは区間［ａ０，ａ０＋１］の０から始まる。左端点が同じ整数値になる４つのＶＣＩが存在する。例えば、ＶＣＩ０〜３（４００〜４０３）は、すべてａ０から始まるが、それらの右端点は異なる。
【００１７】
図５は、述語挿入ハンドラ（図２の２１１）を実施するフローチャートである。述語区間ｐ：［ｘ，ｙ］（ステップ５００）を挿入するため、本発明は最初に、当該述語区間が最大仮想構成区間より大きいかどうか、すなわち、ｙ−ｘ＞Ｌであるかどうかを確かめるチェックを行う（ステップ５０１）。大きくない場合は、分解は必要でなく、本発明は単に、当該述語区間と同じＶＣＩのＩＤを見つけるだけである（ステップ５０５）。分解が必要な場合、本発明は、述語区間をｘから始まる長さＬの
【数１】
2005108221.tif 000003
個の区間に繰り返し分割する（ステップ５０２）。最後の残余部分は、［ｘ＋ｍＬ，ｙ］となる。この分解の後、各分解ＶＣＩのＩＤが計算される（ステップ５０３、ステップ５０４）。最後に、各分解ＶＣＩｃｊ毎に、本発明は、
【数２】
2005108221.tif 000004
が空である場合は対応するビットマップを設定し、述語ＩＤを対応するＩＤリストに挿入する（ステップ５０６）。ｃｊのビットマップを設定するとき、本発明が、ビットマップ
【数３】
2005108221.tif 000005
を１に設定する必要があることに留意されたい。ただし、ｉはａ≦ｉ≦ｂの範囲を順次移動し、ｃｊは［ａ，ｂ］のＩＤである。ここで、
【数４】
2005108221.tif 000006
は、ビットマップ・ベクトルＢｉのビット位置ｃｊを意味する。
【００１８】
図６は、イベント照合ハンドラ（図２の２１２）を実施するフローチャートである。探索は、イベント値ｓから開始される（ステップ６００）。本発明は、探索結果のＭを空に、ｔを０に初期化する（ステップ６０１）。次に本発明は、ｔ＜Ｎであるかどうかを確かめるテストを行う（ステップ６０２）。ただし、ＮはＶＣＩの総数である。ｔ＜Ｎでない場合、探索は終了し、結果が返される（ステップ６０３）。ｔ＜Ｎである場合、本発明はさらに、ｂｓ，ｔ＝＝１であるかどうかを確かめるテストを行う（ステップ６０４）。１に等しい場合、本発明は一致するＶＣＩを有しており、それに関連付けられたＩＤリストがＭと結合される（ステップ６０５）。その後、本発明はｔを次の値に進め（ステップ６０６）、ステップ６０２に復帰する。
【００１９】
図７は、述語削除ハンドラ（図２の２１３）のフローチャートである。このフローチャートは、ステップ７０６を除いて、挿入ハンドラのフローチャートとほぼ同じである。ステップ７０１〜７０５は、分解プロセスを表しているので、図５のステップ５０１〜５０５とまったく同じである。分解の後、本発明は次に、述語ＩＤをＩＤリストから削除し、削除後にＩＤリストが空になった場合はビットマップをリセットする（ステップ７０６）。
【００２０】
図８は、単純構成区間（ＳＣＩ）を使用するＶＣＩ索引付けを示した一例である。２つの述語ｑ：［ａ０，ａ０＋２］（８０１）とｐ：［ａ０，ａ０＋６］（８０２）を挿入する。本発明は、分解を行うのに、図４に示す例示的なＳＣＩを使用する。各ビットマップ・ベクトルは２８ビットを有し、本発明には、７個のビットマップ・ベクトル８１０〜８１６が示されている。２８個のポインタ・ヘッダからなる配列（８２０）が、ＩＤリスト８２１〜８２３を管理するのに使用される。Ｌ＝４であるので、述語ｑ：［ａ０，ａ０＋２］については分解は必要ない。そのため、ＩＤがＨ１（８２１）に挿入され、ｂ０，１、ｂ１，１、ｂ２，１は１に設定される。一方、ｐ：［ａ０，ａ０＋６］は最初に、［ａ０，ａ０＋４］と［ａ０＋４，ａ０＋６］に分解される。［ａ０，ａ０＋４］のＩＤは３であり、［ａ０＋４，ａ０＋６］のＩＤは１７である。そのため、ＩＤが２つのＩＤリスト８２２〜８２３に挿入される。対応するビット位置も同様に１に設定される。
【００２１】
したがって、本発明は、クエリ索引を維持し、使用するための方法（およびサービス／システム）を提供する。上述したように、クエリ索引内のクエリは、述語区間（例えば、３１１〜３１９や８０１〜８０２）を有する。本発明は、仮想構成区間のグループ（４００〜４０３、４０４〜４０７、４０８〜４１１など）を定義することにより開始され、述語区間８０１〜８０２の各々を、仮想構成区間のグループの少なくとも１つに挿入する。より具体的には、述語区間８０１は、図４に示す仮想構成区間の第１のグループ（４００〜４０３）の仮想構成区間４０１に挿入される。仮想構成区間４０１は、図８のビットマップ・ベクトル８１０〜８１２のビット位置ｂ０，１、ｂ１，１、ｂ２，１に対応する。本発明は、述語区間でアトリビュートが取り得る最小値と最大値の間に存在する仮想構成区間を定義するに過ぎない。
【００２２】
仮想構成区間の各グループ（例えば、４００〜４０３）は、複数の述語区間を保持するように適合される。したがって、仮想構成区間４０１が述語区間８０１を維持する一方で、（仮想構成区間４０１と同じ仮想構成区間のグループに属する）仮想構成区間４０３は、述語区間８０２を維持する。（図８の）ビットマップ・ベクトル８１０〜８１４のビット位置ｂ０，３、ｂ１，３、ｂ２，３、ｂ３，３、ｂ４，３は、図４の仮想構成区間４０３に対応する。したがって、述語区間（８０１、８０２）のイベント値（ａ０、ａ０＋１、ａ０＋２など）は、各ビットマップ・ベクトル８１０〜８１６が１つのイベント値に排他的に関連付けられるという点で、仮想構成区間（４０１、４０３）の同じイベント値と整列する。述語区間は必ず対応するイベント値を有する仮想構成区間だけに挿入されることになる。したがって、複数の述語区間（８０１、８０２）の同じイベント値（例えば、ａ０＋１）は、異なる仮想構成区間（４０１、４０３）内の同じイベント値（例えば、ビットマップ・ベクトル８１１に関連付けられるａ０＋１）に挿入され、与えられたビットマップ・ベクトル（８１１）内の異なるビット位置（１、３）に格納されるだけである。先に述べたように、仮想構成区間のどのグループに述語区間が位置するかは、述語ＩＤビットマップ・ベクトル８２０を用いて維持される。
【００２３】
仮想構成区間の各グループは、イベント値の固有のグループを被覆する。例えば、仮想構成区間の第１のグループ（４００〜４０３）は、イベント値ａ０からａ０＋４を被覆し、一方、仮想構成区間の第２のグループ（４０４〜４０７）は、イベント値ａ０＋１からａ０＋５を被覆する。あるグループ内のすべての仮想構成区間（４００〜４０３）は、同じアトリビュート値（ａ０）で始まり、異なるアトリビュート値（ａ０＋１からａ０＋４）で終る。仮想構成区間のグループは一定の長さをもつが（図４）、述語区間は一定の長さをもたない（図３）ことに留意されたい。言い換えると、クエリ索引内の仮想構成区間のグループはすべて、異なるサイズの仮想構成区間からなる同一のパターンをもち、各グループ内の第１の区間は１区間長、第２の区間は２区間長、第３の区間は３区間長などとなる。
【００２４】
述語区間が十分に小さい場合、本発明は、述語区間８０１を仮想構成区間４０１に挿入したように、当該述語区間をそれと同じサイズの仮想構成区間に挿入する。しかし、述語区間がどの仮想構成区間よりも大きい場合、本発明は最初に、当該述語区間の最初の部分を最も大きい利用可能な仮想構成区間に挿入する。非常に長い述語区間の場合、必要であれば、いくつかの最大サイズの仮想構成区間を利用することができる。余分な長さの述語区間は、残余述語区間（remnant predicate interval）と呼ばれる。本発明は、残余述語区間をそれと同じ長さの仮想構成区間に挿入する。したがって、述語区間８０２の最後の２つのイベント値は、同様の長さの仮想構成区間（図４の繰り返しをさらに進めた場合の仮想構成区間４１７）に配置される。
【００２５】
ＶＣＩの異なる組（グループ）を定義することができる。図９には、対数構成区間（ＬＣＩ：logarithmicconstruct interval）の一例が示されている。本発明は、区間の長さとして、連続的に変化する長さの代りに、２０、２１、．．．、２ｋを使用する。Ｌ＝４である場合、本発明は、１組の整数値で事前定義されたＶＣＩとして、長さが１、２、４の異なるＶＣＩを使用する。対数構成区間を用いると、ＶＣＩの総数はＲ（ｌｏｇ（Ｌ）＋１）となり、この数は一般に、ＳＣＩの総数よりもはるかに少ない。
【００２６】
ビットマップ・ベクトル中に使用されることのないいくつかの値が存在することは、当業者であれば理解されよう。これは、いくつかのＶＣＩはイベント値の垂直線と決して交差しないためである。例えば、［３，７］は、２以下、または８以上のどのようなイベント値も決して被覆しない。そのため、本発明は、あるビット位置をビットマップ・ベクトルから取り除くことができる。実際、本発明は、ビットマップ・ベクトルＢｊの最小ＩＤと最大ＩＤを識別することができる。ＳＣＩの場合、最小ＩＤは（ｊ−Ｌ）Ｌ＋Ｌ−１であり、最大ＩＤはｊＬ＋Ｌ−１である。これら２つの境界の外側のビット位置は除去することができ、その結果、ストレージ・コストが節約される。
【００２７】
ユーザ関心事を２以上の述語節によって指定することができ、そのいくつかは等式節になり、残りが不等式節になる場合があることも、当業者であれば理解されよう。本発明で開示される区間索引は、区間述語と等式述語の両方を有するアトリビュートを索引付けするのに使用することができる。この場合、本発明は、等式を長さが０の仮想構成区間として取り扱う。さらに、個々のアトリビュートのイベント値の高速照合のため、個々のアトリビュート用に別個の区間索引を使用することができる。最終的な結果は、別個のアトリビュートからの個々の結果を結合することによって取得される。
【００２８】
述語区間が無限区間（open-ended interval）でよいことも、当業者であれば理解されよう。この場合、本発明は、２つの特殊なＶＣＩとして、すなわち、右無限区間を表す［ｂｍａｘ，∞）と、左無限区間を表す（−∞，ａｍｉｎ］として、２つの無限区間を取り扱う。ａｍｉｎより小さい任意のイベント値は、左端点として−∞を有するすべての述語区間を見つける。同様に、ｂｍａｘより大きい任意のイベント値は、右端点として∞を有するすべての述語区間を見つける。
【００２９】
本発明は、仮想構成区間と呼ばれる新しい概念を導入し、各述語区間は、１組のこの構成区間に分解される。各構成区間は、一意のＩＤまたは区間座標と、１組の端点を有する。構成区間は、それを分解に使用する述語区間がシステムに追加されたとき、活動化されると考えられる。各アトリビュート値毎に、ビットマップ索引が、そのアトリビュート値を被覆する任意の仮想構成区間の活動化を示すのに使用される。難しいのは、述語分解を簡潔にする適切な１組の構成区間を見つけることであり、より重要で難しいのは、効率的なビットマップ索引を構築することである。各構成区間はアトリビュート値の僅かな範囲を被覆するに過ぎないので、ビットマップ・クリッピングを用いて、不必要なビットマップの保存を削減する。ビットマップ・クリッピングを容易にするため、被覆セグメントの概念を導入する。被覆セグメントの外部のビット位置が取り除かれる。
【００３０】
本発明を好ましい実施形態によって説明してきたが、添付の特許請求の範囲の主旨および範囲の内で本発明に修正を施し得ることは、当業者には理解されよう。
【図面の簡単な説明】
【００３１】
【図１】本発明を配置できる分散システム環境のブロック図である。
【図２】本発明を実施するシステムのブロック図である。
【図３】１つまたは複数の述語区間の存在下でイベント照合を実行する問題を示した一例の図である。
【図４】１組の単純構成区間（ＳＣＩ）の一例の図である。
【図５】述語挿入ハンドラを実施するフローチャートである。
【図６】イベント照合ハンドラを実施するフローチャートである。
【図７】述語削除ハンドラのフローチャートである。
【図８】単純構成区間を使用するＶＣＩ索引付けを示した一例の図である。
【図９】対数構成区間（ＬＣＩ）の一例の図である。
【符号の説明】
【００３２】
１００  クライアント
１０１  クライアント
１０２  データ・ソース
１０３  データ・ソース
１０４  サービス・プロバイダ
１０５  サービス・プロバイダ
１０６  通信ネットワーク
２０１  ユーザ関心事
２０２  イベント値
２０３  出力
２１０  区間索引付け方法
２１１  述語挿入ハンドラ
２１２  イベント照合ハンドラ
２１３  述語削除ハンドラ
２１４  ユーザ・アカウント・マネージャ
２３０  コンピュータ・システム
２３１  メイン・メモリ
２３２  ディスク
２３３  ＣＰＵ
３１１  述語区間
３１２  述語区間
３１３  述語区間
３１４  述語区間
３１５  述語区間
３１６  述語区間
３１７  述語区間
３１８  述語区間
３１９  述語区間
８０１  述語ｑ：［ａ０，ａ０＋２］
８０２  述語ｐ：［ａ０，ａ０＋６］
８１０  ビットマップ・ベクトル
８１１  ビットマップ・ベクトル
８１２  ビットマップ・ベクトル
８１３  ビットマップ・ベクトル
８１４  ビットマップ・ベクトル
８１５  ビットマップ・ベクトル
８１６  ビットマップ・ベクトル
８２０  ポインタ・ヘッダ配列
８２１  ＩＤリスト
８２２  ＩＤリスト
８２３  ＩＤリスト
【図１】
2005108221.tif 000007
【図２】
2005108221.tif 000008
【図３】
2005108221.tif 000009
【図４】
2005108221.tif 000010
【図５】
2005108221.tif 000011
【図６】
2005108221.tif 000012
【図７】
2005108221.tif 000013
【図８】
2005108221.tif 000014
【図９】
2005108221.tif 000015