(57)【要約】  ネットワーク（１０４）内の１又は２以上のソースからのレコードを処理する。複数の時間間隔で、１又は２以上のレコードのセットに対してマッチングプロシージャ（２００）が試行されるが、マッチングプロシージャ（２００）は、種々のレコードに関連する識別子を比較してセットを生成すること、及び、セットのうちの１又は２以上について完全性基準が満たされるかどうかを判定する（２１０）ことを含む。処理はまた、時間間隔のうちの少なくともいくつかで、時間間隔内に初めてマッチングプロシージャ（２００）が試行される受信されたレコードのうちの１又は２以上と、時間間隔の前にデータストア（１１０）に記憶された１又は２以上のレコードとからなる少なくとも１つの完全なセットを処理すること、及び、時間間隔のうちの少なくともいくつかで、時間間隔の前にデータストア（１１０）に記憶された１又は２以上のレコードからなる少なくとも１つの不完全なセットを処理することを含む。
2015528967.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内のノードにおいて受信されたデータを処理する方法であって、
前記ネットワーク内の１又は２以上のソースからレコードを受信するステップであって、前記レコードのうちの少なくともいくつかがそれぞれ識別子に関連するステップと、
複数の時間間隔で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行するステップであって、前記マッチングプロシージャが、種々のレコードに関連する識別子を比較して前記セットを生成することと、前記セットのうちの１又は２以上について完全性基準が満たされているか否かを判定することとを含み、前記１又は２以上のレコードの特定のセットに関する前記完全性基準が、前記特定のセット内の少なくともいくつかのレコードを集約した結果に少なくとも部分的に基づくステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされた少なくとも１つの完全なレコードセットを処理するステップであって、前記少なくとも１つの完全なレコードセットが、前記時間間隔内に初めて前記マッチングプロシージャが試行される前記受信されたレコードのうちの１又は２以上のレコードと、前記時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理するステップであって、前記少なくとも１つの不完全なレコードセットが、前記時間間隔の前に前記データストアに記憶された１又は２以上のレコードからなるステップ
とを含む方法。
【請求項２】
マッチングプロシージャの少なくともいくつかの試行の後で、前記試行中に完全性基準が満たされなかった少なくともいくつかの不完全なレコードセットをデータストアに記憶し、前記不完全なレコードセットに対応するキーを、前記データストアとは別のデータ構造に記憶するステップと、
後続の時間間隔内に、記憶されたキーを前記データ構造から取り出して、対応するレコードに対して前記マッチングプロシージャを試行するステップ
とをさらに含む、請求項１に記載の方法。
【請求項３】
記憶されたキーが、時間間隔とは非同期にデータ構造から取り出される、請求項２に記載の方法。
【請求項４】
時間間隔のうちの少なくともいくつかで、少なくとも１つの完全なレコードセットを処理し、前記処理された完全なレコードセットを処理済みとして識別する情報をデータストアに記憶するステップをさらに含む、請求項１に記載の方法。
【請求項５】
時間間隔のうちの少なくともいくつかで、少なくとも１つの不完全なレコードセットを処理し、前記処理された不完全なレコードセットを処理済みとして識別する情報をデータストアに記憶するステップをさらに含む、請求項１に記載の方法。
【請求項６】
不完全なレコードセットが、マッチングプロシージャの少なくとも２回の試行の後で、前記不完全なレコードセット内の少なくとも１つのレコードに関連する時間と満了基準との比較に応答して処理される、請求項１に記載の方法。
【請求項７】
満了基準が、不完全なレコードセットの不完全性の程度に依存する、請求項６に記載の方法。
【請求項８】
種々のレコードに関連する識別子を比較してセットを生成し、前記レコードセットのうちの１又は２以上について完全性基準が満たされるか否かを判定するステップが、
受信されたレコードに関連する個別識別子を決定するステップと、
個別識別子ごとに、前記個別識別子に関連する、データストアに記憶されているレコードを取り出し、前記受信されたレコードのうちの１又は２以上と、取り出されたレコードとを含む、前記識別子に関連するレコードのセットを集約するステップと、
集約されたレコードセットごとに、前記完全性基準が満たされるか否かを判定するステップ
とを含む、請求項２に記載の方法。
【請求項９】
個別識別子に関連する、データストアに記憶されているレコードを取り出すことが、前記データストアに関連する索引内で前記個別識別子をルックアップすることを含む、請求項８に記載の方法。
【請求項１０】
個別識別子に関連する、データストアに記憶されているレコードを取り出すことが、前記個別識別子に関連するレコードを含む前記データストアの一部分を圧縮解除することを含む、請求項９に記載の方法。
【請求項１１】
個別識別子に関連する、データストアに記憶されているレコードを取り出すことが、前記データストアの圧縮解除された部分を走査して、前記個別識別子に関連するいずれかのレコードを検索することを含む、請求項１０に記載の方法。
【請求項１２】
個別識別子に関連する、データストアに記憶されているレコードを取り出すことが、前記個別識別子に関連する記憶済みレコードセットが処理済みとして識別されているか否かを判定することを含む、請求項８に記載の方法。
【請求項１３】
個別識別子に関連する、データストアに記憶されているレコードを取り出すことが、前記個別識別子に基づいてハッシュ値を決定することを含む、請求項８に記載の方法。
【請求項１４】
ネットワーク内の１又は２以上のソースからレコードを受信するステップが、前記受信されたレコードを入力バッファに記憶することを含む、請求項２に記載の方法。
【請求項１５】
後続の時間間隔内に、記憶されたキーをデータ構造から取り出して、対応するレコードに対してマッチングプロシージャを試行することが、前記データ構造からキーを削除し、前記削除されたキー、又は前記削除されたキーに対応するレコードを、入力バッファに追加することを含む、請求項１４に記載の方法。
【請求項１６】
レコードセットに関連するキーが、前記レコードセットに関連する識別子を含む、請求項１に記載の方法。
【請求項１７】
時間間隔が、ノードにおけるクロックに基づいて決定される、請求項１に記載の方法。
【請求項１８】
時間間隔が、受信されたレコードの数に基づいて決定される、請求項１に記載の方法。
【請求項１９】
時間間隔のうちの１又は２以上がチェックポイント期間内に含まれ、前記チェックポイント期間では、前のチェックポイント期間以降に受信されたか又は生成された、マッチングプロシージャに関連するデータが、永続的に記憶される、請求項１に記載の方法。
【請求項２０】
データストアが、前記データストアに記憶されたレコードのランダムアクセスを可能にする、請求項１に記載の方法。
【請求項２１】
レコードセットを処理するステップが、前記セット内の前記レコード内の情報をネットワーク内の別のノードに送信することを含む、請求項１に記載の方法。
【請求項２２】
ネットワーク内のノードにおいて受信されたデータを処理するためのコンピュータプログラムを記憶するコンピュータ可読記憶媒体であって、
前記コンピュータプログラムが、
前記ネットワーク内の１又は２以上のソースからレコードを受信する機能であって、前記レコードのうちの少なくともいくつかがそれぞれ識別子に関連する機能と、
複数の時間間隔で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行する機能であって、前記マッチングプロシージャが、種々のレコードに関連する識別子を比較して前記セットを生成することと、前記セットのうちの１又は２以上について完全性基準が満たされているか否かを判定することとを含み、前記１又は２以上のレコードの特定のセットに関する前記完全性基準が、前記特定のセット内の少なくともいくつかのレコードを集約した結果に少なくとも部分的に基づく機能と、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされた少なくとも１つの完全なレコードセットを処理する機能であって、前記少なくとも１つの完全なレコードセットが、前記時間間隔内に初めて前記マッチングプロシージャが試行される前記受信されたレコードのうちの１又は２以上のレコードと、前記時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなる機能と、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理する機能であって、前記少なくとも１つの不完全なレコードセットが、前記時間間隔の前に前記データストアに記憶された１又は２以上のレコードからなる機能
とをコンピューティングシステムに実行させるための命令を含む、コンピュータ可読記憶媒体。
【請求項２３】
ネットワーク内の１又は２以上のソースからレコードを受信するように構成されたネットワークインタフェースであって、前記レコードのうちの少なくともいくつかがそれぞれ識別子に関連するものであるネットワークインタフェースと、
レコードのセットを処理するように構成された少なくとも１つのプロセッサとを含むネットワークノードであって、
前記処理が、
複数の時間間隔で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行するステップであって、前記マッチングプロシージャが、種々のレコードに関連する識別子を比較して前記セットを生成することと、前記セットのうちの１又は２以上について完全性基準が満たされているか否かを判定することとを含み、前記１又は２以上のレコードの特定のセットに関する前記完全性基準が、前記特定のセット内の少なくともいくつかのレコードを集約した結果に少なくとも部分的に基づくステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされた少なくとも１つの完全なレコードセットを処理するステップであって、前記少なくとも１つの完全なレコードセットが、前記時間間隔内に初めて前記マッチングプロシージャが試行される前記受信されたレコードのうちの１又は２以上のレコードと、前記時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理するステップであって、前記少なくとも１つの不完全なレコードセットが、前記時間間隔の前に前記データストアに記憶された１又は２以上のレコードからなるステップ
とを含む、ネットワークノード。
【請求項２４】
ネットワーク内の１又は２以上のソースからレコードを受信する手段であって、前記レコードのうちの少なくともいくつかがそれぞれ識別子に関連するものである、受信する手段と、レコードのセットを処理する手段とを含むネットワークノードであって、
前記処理が、
複数の時間間隔で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行するステップであって、前記マッチングプロシージャが、種々のレコードに関連する識別子を比較して前記セットを生成することと、前記セットのうちの１又は２以上について完全性基準が満たされているか否かを判定することとを含み、前記１又は２以上のレコードの特定のセットに関する前記完全性基準が、前記特定のセット内の少なくともいくつかのレコードを集約した結果に少なくとも部分的に基づくステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされた少なくとも１つの完全なレコードセットを処理するステップであって、前記少なくとも１つの完全なレコードセットが、前記時間間隔内に初めて前記マッチングプロシージャが試行される前記受信されたレコードのうちの１又は２以上のレコードと、前記時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるステップと、
前記時間間隔のうちの少なくともいくつかで、前記試行中に前記完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理するステップであって、前記少なくとも１つの不完全なレコードセットが、前記時間間隔の前に前記データストアに記憶された１又は２以上のレコードからなるステップ
とを含む、ネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、参照により本明細書に組み込まれる、２０１２年８月２日に出願された米国出願第１３／５６５，３２１号明細書に対する優先権を主張するものである。
【０００２】
本記述は、メディエーションシステムにおけるデータの集約に関する。
【背景技術】
【０００３】
いくつかのシステムでは、様々な種類のデータの集約が実行され、それにより、ネットワーク内の様々なソースから入手可能な全ての関連情報を、意思決定及びいくつかの機能の実行に使用できることが保証される。例えば、遠隔通信ネットワークでは、ネットワーク内のノード上で稼働する料金請求メディエーションプラットフォームが、他のノード（例えば、ルーティングノード又はゲートウェイノード）からのレコード（例えば、コール詳細レコード（ＣＤＲ，call detail records））を収集して、ダウンストリーム料金請求システムに向けた料金請求情報を決定する。収集されたレコードの処理は、同じコール（call）に関係する種々のレコードの集約を含む場合がある。集約されることになるいくつかのレコードは、同じノードによって異なる時点で生成されたものである場合がある（例えば、通話の開始及び終了に対応する開始ＣＤＲ及び停止ＣＤＲ）。集約されることになるいくつかのレコードは、異なるノード（例えば、開始及び停止ＣＤＲを提供するノードと、コール品質メトリックレコードを提供するノード）によって生成されたものである場合がある。
【発明の概要】
【課題を解決するための手段】
【０００４】
一態様では、一般に、ネットワーク内のノードにおいて受信されたデータを処理する方法は、ネットワーク内の１又は２以上のソースからレコードを受信することを含む。レコードのうちの少なくともいくつかは、それぞれ識別子に関連する。この方法はまた、複数の時間間隔の各々で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行することを含む。マッチングプロシージャは、種々のレコードに関連する識別子を比較してセットを生成すること、及び、セットのうちの１又は２以上について完全性基準が満たされるか否かを判定することを含む。この方法はまた、時間間隔のうちの少なくともいくつかで、試行中に完全性基準が満たされた少なくとも１つの完全なレコードセットを処理することであって、少なくとも１つの完全なレコードセットが、時間間隔内に初めてマッチングプロシージャが試行される受信されたレコードのうちの１又は２以上と、時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるものであること、及び、時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理することであって、少なくとも１つの不完全なレコードセットが、時間間隔の前にデータストアに記憶された１又は２以上のレコードからなるものである、ことを含む。
【０００５】
態様は、以下の特徴のうちの１又は２以上を含みうる。
【０００６】
この方法はさらに、マッチングプロシージャの少なくともいくつかの試行の後で、この試行中に完全性基準が満たされなかった少なくともいくつかの不完全なレコードセットをデータストアに記憶し、不完全なレコードセットに対応するキーを、データストアとは別のデータ構造に記憶すること、及び、後続の時間間隔内に、記憶されたキーをデータ構造から取り出して、対応するレコードに対してマッチングプロシージャを試行することを含む。
【０００７】
記憶されたキーは、時間間隔とは非同期にデータ構造から取り出される。
【０００８】
この方法はさらに、時間間隔のうちの少なくともいくつかで、少なくとも１つの完全なレコードセットを処理し、処理された完全なレコードセットを処理済みとして識別する情報をデータストアに記憶することを含む。
【０００９】
この方法はさらに、時間間隔のうちの少なくともいくつかで、少なくとも１つの不完全なレコードセットを処理し、処理された不完全なレコードセットを処理済みとして識別する情報をデータストアに記憶することを含む。
【００１０】
不完全なレコードセットは、マッチングプロシージャの少なくとも２回の試行の後で、不完全なレコードセット内の少なくとも１つのレコードに関連する時間と満了基準との比較に応答して処理される。
【００１１】
満了基準は、不完全なレコードセットの不完全性の程度に依存する。
【００１２】
種々のレコードに関連する識別子を比較してセットを生成し、レコードセットのうちの１又は２以上について完全性基準が満たされるか否かを判定することは、受信されたレコードに関連する個別識別子を決定すること、個別識別子ごとに、この個別識別子に関連する、データストアに記憶されているレコードを取り出し、受信されたレコードのうちの１又は２以上と、いずれかの取り出されたレコードとを含む、この識別子に関連するレコードのセットを集約すること、及び、集約されたレコードセットごとに、完全性基準が満たされるか否かを判定することを含む。
【００１３】
この個別識別子に関連する、データストアに記憶されているレコードを取り出すことは、データストアに関連する索引内で個別識別子をルックアップすることを含む。
【００１４】
この個別識別子に関連する、データストアに記憶されているレコードを取り出すことは、個別識別子に関連するいずれかのレコードを含むデータストアの一部分を圧縮解除することを含む。
【００１５】
この個別識別子に関連する、データストアに記憶されているレコードを取り出すことは、データストアの圧縮解除された部分を走査して、個別識別子に関連するいずれかのレコードを検索することを含む。
【００１６】
この個別識別子に関連する、データストアに記憶されているレコードを取り出すことは、この個別識別子に関連する記憶済みレコードセットが、処理済みとして識別されているか否かを判定することを含む。
【００１７】
この個別識別子に関連する、データストアに記憶されているレコードを取り出すことは、個別識別子に基づいてハッシュ値を決定することを含む。
【００１８】
ネットワーク内の１又は２以上のソースからレコードを受信することは、受信されたレコードを入力バッファに記憶することを含む。
【００１９】
後続の時間間隔内に、記憶されたキーをデータ構造から取り出して、対応するレコードに対してマッチングプロシージャを試行することが、データ構造からキーを削除し、削除されたキー、又は削除されたキーに対応するレコードを、入力バッファに追加することを含む。
【００２０】
レコードセットに関連するキーは、レコードセットに関連する識別子を含む。
【００２１】
時間間隔は、ノードにおけるクロックに基づいて決定される。
【００２２】
時間間隔は、受信されたレコードの数に基づいて決定される。
【００２３】
時間間隔のうちの１又は２以上はチェックポイント期間内に含まれ、チェックポイント期間では、前のチェックポイント期間以降に受信されたか又は生成された、マッチングプロシージャに関連するデータが、永続的に記憶される。
【００２４】
データストアは、データストアに記憶されたレコードのランダムアクセスを可能にする。
【００２５】
レコードセットを処理することは、セット内のレコード内の情報をネットワーク内の別のノードに送信することを含む。
【００２６】
別の態様では、一般に、コンピュータ可読記憶媒体は、ネットワーク内のノードにおいて受信されたデータを処理するためのコンピュータプログラムを記憶する。このコンピュータプログラムは、ネットワーク内の１又は２以上のソースからレコードを受信することであって、レコードのうちの少なくともいくつかがそれぞれ識別子に関連するものである、受信すること；複数の時間間隔の各々で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行することであって、マッチングプロシージャが、種々のレコードに関連する識別子を比較してセットを生成することと、セットのうちの１又は２以上について完全性基準が満たされるか否かを判定することとを含むものである、試行すること；時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされた少なくとも１つの完全なレコードセットを処理することであって、少なくとも１つの完全なレコードセットが、時間間隔内に初めてマッチングプロシージャが試行される受信されたレコードのうちの１又は２以上と、時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるものである、処理すること；及び、時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理することであって、少なくとも１つの不完全なレコードセットが、時間間隔の前にデータストアに記憶された１又は２以上のレコードからなる、コンピューティングシステムに行わせるための命令を含む。
【００２７】
別の態様では、一般に、ネットワークノードは、ネットワーク内の１又は２以上のソースからレコードを受信するように構成されたネットワークインタフェースであって、レコードのうちの少なくともいくつかがそれぞれ識別子に関連するものであるネットワークインタフェースと、レコードのセットを処理するように構成された少なくとも１つのプロセッサとを含む。処理は、複数の時間間隔の各々で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行することであって、マッチングプロシージャが、種々のレコードに関連する識別子を比較してセットを生成することと、セットのうちの１又は２以上について完全性基準が満たされるか否かを判定することとを含むものである、試行すること；時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされた少なくとも１つの完全なレコードセットを処理することであって、少なくとも１つの完全なレコードセットが、時間間隔中に初めてマッチングプロシージャが試行される受信されたレコードのうちの１又は２以上と、時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるものである、処理すること；及び、時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理することであって、少なくとも１つの不完全なレコードセットが、時間間隔の前にデータストアに記憶された１又は２以上のレコードからなる、ことを含む。
【００２８】
別の態様では、一般に、ネットワークノードは、ネットワーク内の１又は２以上のソースからレコードを受信する手段であって、レコードのうちの少なくともいくつかがそれぞれ識別子に関連するものである、受信する手段と、レコードのセットを処理する手段とを含む。処理は、複数の時間間隔の各々で、１又は２以上のレコードのセットに対してマッチングプロシージャを試行することであって、マッチングプロシージャが、種々のレコードに関連する識別子を比較してセットを生成することと、セットのうちの１又は２以上について完全性基準が満たされるか否かを判定することとを含むものである、試行すること；時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされた少なくとも１つの完全なレコードセットを処理することであって、少なくとも１つの完全なレコードセットが、時間間隔内に初めてマッチングプロシージャが試行された受信されたレコードのうちの１又は２以上と、時間間隔の前にデータストアに記憶された１又は２以上のレコードとからなるものである、処理すること；及び、時間間隔のうちの少なくともいくつかで、この試行中に完全性基準が満たされなかった少なくとも１つの不完全なレコードセットを処理することであって、少なくとも１つの不完全なレコードセットが、時間間隔の前にデータストアに記憶された１又は２以上のレコードからなる、ことを含む。
【００２９】
態様は、以下の利点のうちの１又は２以上を含みうる。
【００３０】
本明細書に述べる技法は、ネットワーク内の１又は２以上のアップストリームノードからネットワーク内のノードに到着したデータの効率的な集約を可能にする。データは、例えば、ダウンストリームシステムに送達されることになる情報を含有するレコードの複数のストリームを含む場合がある。マッチングプロシージャは、あるストリームのレコードを別のストリームのレコードと集約すること、又は、異なる時点で到着する、同じストリームの複数のレコードを集約することができる。何らかの完全性基準に従って、完全なレコードセットを処理することができる（例えば、レコード自体、又はレコードに関連する情報が、ダウンストリームシステムに送達される）。種々の基準間のトレードオフを提供するように、情報をダウンストリームシステムに送達することが望ましいであろう。例えば、いくつかの実施形態では、情報は低レイテンシで送達されるべきであり、送達される情報はできるだけ完全であるべきである。情報ができるだけ完全であるために、マッチングプロシージャは、いくつかのレコードを後で到着する他のレコードと集約できるまで、このいくつかのレコードの送達を遅延させるべきである。しかし、レイテンシ基準を満たすために、いくつかの予期されるレコードからの情報が欠損している不完全な情報が、いくらかの制限時間の後で送達されることが必要な場合も依然としてある。
【００３１】
不完全なレコードセットを記憶するデータストア、及び、不完全なレコードセットに対するキーを記憶するデータ構造は、マッチングプロシージャを繰り返して完全性基準が後で満たされるかどうかを判定するための効率的な技法を可能にする。後で特定の不完全なセットをマッチさせようとする試行は、キーの非同期取出しに基づくので、あらゆる試行中にデータストア全体を走査する必要はなく、これにより各試行のレイテンシが短縮される。また、データストア内の不完全なセットを更新することは、テーブルに対する計算的に高価な多数のデータベース操作（例えば、挿入、更新、ルックアップ、削除操作）、又は、ロッキング、フォーマットバージョニング、若しくはメタデータアクティビティなどいくつかのデータベーストランザクションに関連するオーバヘッドを必ずしも必要としないので、レイテンシはやはり低く維持することができる。例えば、更新されたレコードセットがデータストアのファイルに付加されてよく、更新時に古いバージョンが削除される必要なしに、索引が更新されて、レコードセットのこの一番最近に更新されたバージョンの位置が示される。
【００３２】
データストアの構造及びデータ構造（「保留キュー」と呼ばれる）は、サイズ及びアクセス速度需要に基づいて最適化することができる。データストアに記憶される不完全なレコードセットは、大容量記憶デバイス（例えば不揮発性ストレージ）内の比較的大量の記憶空間を必要とする場合がある。不完全なセット内のレコードの内容全体が保留キューに追加される必要があるのではなく、不完全なセットを識別するキーを含めて、おそらくははるかに少量である情報が、保留キューに追加される。後で不完全なセットの内容がデータストア内で更新された場合は、保留キュー内の同じキーを依然として使用して、更新されたバージョンを処理することができる。いくつかの場合では、保留キューは、比較的高速なメモリ（例えば揮発性メモリ）に十分収まるほど小さい。保留キューにより、妥当な時間量内に予期されるレコードと一致しない１又は２以上のレコードのセットは、満了基準（セットの完全性又は不完全性に依存する場合がある）に基づいて「時間切れ」になりうることが保証される。キーは、マッチングプロシージャ試行とは非同期に、及び／又はより低い頻度で、保留キューから取り出されてよい。キーが保留キューから取り出される頻度は、レイテンシと完全性との間の望まれるトレードオフに基づいて調整することができる。
【００３３】
本発明の他の特徴及び利点は、後続の記述及び特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００３４】
【図１】メディエーションシステムのブロック図である。
【図２】マッチングプロシージャの例のフローチャートである。
【発明を実施するための形態】
【００３５】
図１に、集約技法をその中で使用できるメディエーションシステム１００の例を示す。システム１００は、ネットワーク１０４に接続されたノード１０２Ａを含む。ノード１０２Ａはネットワークインタフェース１０６を備え、このネットワークインタフェース１０６を介して、ノード１０２Ａはネットワーク１０４内の他のノード１０２Ｂ〜１０２Ｄと通信する。ノード１０２Ａはまた、ノード１０２Ａがネットワークからのデータを集約し、処理済み結果データを提供する実行環境も提供し、このデータは、次いで、ノード１０２Ａと通信するダウンストリームシステムに送信されうる、又は、ノード１０２Ａにおける後続のアクションを開始するのに使用されうる。実行環境は、ＵＮＩＸオペレーティングシステムなどの適切なオペレーティングシステムの制御下で、１又は２以上の汎用コンピュータ上でホストされてよい。例えば、実行環境は、複数の中央処理装置（ＣＰＵ，central processing units）を使用するコンピュータシステムの構成を含む並列コンピューティング環境を含んでよく、これらのＣＰＵは、ローカルの（例えば、ＳＭＰコンピュータなどのマルチプロセッサシステム）又はローカルに分散された（例えば、クラスタ若しくはＭＰＰとして接続された複数のプロセッサ）ものであるか、或いは、リモートの、又はリモートに分散された（例えば、ローカルエリアネットワーク（ＬＡＮ，local area network）及び／若しくはワイドエリアネットワーク（ＷＡＮ，wide-area network）を介して接続された複数のプロセッサ）ものであるか、或いは、これらのいずれかの組合せである。
【００３６】
ノード１０２Ａは、ネットワーク内の１又は２以上のソース（例えば、他のノード）からの入来データ（incoming data）を受信する入力バッファ１０６を含む。入来データは、個々のレコードを含むことがある。種々のタイプのレコードが、対応するストリーム若しくはフィードから受信される可能性があり、又は、レコードは、単一のストリーム若しくはフィードから受信される可能性がある。入力バッファ１０６は、メモリ（例えば、揮発性メモリ）に記憶されたキューなどファイル若しくはデータ構造、又は名前付きパイプ若しくはソケットなどプロセス間通信メカニズムを含めた、様々なデータ記憶技法のうちのいずれかを使用することができる。例えば、入力バッファ１０６は、１又は２以上の入力キューを含んでよく、異なるタイプのレコードがそれぞれの異なるキューに追加されるように、又はこれらのレコードが単一のキューに追加されるように編成されてよい。レコードは、受信された後で、又は入力バッファ１０６から読み取られた後で、処理（例えば、再フォーマット）されてよい。処理は、レコードにタイムスタンプを追加することを含んでよく、タイムスタンプは、後でより詳細に述べる満了基準をテストするのに使用することができる。レコードはまた、エラー又は欠損データを検出するために検証されてよい（例えば、マッチングに使用されることになる識別子を含有するフィールドが存在し、空でないことを検証する）。
【００３７】
いくつかの実施形態では、受信されたレコードは、それぞれの時間間隔内に受信されたレコードに対応する作業単位に分割される。期間は、例えば、所定のレコード数で、又は、ノード１０２Ａにおけるクロックに基づく所定の時間量（例えば、２分ごと）で、構成可能とすることができる。レコードのフローを作業単位に分割する技法の１つは、参照により本明細書に組み込まれる「Continuous Flow Compute Pont Based Data Processing」という名称の米国特許第６，６５４，９０７号明細書に記載されている。各時間間隔で、又は所定の複数の時間間隔の後で、他の様々なアクティビティが実行されてもよい。例えば、チェックポイント期間が指定されてよく、このチェックポイント期間では、前のチェックポイント期間以降に受信されたか又は生成された、メディエーションアクティビティに関連するデータが、（例えば、障害があった場合の回復のために）永続的に記憶される。
【００３８】
アグリゲータ１０８が、入力バッファ１０６からレコードを受け取り、作業単位中のレコードに対してマッチングプロシージャを試行する。アグリゲータ１０８は、種々のレコードに関連する識別子を比較して、特定のイベント（例えば、通話）に関連するレコードのセットを集める。例えば、いくつかの場合では、識別子はグローバルコールＩＤであり、このグローバルコールＩＤは、レコード内に含まれるか、又は、特定のグローバルコールＩＤにマッピングされうるレコード内の他の情報に基づいてレコードに割り当てられてよい。アグリゲータ１０８は、作業単位中のレコードの識別子を相互に比較して一致を見つけ、前にデータストア１１０に記憶された、作業単位中のレコードのいずれかと同じ識別子を有するレコードがあるかどうかを判定する。データストア１１０は、不揮発性記憶デバイス内の永続的ストレージを提供するが、後でより詳細に述べるように、このストレージには、索引１１２を使用してアクセスすることができる。索引１１２又は他のルックアップ技法（例えば、ハッシュベースのルックアップ）の使用により、アグリゲータ１０８は、マッチングプロシージャを試行する度にデータストア１１０全体を走査する必要なしに、特定の識別子を検索することができる（すなわち、ランダムアクセス）。作業単位中のレコード内で表される個別識別子ごとに、アグリゲータ１０８は、この識別子に関連するレコードのセットについて完全性基準が満たされるか否かを判定する。集約されたセットが特定の完全性基準を満たした後で、又はいくらかの時間量の後で（満了基準に従って）、ノード１０２Ａは、集約されたセットを処理し、例えば集約されたレコードセットをダウンストリームシステムに送信することによって、処理済み結果データを提供する。ノード１０２Ａはまた、集約されたセットの識別子に関連するいかなる記憶済みレコードも処理済みとして識別する情報を、データストア１１０に記憶する。
【００３９】
マッチングプロシージャの試行中に完全性基準が満たされなかった１又は２以上のレコードの不完全なセットがある場合、ノード１０２Ａは、不完全なセット（又は不完全なセット内のレコードに含有される情報）を、関連する識別子に従って索引付けされた状態でデータストア１１０に記憶する。ノード１０２Ａはまた、不完全なレコードセットに対応するキー（鍵）を、データストア１１０とは別の保留キュー１１４（例えば、先入れ先出し（ＦＩＦＯ）キュー）に記憶する。キーは、不完全なセットを一意に識別する。保留キュー１１４内のエントリは「キーレコード」と呼ばれるが、このエントリは、単純にキー自体であってもよく、又は、キー及び少量の他の関連情報を含むコンパクトなレコードであってもよい。いくつかの実施形態では、キーは、レコードのセットを集約するのに使用された識別子と同じであるか、又は、識別子との１対１対応を有する。いくつかの実施形態では、ＦＩＦＯキューが使用される代わりに、キーレコード内の情報は、データストア１１０と同じ記憶媒体（例えば、ハードドライブ）又は同じ記憶システム（例えば、データベース）に記憶されたデータ構造に記録され、データ構造内のエントリ（例えば、索引エントリ）は、各レコード又は各レコードセットのステータスを示す。
【００４０】
完全性基準の例は、次のとおりである。この例では、レコードのソースは、ネットワーク内の様々なノードを含む。ゲートウェイノードは、通話の開始に関連する開始ＣＤＲと、通話の終了に関連する停止ＣＤＲとを含むＣＤＲのストリームを送信する。ルーティングノードもまた、同じ通話に関連する開始ＣＤＲと停止ＣＤＲとを含むストリームを送信する。品質モニタリングノードは、同じ通話に関連するコール品質メトリックレコードのストリームを送信する。完全性基準は、１対の開始及び停止ルーティングＣＤＲと、１対の開始及び停止ゲートウェイＣＤＲと、コール品質メトリックレコードとを含むものとして、特定のコールに関するレコードの完全なセットを指定する。これらのレコードの各々は、特定の通話に対応する同じ識別子に関連する。ノードから送信された、完全性基準の一部でない他のレコードがある場合もある（例えば、接続が完了しなかった試みられた通話に関連する試行ＣＤＲ）。このようなレコードは、潜在的なマッチングのために遅延されることなく、ダウンストリームシステムに送信されてよい。
【００４１】
不一致レコードマネージャ１１６は、記憶されたキーレコードを取り出すこと、それらを保留キュー１１４から削除すること、及びそれらを入力バッファ１０６に追加することを管理し、それにより、アグリゲータ１０８は、データストア１１０内の対応するレコードに対して、同じ作業単位中で受信された他のレコードと共に、マッチングプロシージャを試行することができる。予期される欠損レコードが到着したときに、不完全なレコードセットに対してマッチングプロシージャが既に試行されていることになるのは事実だが、不一致レコードマネージャ１１６によって管理されるこの取出しプロセスにより、不完全なセットを満了基準に対して繰返しテストすることができる。例えば、満了基準は、第１の所定の制限時間（例えば、１０分）後に、不完全なセットが開始ＣＤＲと停止ＣＤＲの両方の一致する対を含んでおり、コール品質メトリックレコードのみを欠いている限り、この不完全なレコードセットがダウンストリームシステムに送信されてデータストア１１０内で処理済みとして示されてよい、と指定することができる。満了基準はまた、第２の所定の制限時間（例えば、３０分）後に、どんな予期されるレコードが欠損しているかにかかわらず、不完全なレコードセットがダウンストリームシステムに送信されてデータストア１１０内で処理済みとして示されてよい、と指定することができる。したがって、この例では、満了基準は、不完全なレコードセットの不完全性の程度に依存する。不一致レコードマネージャ１１６は、不完全なレコードセットをこれらの制限時間と比較するとき、現在時刻（例えば、ローカルクロックに基づく）に対して、セット内の第１のレコードが入力バッファ１０６から読み取られた時刻（例えば、レコード内のタイムスタンプに基づく）を使用することができる。不完全なセットがすでに送信された後で予期されるレコードが受信された場合、予期されるレコードは廃棄されてよく、又は、後期更新として何らかの方法でダウンストリームシステムに送信されてよい。
【００４２】
キーレコードを保留キュー１１４から取り出す頻度を、作業単位を定義する時間間隔の頻度から独立して調整することによって、レイテンシと完全性との間の望まれるトレードオフを達成することができる。アグリゲータ１０８と不一致レコードマネージャ１１６は、例えば、独立して動作する２つの別々のプロセスによって制御されてよい。いくつかの場合では、不完全なレコードセットを処理する際の比較的長い遅延が許容可能であってよく、この場合、不一致レコードマネージャ１１６は、作業単位を定義する時間間隔に比べて相対的に低い頻度で（例えば、１００作業単位ごとに）、又は、時間間隔に同期しない特定の頻度で（例えば、１０分ごとに）、キーレコードを取り出すことができる。保留キュー１１４から一度に取り出されるキーレコードの数もまた、単一の（最も早く記憶された）キーレコードから、全ての記憶済みキーレコードまでの間で調整することができる。いくつかの実施形態では、保留キュー１１４から取り出された重複するキーレコードがあれば、それらは識別されて削除される。全てよりも少ないキーレコードが取り出された場合、保留キュー１１４から削除されたキーレコードのインスタンスが１つある可能性があり、このキーレコードの別のインスタンスはまだ保留キュー１１４に残っている可能性がある。このような場合、キーレコードの両方のインスタンスがアグリゲータ１０８によってチェックされてよい（異なるそれぞれの時間間隔に）。第１のキーレコードの結果として、対応するレコードセットが（例えば、満了基準が満たされたことから）ダウンストリームに送信された場合は、このセットは、マッチングプロシージャが第２のキーレコードに対して試行されたときにデータストア１１０内で処理済みとして示されることになる。
【００４３】
図２に、アグリゲータ１０８によって実行されるマッチングプロシージャ２００の例のフローチャートを示す。アグリゲータ１０８は、直近の時間間隔に受信された、入力バッファ１０６からのレコード（現在の作業単位）をソートする（２０２）。レコードは、マッチングプロシージャ２００に使用されることになる識別子でソートされる。アグリゲータ１０８は、個別識別子ごとに１つの集約されたレコードセットがあるように、ソートされたレコードを集約する（２０４）ことによって、受信されたレコードに関連する個別識別子を決定する。同じ個別識別子を共有するレコードの集約されたセットを結合して、単一のレコード（例えば、他のレコードのベクトルを含むレコード、又は、複数のレコードからの情報を保持する別のタイプのデータ構造）にすることができる。入力バッファ１０６からのレコードのいくつかは、不一致レコードマネージャ１１６によって追加されたキーレコードである場合がある（及び、いくつかの場合では、作業単位中の新たに受信されたフルレコードとは異なるフォーマットを有するものとしてフラグがセットされている場合がある）。これらのキーレコードは、フルレコードと共にソート及び集約されて、マッチングプロシージャ２００の次段階で使用されることになる個別識別子が見つけられる。いくつかの実施形態では、ソート２０２及び集約２０４は、インメモリハッシング技法において共に実行される。
【００４４】
直近の作業単位のレコード内で見つかった個別識別子ごとに、アグリゲータ１０８は、識別子を索引１１２内でルックアップして、この識別子で索引付けされたレコードがデータストア１１０に記憶されていれば取り出すことによって、データストア１１０のクエリ（照会）２０６を実行する。同じ識別子を有し、すでに処理済みとして示されていない記憶済みレコードのセットがあれば、アグリゲータ１０８は、それらを取り出し、この識別子に対応する受信されたレコードの集約されたセットと結合する（２０８）。また、他の例では、ソート２０２及び集約２０４をデータストア１１０のクエリ２０６の後で実行することもできるが、同じ識別子を有するレコードが近い時点で到着するような入来データストリームの場合、この例は、データストア１１０に対して実行されるクエリの回数を削減することによって、性能を向上させることができる。
【００４５】
アグリゲータ１０８は、集約／結合されたレコードセットごとに、このレコードセットについて完全性基準が満たされるか否かを判定する（２１０）ことによって、マッチングプロシージャ２００の試行が成功したかどうかを判定する。完全性基準が満たされる場合は、アグリゲータ１０８は、この完全なレコードセットを処理し（２１２）、このレコードセットを処理済みとして示すようにデータストア１１０を更新する。このレコードセットについて完全性基準が満たされない場合は、アグリゲータ１０８は、満了基準をチェックする（２１４）。不完全なレコードセットが満了している場合は、アグリゲータ１０８は、このレコードセットを処理し（２１６）、このレコードセットを処理済みとして示すようにデータストア１１０を更新する。不完全なレコードセットが満了していない場合は、アグリゲータ１０８は、不完全なレコードセットに対するキーレコードを保留キュー１１４に追加し（２１８）、必要なら、不完全なレコードセットの初期の又は更新済みバージョンを、識別子（キーと同一であるか又はキーに基づいて一意に決定されたものであってよい）で索引付けされた状態で、データストア１１０に記憶する（２２０）。データストア１１０のいくつかの実施形態では、同じ不完全なレコードセットのいかなる古いバージョンも削除する必要はない。というのは、索引１１２がチェックされるとき、直近のバージョンがアクセスされることになるからである。いくつかの実施形態では、アグリゲータ１０８はまた、完全な又は満了したレコードセットの初期の又は更新済みバージョンをデータストア１１０に記憶し（２２０）、それにより、処理されたレコードセットの最新の履歴レコードがあるようにする。いくつかの実施形態では、満了基準はなく、アグリゲータ１０８は、完全性基準が満たされないいかなるレコードセットに対しても、キーレコードを保留キュー１１４に追加する（２１８）。
【００４６】
データストア１１０は、索引を使用して効率的にアクセスできる位置にデータを素早く書き込むための様々な技法のいずれかを使用して実現されてよい。例えば、レコードは、特定の識別子を有するこれらのレコードが書き込まれた位置へのポインタを記憶する索引と共に、ファイルに順に書き込まれてよい。高速更新を可能にするために、不完全なレコードセットの新しいバージョンが、古いバージョンをすぐに削除する必要なしに、ファイルの最後に付加されてよい。データストア１１０のサイズを管理するために、複数のファイルが書き込まれてよく、既に処理されたレコードのみを記憶する古いファイルは、いくらかの制限時間（例えば１時間又は１日）後に削除されてよい。データストア１１０はまた、圧縮を使用して、使用される空間の量を削減することができる。古いファイルを削除することによってまた、矛盾を有することなく識別子を再利用できることが保証される。これらのプロパティを有する技法の一例は、参照により本明細書に組み込まれる米国特許第７，８８５，９３２号明細書に記載の複合圧縮レコードファイルである。複合圧縮レコードファイル内の各圧縮レコードファイルは、複数の圧縮ブロックを含み、各ブロックは、特定の範囲に入る識別子を有するレコードを記憶する。各ブロックの位置は索引付けされ、特定の識別子を有するレコードのセットが取り出されつつあるときは、単一のブロックのみが圧縮解除されればよく、限られた数のレコードのみが検索されればよい。また、複数のレコードを共に圧縮することで、個々のレコードを圧縮する場合よりも高い圧縮率がもたらされる。
【００４７】
いくつかの実施形態では、いくつかのレコードは、サイズ又は保留キュー１１４へのアクセスの効率に大きく影響することなしに、データストア１１０ではなく保留キュー１１４に記憶されてよい。例えば、別のレコードと集約されるまでは特定の識別子に関連付けられることのできない、いくつかのレコードがある場合がある。このような場合、フルレコードが保留キュー１１４に追加されてよく、データストア１１０には追加されなくてよい。フルレコードが集約されて識別子を割り当てられた後、次いでフルレコードは、その集約セットが完成され処理されるまで、データストア１１０に記憶される必要がありうる。この最初の集約が短い時間枠内で行われる場合、フルレコードが保留キュー１１４内に非常に長く留まる可能性は低い。
【００４８】
いくつかの実施形態では、複数のアグリゲータ１０８をカスケード接続して、種々のタイプの識別子を使用して種々のマッチングプロセスを入来レコードに対して実行することができる。各アグリゲータは、それ自体のデータストア１１０及びそれ自体の保留キュー１１４を使用することができ、又は、２つのアグリゲータに対する識別子及びキーを区別できる限り、単一のデータストア１１０及び保留キュー１１４を共有することができる。例えば、データストア１１０は、レコードの種々のフィールドからくる複数のタイプの識別子について索引付けされてよく、いずれのタイプの識別子も索引１１２内でルックアップすることができ、それによりデータストア１１０内でレコードのセットを検索することができる。
【００４９】
前述の集約手法は、コンピュータ上で実行されるためのソフトウェアを使用して実現されてよい。例えば、ソフトウェアは、１又は２以上のプログラム済み又はプログラム可能コンピュータシステム（分散型、クライアント／サーバ、又はグリッドなど、様々なアーキテクチャのものであってよい）上で実行される１又は２以上のコンピュータプログラム内のプロシージャを形成し、各コンピュータシステムは、少なくとも１つのプロセッサと、少なくとも１つのデータ記憶システム（揮発性及び不揮発性のメモリ及び／又は記憶要素を含む）と、少なくとも１つの入力デバイス又はポートと、少なくとも１つの出力デバイス又はポートとを含む。ソフトウェアは、データフローグラフの設計及び構成に関係する他のサービスを例えば提供するより大きいプログラムの、１又は２以上のモジュールを形成することができる。グラフのノード及び要素は、コンピュータ可読媒体に記憶されたデータ構造として、又は、データリポジトリに記憶されたデータモデルに準拠する他の組織化されたデータとして実現されてよい。
【００５０】
ソフトウェアは、ＣＤ−ＲＯＭなど、汎用又は専用のプログラム可能コンピュータによって読取り可能な記憶媒体上で提供されてよく、又は、ネットワークの通信媒体を介してコンピュータの記憶媒体に送達（伝搬シグナル中で符号化）されて、このコンピュータで実行されてよい。全ての機能は、専用コンピュータ上で、又はコプロセッサなどの専用ハードウェアを使用して実行されてよい。ソフトウェアは分散方式で実現されてもよく、この場合、ソフトウェアによって指定される異なる計算部分が、異なるコンピュータによって実行される。このような各コンピュータプログラムは、好ましくは、汎用又は専用のプログラム可能コンピュータによって読取り可能な記憶媒体或いはデバイス（例えば、固体メモリ若しくは媒体、又は磁気若しくは光学媒体）に記憶されるかダウンロードされ、それにより、記憶媒体又はデバイスがコンピュータシステムによって読み取られたとき、本明細書に記載のプロシージャを実行するようにコンピュータが構成及び操作される。本発明のシステムはまた、コンピュータプログラムで構成されたコンピュータ可読記憶媒体として実現されると考えることもでき、この場合、このように構成された記憶媒体は、コンピュータシステムを、本明細書に記載の機能を実行するように特定の及び事前定義済みの方式で動作させる。
【００５１】
本発明のいくつかの実施形態について述べた。しかし、本発明の主旨及び範囲を逸脱することなく様々な修正を加えることができることが理解されるであろう。例えば、前述のステップのいくつかは、順序に依存しないものとすることができ、したがって、述べた順序とは異なる順序で実行されてもよい。
【００５２】
以上の記述は、本発明を例示するものとし、本発明の範囲を限定するものとはしないことを理解されたい。本発明の範囲は、添付の特許請求の範囲によって定義される。例えば、前述の機能ステップのいくつかは、全体的な処理に実質的に影響を及ぼすことなく、異なる順序で実行されてもよい。他の実施形態は、後続の特許請求の範囲内である。
【図１】
2015528967.tif 000003
【図２】
2015528967.tif 000004
【国際調査報告】
2015528967.tif 000005
2015528967.tif 000006