"グラフデータストリーム内のオブジェクトをクラス化するための方法であって、前記グラフデータストリームは、エレメントを表わす複数のノードと、前記エレメント間の接続を表わすエッジとを含み、前記データストリーム内のオブジェクトは、ノードとそれらノード間のエッジとが一緒になったグループであり、前記方法は、グラフデータの訓練ストリームを受信するステップであって、前記訓練ストリームは、複数のオブジェクトを前記オブジェクトの各々に関連付けられたクラスラベルと共に含むものである、受信ステップと、前記クラスラベルについて前記訓練ストリーム内の判別エッジ集合を決定するステップであって、前記判別エッジ集合は、所与のクラスラベルを有するエッジを含むオブジェクトを指し示すものである、第1の決定ステップと、前記グラフデータの着信データストリームを受信するステップであって、前記着信データストリーム内の前記オブジェクトにはまだクラスラベルが割り当てられていない、受信ステップと、前記判別エッジ集合に基づいて、前記着信データストリーム内の前記オブジェクトに関連付けられるクラスラベルを決定する、第2の決定ステップと、前記第2の決定ステップに基づいた前記オブジェクト-クラスラベル対を情報リポジトリに出力するステップとを含み、前記方法がプロセッサを用いて行われる、方法。異なるオブジェクトの前記エッジが、前記グラフデータ内に順序が乱れて出現する、請求項1に記載の方法。前記第1の決定ステップが、前記訓練ストリームの第1の着信エッジを2次元2Dデータ構造内に配置するステップと、前記2Dデータ構造の各々の行及び列内の前記エッジについて、min-hash関数を用いて生成されるハッシュ値を生成するステップと、相関エッジ集合を識別するステップであって、相関エッジ集合は、前記訓練データ内の特定のオブジェクトに関連したエッジの集合であり、同じmin-hash値を有するエッジの集合が相関エッジ集合である、識別ステップと、クラスラベルを前記相関エッジ集合に割り当てて前記判別エッジ集合を得るステップであって、特定の相関エッジ集合に割り当てられるクラスラベルが、前記相関エッジ集合の優勢クラスラベルである、割当ステップと、前記判別エッジ集合をそれらの所与のクラスラベルと共にデータセット内に格納するステップであって、前記データセットが、ディスク上又は主コンピュータメモリ内に格納される、格納ステップとを含む、請求項1に記載の方法。前記2Dデータ構造が、前記主コンピュータメモリ内に格納される、請求項3に記載の方法。前記訓練ストリームの第2の着信エッジを受信するステップと、前記2Dデータ構造の各々の行及び列内の前記エッジについて、新たなハッシュ値を生成するステップと、前記新たなハッシュ値に基づいて、前記2Dデータ構造のインデックス及び値を更新するステップと、前記更新された2Dデータ構造を用いて、請求項3の識別ステップ、割当ステップ、及び格納ステップを繰り返すステップとをさらに含む、請求項3に記載の方法。前記第1の決定ステップが、前記訓練ストリームの第1の着信エッジを2Dデータ構造内に配置するステップと、前記2Dデータ構造の列を、第1のハッシュ関数を用いて擬似列にマッピングするステップであって、各々の擬似列がその中にマッピングされた複数の列を含む、マッピングステップと、前記2Dデータ構造の各々の行及び擬似列内の前記エッジについて、min-hash関数を用いて生成されるハッシュ値を生成するステップと、相関エッジ集合を識別するステップであって、相関エッジ集合は、前記訓練データ内の特定のオブジェクトに関連したエッジの集合であり、同じmin-hash値を有するエッジの集合が相関エッジ集合である、識別ステップと、クラスラベルを前記相関エッジ集合に割り当てて前記判別エッジ集合を得るステップであって、特定の相関エッジ集合に割り当てられるクラスラベルが、前記相関エッジ集合の優勢クラスラベルである、割当ステップと、前記判別エッジ集合をそれらの所与のクラスラベルと共にデータセット内に格納するステップであって、前記データセットが、ディスク上又は主コンピュータメモリ内に格納される、格納ステップとを含む、請求項1に記載の方法。前記2Dデータ構造が、前記主コンピュータメモリ内に格納される、請求項6に記載の方法。前記訓練ストリームの第2の着信エッジを受信するステップと、前前記第2の着信エッジが配置された前記2Dデータ構造の列を、前記第1のハッシュ関数を用いて擬似列にマッピングするステップと、前記2Dデータ構造の各々の行及び擬似列内の前記エッジについて、新たなハッシュ値を生成するステップと、前記新たなハッシュ値に基づいて、前記2Dデータ構造のインデックス及び値を更新するステップと、前記更新された2Dデータ構造を用いて、請求項6の識別ステップ、割当ステップ、及び格納ステップを繰り返すステップとをさらに含む、請求項6に記載の方法。前記第2の決定ステップが、前記着信データストリーム内の特定のオブジェクトについて、a前記クラスラベルについての前記訓練ストリーム内の前記判別エッジ集合が格納されたメモリにアクセスし、b前記オブジェクトに対応する判別エッジ集合を見つけ出すステップと、これらの前記判別エッジ集合の優勢クラスラベルを前記オブジェクトのクラスラベルとして割り当てるステップとを含む、請求項1に記載の方法。前記着信データストリーム内のユーザ定義パターンを見つけ出すことを求める要求を受け取るステップと、前記ユーザ定義パターンのパラメータに対応する、前記情報リポジトリ内に格納されたオブジェクトクラスラベル対を検索するステップと、前記検索結果をユーザに表示するステップとをさらに含む、請求項1に記載の方法。前記ユーザ定義パターンが、ソーシャルネットワークにおける特定の時間窓の中でのユーザの通信パターン、ウェブグラフのユーザが特定のウェブページに入るときの閲覧パターン、又は通信ネットワーク上の侵入トラフィックを含む、請求項10に記載の方法。前記グラフデータが、ウェブグラフ、ソーシャルネットワーク又は通信ネットワークから提供される、請求項1に記載の方法。前記ウェブグラフのノードは、ユニフォームリソースロケータURLアドレスを含み、前記ウェブグラフのエッジは、前記URLアドレス間のリンクを含み、前記ソーシャルネットワークのノードは、ユーザ識別子を含み、前記ソーシャルネットワークのエッジは、前記ユーザ識別子間のリンクを含み、又は、前記通信ネットワークのノードは、インターネットプロトコルIPアドレスを含み、前記通信ネットワークのエッジは、前記IPアドレス間のリンクを含む、請求項12に記載の方法。グラフデータストリーム内のオブジェクトをクラス化するためのコンピュータプログラムであって、前記グラフデータストリームは、エレメントを表わす複数のノードと、前記エレメント間の接続を表わすエッジとを含み、前記データストリーム内のオブジェクトは、ノードとそれらノード間のエッジとが一緒になったグループであり、前記コンピュータプログラムは、グラフデータの訓練ストリームを受信するステップであって、前記訓練ストリームは、複数のオブジェクトを前記オブジェクトの各々に関連付けられたクラスラベルと共に含むものである、受信ステップと、前記クラスラベルについて前記訓練ストリーム内の判別エッジ集合を決定するステップであって、前記判別エッジ集合は、所与のクラスラベルを有するエッジを含むオブジェクトを指し示すものである、第1の決定ステップと、前記グラフデータの着信データストリームを受信するステップであって、前記着信データストリーム内の前記オブジェクトにはまだクラスラベルが割り当てられていない、受信ステップと、前記判別エッジ集合に基づいて、前記着信データストリーム内の前記オブジェクトに関連付けられるクラスラベルを決定する、第2の決定ステップと、前記第2の決定ステップに基づいたオブジェクト-クラスラベル対を情報リポジトリに出力するステップとを実行するように構成されたコンピュータ可読プログラムコードを含む、コンピュータプログラム。前記第1の決定ステップが、前記訓練ストリームの第1の着信エッジを2次元2Dデータ構造内に配置するステップと、前記2Dデータ構造の各々の行及び列内の前記エッジについて、min-hash関数を用いてされるハッシュ値を生成するステップと、相関エッジ集合を識別するステップであって、相関エッジ集合は、前記訓練データ内の特定のオブジェクトに関連したエッジ集合であり、同じmin-hash値を有するエッジの集合が相関エッジ集合である、識別ステップと、クラスラベルを前記相関エッジ集合に割り当てて前記判別エッジ集合を得るステップであって、特定の相関エッジ集合に割り当てられる前記クラスラベルが、前記相関エッジ集合の優勢クラスラベルである、割当ステップと、前記判別エッジ集合をそれらの所与のクラスラベルと共にデータセット内に格納するステップとを含む、請求項14に記載のコンピュータプログラム。前記第1の決定ステップが、前記訓練ストリームの第1の着信エッジを2Dデータ構造内に配置するステップと、前記2Dデータ構造の列を、第1のハッシュ関数を用いて擬似列にマッピングするステップであって、各々の擬似列がその中にマッピングされた複数の列を含む、マッピングステップと、前記2Dデータ構造の各々の行及び擬似列内の前記エッジについて、min-hash関数を用いて生成されるハッシュ値を生成するステップと、相関エッジ集合を識別するステップであって、相関エッジ集合は、前記訓練データ内の特定のオブジェクトに関連したエッジ集合であり、同じmin-hash値を有するエッジ集合が相関エッジ集合である、識別ステップと、クラスラベルを前記相関エッジ集合に割り当てて前記判別エッジ集合を得るステップであって、特定の相関エッジ集合に割り当てられるクラスラベルが、前記相関エッジ集合の優勢クラスラベルである、割当ステップと、前記判別エッジ集合をそれらの所与のクラスラベルと共にデータセット内に格納するステップとを含む、請求項14に記載のコンピュータプログラム。グラフデータストリーム内のオブジェクトをクラス化するための方法であって、前記グラフデータストリームは、エレメントを表わす複数のノードと、前記エレメント間の接続を表わすエッジとを含み、前記データストリーム内のオブジェクトは、ノードとそれらノード間の前記エッジとが一緒になったグループであり、前記方法は、グラフデータの訓練ストリームを受信するステップであって、前記訓練ストリームは、複数のオブジェクトを前記オブジェクトの各々に関連付けられたクラスラベルと共に含むが、前記訓練ストリーム内の前記エッジは、それらが属するオブジェクトと共には受信されない、受信ステップと、前記クラスラベルについて前記訓練ストリーム内の判別エッジ集合を決定するステップであって、前記判別エッジ集合は、所与のクラスラベルを有するエッジを含むオブジェクトに属するものである、第1の決定ステップと、前記グラフデータの着信データストリームを受信するステップであって、前記着信データストリーム内の前記オブジェクトにはまだクラスラベルが割り当てられていない、受信ステップと、前記判別エッジ集合に基づいて、前記着信データストリーム内の前記オブジェクトに関連付けられるクラスラベルを決定する、第2の決定ステップと、前記第2の決定ステップに基づいた前記オブジェクト-クラスラベル対を情報リポジトリに出力するステップとを含み、前記方法がプロセッサを用いて行われる、方法。前記第1の決定ステップが、前記訓練ストリームのグラフデータに対して行われ、前記グラフデータは、行及び列を有するデータ構造として主コンピュータメモリ内に格納される、請求項17に記載の方法。前記第1の決定ステップが、前記データ構造内のエッジデータに対してハッシュ手順を実行して相関エッジ集合を決定するステップを含み、相関エッジ集合は、特定のオブジェクトに対して高いコヒーレンス確率を有するエッジを含むものである、請求項18に記載の方法。前記第1の決定ステップが、前記相関エッジ集合について優勢クラスラベルを決定するステップをさらに含み、前記優勢クラスラベルは、そのエッジ集合について最高絶対度数を有するクラスラベルである、請求項19に記載の方法。大規模グラフがストリーム形態である場合には、そのことが、将来的な解析のために構造情報をマイニングするために用いることができるアルゴリズムの種類を制限する。例えば、ストリームであるという制約条件は、データ上で1つのパスしか許容しない。さらに、グラフのエッジは、データストリーム内で順序が乱れて到着することがある。グラフのサイズが大規模であることで、クラス化に関連した情報の効果的な抽出にとっての難題も生じる。例えば、グラフデータ内の多数の相異なるエッジに関する集計情報を格納することは困難である。さらに、構造的挙動は多数の相異なるエッジの組合せによって支配されるので、部分構造決定問題の複雑度の指数関数的増大は、部分構造のカーディナリティが増すにつれて非常に速く増大する。このような場合、頻度判別的部分グラフの決定は、計算的にも空間的にも非実用的な程度まで非効率的になることがある。本発明の例示的な実施形態は、グラフデータストリーム内のオブジェクトをクラス化するための方法及びコンピュータプログラム製品を提供する。グラフデータストリームは、エレメントを表わす複数のノードと、エレメント間の接続を表わすエッジとを含むことができる。データストリーム内のオブジェクトは、ノードとそれらのノード間のエッジとが一緒になったグループとすることができる。例示的な方法において、グラフデータの訓練ストリームが受信され、この訓練ストリームは、複数のオブジェクトをそれらオブジェクトの各々に関連付けられたクラスラベルと共に含む。クラスラベルについて訓練ストリーム内の判別エッジ集合例えば、部分グラフが決定され、ここで判別エッジ集合は、所与のクラスラベルを有するエッジを含むオブジェクトを指し示すものしかし、直接対応するものではないである。次にグラフデータの着信データストリームが受信されるが、着信データストリーム内のオブジェクトにはまだクラスラベルは割り当てられていない。判別エッジ集合に基づいて、着信データストリーム内のオブジェクトに関連付けられるクラスラベルが決定される。第2の決定に基づいたオブジェクト-クラスラベル対が、情報リポジトリに出力される。本発明の例示的な実施形態による、グラフデータストリーム内のオブジェクトをクラス化するための方法を以下説明する。グラフデータストリームは、大規模なものとすることができる。オブジェクトは、ウェブサーフィンのパターンを識別するグラフのノード及びエッジを含むことができる。例えば、訪問したウェブサイトがノードであり、1つのウェブページから別のウェブページへのパスがエッジである。したがって、ページ1の次にページ2へ、その次にページ3へと訪問するユーザは、ある特定の特性を有していそうなすなわち、特定の本を購入しそうな人である。本発明は、そのようなパターンを識別し、次いで、これらのパターンに、関連したラベルを割り当てることを目的とする。このことを達成するために、グラフデータの訓練ストリーム内に存在する判別的discriminative部分グラフを最初に決定し、次いでクラスラベルを与える。簡単に言えば、着信データを小空間に縮小する2次元2Dハッシュ圧縮技術を用いて相関エッジ集合を決定する。次いで相関エッジ集合について優勢クラスラベルを決定し、この優勢クラスラベルをそれぞれの部分グラフに対して最終的なクラスラベルとして与えて、判別的部分グラフを得る。次にこの判別的部分グラフを用いて、検定グラフストリーム内のオブジェクトのクラスラベルを推論することができる。例えば上述のウェブサーフィンのパターンを反映したオブジェクトを含む検定グラフストリームがストリームプロセッサにおいて受信される場合には、判別的部分グラフとそれらの関連付けられたクラスラベルとを含むメモリにアクセスして、着信オブジェクトに対応する部分グラフを見つけ出すことができる。着信オブジェクトが対応する部分グラフのクラスラベルが、そのオブジェクトに与えられる。この場合、クラスラベルは、そのオブジェクトが特定の本を購入しそうなユーザのパターンに対応することを示すことができる。図1は、大規模グラフの一部を示す。この例では、ウェブグラフ100が示されている。しかしながら、大規模グラフは、通信ネットワーク、ソーシャルネットワーク等のグラフとすることができる。図1に示されるように、ウェブグラフ100は、複数のノードA-P及びエッジすなわちノード間の矢印を含む。ウェブグラフ100は、例えば、107を超えるノード及び1013を超えるエッジを含むことがあるので、図1にはウェブグラフ100の一部しか示されていない。ウェブグラフ100のノードA-Pは、ウェブページを表わすことができ、ウェブグラフ100のエッジは、ウェブページ間のハイパーリングを表わすことができる。ウェブグラフ100のリンク構造は、様々なデータマイニング目的で利用することができる豊富な情報を保持する。例えば、マイニングを通じて識別されたウェブ閲覧パターンは、脅威をクラス化してテロリズムと戦うために政府が用いることもでき、又は、顧客が正に必要とするものを供給することによってより良い顧客との関係を確立するために会社が用いることもできる。図2は、本発明の例示的な実施形態による、グラフデータストリーム内のオブジェクトをクラス化するための方法のフローチャートである。再び図1を参照すると、オブジェクトは、ノードA-Pとそれらのエッジとが一緒になったグループとすることができる。例えば、オブジェクトは、ノードA及びBをそれらの間の単一のエッジと共に含むことができ、又は、より多くのノードとそれらの間のエッジとを含むこともできる。図2に示されるように、ストリームプロセッサは、ウェブグラフ100からデータの訓練ストリームを受信する210。ストリームプロセッサは、ニューヨーク州アーモンクArmonkのインターナショナルビジネスマシーンズコーポレーションが提供するInfoSphereStreams登録商標以前はSystemSとして知られていたのような実時間ストリーム処理プラットフォームを実行することができるコンピューティング環境とすることができる。InfoSphereStreams商標に関する詳細は、例えば、非特許文献1を含む種々のIBM商標の刊行物で提供される。InfoSphereStreams商標プラットフォームは、ストリーム処理言語SPL:StreamProcessingLanguage、以前はSPADEとして知られていたと呼ばれる高水準プログラミング言語を用いる。SPADEは、非特許文献2で説明されている。SPLに関するさらなる詳細は、非特許文献3で説明されている。InforSphereStreams商標及びストリーム処理言語は、多数の演算ノードに及ぶことがある分散データストリーム処理アプリケーションをサポートする。ストリーム処理言語の宣言型言語は、一例において、これらの多重オペレータアプリケーションをプログラムするために用いられる。ストリーム処理言語のストリーム中心の設計は、基本ビルディングブロックがストリームである言語を含意する。ストリーム処理言語のオペレータベースのプログラミングは、あるアプリケーションがその実行のために設計された演算を供給するのに必要とされる可能な限り最小限のビルディングブロックに基づいて、アプリケーションを設計することに焦点を合わせている。ステップ210において受信されたグラフデータの訓練ストリームは、複数のオブジェクトをこれらのオブジェクトに関連付けられたクラスラベルと共に含む。ストリーム内の個々のオブジェクトは、グラフG1..GN...で示すことができる。各グラフGiは、{1...m}から引き出されるクラスラベルCiに関連付けられる。ウェブグラフは、ノード集合Nにわたって定義することができる。ストリーム内のデータは、順々にストリームプロセッサに到着する。例えば、データは、GraphIdEdgeClassLabelのように到着することができる。ストリーム内で、クラスラベルは常にグラフ識別子に添付されていると仮定する。グラフGiのエッジは、ストリーム内で順序が乱れて出現することがある。これは、ソーシャルネットワーク及び通信ネットワークのような多くのアプリケーションでは一般によくあることであり、その理由は、異なるエッジを横断してメッセージ及び通信の順序を制御することができないからである。変数Edgeの値は、その2つの構成ノードにより定義される。ストリーム内のデータのうちの幾つかの例として、ネットワーク侵入アプリケーションを考えると、この場合、識別子は侵入が生じたタイムスタンプに対応する。侵入は、部分グラフに対応するエッジ集合を誘導することができる。したがって、グラフの識別子は、タイムスタンプとすることができる。エッジは、攻撃者と犠牲者の送信元及び宛先のIPアドレスを含むことができる。クラスラベルは、侵入のタイプとすることができる例えばサービス妨害攻撃。グラフデータの訓練ストリームの受信に応答して、訓練ストリーム内の判別エッジ集合例えば、部分グラフがクラスラベルについて決定される220。このステップにおいて、最初に相関エッジ集合を見つけ出し、次にこれらにクラスラベルを与えて、判別エッジ集合を得る。例えば、対応する共起エッジグループとしての存在が統計的に期待されるよりはるかに高い部分グラフが、最初に見つけ出される。そのような部分グラフは、以下の議論において、有意な部分グラフと呼ばれる。次に、特定のクラスに対して判別的な部分グラフが決定される。相関エッジ集合を見つけ出し、これにクラスラベルを与えて判別エッジ集合を得る方法を検討する前に、幾つかの関連した注釈及び定義をここで紹介する。有意な部分グラフPは、その構成エッジの相対度数に関して有意な統計的存在を有するものとして定義される。これは、エッジコヒーレンスと呼ばれる。この概念は、形式上、以下のように定義される。f∩Pを、G1...GNのうち、Pの全てのエッジが存在するグラフの分率とする。f∪Pを、Pのエッジのうちの少なくとも1つ又は複数が存在するグラフの分率とする。すると、部分グラフPのエッジコヒーレンスCPは、f∩P/f∪Pで表される。このエッジコヒーレンスの定義は、部分グラフパターンの絶対存在ではなく、むしろ相対存在に焦点を合わせたものである。このことは、有意な部分グラフだけが見つけ出されることを保証する。このことは、度数は高いが有意性は低い多数の関連性のないパターンは考慮されないこともまた保証する。クラスラベルr∈{1...m}に関するエッジ集合Pのクラス信頼度は、以下のように定義される。部分グラフPを含む全てのグラフの中で、sP,rを、クラスラベルrに属する分率とする。この分率は、クラスrに関するパターンPの信頼度である。次いで、特定の部分グラフについての優勢クラス信頼度は、以下のように定義される。優勢クラス信頼度DIP又は部分グラフPは、全ての異なるクラス{1...m}にわたる最大クラス信頼度として定義される。特定の検定インスタンスについてのDIPの有意に大きい値は、そのパターンPがクラス化にとって非常に関連性のあるものであること、及び、対応する優勢クラスラベルがその検定インスタンスのラベルの魅力的な候補となり得ることを示している。絶対存在の点で興味深い、特定のクラスについて判別的な部分グラフを決定するために、エッジコヒーレンス及びクラス興味率classinterestratioに対する閾値パラメータに対応する、パラメータ対α,θも用いられる。部分グラフPは、以下の2つのエッジコヒーレンス及びクラス判別の制約条件を満たすならば、α,θ有意であるといわれる。部分グラフPのエッジコヒーレンスCPが少なくともαであること。すなわち、CP>α。優勢クラス信頼度DIPが少なくともθである。すなわち、DIP>θ。相関エッジ集合を見つけ出すために、本発明の例示的な実施形態によれば、2Dハッシュ圧縮技術が用いられる。この技術は、クラス化に最も関連した判別的部分グラフを決定することができる連続的に更新可能なデータ構造を使用する。このデータ構造は小さいので、主メモリ内で維持することができ、着信データストリームが到着している間の任意の時点で用いることができる。議論を簡単にするために、データ構造は、グラフデータセットのN行n列の表形式の二進表現とすることができる。N行は、データ内に存在するN個の異なるグラフに対応する。列は、データ内の異なるエッジを表わすが、これは1対1写像ではない。nの選択は、主メモリ内で表を保持するのに利用可能な空間に依存する。2つの2Dハッシュ圧縮技術を、本発明に従って用いることができる。1つは、min-hash圧縮を行に対してのみ用いる技術であり、各列は相異なるエッジに対応する。もう1つは、従来のハッシュ関数を用いることにより複数の列を単一の列にマッピングし、次に、min-hash圧縮を行に対して用いる技術である。ここで第1の技術について論じる。このmin-hashスキームの主たる思想は、データ内の行に対するソート順序を用いることにより、異なる列上の値における共起性を決定することである。このソート順序を作り出すために、単一の一様乱数ハッシュ値が、データ内の各行について生成される。データ内の全ての列は、このハッシュ値の順序によりソートされる。このような手法の結果として、各列は全く同じランダムな順序でソートされることになることに留意されたい。それゆえ、以下のことを観察することができる。Pエッジの集合を考える。P’を、Pに対応する表内の列とする。列は、ハッシュ値によりソートされた順序で検査される。1の値を有するP’内の各列についての第1の行のインデックスが同じである確率は、エッジコヒーレンスCPに等しい。P’内の列のうちのいずれかの中に1を有する第1の行のインデックスは、P’のエッジのうちのいずれかが存在する第1の行でもあるので、上記の観察は検証が簡単である。この行が、関連した列にわたって全て1の値を含む確率が、エッジコヒーレンス確率CPである。この手法を用いて、エッジコヒーレンス確率の標本推定を構築することができる。例えば、k個の異なるハッシュ値を用いてソート順序を構築することができ、上記の確率は、全ての値が1であるk個の標本の分率を計算することによって推定することができる。ここで、完全な表の使用を伴う第1の技術の実施を検討する。この場合、表がE個の列を有すると仮定すると、E=NN-1/2が、データ内の可能な相異なるエッジの数である。min-hashインデックスを用いて、根底にあるデータのトランザクション表現を構築する。これを行うために、最初にk個の異なるハッシュ値を用いたmin-hash手法を適用し、サイズk×Eの表を作成する。ここで、このmin-hash表現からの特定の標本を検査する。r1...rEを、対応する列内に1を有する第1の行の行インデックスとする。次に、集合r1...rEを、min-hashインデックス値が同じであるグループに分割する。したがって、r1...rEがQ1...Qhに分割されたならば、各ri∈Qjは同じ値を有する一定のjについて。各分割Qjについて、対応する列のインデックスを含むカテゴリ的トランザクションを作成する。例えば、Qj={r2,r23,r45,r71}ならば、トランザクションTj={2,23,45,71}を作成する。最後に、等インデックス分割Q1...Qhに対応するトランザクションT1...Thを構築する。各インデックス集合は対応するトランザクション集合を作成するので、この標本抽出プロセスをk回繰り返してk個の異なるインデックス集合を作成することにより、推定プロセスの精度を高めることができる。例えば、各インデックス集合について、対応するトランザクション集合を全トランザクション集合Tに加える。以下の観察がなされる。Tを、min-hashインデックス集合から構築されたトランザクションとする。すると、エッジ集合Pのコヒーレンス確率CPは、トランザクション集合TにおけるP’の絶対台absolutesupportをkで割ったものとして推定することができる。高いコヒーレンス確率CPを有するエッジが、相関エッジ集合であると決定される。この観察は、従来の観察の直接的拡張である。なぜなら、列集合P’は、T1...Th内のトランザクションを、P’内のエッジのmin-hashインデックスが、該トランザクションがそこから構築された対応するmin-hash標本内で同一であるときかつそのときに限り、支持するからである。特定のグラフ内のエッジの存在を表わす表の行は、所与の時点で利用可能でないことがあることに留意されたい。なぜなら、所与のグラフについてのエッジは、ストリームシナリオにおいては連続的に到着しない場合があるからである。さらに、データは典型的に非常に疎であり、表内の大部分の値は0である。したがって、本発明は、疎な無順序のエッジと共に機能することができる新規な更新プロセスを使用する。このプロセスの例は、図3のアルゴリズム300によって示される。図3に示されるように、ストリーム内の各々の着信グラフエッジe∈Gグラフ識別子IdGを有するについて、k個のランダムハッシュ値h1,IdG...hk,IdGが生成される。i番目のハッシュ値hi,IdGは、piで表される。ハッシュ関数h,は、入力としてIdGを用いるので、ストリーム内の後の段階において同じグラフGからのエッジに遭遇したときに、同じランダムハッシュ値を生成することができる。ランダムハッシュ値を生成するために、h,の2つの引数に対応する文字列の連接に対して、標準的なハッシュ関数を用いることができる。Lを、ストリーム内で今までに遭遇した相異なるエッジの数の実行中推定runningestimateとする。アルゴリズム300は、kL個の実行中最小ハッシュ値の集合Vを、これらの最小値が得られたkL個の対応するグラフ識別子の集合Iと共に維持する。Lの値は、データストリームの進行中に、ますます多くの相異なるエッジがストリームによって受信されるので、増加する。V内の各エントリはe,MinHashValueの形式であり、I内の各エントリはe,GraphIdentifierの形式である。データストリーム内で今までに遭遇した各々の相異なるエッジについて、V及びIの両方の中にこのようなk個のエントリが存在する。各エッジeについて、V内のi番目の最小ハッシュ標本は、eを含む全グラフG上でのhi,IdGの最小値を表わす。特定のエッジeについてのI内のk個のエントリは、V内のこれら最小ハッシュ値が得られたk個のグラフ識別子を表わす。ストリーム内のエッジは、順序が乱れて出現することがあるので、アルゴリズム300の適用により、各エッジは、ストリーム内で自身に対応するグラフ識別子に関連付けられる。この場合、各々の着信エッジe及びグラフ識別子IdGについて、集合V及びIは、アルゴリズム300によって以下のように更新される。k個の異なるハッシュ値pl=h1,IdG...pk=hk,IdGを生成する。今までにエッジeに遭遇していない場合には、その情報はV及びI内に存在しないことになる。そのような場合には、Lの値を増やし、eについての対応するエントリをV及びIの中にそれぞれ含める。具体的には、この新たに追跡されるエッジについてのV内のk個のハッシュ値が、最近生成されたk個のハッシュ値p1...pkに設定される。したがって、エントリe,p1...e,pkが、Vの中に含められる。これに対応して、エントリe,IdG...e,IdGが、Iに追加される。一方、ストリーム内で既にエッジeに遭遇している場合には、対応するエントリe,MinHashValue1...e,MinHashValuekがV内で検査される。新たに生成されたハッシュ値piがMinHashValueiより小さい場合には、e,MinHashValueiは、e,piで置き換えられる。さらに、I内の対応するエントリは、e,IdGで置き換えられる。図4は、各々の着信エッジについてmin-hashインデックスを更新するプロセスを示す、図3のアルゴリズム300の一部を反映したフローチャートである。特に、図4は、各々の着信グラフストリームについて要求されるステップを示す。ステップ410において、各行についてk個のランダムハッシュ値が生成され、この行は、本質的にはストリーム内の着信グラフである。k個のランダムハッシュ値は、図3においては、p1...pkとも称される。ステップ420において、各行のmin-hashインデックスが更新される。ステップ430において、各行についてのmin-hash値が更新される。これらの更新は、生成されたmin-hash値が現行の値より小さい場合にのみ行われる。この生成ステップは、図3の最も内側のループにより行われる。以上のように、図3及び図4を参照して検討したプロセスは、着信グラフの集計表現を連続的に維持する。これらの集計統計量は主メモリ内で維持されるので、任意の時点でこれらを用いて、コヒーレントなエッジパターン、すなわち相関エッジ集合を決定することができる。図3のアルゴリズム300の使用に伴う主定数は、集計統計量V及びIがサイズOkLを有することであり、ここでLは今までに遭遇した相異なるエッジの数であることに留意されたい。ここでの問題点は、本開示において検討されている大規模グラフ仮説のため、Lの値が非常に大きくなることがあるという点である。そのような大きい集計は、このシナリオでの効率的な更新プロセスのために必要とされるディスク上又は主メモリ内に容易に維持することができないことがある。したがって、図3のmin-hash行圧縮アルゴリズム300は、図5のアルゴリズム500により示されるプロセスで補完される。図5に示されるプロセスは、第2のmin-hash技術であり、データ構造のサイズを縮小するために列圧縮を用いる。この結果として、行及び列が同時に圧縮されるが、図5における列圧縮は、図3とは異なるやり方で実行される。図5のアルゴリズム500は、図3のアルゴリズム300と同様であるが、但し、データ内の各エッジは、最初に一様乱数ハッシュ関数を用いて範囲[1,n]内の整数にマッピングされ、次に図3のアルゴリズム300のステップが適用される。したがって、この場合には、実際のエッジ上でパターンを決定する代わりに、範囲[1,n]内の整数上でパターンが決定される。さらに、図5のアルゴリズム500は、列圧縮サイズnを入力として用い、これを用いて各エッジを[1,n]内の整数上にマッピングするという点で、図3のアルゴリズムとは異なる。アルゴリズム300においては、このマッピングは、一様ハッシュ関数を使用して行われる。エッジの文字列表現は、2つの端部のノードラベルを連接することにより構築される。次いで、ハッシュ関数がこの文字列表現に適用される。nの値は、記憶装置の要件に基づいて選ぶことができ、典型的には、相異なるエッジの数よりもずっと小さくされる。nの選択は、記憶装置の大きさと精度との間のトレードオフに起因する。複数のエッジを同じ整数にマッピングすることができるので、この手法の結果として計算精度のある程度の低下がさらに生じることがある。しかしながら、列圧縮スキームは、質の低下が比較的小さい状態で、空間の要求条件を顕著に小さくする。列圧縮を用いて各々の着信グラフについてのハッシュインデックスを更新するための方法を示す、図5のアルゴリズム500の一部を反映したフローチャートが図6に示される。このフローチャートは、図4に示されるものと同様であるが、但し、エッジは、より制限されたハッシュ値の集合にマッピングされている。これは、全ての相異なるエッジについてのハッシュ値を追跡するには、相異なるエッジの数が多すぎる過ぎることがあるという理由で行われる。図6に示されるように、ステップ610において、エッジは、従来のハッシュ関数により、擬似列の制限された集合に対してマッピングされる。その後のステップは、図4のステップと同様である。ステップ620において、異なる行についてのハッシュ値が生成される。ステップ630及びステップ640において、生成されたmin-hash値が今までにストリーム内で遭遇した現行の値より小さければ、現行のmin-hashインデックス及び値がそれぞれ生成される。クラスラベルもまた、min-hashスキームの実行中に追跡される。先に述べたように、グラフのクラスラベルは、各グラフGについての識別子IdGに添付されていると仮定する。したがって、クラスラベルは、グラフ識別子と共に追跡される。具体的には、グラフ識別子の最後の部分が、そのグラフのクラスラベルである。min-hashインデックスはグラフ識別子を含むので、暗黙的にクラスラベルも含む。これらのクラスラベルを用いて、データの圧縮された集計から判別エッジ集合を計算する。これは、特定のクラスラベルと高度に相関するmin-hashインデックス内の頻度の高いエッジのパターン換言すれば、コヒーレントな又は相関エッジパターンを決定することにより達成される。具体的には、min-hash相内で決定された高頻度パターンに関係した優勢クラスラベルが決定され、クラスの存在がユーザ定義閾値を上回る全てのパターンの集合が保存される。ここで、図2のステップ230を参照すると、ストリームプロセッサは、グラフデータの着信ストリームを受信する。このストリームは訓練ストリームと同様であるが、但し、ストリーム内のオブジェクトにはまだクラスラベルが割り当てられていないことに留意されたい。このようなストリームの例は、侵入の性質はまだ決定されていないが侵入に対応する部分グラフは既に受信された、侵入アプリケーションとすることができる。グラフデータの着信ストリームを入力として用いて、クラスラベルが着信データストリーム内のオブジェクトに関連付けられる240。これは、ステップ220で決定された判別エッジ集合を用いることによって行われる。具体的には、訓練相において決定された判別的部分グラフに対応するオブジェクトを着信グラフ内で見つけ出す。次に、見つけ出されたオブジェクトに対して、その単独の対応する部分グラフのクラスラベル又はその対応する部分グラフの多数派のクラスラベルが割り当てられる。これらのオブジェクト-クラスラベル対は、次にストリームプロセッサから出力され、情報リポジトリ内に格納される250。これらの対を処理して、多様なアプリケーションのための有用な情報を提供することができる。特に、ユーザは、着信データストリームの中から見つけ出すべき特定のパターンを定義することができる260。例えば、侵入検出アプリケーションでは、ユーザは、侵入攻撃の性質例えば、それがサービス妨害攻撃であるか否かに関して知りたいと望むかもしれない。オブジェクト-クラスラベル対は、着信ストリーム内のクラスをサービス妨害とラベル付けすることにより、そのような攻撃の性質に関する情報を提供することができる。ここで、本発明の例示的な実施形態を、図7の装置701を参照して説明する。装置701はコンピュータとすることができ、これは、メモリ702、ディスク703、及び中央処理ユニットCPU704などのプロセッサを含む。本明細書で用いられるプロセッサという用語は、図2を参照して上で検討したストリームプロセッサのような、任意の処理デバイス、例えばCPU及び/又は他の形態の処理回路を含むものなどを含むことを意図することを理解されたい。さらに、プロセッサという用語は、複数の個別のプロセッサを指すことができる。メモリという用語は、プロセッサ又はCPUに関連付けられたメモリ、例えば、RAM、ROM、固定メモリデバイス例えば、ハードドライブ、取り外し可能なメモリデバイス例えば、ディスケット、フラッシュメモリなどを含むことが意図される。さらに、本明細書で用いられる入力/出力インターフェースという語句は、例えば、処理ユニットにデータを入力するための1つ又は複数の機構例えば、マウス、及び、処理ユニットに関連付けられた結果を提供するための1つ又は複数の機構例えば、プリンタを含むことが意図される。図7に示されるように、装置701が入力インターフェースを介して訓練ストリームのようなグラフデータストリームを受信すると、これを、図2-図6を参照して上で説明したメモリ702内の2Dデータ構造内に格納することができる。グラフデータストリームは、任意のタイプの大規模グラムから到来したものとすることができる。着信グラフデータをCPU704で処理して、例えば図2-図6を参照して上で説明した方法で判別エッジ集合を決定する。判別エッジ集合は、それらのクラスラベルと共にディスク703内に格納することができる。装置701が入力インターフェースを介して非訓練/検定グラフデータストリームを受信したときには、この入力データストリームはメモリ702内に置くことができる。次いで、ディスク703内に格納された判別エッジ集合にアクセスして、非訓練/検定グラフデータストリーム内のオブジェクトに関連付けられるクラスラベルを、図2-図6を参照して説明した方法で決定することができる。次いで、この決定に基づいたオブジェクト-クラスラベル対を、装置701の出力インターフェースを通じて情報リポジトリ705に出力することができる。情報リポジトリ705は、オブジェクト-クラスラベル対が格納されるディスク記憶装置の形態とすることができる。オブジェクト-クラスラベル対は、将来的な処理のために任意の種類のデータベース内に格納することができる。非訓練グラフデータストリーム内の所望のパターンを識別するために、オブジェクト-クラスラベル対は、情報リポジトリ705から装置701又は別のコンピューティング装置によってアクセスすることができる。次に、オブジェクト-クラスラベル対を解析して、所望のパターンを決定することができる。例えば、特定のウェブサイトを訪問したときのユーザの挙動を指し示すオブジェクト-クラスラベル対を見つけ出すことができる。幾つかの実施形態においては、パターン識別を実施することを求める要求710、例えばユーザから入力される検索要求を、装置701に入力することができる。幾つかの実施形態においては、要求に対する応答720が装置701から出力される。当業者により認識されるように、本発明の態様は、システム、方法又はコンピュータプログラム製品として具体化することができる。したがって、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態ファームウェア、常駐ソフトウェア、マイクロコード等を含む、又はソフトウェアの態様とハードウェアの態様とを組み合わせた実施形態の形態をとることができ、これらは全て本明細書において一般的に回路、モジュール又はシステムと呼ばれることがある。さらに、本発明の態様は、具体化されたコンピュータ可読プログラムコードをその中に有する1つ又は複数のコンピュータ可読媒体内に具体化されたコンピュータプログラム製品の形態をとることができる。1つ又は複数のコンピュータ可読媒体のあらゆる組み合わせを用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体であってもよく、又はコンピュータ可読ストレージ媒体であってもよい。コンピュータ可読ストレージ媒体は、例えば、電子的、磁気的、光学的、電磁的、赤外線若しくは半導体のシステム、装置若しくはデバイス、又はそれらのいずれかの適切な組み合わせとすることができるがこれらに限定されない。コンピュータ可読ストレージ媒体のより具体的な例非網羅的なリストは、以下もの、即ち、1つ又は複数のワイヤを有する電気的接続、ポータブルコンピュータディスケット、ハードディスク、RAM、ROM、消去可能なプログラム可能読み取り専用メモリEPROM又はフラッシュメモリ、光ファイバ、ポータブルコンパクトディスク型読み取り専用メモリCD-ROM、光ストレージデバイス、磁気ストレージデバイス、又はそれらのいずれかの適切な組み合わせを含む。本文書の文脈において、コンピュータ可読ストレージ媒体は、命令実行システム、装置若しくはデバイスによって用いられるプログラム又はそれらに関連して用いられるプログラムを収容又は格納することができる、いずれかの有形媒体とすることができる。コンピュータ可読信号媒体は、具体化されたコンピュータ可読プログラムコードを例えばベースバンド内に又は搬送波の一部としてその中に有する、伝搬データ信号を含むことができる。このような伝搬信号は、電磁的形態、光学的形態又はこれらのいずれかの適切な組み合わせを含む種々の形態のうちのいずれの形態をとることもできるが、それらに限定されない。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、且つ、命令実行システム、装置若しくはデバイスによって用いられるプログラム又はそれらに関連して用いられるプログラムを伝達、伝搬又伝送することができる、いずれかのコンピュータ可読媒体とすることができる。コンピュータ可読媒体上に具体化されたプログラムコードは、無線、有線、光ファイバケーブル、RF等、又はこれらのいずれかの適切な組み合わせを含むがそれらに限定されない、いずれかの適切な媒体を用いて送信することができる。本発明の態様に関する動作を遂行するためのコンピュータプログラムコードは、Java、Smalltalk、C等のようなオブジェクト指向プログラミング言語、及びCプログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、1つ又は複数のプログラミング言語のいずれかの組み合わせで記述することができる。プログラムコードは、全体がユーザのコンピュータ上で実行される場合もあり、独立型ソフトウェアパッケージとして一部がユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は全体が遠隔コンピュータ若しくはサーバ上で実行される場合もある。後者のシナリオの場合、遠隔コンピュータは、ローカルエリアネットワークLAN又は広域ネットワークWANを含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は外部コンピュータへの接続がなされる場合もある例えば、インターネットサービスプロバイダを用いたインターネットを通じて。本発明の態様は、本発明の実施形態による方法、装置システム及びコンピュータプログラムのフローチャート図及び/又はブロック図を参照しながら説明される。フローチャート図及び/又はブロック図の各ブロック、並びにフローチャート図及び/又はブロック図内のブロックの組み合わせは、コンピュータプログラム命令によって実施することができることが理解される。これらのコンピュータプログラム命令を、機械を製造するために汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに提供し、これにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令がフローチャート及び/又はブロック図の1つ又は複数のブロックにおいて指定された機能/動作を実施するための手段を作り出すようにさせることができる。これらのコンピュータプログラム命令を、コンピュータ、他のプログラム可能データ処理装置又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、これにより、そのコンピュータ可読媒体内に格納された命令がフローチャート及び/又はブロック図の1つ又は複数のブロックにおいて指定された機能/動作を実施する命令を含む製品を製造するようにさせることもできる。コンピュータプログラム命令をコンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上にロードして、一連の動作ステップをコンピュータ、他のプログラム可能装置又は他のデバイス上で実行させて、コンピュータ実施プロセスを生成し、これにより、コンピュータ又は他のプログラム可能装置上で実行される命令がフローチャート及び/又はブロック図の1つ又は複数のブロックにおいて指定された機能/動作を実施するためのプロセスを提供するようにさせることもできる。図面内のフローチャート及びブロック図は、本発明の種々の実施形態によるシステム、方法及びコンピュータプログラムの可能な実装のアーキテクチャ、機能及び動作を示す。この点に関して、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための1つ又は複数の実行可能な命令を含むモジュール、セグメント又はコードの一部を表すことができる。幾つかの代替的な実装において、ブロック内に記された機能は、図面内に記された順序とは異なる順序で行われることもあることにも留意されたい。例えば、連続して示された2つのブロックが実際には実質的に同時に実行されることもあり、又は、それらのブロックは、関与する機能に応じて、ときには逆順で実行されることもある。ブロック図及び/又はフローチャート図の各ブロック、並びにブロック図及び/又はフローチャート図内のブロックの組み合わせは、指定された機能又は動作を実行する専用ハードウェアベースのシステム、又は専用ハードウェアとコンピュータ命令との組み合わせによって実装することができることにも留意されたい。本明細書において用いられる用語は、特定の実施形態を説明することのみを目的とするものであり、本発明を限定することを意図していない。本明細書で用いられる場合、単数形の1つのa、an及びそのtheは、文脈が明確に他の場合を指示していない限り、複数形をも含むことを意図している。含むcomprises及び/又は含んでいるcomprisingという用語は、本明細書において用いられる場合、述べられた特徴、整数、ステップ、動作、要素及び/又はコンポーネントの存在を特定するが、1つ又は複数の他の特徴、整数、ステップ、操作、要素、コンポーネント及び/又はそれらの群の存在又は付加を排除するものではないこともさらに理解されよう。下記の特許請求の範囲における全ての手段又はステップと機能との組合せミーンズ又はステッププラスファンクション要素の対応する構造、材料、動作及び均等物は、明確に特許請求される他の特許請求された要素と組み合わされてその機能を実施するためのいかなる構造、材料又は動作をも含むことを意図している。本発明の記載は、例示及び説明の目的で提示されたが、網羅的であることを意図するものでも、開示された形態の発明に限定することを意図するものでもない。当業者には、本発明の範囲及び真意から逸脱しない多くの修正及び変形が明らかであろう。実施形態は、本発明の原理及び実際の適用を最も良く説明し、且つ、当業者が企図される特定の使用に適した種々の修正を伴う種々の実施形態について本発明を理解できるように、選択され、説明された。"