(57)【要約】【課題】  多経路ストリーム相関を処理するためのコンピュータ実施方法、装置、およびコンピュータ使用可能プログラム・コードを提供すること。【解決手段】  相関のためのストリーム・データが受け取られる。多経路ストリーム相関作業負荷をより小さな作業負荷部片に連続的に区分するための、タスクが形成される。より小さな作業負荷部片のそれぞれを、単一のホストによって処理することができる。ストリーム・データは、相関処理のために異なるホストに送られる。【選択図】  図３
2007299406.tif 000002
【特許請求の範囲】
【請求項１】
多経路ストリーム相関の処理をコンピュータで実施するための方法であって、
相関のためにストリーム・データを受信するステップと、
多経路ストリーム相関の作業負荷をより小さな作業負荷の部片に連続的に区分するために、タスクを形成するステップであって、前記より小さな作業負荷のそれぞれの部片は単一のホストによって処理することが可能である、前記形成するステップと、
前記ストリーム・データを、相関処理のために異なるホストに送信するステップと、
を有する、方法。
【請求項２】
前記形成するステップが、ストリーム区分を実行するためのステップであり、
入力ストリームをセグメントに分割するステップと、
相関処理のために前記異なるホスト上のセグメントに分散するステップと、
をさらに有する、請求項１に記載の方法。
【請求項３】
前記形成するステップが、オペレータ区分を実行するためのステップであり、
多経路相関オペレータを複数のより小さなオペレータに分割するステップと、
異なる分散型ホスト上で異なるより小さなオペレータを実行するステップと、
をさらに有する、請求項１に記載の方法。
【請求項４】
前記多経路ストリーム相関が、複数の入力ストリームを介してスライディング・ウィンドウ結合によって実施される、請求項１に記載の方法。
【請求項５】
前記形成するステップが、連続的な最適化問題を形成するためのステップであり、
相関制約を識別するステップと、
相関制約が満たされること、前記異なるホストの作業負荷が平均化されること、および前記ストリーム・データの複製オーバヘッドを最小化することを保証するために、各ストリーム・データに関するルーティング・パスを計算するステップと、
を含む、請求項１に記載の方法。
【請求項６】
最高率の入力ストリームをマスタ・ストリームとして選択するステップ、および他のストリームをスレーブ・ストリームとして示すステップと、
前記マスタ・ストリームを非結合セグメントに区分するステップと、
相関制約を満たすためにスレーブ・ストリームを重複セグメントに区分するステップと、
をさらに有する、請求項２に記載の方法。
【請求項７】
前記選択するステップが、ランタイム時に動的に変更される、請求項６に記載の方法。
【請求項８】
前記選択するステップが、
前記マスタ・ストリームが任意の他のストリームよりも遅くなることに応答して、前記最高率の入力ストリームをマスタ・ストリームとして選択するため、および他のストリームをスレーブ・ストリームとして示すために、ストリーム・ロール・スイッチを起動するステップと、
前記相関制約に従って前記ストリーム・ロール・スイッチを達成するために遷移段階を採用するステップと、
をさらに有する、請求項７に記載の方法。
【請求項９】
前記マスタ・ストリームを非結合セグメントに区分するステップが、前記非結合セグメントのセグメント長さを調整するためのステップであり、
システム条件が変更された場合に、セグメント適応を起動するステップと、
新しいセグメント長さを探索するためにサンプリング・ベースのプロファイリング・プロセスを実行するステップと、
をさらに有する、請求項６に記載の方法。
【請求項１０】
前記オペレータ区分が、
前記多経路相関の処理を複数のホップに分割するために結合順序を決定するステップと、
各ホップの相関セグメントの位置をルックアップするステップと、
前記各ホップの相関セグメントをすべてカバーする最小ホスト・セットを計算するステップと、
をさらに有する、請求項３に記載の方法。
【請求項１１】
前記結合順序が、異なるストリーム間で観察される結合選択性によって決定される、請求項１０に記載の方法。
【請求項１２】
前記ルックアップするステップが、ルーティング・テーブルを使用して実行され、前記ルーティング・テーブルは、異なる入力ストリームのスライディング・ウィンドウ内の前記相関セグメントの配置情報を含む、請求項１０に記載の方法。
【請求項１３】
前記計算するステップが、
以前のホップによるホスト・セット選択を考慮するステップと、
中間結果の転送を最低限にするために、前記以前のホップによって選択された前記ホストを再使用するステップと、
をさらに有する、請求項１０に記載の方法。
【請求項１４】
相関のために入力ストリームからストリーム・データを受信するため、および多経路ストリーム相関の作業負荷をより小さな作業負荷の部片に連続的に区分するためのタスク形成のための、データ処理システムであって、前記より小さな作業負荷の部片のそれぞれが単一のホストによって処理可能であり、前記タスクが、多経路相関オペレータを複数のより小さなオペレータに分割するため、および異なる分散型ホスト上で異なるより小さなオペレータを実行するために、オペレータ・区分を実行するため、ならびに入力ストリームをセグメントに分割するため、および相関処理のためにホスト上のセグメントに分散するために、ストリーム区分を実行するためのものである、データ処理システムと、
前記データ処理システムに動作可能に接続された、複数のホストと、
を備え、前記データ処理システムが前記相関処理のために前記複数のホストに前記ストリーム・データを送信する、システム。
【請求項１５】
前記データ処理システムが、最高率の入力ストリームをマスタ・ストリームとして選択し、他のストリームをスレーブ・ストリームとして示し、前記マスタ・ストリームを非結合セグメントに区分し、相関制約を満たすためにスレーブ・ストリームを重複セグメントに区分する、請求項１４に記載のシステム。
【請求項１６】
請求項１〜１３のいずれか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に改善されたデータ処理システムに関し、とりわけ、データ・ストリームを処理するためのコンピュータ実施方法および装置に関する。さらに具体的に言えば、本発明は、多経路（multi-way）データ・ストリーム相関をスケーラブルに処理するためのコンピュータ実施方法、装置、およびコンピュータ使用可能プログラム・コードに関する。
【背景技術】
【０００２】
本発明は、米国国防省によって認められた契約第ＴＩＡ  Ｈ９８２３０−０５−３−０００１号の下で政府の支援により作成された。政府は、本発明に対して一定の権利を有する。
【０００３】
ストリーム処理コンピューティング・アプリケーションとは、データに関する何らかの制限を満たす情報の流れの形でデータがシステムに入るアプリケーションである。処理されるデータの量は格納できないほど大量である可能性があるため、情報の流れは、センサ・データ分析およびネットワーク・トラフィック監視などの、動的なデータ・ストリームを介した高度なリアルタイム処理を必要とする。ストリーム処理コンピューティング・アプリケーションの例には、ビデオ処理、オーディオ処理、ストリーミング・データベース、およびセンサ・ネットワークが含まれる。これらのアプリケーションでは、外部ソースからのデータ・ストリームがデータ・ストリーム管理システムに流れ込み、ここで様々な連続する照会オペレータによって処理される。
【０００４】
無制限のストリームをサポートするために、ストリーム処理システムは、各ストリームにスライディング・ウィンドウ（sliding-window）を関連付ける。スライディング・ウィンドウは、ストリーム上で最も新しく到着したデータ項目を含む。ウィンドウは、最新の６０秒以内に到着したビデオ・フレームなどの時間ベース、または最新の１０００のビデオ・フレームなどの数量ベースの、いずれかとすることができる。最も重要な連続する照会オペレータのうちの１つが、複数の異なるデータ・ストリームにわたるスライディング・ウィンドウ結合である。スライディング・ウィンドウ結合の出力は、事前に定義された結合述部を満たし、それらのそれぞれのウィンドウ内に同時に存在する、相関されたタプルのすべてのセットを含む。
【０００５】
いくつかのアプリケーション例には、ホット・トピックを検出するために異なるニュース・ビデオ・ストリーム間で同様のイメージを検索すること、および、侵入を検出するために異なるネットワーク・トラフィック・フロー間でソース／宛先アドレスを相関させることが含まれる。多くのストリーム相関アプリケーションがキー比較よりも複雑な結合述部を要求するため、キー・ベースの等価結合はあまり効果的でない場合がある。たとえばニュース・ビデオ相関アプリケーションでは、結合条件は、２つのイメージの４０次元分類値間の距離がしきい値より短いかどうかである。したがって、異なるストリームのデータを相関させるということは、１つまたは複数の事前に定義された相関述部を満たす異なるストリーム上でそれらのデータを見つけることを意味する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
多経路のストリーム結合を処理するための主な課題は、複数の高容量および時変化のデータ・ストリームにわたってリアルタイムで多数の結合比較を実行することである。高ストリーム・レートおよび大規模ウィンドウ・サイズが与えられた場合、ウィンドウ表示されたストリーム結合は大規模メモリ要件を有する可能性がある。さらに、イメージ比較などのいくつかの照会処理は、中央処理装置集約型となる可能性もある。単一のホストでは、多経路ストリーム結合の作業負荷によって容易に過負荷となる可能性がある。
【課題を解決するための手段】
【０００７】
例示的な諸実施形態は、多経路ストリーム相関を処理するためのコンピュータ実施方法、装置、およびコンピュータ使用可能プログラム・コードを提供する。相関のためにストリーム・データが受信される。多経路ストリーム相関の作業負荷をより小さな作業負荷の部片に連続的に区分するために、タスクが形成される。より小さな作業負荷のそれぞれの部片を、単一のホストによって処理することができる。ストリーム・データは、相関処理のために異なるホストに送信される。
【０００８】
例示的諸実施形態の特徴であるとみなされる新規な機能は、添付の特許請求の範囲に記載される。しかしながら例示的諸実施形態自体、ならびにそれらの好ましい使用方法、他の目的および利点は、添付の図面と共に例示的実施形態の以下の詳細な説明を参照することによって、最も良く理解されるであろう。
【発明を実施するための最良の形態】
【０００９】
次に図面、特に図１〜図２を参照すると、例示的諸実施形態が実施可能なデータ処理環境の例示的図面が提供されている。図１〜図２は単なる例であり、異なる諸実施形態が実施可能な環境に関していかなる制限も表明または暗示することを意図するものでないことを理解されたい。示された環境に対する多くの修正形態が実行可能である。
【００１０】
次に図面を参照すると、図１は、例示的諸実施形態が実施可能なデータ処理システムのネットワークを示す絵画図である。ネットワーク・データ処理システム１００は、諸実施形態が実施可能なコンピュータのネットワークである。ネットワーク・データ処理システム１００は、様々なデバイス間の通信リンクと、ネットワーク・データ処理システム１００内で互いに接続されたコンピュータとを提供するために使用される媒体である、ネットワーク１０２を含む。ネットワーク１０２は、有線、無線通信リンク、または光ファイバケーブルなどの、接続を含むことができる。
【００１１】
示された例では、サーバ１０４およびサーバ１０６が、ストレージ・ユニット１０８と共にネットワーク１０２に接続する。加えて、クライアント１１０、１１２、および１１４がネットワーク１０２に接続する。これらのクライアント１１０、１１２、および１１４は、たとえばパーソナル・コンピュータまたはネットワーク・コンピュータとすることができる。示された例では、サーバ１０４が、ブート・ファイル、オペレーティング・システム・イメージ、およびアプリケーションなどのデータを、クライアント１１０、１１２、および１１４に提供する。クライアント１１０、１１２、および１１４は、この例ではサーバ１０４に対するクライアントである。ネットワーク・データ処理システム１００は、図示されていない追加のサーバ、クライアント、および他のデバイスを含むことができる。
【００１２】
示された例において、ネットワーク・データ処理システム１００は、互いに通信するために伝送制御プロトコル／インターネット・プロトコル（ＴＣＰ／ＩＰ）のプロトコル・スイートを使用する、ネットワークおよびゲートウェイの世界的な集合体を表すネットワーク１０２を備えたインターネットである。インターネットの心臓部は、データおよびメッセージをルーティングする何千もの商用、行政用、教育用、およびその他のコンピュータ・システムからなる、主ノードまたはホスト・コンピュータ間の高速データ通信回線のバックボーンである。もちろん、ネットワーク・データ処理システム１００は、たとえばイントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）、またはワイド・エリア・ネットワーク（ＷＡＮ）などの、いくつかの異なるタイプのネットワークとして実施することも可能である。図１は一例であり、様々な諸実施形態に対するアーキテクチャ上の制限として意図されたものではない。
【００１３】
次に図２を参照すると、例示的諸実施形態が実施可能なデータ処理システムのブロック図が示されている。データ処理システム２００は、プロセスを実施するコンピュータ使用可能コードまたは命令を例示的諸実施形態に関して配置することができる、図１のサーバ１０４またはクライアント１１０などのコンピュータの一例である。
【００１４】
示された例では、データ処理システム２００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ＭＣＨ）２０２とサウス・ブリッジおよび入力／出力（Ｉ／Ｏ）コントローラ・ハブ（ＩＣＨ）２０４とを含む、ハブ・アーキテクチャを採用する。プロセッサ２０６、主メモリ２０８、およびグラフィックス・プロセッサ２１０は、ノース・ブリッジおよびメモリ・コントローラ・ハブ２０２に結合される。グラフィックス・プロセッサ２１０は、たとえばアクセラレーテッド・グラフィックス・ポート（ＡＧＰ）を介して、ＭＣＨに結合することができる。
【００１５】
示された例では、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２がサウス・ブリッジおよびＩ／Ｏコントローラ・ハブ２０４に結合され、オーディオ・アダプタ２１６、キーボードおよびマウス・アダプタ２２０、モデム２２２、読み取り専用メモリ（ＲＯＭ）２２４、ユニバーサル・シリアル・バス（ＵＳＢ）ポートおよび他の通信ポート２３２、ならびにＰＣＩ／ＰＣＩｅデバイス２３４は、バス２３８を介してサウス・ブリッジおよびＩ／Ｏコントローラ・ハブ２０４に結合され、ハード・ディスク・ドライブ（ＨＤＤ）２２６およびＣＤ−ＲＯＭドライブ２３０は、バス２４０を介してサウス・ブリッジおよびＩ／Ｏコントローラ・ハブ２０４に結合される。ＰＣＩ／ＰＣＩｅデバイスは、たとえばイーサネット（登録商標）・アダプタ、アドイン・カード、およびノートブック・コンピュータ用のＰＣカードを含むことができる。ＰＣＩはカード・バス・コントローラを使用するが、ＰＣＩｅは使用しない。ＲＯＭ  ２２４は、たとえばフラッシュ・バイナリ入力／出力システム（ＢＩＯＳ）とすることができる。ハード・ディスク・ドライブ２２６およびＣＤ−ＲＯＭドライブ２３０は、たとえばＩｎｔｅｇｒａｔｅｄ  Ｄｒｉｖｅ  Ｅｌｅｃｔｒｏｎｉｃｓ（ＩＤＥ）またはＳｅｒｉａｌ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ（ＳＡＴＡ）インターフェースを使用することができる。スーパーＩ／Ｏ（ＳＩＯ）デバイス２３６をサウス・ブリッジおよびＩ／Ｏコントローラ・ハブ２０４に結合することができる。
【００１６】
オペレーティング・システムがプロセッサ２０６上で実行され、図２のデータ処理システム２００内の様々なコンポーネントを調整し、それらの制御を提供する。オペレーティング・システムは、Ｍｉｃｒｏｓｏｆｔ（Ｒ）のＷｉｎｄｏｗｓ（Ｒ）ＸＰ（ＭｉｃｒｏｓｏｆｔおよびＷｉｎｄｏｗｓは、米国、他の諸外国、またはその両方にあるＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎの商標である）などの、市販のオペレーティング・システムとすることができる。Ｊａｖａ（ＴＭ）プログラミング・システムなどのオブジェクト指向プログラミング・システムはオペレーティング・システムと共に実行することが可能であり、データ処理システム２００上で実行中のＪａｖａプログラムまたはアプリケーションからオペレーティング・システムへ呼び出しを提供する（ＪａｖａおよびすべてのＪａｖａベースの商標は、米国、他の諸外国、またはその両方にあるＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．の商標である）。
【００１７】
オペレーティング・システム、オブジェクト指向プログラミング・システム、およびアプリケーションまたはプログラムに関する命令は、ハード・ディスク・ドライブ２２６などのストレージ・デバイス上に配置され、プロセッサ２０６による実行のために主メモリ２０８にロードすることができる。例示された諸実施形態のプロセスは、たとえば、主メモリ２０８、読み取り専用メモリ２２４などのメモリ内、あるいは１つまたは複数の周辺デバイス内に配置可能な、コンピュータ実施命令を使用するプロセッサ２０６によって実行可能である。
【００１８】
図１〜図２のハードウェアは、実施によって変更可能である。フラッシュ・メモリ、等価の不揮発性メモリ、または光ディスク・ドライブなどの、他の内部ハードウェアまたは周辺デバイスを、図１〜図２に示されたハードウェアに加えて、またはそれらの代わりに使用することができる。また、例示的諸実施形態のプロセスをマルチプロセッサ・データ処理システムに適用することもできる。
【００１９】
いくつかの例では、データ処理システム２００は、一般に、オペレーティング・システム・ファイルおよび／またはユーザ生成データを格納するために不揮発性メモリを提供するためのフラッシュ・メモリで構成される、携帯情報端末（ＰＤＡ）とすることができる。バス・システムは、システム・バス、Ｉ／Ｏバス、およびＰＣＩバスなどの、１つまたは複数のバスで構成することができる。もちろん、バス・システムは、ファブリックまたはアーキテクチャに取り付けられた様々なコンポーネントまたはデバイス間でのデータの転送に備えた、任意のタイプの通信ファブリックまたはアーキテクチャを使用して実施することができる。通信ユニットは、モデムまたはネットワーク・アダプタなどの、データの送信および受信に使用される１つまたは複数のデバイスを含むことができる。たとえばメモリは、ノース・ブリッジおよびメモリ・コントローラ・ハブ２０２に見られるような、主メモリ２０８またはキャッシュとすることができる。処理ユニットは、１つまたは複数のプロセッサまたはＣＰＵを含むことができる。図１〜図２に示された例および前述の例は、アーキテクチャ上の制限を示唆するものではない。たとえばデータ処理システム２００は、ＰＤＡの形を取る以外に、タブレット・コンピュータ、ラップトップ・コンピュータ、または電話デバイスとすることもできる。
【００２０】
例示的諸実施形態は、処理ユニット、主要ストリーム、および出力データに関するユーザ要件の公式な記述に基づいて、自動的に作業フローを作成するプロセスを提供する。このプロセスは、システム・リソースに過度な負担をかけることなく、また人間の対話なしに、新しく使用可能となった主要ストリーム、処理ユニット、および他の変化するパラメータ、環境、または条件に即時に適合することができる。加えて、作業フローを、ウェブ・サービス実行環境内で実行可能なフォーマットに変換することもできる。
【００２１】
図３は、例示的諸実施形態に従ったストリーム処理の一例を示す図である。この例では、特定の株が所定の値を超えそうな場合に通知するように要求したユーザに、相関結果３５０が渡される。一例では、相関結果は、株価の変動が相関された株のセットである。これらの例では、主要ストリームまたはブロードキャスト・ストリームが、取引３１０、テレビ・ニュース３２０、およびラジオ３３０を含む。示された例では、アプリケーション・コンポーネントが株式分析３１２、Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ  ４（ＭＰＥＧ−４）デマルチプレクサ３２２、イメージ分析３２４、音声テキスト３２６、テキスト分析３２８、音声テキスト３３２、テキスト分析３３４、および多経路ストリーム結合３４０を含む。
【００２２】
ストリーム処理アプリケーションは、使用可能な主要ストリームを使用する既存のアプリケーション・コンポーネントからなるものとすることができるため、アプリケーション・コンポーネントはユーザの要求を満たす結果を生成する。したがって、株式分析３１２は情報ストリームである取引３１０を受け取り、結果を多経路ストリーム結合３４０に出力する。
【００２３】
この例では、ＭＰＥＧ−４デマルチプレクサ３２２がブロードキャスト・ストリームであるテレビ・ニュース３２０を受け取り、イメージ分析３２４、テキスト分析３２８、および音声テキスト３２６へと出力する。次に、音声テキスト３２６がテキスト分析３２８へと出力する。イメージ分析３２４およびテキスト分析３２８は多経路ストリーム結合３４０へと出力する。
【００２４】
音声テキスト３３２は主要ストリームであるラジオ３３０を受け取り、テキスト分析３３４へと出力する。次にテキスト分析３３４が多経路ストリーム結合３４０へと出力する。多経路ストリーム結合３４０は、相関結果３５０の形で出力を提供する。
【００２５】
一実施形態では、ストリーム・プロパティは、ストリーム・オブジェクトでパラメータ化された変数（fluent）および述部として符号化することが可能である。プログラミングにおいて述部とは、式を評価し、データの条件に基づいてｔｒｕｅまたはｆａｌｓｅの回答を提供する、ステートメントのことである。これらの条件は、ストリーム・プロパティの観点から論理式として表される。変数とは、述部よりも一般的な関数のことである。変数は、述部のブール・ドメイン以外のドメインから値を取ることができる。変数は、文献では関数とも呼ばれる。コンポーネント記述は、入力および出力ストリーム・オブジェクトでパラメータ化されたアクションとして符号化される。アクションの前提条件は、入力ストリームに関する変換済み入力ポート要件からなり、アクションの結果が、出力ポートに関連付けられた変換公式を使用して、出力ストリーム・オブジェクトのプロパティを計算する。一連のアクションとしてプランニング・システムによって生成されたプランは、その後、ポートに対応するインスタンス生成アクション・パラメータ間でのストリーム・オブジェクトの共有に基づいて、入力出力ポート接続を識別することにより、作業フローに変換される。
【００２６】
例示的諸実施形態は、多経路ストリーム結合を処理するためのスケーラブルな分散ソリューションのために、コンピュータ実施方法、装置、およびコンピュータ使用可能プログラム・コードを提供する。多くのストリーム相関アプリケーションが、キー比較よりも複雑な結合述部を要求するため、等価結合および非等価結合などの総称的なストリーム結合が考慮される。
【００２７】
例示的諸実施形態は、多経路ストリーム結合の分散型実行を可能にする、相関認識タプル・ルーティング・フレームワークを対象とする。分散方式は、スライディング・ウィンドウ結合セマンティクスを観察することができる。スライディング・ウィンドウ結合の出力は、事前に定義された結合述部を満たし、それらのそれぞれのウィンドウ内に同時に存在する、相関済みタプルのすべてのセットを含む。分散オーバヘッドは、相関制約によるスライディング・ウィンドウ結合セマンティクスを維持するために不可避である。結果として、例示的諸実施形態は、分散オーバヘッドが最小限の分散型ホストのセット間で、多経路ストリーム結合オペレータの作業負荷を最適に分散することに対処する。分散オーバヘッドとは、システム・リソースの使用または過度の使用のことである。たとえば、分散オーバヘッドは、着信するデータ・ストリームを処理するために必要なプロセッサの消費時間、メモリ・スペース、およびネットワーク帯域幅を含むことができる。
【００２８】
例示的一実施形態では、整列（aligned）タプル・ルーティング（ＡＴＲ）方法または方式が、ストリーム区画を使用する多経路ストリーム結合の分散型実行を達成する。整列タプル・ルーティングは、最も高速の入力ストリームをマスタ・ストリームとして動的に選択し、相関制約を満たすために他のストリームのタプル・ルーティングをマスタ・ストリームと整列させる。整列タプル・ルーティングは、入力ストリームを、結合処理のために異なるホストにルーティングされるセグメントに分割する。セグメントとは、ストリームの一部分またはセクションのことである。結合処理は相関処理とも呼ばれる。整列タプル・ルーティングを使用して、結合セマンティクスを保持することができる。さらに、整列タプル・ルーティングのオーバヘッドはホストの数とは無関係である。その代わりに、整列タプル・ルーティングのオーバヘッドは、スライディング・ウィンドウのサイズおよびスレーブ・ストリームにのみ関係する。その結果、整列タプル・ルーティングは、スレーブ・ストリームが低く、スライディング・ウィンドウのサイズがそれほど大きくない場合に好適である。
【００２９】
他の例示的実施形態では、制約付き（constrained）タプル・ルーティング（ＣＴＲ）方式が、相関制約の下で異なるストリームのタプルを別々にルーティングする。制約付きタプル・ルーティングは、ストリーム区画およびオペレータ区画の両方を使用して、多経路ストリーム結合オペレータを分散する。整列タプル・ルーティングとは異なり、制約付きタプル・ルーティングは、かなり大規模な多経路結合を、異なるホストによって実行されるより小さな多経路結合のセットに区分することができる。相関されたタプルを負荷の少ないホストの最小限のセットでカバーすることにおける問題は、制約付きタプル・ルーティングの方法、プロセス、およびアルゴリズムによって対処される。制約付きタプル・ルーティングは結合セマンティクスを保持するために使用され、ホストの数とは無関係なオーバヘッドを有する。整列タプル・ルーティングとは異なり、制約付きタプル・ルーティングのオーバヘッドはスライディング・ウィンドウのサイズとは無関係であり、それによって制約付きタプル・ルーティングは、大規模なスライディング・ウィンドウ仕様を供えた結合オペレータにとってより好適なものとなる。
【００３０】
連続するストリームをサポートするために、ストリーム処理システムはスライディング・ウィンドウを各ストリームに関係付ける。ウィンドウは、タプルと呼ばれる最も新しく到着したストリーム上のデータ項目を含む。タプルとは、値またはストリーム・データのセットのことである。ストリーム内のデータはストリーム・データとも呼ばれ、１つまたは複数のデータ・ストリームから現れるビット、ワード、番号、または他のストリーミング・データの形で受け取られる情報である。ウィンドウは時間ベースまたはタプル・ベースとすることができる。時間ベース・ウィンドウは、たとえば最新の１０分間に到着したタプルとすることが可能であり、タプル・ベース・ウィンドウは、たとえば最新の１０００のタプルとすることが可能である。重要な連続する照会オペレータの１つが、ストリームＳ１およびＳ２という２つのストリーム間のスライディング・ウィンドウ結合である。このウィンドウ結合の出力は、結合述部を満たし、それらのそれぞれのウィンドウ内に同時に存在する、ストリームＳ１およびＳ２からのあらゆるタプルのペアを含む。
【００３１】
結合述部は、２つのタプル間の１つまたは複数の共通属性を介した比較関数である。基本的な結合述部は、共通属性Ａを介した２つのタプルｓ１およびｓ２の間の同等比較であり、ｓ１．Ａ＝ｓ２．Ａで示される。しかしながら、例示方式は、任意の総称結合述部に適用することができる。スライディング・ウィンドウ結合は、多くの適用例を有する。たとえば、一方のストリームが電話の呼び出し記録を含み、他方のストリームが株式の取引記録を含む、２つのストリームを考えてみる。共通属性「取引識別子」を介して不審な電話呼び出しと異常な取引記録との間を相関または結合するように動作する、スライディング・ウィンドウ結合を使用して、取引詐欺警告を生成することができる。
【００３２】
図４は、例示的実施形態に従った、スライディング・ウィンドウ・ストリーム結合オペレータ・モデルを示す図である。図４は、スライディング・ウィンドウ結合のセマンティクスを記述し、集中ウィンドウ表示された結合処理プロセスを提示するために使用される。多経路ストリーム結合オペレータ４００は、図１のサーバ１０４および１０６またはクライアント１１０、１１２、および１１４などの、サーバまたはクライアント内で実施することができる。
【００３３】
多経路ストリーム結合オペレータ４００は、ストリーム１  ４０２、ストリーム２  ４０４、ストリーム３  ４０６、およびストリーム４  ４０８を含む、Ｓｉで示された様々なデータ・ストリームを含む。データ・ストリームは、ｓｉ∈Ｓｉで示される一連のタプルまたはデータ項目からなる。各ストリームは可変データ到着を有することができる。たとえばｒｉは、現在の時間間隔にわたるストリームＳｉの平均到着を示す。動的ストリーム環境では、平均ストリームｒｉは経時的に変化する可能性がある。この例では、各タプルｓｉ∈Ｓｉは、タプルｓｉがストリームＳｉに到着した時点を示すためのタイム・スタンプｓｉ．ｔを担持する。Ｓｉ［ｔ１，ｔ２］などの言語は、すべてのタプルが時間［ｔ１，ｔ２］の間にストリームＳｉに到着したことを示す。
【００３４】
無限のデータ・ストリームを取り扱う場合、結合処理の範囲を最近到着したタプルに限定するために、各ストリームにスライディング・ウィンドウが関連付けられる。たとえば、Ｓｉ［Ｗｉ］はストリームＳｉ上のスライディング・ウィンドウを示し、ここでＷｉは時間ユニット内のウィンドウの長さを示す。時間間隔［ｔ−Ｗｉ，ｔ］内でｓｉがＳｉに到着した場合、時間ｔでｓｉはＳｉ［Ｗｉ］に属する。結果として、Ｓｉ［Ｗｉ］はＳｉ［ｔ−Ｗｉ，ｔ］の頭字語とみなすことができる。
【００３５】
ｎ＝２の、ｎ入力ストリーム間の多経路ストリーム結合オペレータ４００は、
【数１】
2007299406.tif 000003
によって示される。多経路ストリーム結合オペレータ４００の出力は、すべてのタプル・グループ（ｓ１、ｓ２、．．．、ｓｎ）からなり、その結果、時間ｓｉ．ｔで∀ｓｉ∈Ｓｉ、∀ｓｋ∈Ｓｋ［Ｗｋ］、１≦ｋ≦ｎ、ｋ≠ｉとなり、ｓ１、．．．、ｓｎが事前に定義された結合述部θ（ｓ１、．．．、ｓｎ）を満たす。結合述部は、多次元空間における距離関数などの任意の総称関数とすることができる。たとえば図１では、結合結果は、ｓ３＜８＞  ４１０で示される、時間８に到着したストリーム３  ４０６のタプルｓ３  ４１０を含むとみなされる。ｓｉ＜ｔ＞は、時間ｔにＳｉに到着したタプルを示す。多経路ストリーム結合オペレータ４００は、ストリーム３  ４０６のｓ３＜８＞  ４１０と、時間８のスライディング・ウィンドウＳ１［Ｗ１］、Ｓ２［Ｗ２］、およびＳ４［Ｗ４］に含まれるすべてのタプルとを比較する。たとえば、多経路ストリーム結合オペレータ４００で、タプルｓ３＜８＞  ４１０は、第１にＳ４［４，７］４１２のタプルと結合する必要がある。
【００３６】
図５は、例示的実施形態に従った、分散型多経路ストリーム結合実行モデルを示す図である。多経路ストリーム結合は、しばしばリソース集約型である。たとえば、多経路ストリーム結合は、すべてのスライディング・ウィンドウ内のタプルをバッファリングするための大規模なメモリ要件、および複数の入力ストリーム間での莫大な数の結合プローブに関する高速処理要件を有する可能性がある。単一のホストは、多経路ストリーム結合照会処理によって容易に過負荷になる可能性がある。多経路ストリーム結合を処理するためのスケーラブルな分散型ストリーム処理システム５００が、これらの問題に対処する。スケーラブルな分散型ストリーム処理システム５００は、高速ネットワーク５０８によって接続された、拡散（diffusion）オペレータ５０２  ＯＰｄ、融合（fusion）オペレータ５０４  ＯＰｆ、およびサーバ・ホスト５０６のクラスタＶ１からなる。
【００３７】
サーバ・ホスト５０６のクラスタは、図１のすべてのネットワーク１０２などのネットワークによって相互接続されたサーバ１０４および１０６などのサーバを含むことができる。
【００３８】
融合オペレータ５０４および拡散オペレータ５０２は、図２のデータ処理システム２００などの、汎用コンピュータ上に実装可能なソフトウェア・モジュールである。拡散オペレータ５０２は、複数の分散型ホストへの多経路ストリーム結合の作業負荷を加速させる可能性がある。融合オペレータ５０４は、分散した結合結果を、図３の相関結果などの完全な相関結果に統合する。
【００３９】
拡散オペレータ５０２は、結合処理のために入力タプル５１０を入力ストリーム５１２から異なるサーバ・ホスト５０６へと動的にルーティングし、融合オペレータ５０４は、分散した結合結果５０８を完全な照会回答５１４へと集約することができる。結合オペレータとは異なり、拡散オペレータ５０２は単純なタプル・ルーティング計算を実行し、入力ストリーム５１２のバッファリングはほとんど必要でない。拡散オペレータ５０２の処理時間は、しばしば、結合計算のそれの数分の１以下である。したがって、拡散オペレータ５０２は、スケーラブルな分散型ストリーム処理システム５００におけるボトルネックではない。
【００４０】
分散型結合を実行するための基本要件の１つが、結合結果の正確さを保持することである。タプル・ルーティング方式は、いかなる結合結果も失われないか、または重複した結合結果を生成しないはずである。しかしながら、総当り（brute-force）タプル・ルーティング方式は、多重ストリーム相関制約または相関制約に違反する可能性がある。前述の例では、図４の多経路ストリーム結合オペレータ４００で、タプルｓ３＜８＞  ４１０は第１にタプルと結合する必要がある。Ｓ４［４，７］４１２内のタプルと結合する必要がある。図４のＳ４［４，７］４１２内のタプルは、分散型実行方式によって、サーバ・ホスト５０６などの様々なホスト上で分散されることが可能である。タプルｓ４＜４＞；ｓ４＜５＞；ｓ４＜６＞がｖ１  ５０６に配置され、タプルｓ４＜５＞；ｓ４＜６＞；ｓ４＜７＞がｖ２  ５０６に配置されると想定する。ｓ３＜８＞がｖ１  ５０６またはｖ２  ５０６のいずれかに送られた場合、いくつかの結合結果が失われる。ｓ３＜８＞がｖ１  ５０６およびｖ２  ５０６の両方に送られた場合、重複した結合結果が生成される可能性がある。スライディング・ウィンドウ結合セマンティクスを保持するために、タプル・ルーティング方式は、以下の相関制約を満たすように注意深く設計しなければならない。
【００４１】
定義１：ｎ経路の結合オペレータ
【数２】
2007299406.tif 000004
とすると、Ｊｉによって相関されなければならない任意の（ｓ１、ｓ２、．．．、ｓｎ）、ｓｉ∈Ｓｉ、１≦ｋ≦ｎが、同じホスト上に１回だけ現れる。
【００４２】
分散型多経路結合の実行が、タプルを複製するか、または相関制約を満たすために中間結合結果をルーティングするかの、いずれかを必要とすることを証明する場合、ｎ個の入力ストリームからのタプルが、相関の必要がある入力ストリームを表すようにする。これとは反対に、複数のホスト上でタプルが複製されず、さらに異なるホストにわたって中間結果もルーティングされないと想定する。あらゆる２つの連続するタプルｓｉ＜ｔｉ＞およびｓｊ＜ｔｊ＞、０≦ｔｊ−ｔｉ＜Ｗｉを考えてみると、ｉ≠ｊの場合、ｓｊ＜ｔｊ＞はｓｉ＜ｔｉ＞を相関させる必要があるため、ｓｊ＜ｔｊ＞はｓｉ＜ｔｉ＞と同じホストにルーティングされる必要がある。ｉ＝ｊの場合、ｓｊ＜ｔｊ＞はｓｉ＜ｔｉ＞と結合されたタプルと結合する必要があるため、ここでもｓｊ＜ｔｊ＞はｓｉ＜ｔｉ＞と同じホストにルーティングされる必要がある。その後、ｎ入力ストリームのすべての相関されたタプルが、同じホストにルーティングされ、これが集中結合実行となる。
【００４３】
したがって、分散型結合の実行では、異なるホスト間でのタプルの複製または中間結果のルーティングが必要であり、これが拡散オーバヘッドと呼ばれる。これらのオーバヘッド・タプルおよびルーティング動作は、システム内のプロセッサの時間、メモリ・スペース、およびネットワーク帯域幅を消費する可能性がある。結果として、拡散オペレータの目標は、相関制約の下で最適な分散型結合実行を達成することである。相関制約は、正式には以下のように定義される。
【００４４】
定義２：結合オペレータ
【数３】
2007299406.tif 000005
およびｍ個のホスト｛ｖ１、．．．、ｖｍ｝とすると、各タプルは１つまたは複数のホストに最適にルーティングされ、その結果（１）相関制約が満たされ、（２）異なるホストの作業負荷が最適に平均化され、（３）拡散オーバヘッドが最小化される。
【００４５】
図６〜図７は、例示的実施形態に従った、相関認識タプル・ルーティング方式を示す図である。図６〜図７は、多経路ストリーム結合オペレータのスケーラブルな処理のための、相関認識タプル・ルーティング方式のセットを表す。図６〜図７の方式は、単一の結合オペレータが、複数のホスト６０２のリソースまたは複数の結合オペレータを利用して、細かい細分性で複数のホスト６０２のリソースを共有できるようにする。細分性は、作業負荷区画のサイズを示す。細分性が細かいということは、相関作業負荷を、異なるホスト上に分散可能なより小さな部片に分割できるという意味である。ホストは、図１のサーバ１０４および１０６などの、複数の相互接続サーバとすることができる。
【００４６】
タスクとは、コンピュータ・システムが事前に定義された目標の達成に着手するプロセスのことである。多経路ストリーム相関作業負荷とは、複数の入力ストリームにわたって相関処理を実行するために必要な処理要件、メモリ、および帯域幅などの、コンピュータ・リソースの量である。連続的最適化プロセスとは、動的なコンピューティング環境において最適な性能を達成し、連続的最適化の問題を解決するために、コンピュータ・システムの動作を連続的に調整することである。相関処理などの結合処理は、１つのストリームのタプルを他のすべてのストリームのタプルと相関させることに着手するためにコンピュータ・システムが必要とする、動作のセットを含む。
【００４７】
高い水準では、相関認識タプル・ルーティング方式のセットは、分散型多経路ストリーム結合の実行を、（１）ストリーム区画：入力ストリームを、異なるホスト６０２にルーティングされるセグメントに分割すること、および（２）オペレータ区画：多経路結合オペレータを、異なるホスト６０２上で処理される相関を使用して計算されるサブオペレータに分割すること、という２つの側面で達成する。
【００４８】
図６は、ストリーム区画のみを実行する、整列タプル・ルーティング（ＡＴＲ）と呼ばれる単純な相関認識タプル・ルーティング方式である。図６は、４つのホスト６０２を使用して３経路結合オペレータを実行する、整列タプル・ルーティング方式６００の分散スナップショットを示す図である。相関制約を満たすために、整列タプル・ルーティング方式６００は、すべての入力ストリームに関するタプル・ルーティングを調整し、ストリーム区画の境界付近にあるタプルのサブセットを複製する。整列タプル・ルーティング方式６００は、異なるホスト６０２にまたがって中間結果をルーティングすることのない、１ホップ・ルーティング・プロセスである。各ホスト６０２は、すべての入力タプルのサブセットに関してのみ、全体の結合計算を実行する。
【００４９】
たとえば図６では、ｖ１、ｖ２、ｖ３、およびｖ４のホスト６０２が、それぞれ時間［ｔ，ｔ＋Ｔ）、［ｔ＋Ｔ，ｔ＋２Ｔ）、［ｔ＋２Ｔ，ｔ＋３Ｔ）、および［ｔ＋３Ｔ，ｔ＋４Ｔ）に到着するタプルに関して結合計算を実行する。しかしながら、多経路結合オペレータが多くの入力ストリームを大規模なスライディング・ウィンドウと相関させる場合、整列タプル・ルーティングの分散細分性が粗すぎるために、効の悪いリソース利用および多大な複製オーバヘッドにつながる可能性がある。
【００５０】
図７の制約付きタプル・ルーティング（ＣＴＲ）方式６０４と呼ばれる第２のタプル・ルーティング方式は、ストリーム区画とオペレータ区画の両方を探る。整列タプル・ルーティング方式６００とは異なり、制約付きタプル・ルーティング方式６０４は、中間結合結果６０６を異なるホスト６０２にまたがってルーティングできるようにすることにより、多経路結合計算の実行を複数のホスト６０２間で分離する。結果として、整列タプル・ルーティング・システムは、すべての相関タプルが第１のルーティング・ホップ内の同じホスト上に配置されることを保証する必要がないため、制約付きタプル・ルーティング方式６０４は複製オーバヘッドを削減することができる。
【００５１】
たとえば図７では、制約付きタプル・ルーティング方式６０４は、第１にホストｖ１上でＳ１およびＳ２のタプルを結合し、その後中間結果をホストｖ２にルーティングして、第３のストリームＳ３を結合する。整列タプル・ルーティング方式６００に比べて、制約付きタプル・ルーティング方式６０４には中間結果６０６をルーティングするという余分なオーバヘッドがあるが、より細分性の細かい良好な負荷分散を達成することができる。図７で、制約付きタプル・ルーティング方式６０４は、１つの多経路結合計算を、異なるホスト上で実行可能な複数の２経路結合に分割できるようにすることによって、オペレータ分割を実行する。
【００５２】
整列タプル・ルーティングの方式、方法、およびアルゴリズムについては、以下の図１２および図１６でさらに詳細に説明する。制約付きタプル・ルーティングの方式、方法、およびアルゴリズムについては、以下の図１３、図１４、および図１７でさらに詳細に説明する。
【００５３】
図８は、例示的実施形態に従った、整列タプル・ルーティング・モデルを示す図である。図８は、図６の整列タプル・ルーティング方式６００などの、整列タプル・ルーティング方式の設計細部を提示する。整列タプル・ルーティング・モデル７００は、結合オペレータの入力ストリームのタプルを同時に協調的にルーティングする。整列タプル・ルーティング・モデル７００は、ストリーム区画を使用して分散型ストリーム結合実行を達成する。整列タプル・ルーティング・モデル７００は、マスタ・ストリーム７０２、スレーブ・ストリーム７０４、およびスレーブ・ストリーム７０６を含む。Ｖ１はホストを示し、Ｗ１はスライディング・ウィンドウ・サイズを示し、Ｔはセグメント長さを示す。マスタ・ストリーム７０２はデータ・フロー速度が最高のストリームである。マスタ・ストリーム７０２の速度がスレーブ・ストリームの速度よりも遅くなると、整列タプル・ルーティングは遷移段階を採用してマスタ・ストリーム７０２を変更する。
【００５４】
整列タプル・ルーティングは、連続的最適化の問題を解決するために使用される方式の１つである。整列タプル・ルーティングは、１つの入力ストリームをマスタ・ストリームとして動的に選択し、タイム・スタンプに従ってすべての他の入力ストリームのタプルをマスタ・ストリームと整列させる。これに対して、相関制約を満たすために、他方のストリームは、スレーブ・ストリーム７０４および７０６と呼ばれるマスタ・ストリームの区画に基づいて重複するセグメントに区分される。
【００５５】
一般に、整列タプル・ルーティングは、すべての入力ストリームを、それぞれがある一定の時間間隔内に到着したタプルを含む異なるセグメントに連続的に分割する。スレーブ・ストリーム７０４および７０６のセグメントは、相関制約に基づいてマスタ・ストリーム７０２のセグメントと整列される。整列セグメントに属するタプルは、結合結果を生成するために同じホストにルーティングされる。
【００５６】
図９は、例示的実施形態に従った、制約付きタプル・ルーティング・モデルを示す図である。図９は、図７の制約付きタプル・ルーティング方式６０４などの、制約付きタプル・ルーティング方式の設計細部を含む、制約付きタプル・ルーティング（ＣＴＲ）モデル８００を提示する。制約付きタプル・ルーティング・モデル８００は、異なるストリームのタプルを独立にルーティングする方式である。ストリーム１  ８０２、ストリーム２  ８０４、およびストリーム３  ８０６の各入力ストリームについて、制約付きタプル・ルーティング・モデル８００は、すべての以前の相関タプルの配置に基づいてルーティングを決定する。
【００５７】
制約付きタプル・ルーティングは、連続的最適化の問題を解決するために使用される別の方式である。制約付きタプル・ルーティング・モデル８００は、整列タプル・ルーティング方法のように異なる入力からタプルを同時にルーティングするのではなく、異なる入力ストリームのタプルを別々にルーティングする。図９は、３経路ストリーム結合オペレータに関する制約付きタプル・ルーティング方式を示す。プローブ・シーケンス
【数４】
2007299406.tif 000006
を伴う任意のタプルｓｉ∈Ｓｉ、１≦ｉ≦ｎの場合、制約付きタプル・ルーティングは、
以前の相関タプルの配置に基づいて、タプルｓｉおよびすべての中間結合結果
【数５】
2007299406.tif 000007
１≦ｋ≦ｎ−１に関するルーティングを決定する。
【００５８】
すべての結合オペレータがルーティング計算を実行しなくてすむように、制約付きタプル・ルーティングは、他のｎ−１ストリームと結合するためにｓｉに関するルーティング・パス全体を計算するソース・ルーティング・プロセスとして実施される。各タプルは、結合結果を生成するためにアクセスする必要があるホストのセットを示すために、そのルーティング・パスを担持する。ルーティング計算のオーバヘッドを削減するために、制約付きタプル・ルーティングは、各入力ストリーム上のタプルをセグメントにグループ化し、各セグメントを全体として異なるホストにルーティングする。したがって、制約付きタプル・ルーティングは、各タプルについてではなく、各セグメントについてのルートを計算するだけでよい。セグメント長さは、負荷バランシング細分性とルーティング・オーバヘッドとの間のトレードオフを示す。
【００５９】
制約付きタプル・ルーティングは、以前にルーティングされたセグメントの配置を記録するルーティング・テーブルも維持する。多経路ストリーム結合セマンティクスに基づいて今後のいかなるセグメントとも相関される必要がなければ、セグメント情報はルーティング・テーブルから削除される。
【００６０】
図１０は、例示的実施形態に従った集中結合方法を示す流れ図である。図１０の方法は、図４の多経路ストリーム結合オペレータ４００などの、多経路ストリーム結合オペレータで実施可能である。
【００６１】
このプロセスは、結合されたストリームに関するタプルを受け取ることによって開始する（ステップ９０２）。たとえば、ステップ９０２のオリジナル・データ・ストリームは、入力ストリーム・バッファによって受け取ることができる。ステップ９０２のオリジナル・ストリームは、図４のストリーム１  ４０２、ストリーム２  ４０４、ストリーム３  ４０６、およびストリーム４  ４０８などの、ストリームとすることができる。
【００６２】
次にプロセスは、タイム・スタンプに基づいて処理するために１つのストリームを選択する（ステップ９０４）。たとえばこのストリームは、現在バッファリングされているタプルのタイム・スタンプに従った次のタプルｓｉである。次にプロセスは、選択されたストリームのタイム・スタンプに従って、他のすべてのストリームにおいて満了したタプルにマークを付ける（ステップ９０６）。次にプロセスは、処理が行われ、他のすべてのストリームによって満了した旨のマークが付けられた満了したタプルを、すべてのストリームから除去する（ステップ９０８）。ステップ９０６および９０８は、ステップ９０４で選択されたストリームに関する結合順序を調べるために使用される。
【００６３】
次にプロセスは、この結合順序に基づいて結合結果を生成する（ステップ９１０）。その後プロセスは、ストリーム結合が完了したかどうかを判別する（ステップ９１２）。ストリーム結合が完了していない場合、プロセスは結合されたストリームに関するタプルを受け取る（ステップ９０２）。ステップ９１０で、プロセスは、ステップ９０４で選択されることになる入力ストリーム・バッファＱｉにおける次のストリームまたはタプルを参照するように、ポインタｐｉを更新することもできる。プロセスは、すべてのストリームの処理を続行するために、図に示されるように反復される。ステップ９１２の意思決定でストリーム結合が完了した場合、プロセスは終了する。
【００６４】
図１１は、例示的実施形態に従った多経路ストリーム結合方法を示す流れ図である。図１１の方法は、図５のスケーラブルな分散型ストリーム処理システム５００などの、多経路ストリーム結合システム内で実施可能である。
【００６５】
このプロセスは、結合されたストリームに関するタプルを受け取ることによって開始する（ステップ１００２）。その後プロセスは、拡散オペレータでの各タプルに関するルーティング・パスを計算する（ステップ１００４）。次にプロセスは、拡散オペレータによって計算されたルーティング・パスに基づいて、１つまたは複数のホストへとタプルをルーティングする（ステップ１００６）。次にプロセスは、異なるホストで同時に集中結合を実行する（ステップ１００８）。ホストは、図５のサーバ・ホスト５０６などのサーバ・ホストとすることができる。集中結合は、図９の方法およびステップを含むことができる。
【００６６】
次にプロセスは、融合オペレータでの結合識別に基づいて結合結果を集約する（ステップ１０１０）。融合オペレータは、図５の融合オペレータ５０４などのオペレータとすることができる。その後プロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１０１２）。ストリーム結合が完了した場合、プロセスは終了する。ステップ１０１２でストリーム結合が完了していない場合、プロセスは結合されたストリームに関するタプルを受け取る（ステップ１００２）。完全な結合結果は、すべての入力タプルが処理された時点で完全に生成される。
【００６７】
図１２は、例示的実施形態に従った、整列タプル・ルーティング方法を示す流れ図である。図１２に示されたステップは、図７の整列タプル・ルーティング・モデル７００などの、整列タプル・ルーティング・モデルを使用して実施可能である。図１２のプロセスは、着信タプルを処理するために連続して反復される。
【００６８】
このプロセスは、タプルＳｉを受け取ることによって開始する（ステップ１１０２）。次にステップは、タプルがマスタ・ストリームＳＡに属するかどうかを判別する（ステップ１１０４）。ステップ１１０４の意思決定は、タプルのストリーム識別およびマスタ・ストリームの識別に基づく。タプルがマスタ・ストリームに属する場合、プロセスは新しいセグメントを開始するかどうかを決定する（ステップ１１０６）。ステップ１１０６の意思決定は、タプルのタイム・スタンプおよび現在のセグメントの開始／終了時間に基づく。新しいセグメントを開始するように決定された場合、プロセスは最も新しく選択されたホストｖｂｌａｓｔを格納する（ステップ１１１０）。次にプロセスは、新しいホストＶｂを選択する（ステップ１１１２）。その後プロセスは、新しく選択されたホストＶｂにＳｉを送る（ステップ１１１４）。その後プロセスは、更新済みのセグメント開始時間を、ｔ＝ｔ＋Ｔとして更新する（ステップ１１１６）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１１０９）。
【００６９】
ステップ１１０６に戻り、プロセスが新しいセグメントを開始しないと決定した場合、プロセスは現在のセグメントに関して選択されたホストにＳｉを送る（ステップ１１０８）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１１０９）。プロセスが、ストリーム結合が完了したものと判別した場合、プロセスは終了する。プロセスが、ステップ１１０９でストリーム結合が完了していないと判別した場合、プロセスはタプルＳｉを受け取る（ステップ１１０２）。
【００７０】
ステップ１１０４に戻り、ステップ１１０４でタプルがマスタ・ストリームＳＡに属さないものとプロセスが判別した場合、プロセスは新しいセグメントを開始するかどうかを決定する（ステップ１１１８）。ステップ１１１８の意思決定は、タプルのタイム・スタンプおよび現在のセグメントの開始／終了時間に基づく。プロセスが新しいセグメントを開始しないと決定した場合、プロセスは第１に、現在のセグメントＶｂに関して選択されたホストにＳｉを送る（ステップ１１２０）。次にプロセスは、ｔ＋ＷＡの前にＳｉが到着するかどうかを判別する（ステップ１１２２）。ｔ＋ＷＡの前にＳｉが到着する場合、プロセスは最も新しいセグメントｖｂｌａｓｔに関して選択されたホストにＳｉを送る（ステップ１１２４）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１１０９）。
【００７１】
ステップ１１２２でｔ＋ＷＡの前にＳｉが到着しない場合、プロセスはストリーム結合が完了したかどうかを判別する（ステップ１１０９）。
【００７２】
プロセスがステップ１１１８で新しいセグメントを開始すると決定した場合、プロセスはＳｉ［ｔ＋Ｔ−Ｗｉ，ｔ＋Ｔ］をＶｂへフラッシュする（ステップ１１２６）。次にプロセスは、ＳｉをＶｂおよびＶｂｌａｓｔに送る（ステップ１１２８）。次にプロセスは、セグメント開始時間をｔ＝ｔ＋１として更新する（ステップ１１３０）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１１０９）。図１２のプロセスについては、図１６の擬似コードでさらに詳しく説明する。
【００７３】
図１３〜図１４は、例示的実施形態に従った、制約付きタプル・ルーティング方法を示す流れ図である。図１３〜図１４は、図９の制約付きタプル・ルーティング・モデルなどの制約付きタプル・ルーティング・モデルを使用して実施することができる。
【００７４】
このプロセスは、タプルＳｉを受け取ることによって開始する（ステップ１２０２）。次にプロセスは、新しいセグメントを開始するかどうかを決定する（ステップ１２０４）。プロセスが新しいセグメントを開始すると決定した場合、プロセスはプローブ・シーケンスを取り出す（ステップ１２０６）。次にプロセスは、第１のルーティング・ホップをｖｏ＝０で開始する（ステップ１２０８）。次にプロセスは、ｋ＝１に設定する（ステップ１２１０）。
【００７５】
次にプロセスは、ｋ＜ｎであるかどうかを判別する（ステップ１２１４）。ｋ＞ｎの場合、プロセスはルーティング・テーブル・パスを更新する（ステップ１２１６）。次にプロセスは、セグメント開始時間をｔ＝ｔ＋Ｔとして更新する（ステップ１２１８）。次にプロセスは、新しいセグメントの位置情報をルーティング・テーブルに追加する（ステップ１２２０）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１２２１）。ストリーム結合が完了した場合、プロセスは終了する。ステップ１２２１でストリーム結合が完了していない場合、プロセスはタプルＳｉを受け取る（ステップ１２０２）。
【００７６】
ステップ１２１４でｋ＜ｎである場合、プロセスはＳｉｋ［Ｗｉｋ］内のセグメントの位置を取り出す（ステップ１２２２）。次にプロセスは、前のホップＶｋ−１によってカバーされているそれらのセグメントを除去する（ステップ１２２４）。次にプロセスは、Ｓｉｋ［Ｗｉｋ］に関する最小セット・カバーを計算する（ステップ１２２６）。次にプロセスは、重複を避けるためにルーティング・パスに注釈を付ける（ステップ１２２８）。次にプロセスは、ルーティング・パスＰにＶｋを付加する（ステップ１２３０）。次にプロセスは、ｋ＝ｋ＋１に設定する（ステップ１２３２）。その後プロセスは戻って、ｋ＜ｎであるかどうかを判別する（ステップ１２１４）。
【００７７】
ステップ１２０４に戻り、プロセスがステップ１２０４で新しいセグメントを開始すると決定した場合、プロセスはＳｉの現在のセグメントに関するルーティング・パスを取得するために、ルーティング・テーブルをチェックする（ステップ１２３４）。次にプロセスは、ルーティング・パスを備えるＳｉに注釈を付ける（ステップ１２３６）。次にプロセスは、第１のルーティング・ホップ内の各ホストにＳｉのコピーを送る（ステップ１２３８）。次にプロセスは、ストリーム結合が完了したかどうかを判別する（ステップ１２３９）。ストリーム結合が完了した場合、プロセスは終了する。ステップ１２３９でストリーム結合が完了していない場合、プロセスはタプルＳｉを受け取る（ステップ１２０２）。図１３〜図１４のプロセスについては、図１７の擬似コードでさらに詳しく説明する。
【００７８】
図１５は、例示的実施形態に従った、多経路ストリーム結合アルゴリズムを示す図である。多経路ストリーム結合アルゴリズム１３００は、単一ホスト上で多経路ストリーム照会
【数６】
2007299406.tif 000008
を処理するための集中アルゴリズムである。多経路ストリーム結合アルゴリズム１３００は、図４の多経路ストリーム結合オペレータ４００などのオペレータによって実施可能である。多経路ストリーム結合オペレータの基本ステップは、図１０の諸ステップなどのプロセス中で実施可能である。システムは、着信タプルをバッファリングするために、各入力ストリームＳｉについて１つのキューＱｉ、１≦ｉ≦ｎを維持する。Ｑｉは入力バッファとすることができる。新しいタプルｓｉ∈Ｓｉが到着すると、ローカル・ホスト上のメモリ・スペースが満杯でなければ、この新しいタプルは対応するキューＱｉに挿入される。
【００７９】
そうでない場合、システムは、新しく到着したタプルをドロップするか、またはバッファ内の古いタプルを新しく到着したタプルに置き換える。すべてのキュー内のタプルが時間順に処理される。たとえば、ｓｉ．ｔ＜ｓｊ．ｔの場合、ｓｉが最初に処理される。各キューＱｉは、ポインタｐｉが、そのバッファ内で結合オペレータによって現在処理されるタプルを参照するように維持する。現在処理されているタプルがｓｉの場合、結合オペレータは、ｓｉを含むすべての結合結果を生成するために、ｓｉとすべての他のストリームＳｊ［Ｗｊ］、１≦ｊ≦ｎ、ｊ≠ｉとを比較する。
【００８０】
ｊ番目のストリームのスライディング・ウィンドウＳｊ［Ｗｊ］は、時間ｓｉ．ｔ−Ｗｋからｓｉ．ｔの間にＳｊに到着したすべてのタプルｓｊからなる。２つのタプル間の各結合述部評価を１つの結合プローブと呼ぶ。
【００８１】
ｓｉ∈Ｓｉの結合順序は、異なるストリーム［１１，１，１０］間での結合選択性に基づいて動的に決定される。ｓｉに関する結合処理はそれ自体から開始され、Ｓｉに対して最もわずかな選択性を有するストリームＳｊを次のホップとして選択する。その後、すべての中間結果が結合され
【数７】
2007299406.tif 000009
Ｓｊに対して最も少ない選択性を有するストリームＳｋが次に選択される。たとえば図４では、現在処理されているタプルは、時間８にストリームＳ３に到着したｓ３＜８＞  ４１０である。Ｓ３のプローブ・シーケンスは、Ｓ３→Ｓ４［Ｗ４］→Ｓ１［Ｗ１］→Ｓ２［Ｗ２］である。したがって、最初にｓ２が、Ｓ３とＳ４との間の結合述部θ３，４に基づいてＳ４［Ｗ４］と比較される。中間結果
【数８】
2007299406.tif 000010
はＳ１［Ｗ１］と比較される。最後に、
【数９】
2007299406.tif 000011
がＳ２［Ｗ２］と比較される。
【００８２】
図１６は、例示的実施形態に従った、整列タプル・ルーティング・アルゴリズムを示す図である。整列タプル・ルーティング・アルゴリズム１４００は、結合オペレータ
【数１０】
2007299406.tif 000012
の入力ストリームを区別して取り扱い、１つの選択されたマスタ・ストリームに従ってすべてのストリームのタプル・ルーティング動作を整列させる。整列タプル・ルーティング・アルゴリズム１４００は、図３経路ストリーム結合オペレータに関する７の整列タプル・ルーティング・モデル７００などのルーティング・モデルで実施することが可能であり、ここでＳ１はマスタ・ストリームである。整列タプル・ルーティング・アルゴリズムの基本ステップは、図１２の諸ステップなどのプロセスで実施可能である。
【００８３】
整列タプル・ルーティング・アルゴリズム１４００は、１つの入力ストリームをＳＡで示されたマスタ・ストリームとして動的に選択し、すべての他の入力ストリームのタプルをタイム・スタンプに従ってマスタ・ストリームと整列させる。拡散オペレータは、マスタ・ストリームＳＡを非結合セグメントに細断または区分する。非結合セグメントとは、互いにいかなる共通タプルも有さないセグメントである。１つのセグメント内のすべてのタプルは同じホストにルーティングされ、負荷の少ない順（least-loaded-first）（ＬＬＦ）などのある種のスケジューリング・ポリシーに基づいて、異なるセグメントは異なるホストにルーティングされる。これに対して相関制約を満たすために、他のｎ−１ストリームは、スレーブ・ストリームと呼ばれるマスタ・ストリームの区画に基づいて重複セグメントに区分される。重複セグメントとは、互いに任意の少なくとも１つの共通タプルを有するセグメントである。
【００８４】
一般に、整列タプル・ルーティングは、すべての入力ストリームを、それぞれがある時間間隔内に到着したタプルを含む異なるセグメントに連続的に分割する。Ｓｉ［ｔ，ｔ＋Ｔ］は、時間［ｔ，ｔ＋Ｔ）内にＳｉに到着したすべてのタプルを含むＳｉのセグメントを示し、ここでｔはセグメントの開始時間と呼ばれ、Ｔはセグメント長さと呼ばれる。スレーブ・ストリームのセグメントは、相関制約に基づいてマスタ・ストリームのセグメントと整列される。整列セグメントに属するタプルは、結合結果を生成するために同じホストにルーティングされる。たとえば図８は、マスタ・ストリームＳ１およびスレーブ・ストリームＳ２、Ｓ３に関する整列タプル・ルーティング・アルゴリズムのルーティング結果を示す。図を見やすくするために、ｒｉ＝１タプル／秒、ｉ＝１、２、３およびセグメント長さＴ＝５、ならびに、３つのスライディング・ウィンドウ・サイズはＷ１＝２、Ｗ２＝２、およびＷ３＝３であると想定する。拡散オペレータは、マスタ・ストリームＳ１を、それぞれホストｖ１、ｖ２、およびｖ３にルーティングされる非結合セグメントに分割する。スレーブ・ストリームＳ２は、Ｓ２［１，７］をｖ１、Ｓ２［４，１２］をｖ２、およびＳ２［９，１７］をｖ３、という重複セグメントに区分される。スレーブ・ストリームＳ３も、Ｓ３［１，７］をｖ１、Ｓ３［３，１４］をｖ２、およびＳ３［８，１７］をｖ３、という重複セグメントに区分される。
【００８５】
図１６は、結合オペレータ
【数１１】
2007299406.tif 000013
の負荷を拡散するための特定の整列タプル・ルーティング・アルゴリズム１４００の諸ステップを示す。図１６は、ｍ個のホスト｛ｖ１，．．．，ｖｍ｝を使用してＪを処理するための、整列タプル・ルーティング・アルゴリズム１４００の擬似コードを示す。セクション１４０２は、マスタ・ストリームＳＡに関するルーティング・ステップを示す。
【００８６】
拡散オペレータがＳＡからタプルｓＡを受け取った場合、第１に、ｓＡがそのタイム・スタンプｓＡ．ｔに従って現在のセグメントＳＡ［ｔ，ｔ＋Ｔ］に属するかどうかをチェックする。ｔ≦ｓＡ．ｔ＜ｔ＋Ｔの場合、ｓＡは現在のセグメントに属し、セグメントの開始時間ｔで選択されるホストｖｉにルーティングされる。ｓＡ．ｔ≧ｔ＋Ｔの場合、整列タプル・ルーティングは新しいセグメントを開始し、新しいホストを新しいセグメントのルーティング宛先として選択する。整列タプル・ルーティングは、負荷の少ない順（ＬＬＦ）ポリシーに従って、各セグメントについてホストを選択する。
【００８７】
分散型結合処理システムでは、プロセッサ、メモリ、およびネットワーク帯域幅などの異なるリソースが考慮されるため、組み合わされたメトリックｗｉがホストｖｉの負荷条件を表す。各リソース・タイプＲｉについて、整列タプル・ルーティング・アルゴリズム１４００は、負荷インジケータΦＲｉ＝ＵＲｉ／ＣＲｉを定義し、ここでＵＲｉおよびＣＲｉは、それぞれホストｖｉ上のリソースＲｉの使用および容量を示す。負荷値ｗｉは以下のように定義され、
ｗｉ＝ω１ΦＣＰＵ＋ω２・Φｍｅｍｏｒｙ＋ω３・Φｂａｎｄｗｉdｔｈ
この式で
【数１２】
2007299406.tif 000014
は、システムによって動的に構成可能な様々なリソース・タイプの重要性を示す。
【００８８】
マスタ・ストリームの区画に基づいて、整列タプル・ルーティングは相関制約を保持するためにすべてのスレーブ・ストリームを重複セグメントに分割する。スレーブ・ストリームＳｉ、ｉ≠Ａでは、整列タプル・ルーティングがセグメントＳＡ［ｔ，ｔ＋Ｔ］をホストｖｋにルーティングする場合、整列タプル・ルーティングは、相関制約を満たすためにセグメントＳｉ［ｔ−Ｗｉ，ｔ＋Ｔ＋ＷＡ］を同じホストｖｋにルーティングする。同様に、整列タプル・ルーティングがマスタ・ストリームの次のセグメントＳＡ［ｔ＋Ｔ，ｔ＋２Ｔ］をホストｖｊに送る場合、整列タプル・ルーティングはスレーブ・ストリームのセグメントＳｉ［ｔ＋Ｔ−Ｗｉ，ｔ＋２Ｔ＋ＷＡ］、１≦ｉ≦ｎ、ｉ≠Ａを、同じホストｖｊに送る必要がある。したがって、時間間隔［ｔ＋Ｔ−Ｗｉ，ｔ＋Ｔ＋ＷＡ］の間にＳｉに到着したタプルは、ｖｉおよびｖｊの両方に送られる。重複するタプルの数はｒｉ・（ＷＡ＋Ｗｉ）である。
【００８９】
整列タプル・ルーティング・アルゴリズム１４００は、拡散オペレータが、タプルをＳｉ［ｔ−Ｗｉ，ｔ］、１≦ｉ≦ｎ、ｉ≠Ａでキャッシュに入れるためのバッファ容量を有すると想定する。この想定が保持されない場合、各セグメントＳＡ［ｔ，ｔ＋Ｔ］に関するホスト選択は前の時間ｔ−Ｗｊにシフトされ、ここでＷｊは、すべてのスレーブ・ストリーム間で最も大規模なスライディング・ウィンドウを示す。たとえば図８では、第２のセグメントに関する配置は時間ｔ＝３で選択される。その後、整列タプル・ルーティングはＳ２［４，７］およびＳ３［３，７］内のタプルを、ホストｖ１およびｖ２の両方にルーティングする。
【００９０】
整列タプル・ルーティング・アルゴリズム１４００の正確さは、整列タプル・ルーティングがオリジナルの結合オペレータと同じ結合結果セットを生成することを示すことによって証明される。Ｃ（Ｊ）およびＣ’（Ｊ）は、それぞれ、
オリジナルの結合オペレータ
【数１３】
2007299406.tif 000015
によって生成される結合結果のセットと、整列タプル・ルーティング・アルゴリズムを使用する分散型処理方式とを示す。整列タプル・ルーティング・アルゴリズムの正確さは、Ｃ（Ｊ）＝Ｃ’（Ｊ）を示すことによって証明される。
【００９１】
定理Ａ：多経路ストリーム結合オペレータ
【数１４】
2007299406.tif 000016
とし、Ｃ（Ｊ）およびＣ’（Ｊ）が、それぞれ整列タプル・ルーティング・アルゴリズムを使用して、オリジナルの結合オペレータと分散型処理方式との両方によって生成される、結合結果のセットを示すようにする。結果として、Ｃ（Ｊ）＝Ｃ’（Ｊ）である。
【００９２】
証明スケッチ：Ｃ（Ｊ）⊆Ｃ’（Ｊ）は、∀ｓｉ、１≦ｉ≦ｎ、であり、
【数１５】
2007299406.tif 000017
の場合、
【数１６】
2007299406.tif 000018
であることを示すことによって証明される。これは、整列タプル・ルーティングがｓｉをサーバｖｉに送る場合、整列タプル・ルーティングも∀ｓｉｋ∈Ｓｉｋ［Ｗｉｋ］、１≦ｋ≦ｎ−１、をｖｉに送ることを示すことによって証明される。
【００９３】
第１に、ｓｉがマスタ・ストリームに属する場合を考えてみる。ｓｉ∈Ｓｉ［ｔ＋Ｔ］がホストｖｉに送信されると想定する。整列タプル・ルーティング・アルゴリズムは、さらにＳｉｋ［ｔ−Ｗｉｋ，ｔ＋Ｔ＋Ｗｉ）をｖｉに送る。他方で、スライディング・ウィンドウＳｉｋ［Ｗｉｋ］はＳｉｋ［ｓｉ．ｔ−Ｗｉｋ，ｓｉ．ｔ］内のすべてのタプルを含む。ｓｉ．ｔ∈［ｔ，ｔ＋Ｔ）であるため、Ｓｉｋ［ｓｉ．ｔ−Ｗｉｋ，ｓｉ．ｔ］⊂Ｓｉｋ［ｔ−Ｗｉｋ，ｔ＋Ｔ＋Ｗｉ）もｔｒｕｅである。したがって、整列タプル・ルーティングは、さらにＳｉｋ［Ｗｉｋ］内、１≦ｋ≦ｎ−１、のすべてのタプルをホストｖｉに送る。
【００９４】
ｓｉがスレーブ・ストリームに属すると考えた場合、ＳＡがマスタ・ストリームを示す、∀ｓＡ∈ＳＡ［ＷＡ］であり、整列タプル・ルーティングはｓＡが送信されるマシン上でｓｉをコピーする。ｓＡがセグメントＳＡ［ｔ，ｔ＋Ｔ］に属し、ｖｉに送られると想定する。整列タプル・ルーティングはさらに、セグメントＳｉ［ｔ−Ｗｉ，ｔ＋Ｔ＋ＷＡ］をｖｉに送る。ｓｉ∈Ｓｉ［ｔ−Ｗｉ，ｔ＋Ｔ＋ＷＡ］であることを証明することによって、ｓＡはセグメントＳＡ［ｔ，ｔ＋Ｔ］に属するため、ｔ≦ｓＡ．ｔ＜ｔ＋Ｔを有する。したがって、結果はｓｉ．ｔ≧ｓＡ．ｔ≧ｔおよびｓｉ．ｔ＜ｓＡ．ｔ＋ＷＡ＜ｔ＋Ｔ＋ＷＡである。したがって、結果はｔ≦ｓｉ．ｔ＜ｔ＋Ｔ＋ＷＡである。したがって、ｓｉはセグメントＳｉ［ｔ−Ｗｉ，ｔ＋Ｔ＋ＷＡ］に属し、これもｖｉに送られる。
【００９５】
Ｓｊがスレーブ・ストリームを示す、∀ｓｊ∈Ｓｊ［Ｗｊ］であることを証明することによって、整列タプル・ルーティングはｓｉおよびｓｊのコピーを同じホストに送る。ｓｉは、ｖｉにルーティングされるマスタ・ストリーム・セグメントＳＡ［ｔ，ｔ＋Ｔ］と整列されたセグメントＳｉ［ｔ，ｔ＋Ｔ］に属すると想定する。したがって、整列タプル・ルーティングはさらに、Ｓｊ［ｔ−Ｗｊ，ｔ＋Ｔ＋ＷＡ］をｖｉに送る。次に、Ｓｊ［Ｗｊ］＝Ｓｊ［ｓｉ．ｔ−Ｗｊ，ｓｉ．ｔ］⊂Ｓｊ［ｔ−Ｗｊ，ｔ＋Ｔ＋ＷＡ］であることを証明することによって、ｔ≦ｓｉ．ｔ＜ｔ＋Ｔであるため、ｔ−Ｗｊ≦ｓｉ．ｔ−Ｗｊおよびｓｉ．ｔ＜ｔ＋Ｔ＋ＷＡを提示する。
【００９６】
したがって、さらにＳｊ［Ｗｊ］⊂Ｓｊ［ｔ−Ｗｊ，ｔ＋Ｔ＋ＷＡ］がｖｉに送られる。結論として、∀ｓｉ、ｓｉ、およびＳｉｋ［Ｗｉｋ］、１≦ｋ≦ｎ−１が同じホスト上に現れることになる。したがって、Ｃ（Ｊ）⊆Ｃ’（Ｊ）である。
【００９７】
次に、Ｃ’（Ｊ）⊆Ｃ（Ｊ）が証明される。第１に、拡散結合オペレータによって生成されるＣ’（Ｊ）における任意の結合結果は、多経路ストリーム結合セマンティクスに従い、これはＣ（Ｊ）にも現れるものとする。第２に、マスタ・ストリーム上のいかなる∀ｓＡ∈ＳＡも２つの異なるホスト上に現れないため、整列タプル・ルーティングは重複する結合結果を生成しない。したがって、Ｃ’（Ｊ）⊆Ｃ（Ｊ）である。Ｃ（Ｊ）⊆Ｃ’（Ｊ）およびＣ’（Ｊ）⊆Ｃ（Ｊ）を組み合わせると、結果としてＣ（Ｊ）＝Ｃ’（Ｊ）となる。
【００９８】
整列タプル・ルーティング・アルゴリズムのオーバヘッドも分析することができる。オリジナルの入力ストリームと比較すると、整列タプル・ルーティングはスレーブ・ストリームを部分的に複製することにより、より多くのタプルをシステムにプッシュする。整列タプル・ルーティング・アルゴリズムのオーバヘッドは、時間ユニットあたりに整列タプル・ルーティングによって生成される余分なタプルの数として定義される。分散型ストリーム処理システムは、それらのオーバヘッド・データを伝送、処理、およびバッファリングするために、ネットワーク帯域幅、ＣＰＵ時間、およびメモリ・スペースの一部分を、消費する必要がある。
【００９９】
定理Ｂ：多経路ストリーム結合オペレータ
【数１７】
2007299406.tif 000019
とすると、ＳＡが現在のマスタ・ストリームを示すようにする。Ｔがセグメント長さを示すようにする。ｒｉ、１≦ｉ≦ｎがストリームＳｉの平均レートを示すようにする。ＯＡＴＲが整列タプル・ルーティング・アルゴリズムの平均オーバヘッドを示すようにする。結果として、
【数１８】
2007299406.tif 000020
となる。
【０１００】
証明スケッチ：時間間隔Ｔにわたる各セグメントＳＡ［ｔ，ｔ＋Ｔ］および各スレーブ・ストリームＳｉ、１≦ｉ≦ｎ、ｉ≠Ａについて、整列タプル・ルーティングは、オリジナルのスレーブ・ストリームＳｉよりも多くのタプルｒｉ・（Ｗｉ＋ＷＡ）を導入する。したがって、各セグメント長さＴについて、整列タプル・ルーティング・アルゴリズムによって生成される余分なタプルの合計数は、
【数１９】
2007299406.tif 000021
である。したがって、時間ユニットあたりに整列タプル・ルーティング・アルゴリズムによって生成される余分なタプルの平均数は、
【数２０】
2007299406.tif 000022
である。
【０１０１】
上記の分析は、整列タプル・ルーティング・アルゴリズムの興味深い特性を明らかにしている。整列タプル・ルーティング・アルゴリズムのオーバヘッドは、結合オペレータを処理するために使用されるホストの数とは無関係である。この特性により、整列タプル・ルーティングは、利用可能なリソースを過度の負荷拡散オーバヘッドなしに多数のホストから集めることが可能な、大規模ストリーム処理クラスタに対して特に好適となる。
【０１０２】
様々な適応方式を使用して、動的ストリーム環境における整列タプル・ルーティング・アルゴリズムの性能を最適化することができる。定理Ｂにより、整列タプル・ルーティング・アルゴリズムのオーバヘッドがセグメント長さに反比例することが観察される。セグメントが長くなるほど、重複セグメントのコストがより長い期間にわたって償却されるため、負荷拡散オーバヘッドは少なくなる。しかしながら、セグメントが長いことにより、大型セグメント内の大量のタプルが同じホストに集中させられるため、負荷バランシングの細分性が制限される。
【０１０３】
結果として、整列タプル・ルーティングは、動的なストリーム環境において最適な性能を維持するために、セグメント長さＴのセグメント適応を適応的に調整またはトリガする。整列タプル・ルーティングは、サンプリング・ベースのプロファイリング・プロセスを採用して、システム条件が変更された場合に最適なセグメント長さを見つける。Ｔが現在のセグメント長さを示し、ΔＴが適応ステップ値を示すようにする。適応プロセスは、Ｔ＋ΔＴ、およびＴ−ΔＴの両方をテストする。Ｔ＋ΔＴの性能の方が良好な場合、最適なセグメント長さは現在のセグメント長さよりも長いはずである。システムは、測定されるシステム性能がそのピーク値に達するまで、セグメントを徐々に長くしていく。そうでない場合、Ｔ−ΔＴの性能の方が良好な場合、システムはセグメントを徐々に短くして最適な値を探る。整列タプル・ルーティングは、適応が相関制約に違反しないことを保証するために、１つのセグメントの終わりで常にセグメント長さを変更する。
【０１０４】
整列タプル・ルーティングのオーバヘッドはスレーブ・ストリーム率にのみ関係し、マスタ・ストリーム率とは無関係である。動的ストリーム環境では、各入力ストリーム率は経時的に動的に変化する可能性がある。結果として、整列タプル・ルーティングは、定理Ｂに従って最低の負荷拡散オーバヘッドを有するマスタ・ストリームを動的に選択する。マスタ・ストリームは、常に最高率を有するストリームであるものとする。マスタ・ストリーム率がスレーブ・ストリームのうちの１つよりも遅くなった場合、整列タプル・ルーティングは遷移段階を採用してマスタ・ストリームを変更する。セグメント適応と同様、相関制約を満たすために、１つのセグメントの終わりにストリーム・ロール・スイッチが常に起動される。
【０１０５】
図１７は、例示的実施形態に従った、制約付きタプル・ルーティング・アルゴリズムを示す図である。制約付きタプル・ルーティング・アルゴリズム１５００は、図９の制約付きタプル・ルーティング・モデル８００などのルーティング・モデルで実施することができる。制約付きタプル・ルーティング・アルゴリズム１５００の基本ステップは、図１３〜１４の諸ステップなどのプロセスで実施可能である。
【０１０６】
制約付きタプル・ルーティング１５００は、セクション１５０２でプローブ・シーケンス
【数２１】
2007299406.tif 000023
を伴う任意のタプルｓｉ∈Ｓｉ、１≦ｉ≦ｎについてルーティングを決定し、制約付きタプル・ルーティングは、以前の相関タプルの配置に基づいて、タプルｓｉおよびすべての中間結合結果
【数２２】
2007299406.tif 000024
１≦ｋ≦ｎ−１について、ルーティングを決定する。すべての結合オペレータがルーティング計算をする必要がないように、制約付きタプル・ルーティングは、他のｎ−１ストリームと結合するためにｓｉに関するルーティング・パス全体を計算するソース・ルーティング・アルゴリズムとして実施される。各タプルは、結合結果を生成するためにアクセスする必要のあるホストのセットを示す、そのルーティング・パスを担持する。
【０１０７】
ルーティング計算のオーバヘッドを削減するために、制約付きタプル・ルーティングは各入力ストリーム上のタプルをセグメントにグループ化し、各セグメントを全体として異なるホストにルーティングする。したがって、制約付きタプル・ルーティングは、各タプルについてではなく、各セグメントについてのルートを計算するだけでよい。セグメント長さは、負荷バランシング細分性とルーティング・オーバヘッドとの間のトレードオフを示す。制約付きタプル・ルーティングは、以前にルーティングされたセグメントの配置を記録するルーティング・テーブルも維持する。多経路ストリーム結合セマンティクスに基づいて今後のいかなるセグメントとも相関される必要がなければ、セグメント情報はルーティング・テーブルから削除される。
【０１０８】
セクション１５０４で、制約付きタプル・ルーティングは、スライディング・ウィンドウＳｉ１［Ｗｉ１］内のタプルと結合する必要があるセグメントηｉ＝Ｓｉ［ｔ，ｔ＋Ｔ］のルーティングを決定する。制約付きタプル・ルーティングは、第１に、Ｓｉ１［Ｗｉ１］＝Ｓｉ１［ｔ−Ｗｉ１，ｔ＋Ｔ］内のすべてのタプルの位置を取得する。オーバヘッドを最小限にするために、制約付きタプル・ルーティングは、すべての相関タプルをカバーすることが可能な最小のホスト・セットＶ１⊆｛ｖ１，．．．，ｖｍ｝を選択する。前述の問題は、以下で詳細に説明する、重み付けされた最小セットのカバー問題として公式化される。制約付きタプル・ルーティング中に、この結合順序を使用して、多経路相関処理をより小さな複数のオペレータに分割する。具体的に言えば、ｎ経路の結合オペレータ
【数２３】
2007299406.tif 000025
は、（ｎ−１）の２経路結合オペレータ
【数２４】
2007299406.tif 000026
に区分され、そのそれぞれが異なるホスト上で実行可能である。相関セグメントの位置は、各ホップでルックアップされる。最小のホスト・セットは、各ホップでのすべての相関セグメントをカバーして計算される。その後、制約付きタプル・ルーティングは、ηｉの第１のルーティング・ホップが、Ｖ１内のすべてのホストとなるように設定する。セグメントηｉ＝Ｓｉ［ｔ，ｔ＋Ｔ］は、結合セマンティクスに従ってそのタプルが必要なくなるまで、Ｖ１内の各ホスト上のメモリ・バッファＱｉ内に保存されることになる。
【０１０９】
制約付きタプル・ルーティングは、ηｉ＝Ｓｉ［ｔ，ｔ＋Ｔ］がＶ１内のホスト・セット上に位置することを記録するために、ルーティング・テーブルも更新する。たとえば図９で、制約付きタプル・ルーティングは、プローブ・シーケンスがｓ１→Ｓ２［Ｗ２］→Ｓ３［Ｗ３］である、Ｓ１［９，１０］に関するルートを計算する。制約付きタプル・ルーティングは、Ｓ２［１，２］がｖ１、ｖ２上、Ｓ２［３，４］がｖ２、ｖ３上、Ｓ３［５，６］がｖ１、ｖ４上というように、Ｓ２［Ｗ２］内のすべての相関タプルの配置を取得する。その後、制約付きタプル・ルーティングは、Ｓ２［Ｗ２］内のすべてのタプルをカバーすることができる最小のホスト・セットＶ１＝｛ｖ２，ｖ４｝を選択する。
【０１１０】
結果として、制約付きタプル・ルーティングは、第１のホップをＶ１＝｛ｖ２，ｖ４｝となるようにＳ１［９，１０］のルーティング・パス上に設定する。制約付きタプル・ルーティングは、セグメントＳ１［９，１０］がホストＶ１＝｛ｖ２，ｖ４｝上に配置されることを指定する、ルーティング・テーブル内のエントリも追加する。
【０１１１】
次に、制約付きタプル・ルーティングは、中間結果
【数２５】
2007299406.tif 000027
を、Ｓｉ２［Ｗｉ２］内のすべてのタプルをカバーするホストにルーティングする必要がある。第１のステップと同様に、制約付きタプル・ルーティングは第１に、Ｓｉ２［Ｗｉ２］内のすべての相関タプルの位置を取得する。しかしながら、異なるホストにまたがって中間結果を伝送する際のオーバヘッドを最小限にするために、
【数２６】
2007299406.tif 000028
に関するルーティングを決定するには、
【数２７】
2007299406.tif 000029
の現在の位置を考慮に入れなければならない。第１のルーティング・ホップをＶ１＝｛ｖ１，．．．，ｖｋ｝とすると、制約付きタプル・ルーティングは最初に、Ｖ１内のホストによってすでにカバーされているＳｉ２［Ｗｉ２］内のそれらのタプルを消去する。その論拠は、現在Ｖ１内のホスト上に位置するいずれの中間結果
【数２８】
2007299406.tif 000030
も、Ｓｉ２［Ｗｉ２］内のローカルに利用可能なタプルと結合しなければならないためである。その後、制約付きタプル・ルーティングは、Ｓｉ２［Ｗｉ２］内の残りのタプルをカバーするために、最小ホスト・セットＶ２を計算する。しかしながら、オリジナルのタプルとは異なり、中間結果は他のタプルと結合するためのメモリ・キューにはバッファリングされない。したがって、制約付きタプル・ルーティングは、ルーティング・テーブル内の中間結果の配置を記録する必要がない。
【０１１２】
たとえば図９では、第２のルーティング・ホップは、現在ホストｖ２、ｖ４に位置する中間結果
【数２９】
2007299406.tif 000031
用のホスト・セットを選択するためのものである。その後、制約付きタプル・ルーティングは、ホストｖ２によってすでにカバーされている、Ｓ３［３，４］およびＳ３［７，８］を除去する。次に、｛ｖ３，ｖ５｝上のＳ３［１，２］、｛ｖ５，ｖ６｝上のＳ３［５，６］、｛ｖ６，ｖ７｝上のＳ３［９，１０］などの、残りのタプルの位置に基づいて、制約付きタプル・ルーティングは、セグメントＳ１［９，１０］に関する第２のルーティング・ホップとして、最小ホスト・セットＶ２＝｛ｖ５，ｖ６｝を計算する。
【０１１３】
上記の計算は、制約付きタプル・ルーティングが、
【数３０】
2007299406.tif 000032
内のすべてのｎ−１プローブ・ステップについて、ホスト・セットＶ１、．．．、Ｖｎ−１を計算するまで反復される。その後、制約付きタプル・ルーティングは、その位置がＶ１によって指定されたホスト・セットであるセグメントηｉに関するエントリを挿入することによって、ルーティング・テーブルを更新する。セクション１５０４で、制約付きタプル・ルーティング・アルゴリズム１５００は、ルーティング・パスＶ１→Ｖ２．．．→Ｖｎ−１を使用して各タプルｓｉ∈Ｓｉ［ｔ，ｔ＋Ｔ］に注釈を付ける。図１５は、ｍ個のホスト｛ｖ１，．．．，ｖｍ｝を使用して、結合オペレータ
【数３１】
2007299406.tif 000033
を処理するための、制約付きタプル・ルーティング・アルゴリズムの擬似コードを示す図である。
【０１１４】
図１３〜図１４のプロセスなどの最適なホスト・セットの選択のために、他のアルゴリズムを使用することもできる。最適なホスト選択アルゴリズムの目的は、各ルーティング・ホップＶｋ、１≦ｋ≦ｎ−１について最良のホスト・セットを選択することである。ｋ番目のルーティング・ホップの目標は、
【数３２】
2007299406.tif 000034
χ０＝ｓｉ、およびＳｉｋ［Ｗｉｋ］内のすべてのタプルの間に、すべての結合結果を生成することである。スライディング・ウィンドウＳｉｋ［Ｗｉｋ］が、Ｅ＝｛η１，．．．，ηｅ｝によって示されるセグメントのセットからなると想定する。各セグメントに関する配置情報は、ルーティング・テーブルから取り出される。
【０１１５】
各セグメントηｚ、１≦ｚ≦ｅは、ホストのセットＵｚ⊆｛ｖ１，．．．，ｖｍ｝上で分散される。その後、制約付きタプル・ルーティングは、セグメント配置情報をホスト・カバレッジ情報に変換する。たとえば、ηｚがホスト・セットＵｚ上で分散され、Ｕｚ内の各ホストがセグメントηｚをカバーすると考えてみる。
【数３３】
2007299406.tif 000035
と示される。各ホスト
【数３４】
2007299406.tif 000036
では、Ａｉ⊆Ｅで示されるＥのサブセットを形成するセグメントのセットをカバーする。目標は平衡のとれた負荷分散を達成することであるため、Ｓｉｋ［Ｗｉｋ］内のすべての相関タプルをカバーすることができる最低数の最小負荷のホストに対して、Ｘｋ−１が分散される。したがって、重み値ｗｉが各サブセットＡｉに関連付けられる。重み値ｗｉはホストｖｉの負荷値ｗｉであり、負荷値に関する数式で定義される。結果として、最適なホスト選択問題は、以下のように重み付けされた最小セットのカバー問題に公式化される。
【０１１６】
定義：グラウンド（ground）・セットＥ＝｛η１，．．．，ηｅ｝、サブセットＡ１、．．．、ＡＫ⊆Ｅ、および各サブセットＡｉに関するコストｗｉとすると、目標は、∪ｊ∈ＩＡｊ＝Ｅおよび
【数３５】
2007299406.tif 000037
となるような、最小セット・カバーＩ⊆｛１，．．．，Ｋ｝を見つけることである。
【０１１７】
ホスト・セットＶｋは、Ｉに従って導出される。たとえば、セット・カバーＩ＝｛１，２｝の場合、Ｖｋ＝｛ｖ１，ｖ２｝である。最小セット・カバー問題は、良く知られたＮＰハード問題である。結果として、制約付きタプル・ルーティングは、最小セット・カバーを見つけるために欲張り（greedy）ヒューリスティック・アルゴリズムを使用する。基本的な考え方は、
ａｒｇｍｉｎｊの最小値、
【数３６】
2007299406.tif 000038
を有するサブセットＡｊを選択することであり、上式で｜Ａｊ｜はセットＡｊのカーディナリティ（cardinality）を示す。Ａｊはセット・カバーＩに追加され、Ａｊに含まれるそれらの要素を除去することによって残りの各サブセットを更新する。Ａｊをセットに追加するプロセスは、選択されるセット・カバーＩが、Ｅ＝｛η１，．．．，ηｅ｝内のすべてのセグメントを含むまで反復される。
【０１１８】
しかしながら、前述の方式は、冗長結合計算を実行することができる。現在選択されたホスト・セットがＶｋであると想定する。任意のセグメントηｚ∈Ｓｉｋ［Ｗｉｋ］について、ホストのセットＵｚ＝｛ｖｚ１，．．．，ｖｚ１｝上に配置される。セットＶｋおよびＵｚが複数の共通ホストを含む場合（すなわち、｜Ｖｋ∩Ｕｚ｜＞１）、Ｘｋ−１とηｚの間の結合プローブは、｜Ｖｋ∩Ｕｚ｜内に含まれる異なるホストで冗長に計算される。こうした冗長計算は、冗長結合結果につながる可能性がある。この問題に対処するには、各結合プローブが１つのホストによってのみ実行されることを保証するために、Ｘｋ−１の異なるコピーによって担持されるルーティング・パスに注釈が付けられる。Ｓｉｋ［Ｗｉｋ］内のすべてのタプルと相関させるために、Ｘｋ−１のコピーがＶｋ内のすべてのホストに送られる。Ｖｚ内のホスト上に配置された∀ηｚ∈｛η１，．．．，ηｅ｝について、｜Ｖｋ∩Ｕｚ｜＞１の場合、Ｘｉとηｚとの間で結合プローブを実行するためにＶｋ∩Ｕｚからの最小負荷のホストｖｊが選択される。任意の他のホストｖｊ∈Ｖｋ∩Ｕｚについて、ルーティング・パスにはフラグ（ｖｊ／ηｚ）で注釈が付けられ、これは、
【数３７】
2007299406.tif 000039
のいかなる中間結果タプルもがホストｖｊ上のηｚと結合しないことを意味する。
【０１１９】
制約付きタプル・ルーティング・アルゴリズムの正確さは、制約付きタプル・ルーティングがオリジナルの結合オペレータと同じ結合結果のセットを生成することを証明することによって示される。Ｃ（Ｊ）およびＣ’（Ｊ）は、それぞれ、
オリジナルの結合オペレータ
【数３８】
2007299406.tif 000040
によって生成される結合結果のセットと、制約付きタプル・ルーティング・アルゴリズムを使用する分散型処理方式とを示す。制約付きタプル・ルーティング・アルゴリズムの正確さは、Ｃ（Ｊ）＝Ｃ’（Ｊ）を示すことによって証明される。
【０１２０】
定理Ｃ：多経路ストリーム結合オペレータ
【数３９】
2007299406.tif 000041
とし、Ｃ（Ｊ）およびＣ’（Ｊ）が、それぞれ制約付きタプル・ルーティング・アルゴリズムを使用して、オリジナルの結合オペレータと分散型処理方式との両方によって生成される、結合結果のセットを示すようにする。結果として、Ｃ（Ｊ）＝Ｃ’（Ｊ）である。
【０１２１】
証明スケッチ：Ｃ（Ｊ）⊆Ｃ’（Ｊ）は、第１に∀ｓｉ、１≦ｉ≦ｎ、
【数４０】
2007299406.tif 000042
の場合、
【数４１】
2007299406.tif 000043
であることを示すことによって証明される。これは、
【数４２】
2007299406.tif 000044
が制約付きタプル・ルーティングによって生成されるという、より強力なステートメントを証明することによって証明される。数学的帰納法を使用して、（１）ｋ＝１の場合、このステートメントがｔｒｕｅであることを証明する。制約付きタプル・ルーティングは、Ｓｉ１［Ｗｉ１］内のすべてのタプルをカバーするホストのセットＶ１にｓｉを送るため、制約付きタプル・ルーティングによって
【数４３】
2007299406.tif 000045
が生成され、（２）何らかのｋ、１≦ｋ≦ｎ−２の場合にこのステートメントがｔｒｕｅであると想定すると、このステートメントはｋ＋１の場合にｔｒｕｅであることを証明する。この想定に従って、制約付きタプル・ルーティングによって
【数４４】
2007299406.tif 000046
が生成される。Ｓｉｋ＋１［Ｗｉｋ＋１］内のすべてのタプルがＸｋと同一の場所に位置するか、またはｋ＋１番目のルーティング・ホップＶｋ＋１内のホストによってカバーされているため、制約付きタプル・ルーティングによって
【数４５】
2007299406.tif 000047
内のすべての結果タプルが生成される。結果として、Ｃ（Ｊ）⊆Ｃ’（Ｊ）である。
【０１２２】
次に、Ｃ’（Ｊ）⊆Ｃ（Ｊ）が証明される。第１に、拡散結合オペレータによって生成されるＣ’（Ｊ）における任意の結合結果は、多経路ストリーム結合セマンティクスに従い、これはＣ（Ｊ）にも現れるものとする。第２に、制約付きタプル・ルーティングはいかなる重複結果も生成しないことが証明される。制約付きタプル・ルーティングは重複を避けて実行されるため、いかなる結果タプル
【数４６】
2007299406.tif 000048
も、単一のホストによって１回だけ生成される。したがって、Ｃ’（Ｊ）⊆Ｃ（Ｊ）である。Ｃ（Ｊ）⊆Ｃ’（Ｊ）およびＣ’（Ｊ）⊆Ｃ（Ｊ）を組み合わせると、結果としてＣ（Ｊ）＝Ｃ’（Ｊ）となる。
【０１２３】
制約付きタプル・ルーティング・アルゴリズム１５００のオーバヘッドは、時間ユニットあたりに制約付きタプル・ルーティングによって生成される余分なタプルの数として定義される。１ホップ・ルーティングを実行する整列タプル・ルーティングとは異なり、制約付きタプル・ルーティングは、複数ホスト上でオリジナル入力ストリームのタプルを複製するだけでなく、異なるホストにまたがって中間結果を転送する必要のある、複数ホップ・ルーティングを実行する。
【０１２４】
したがって、制約付きタプル・ルーティングのオーバヘッドは、（１）セグメントｓｉ［ｔ，ｔ＋Ｔ］を第１のルーティング・ホップＶ１によって指定された複数ホップへ送ることによって、オリジナルの入力ストリームを複製すること、（２）中間結果
【数４７】
2007299406.tif 000049
を、Ｖｋによって指定された複数ホップに伝送すること、という、２つの部分からなる。オーバヘッドの第１の部分では、システムは、それらのオーバヘッド・データに関する余分な処理、メモリ、およびネットワーク帯域幅を消費する必要がある。しかしながら、中間結果はメモリ・バッファに格納されないため、中間結果のオーバヘッドはＣＰＵおよび帯域幅のコストのみを発生させる。
【０１２５】
定理Ｄ：多経路ストリーム結合オペレータ
【数４８】
2007299406.tif 000050
とし、ｒｉ、１≦ｉ≦ｎが、ストリームＳｉの平均率を示すようにする。Ｔがセグメント長さを示すようにする。Ｓｉのプローブ・シーケンスは、Ｓｉ１、．．．、Ｓｉｎ−１によって示される。σｉ，ｊがＳｉとＳｊの間の結合選択性を定義するようにする。Ｓｉ、１≦ｉ≦ｎ内のタプルに関する複製の平均数は、Ｍｉによって示される。中間結果
【数４９】
2007299406.tif 000051
に関する複製の平均数は、Ｍｉｋによって示される。ＯＣＴＲがオリジナルのデータ・ストリームの平均複製オーバヘッドを示すようにする。Ｏ＊ＣＴＲが中間結果の平均オーバヘッドを示すようにする。その結果、
【数５０】
2007299406.tif 000052
となる。
【０１２６】
証明スケッチ：各セグメントＳｉ［ｔ，ｔ＋Ｔ］、１≦ｉ≦ｎについて、制約タプル・ルーティングはオリジナルの入力ストリームと比べて（Ｍｉ−１）・ｒｉ・Ｔの余分なタプルを時間間隔Ｔにわたって送る。したがって、時間ユニットあたりに制約付きタプル・ルーティング・アルゴリズムによって生成される余分なタプルの平均数は、
【数５１】
2007299406.tif 000053
である。各セグメントＳｉ［ｔ，ｔ＋Ｔ］、１≦ｉ≦ｎについて、Ｓｉ１［Ｗｉ１］、．．．、Ｓｉｎ−１［Ｗｉｎ−１］と結合する必要がある。
【数５２】
2007299406.tif 000054
から生成される中間結果の数は、σｉ，ｉ１（ｒｉ・Ｔ）・（ｒｉ１・Ｗｉ１）である。各中間結果はＭｉ２に送られ、Ｓｉ２［Ｗｉ２］と結合する。
【数５３】
2007299406.tif 000055
に関する中間結果のオーバヘッドは、Ｍｉｋ・σｉ，ｉ１（ｒｉ・Ｔ）・（ｒｉ１・Ｗｉ１）・σｉ１，ｉ２・（ｒｉ２・Ｗｉ２）．．．σｉｋ−１，ｉｋ（ｒｉｋ・Ｗｉｋ）である。したがって、
【数５４】
2007299406.tif 000056
を計算するための中間結果の合計数は、
【数５５】
2007299406.tif 000057
である。ｎ個の入力ストリームすべてについて、時間ユニットあたりに制約付きタプル・ルーティング・アルゴリズムによって生成される中間結果の合計数は、
【数５６】
2007299406.tif 000058
である。
【０１２７】
整列タプル・ルーティング方式と同様に、制約付きタプル・ルーティングのオーバヘッドも、多経路ストリーム結合オペレータを実行するために使用されるホスト｛ｖ１，．．．，ｖｍ｝の合計数とは無関係である。したがって、制約付きタプル・ルーティングは、結合オペレータが分散型ストリーム処理システム内のすべての使用可能ホストを、過度のオーバヘッドなしに利用できるようにするものである。制約付きタプル・ルーティングのオーバヘッドは、オリジナル・タプルおよび中間結果タプルをルーティングするためのホスト・セットの平均数を定義する、２つの新しいパラメータＭｉおよびＭｉｋに依存する。発明者等の最適なホスト・セット選択アルゴリズムは、常に相関制約を満たすための最小のホスト・セットを選択する。ＭｉまたはＭｉｋの値は、しばしば、合計ホスト数よりもかなり少ない。整列タプル・ルーティングＯＡＴＲの複製オーバヘッドとは異なり、オリジナル・ストリームＯＣＴＲの複製オーバヘッドはスライディング・ウィンドウ・サイズとは無関係である。
【０１２８】
したがって、結合オペレータが大規模なスライディング・ウィンドウを採用する場合、制約付きタプル・ルーティングの方が整列タプル・ルーティングよりもオーバヘッドが少ない可能性がある。制約付きタプル・ルーティングは整列タプル・ルーティングに比べて余分な中間結果オーバヘッドを有するが、実際の適用例ではしばしば結合選択性が非常に小さいため、中間結果オーバヘッドＯ＊ＣＴＲは重大でない。整列タプル・ルーティングと制約付きタプル・ルーティングとの間の他の相違点は、整列タプル・ルーティングがｎ個の入力ストリームを区別して取り扱うのに対して、制約付きタプル・ルーティングはすべての入力ストリームを同等に扱うことである。したがって、小さなスライディング・ウィンドウを備えた１つの高速ストリームと低速ストリームのセットとの間で結合する場合は、整列タプル・ルーティングの方が好適であり、すべての入力ストリームが同様の率を有し、結合オペレータが大きなスライディング・ウィンドウを採用する場合は、制約付きタプル・ルーティングが最適である。
【０１２９】
さらに、制約付きタプル・ルーティングは、新しくルーティングされたセグメントの位置を追跡するルーティング・テーブルを維持する必要がある。セグメント長さが制約付きタプル・ルーティングの複製オーバヘッドに影響を与えるが、セグメント長さはルーティング・テーブルのサイズおよびルーティング計算オーバヘッドを決定する。
【０１３０】
したがって、例示的諸実施形態は、ストリーム処理環境において自動的にプランニングするための方法を提供する。説明する検索方法は、ストリーム処理プランニング問題に適用すると、他のプランニング方法に比べて大幅に改善されたスケーラビリティを達成する。複雑な多経路ストリーム結合の正確な処理を可能にすることによって、スケーラビリティが改善される。加えて、例示的諸実施形態は、データ・ストリームの変動にも対応する。
【０１３１】
本発明は、完全なハードウェア実施形態、完全なソフトウェア実施形態、またはハードウェアおよびソフトウェアの両方の要素を含む実施形態の、形を取ることが可能である。好ましい実施形態では、本発明は、ファームウェア、常駐ソフトウェア、マイクロコードなどを含むがこれらに限定されることのない、ソフトウェアで実施される。
【０１３２】
さらに本発明は、コンピュータまたは任意の命令実行システムによって、またはこれらに関連して使用するための、プログラム・コードを提供する、コンピュータ使用可能またはコンピュータ読み取り可能な媒体からアクセス可能な、コンピュータ・プログラム製品の形を取ることができる。本記述では、コンピュータ使用可能またはコンピュータ読み取り可能な媒体は、命令実行のシステム、装置、またはデバイスによって、またはそれらに関連して使用するためのプログラムを、包含、格納、通信、伝播、または移送可能な、任意の有形の装置とすることができる。
【０１３３】
媒体は、電子、磁気、光、電磁、赤外線、または半導体のシステム（あるいは装置またはデバイス）、あるいは伝播媒体とすることができる。コンピュータ読み取り可能媒体の例には、半導体またはソリッド・ステート・メモリ、磁気テープ、取り外し可能コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛体磁気ディスク、および光ディスクが含まれる。光ディスクの現行例には、コンパクト・ディスク−読み取り専用メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク−読み取り／書き込み（ＣＤ−Ｒ／Ｗ）、およびＤＶＤが含まれる。
【０１３４】
プログラム・コードの格納あるいは実行またはその両方に好適なデータ処理システムは、システム・バスを介して直接または間接的にメモリ要素に結合された、少なくとも１つのプロセッサを含むことになる。メモリ要素は、プログラム・コードの実際の実行中に採用されるローカル・メモリ、大容量ストレージ、および、実行中にバルク・ストレージからコードを取り出さなければならない回数を減らすために、少なくともいくつかのプログラム・コードの一時ストレージを提供する、キャッシュ・メモリを含むことができる。
【０１３５】
（キーボード、ディスプレイ、ポインティング・デバイスなどを含むがこれらに限定されることのない）入力／出力またはＩ／Ｏデバイスは、直接、またはＩ／Ｏコントローラの介在を通じて、システムに結合することができる。
【０１３６】
データ処理システムを、専用または公衆ネットワークの介在を通じて、他のデータ処理システムあるいはリモートのプリンタまたはストレージ・デバイスに結合できるようにするために、ネットワーク・アダプタをシステムに結合することもできる。モデム、ケーブル・モデム、およびイーサネット（登録商標）・カードは、現在使用可能なネットワーク・アダプタ・タイプのごく一部にすぎない。
【０１３７】
以上、説明してきた例示的諸実施形態は、例示および説明を目的とするものであり、本発明を網羅するかまたは開示された形に限定することを意図するものではない。当業者であれば、多くの修正形態および変形形態が明らかとなろう。実施形態は、本発明の原理、実際の適用例を最も良く説明するため、ならびに、企図された特定の用途に好適な様々な修正を備えた様々な諸実施形態について、当業者が本発明を理解できるようにするために、
選択および説明されたものである。
【図面の簡単な説明】
【０１３８】
【図１】例示的諸実施形態が実施可能なデータ処理システムのネットワークを示す絵画図である。
【図２】例示的諸実施形態が実施可能なデータ処理システムを示すブロック図である。
【図３】例示的諸実施形態に従ったストリーム処理の一例を示す図である。
【図４】例示的実施形態に従った、スライディング・ウィンドウ・ストリーム結合オペレータ・モデルを示す図である。
【図５】例示的実施形態に従った、分散型多経路ストリーム結合実行モデルを示す図である。
【図６】例示的実施形態に従った、相関認識タプル・ルーティング方式を示す図である。
【図７】例示的実施形態に従った、相関認識タプル・ルーティング方式を示す図である。
【図８】例示的実施形態に従った、整列タプル・ルーティング・モデルを示す図である。
【図９】例示的実施形態に従った、制約付きタプル・ルーティング・モデルを示す図である。
【図１０】例示的実施形態に従った集中結合方法を示す流れ図である。
【図１１】例示的実施形態に従った分散結合方法を示す流れ図である。
【図１２】例示的実施形態に従った、整列タプル・ルーティング方法を示す流れ図である。
【図１３】例示的実施形態に従った、制約付きタプル・ルーティング方法を示す流れ図である。
【図１４】例示的実施形態に従った、制約付きタプル・ルーティング方法を示す流れ図である。
【図１５】例示的実施形態に従った、多経路ストリーム結合アルゴリズムを示す図である。
【図１６】例示的実施形態に従った、整列タプル・ルーティング・アルゴリズムを示す図である。
【図１７】例示的実施形態に従った、制約付きタプル・ルーティング・アルゴリズムを示す図である。
【符号の説明】
【０１３９】
３１０    取引
３１２    株式分析
３２０    ＴＶニュース
３２２    ＭＰＥＧ４デマルチプレクサ
３２４    イメージ分析
３２６    音声テキスト
３２８    テキスト分析
３３０    ラジオ
３３２    音声テキスト
３３４    テキスト分析
３４０    多経路ストリーム結合
３５０    相関結果
【図１】
2007299406.tif 000059
【図２】
2007299406.tif 000060
【図３】
2007299406.tif 000061
【図４】
2007299406.tif 000062
【図５】
2007299406.tif 000063
【図６】
2007299406.tif 000064
【図７】
2007299406.tif 000065
【図８】
2007299406.tif 000066
【図９】
2007299406.tif 000067
【図１０】
2007299406.tif 000068
【図１１】
2007299406.tif 000069
【図１２】
2007299406.tif 000070
【図１３】
2007299406.tif 000071
【図１４】
2007299406.tif 000072
【図１５】
2007299406.tif 000073
【図１６】
2007299406.tif 000074
【図１７】
2007299406.tif 000075