(57)【要約】【課題】タスク結果を計算するための技法を提供する。【解決手段】レコードの処理データ集合を生成し、このレコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、実際のサブタスク集合によって共有されるデータに対する参照を含み、レコードの数が、実際のサブタスク集合内の実際のサブタスクの数に相当する。マッパー集合における各マッパーによって、処理データ集合のレコードの１つを受信し、レコードの受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させる。単一のリデューサーによって、マッパー集合内の各マッパーからの出力を集約してタスク結果を決定する。【選択図】図１
2016507093.tif 000002
【特許請求の範囲】
【請求項１】
レコードの処理データ集合を生成することであって、前記レコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、前記実際のサブタスク集合によって共有されるデータに対する参照を含み、前記レコードの数が、前記実際のサブタスク集合内の前記実際のサブタスクの数に相当する、ことと、
マッパー集合における各マッパーによって、前記処理データ集合の前記レコードの１つを受信することと、
前記レコードの前記受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させることと、
単一のリデューサーによって、前記マッパー集合内の各マッパーからの前記出力を集約してタスク結果を決定することと、
を含むコンピュータ・システムによって実行される方法。
【請求項２】
元のデータセットの少なくとも１つの特徴に基づいて、潜在的サブタスクの最大数を計算することと、
前記実際のサブタスクの実行に利用可能な前記マッパー集合内のマッパー数と前記潜在的サブタスクの最大数とに基づいて、実行される前記実際のタスク集合内の実際のサブタスク数を計算することと、
を更に含む、請求項１に記載の方法。
【請求項３】
Ｍ個の実際のサブタスクとして示される前記実際のサブタスク数を計算することを更に含み、Ｍ＝２ｍであり、Ｍ≦Ｌおよびｍ＜ｋ−ｌであり、Ｌは、前記実際のサブタスクの計算に利用可能な前記マッパー集合内の前記マッパー数であり、ｋは予測子の数である、請求項２に記載の方法。
【請求項４】
前記予測子を、先行インデックス予測子と共通インデックス予測子とに分割することを更に含む、請求項３に記載の方法。
【請求項５】
グローバル検索シーケンスをＭ個の多数のローカル検索シーケンスに分割することと、
前記ローカル検索シーケンスの各々について、前記先行インデックス予測子から先行インデックス・シーケンスを識別することと、
Ｍ個のレコードを用いて一時入力ファイルを生成することと、を更に含み、前記レコードの各々が先行インデックス・シーケンスを含み、前記レコードの各々が、共通インデックス予測子およびスイープ動作を適用する行列に対する参照を含む、請求項４に記載の方法。
【請求項６】
前記マッパー集合内の各マッパーにおいて、
前記ローカル検索シーケンスの１つの先行インデックス・シーケンスを受信することと、
処理データ集合の各レコードにおける前記参照を介して共通インデックス予測子および前記行列を受信することと、
前記共通インデックス予測子を用いて共通インデックス・シーケンスを発生させることと、
前記先行インデックス・シーケンスに従って前記行列にスイープ動作を実行することと、
前記共通インデックス・シーケンスに従って、結果として得られた前記行列にスイープ動作を実行することと、
前記出力を識別することと、を更に含み、前記出力がローカル回帰モデルである、請求項５に記載の方法。
【請求項７】
前記共通インデックス・シーケンスを送信することなく、前記先行インデックス・シーケンスを前記マッパー集合内の各マッパーに送信することが、ネットワーク・トラフィックを軽減する、請求項６に記載の方法。
【請求項８】
前記タスク結果がグローバル回帰モデルである、請求項６に記載の方法。
【請求項９】
クラウド環境におけるサービスとしてソフトウェアが提供される、請求項１に記載の方法。
【請求項１０】
具現化されたコンピュータ読み取り可能プログラム・コードを有するコンピュータ読み取り可能記憶媒体であって、前記コンピュータ読み取り可能プログラム・コードが、コンピュータの少なくとも１つのプロセッサによって実行された場合、
レコードの処理データ集合を生成することであって、前記レコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、前記実際のサブタスク集合によって共有されるデータに対する参照を含み、前記レコードの数が、前記実際のサブタスク集合内の前記実際のサブタスクの数に相当する、ことと、
マッパー集合における各マッパーによって、前記処理データ集合の前記レコードの１つを受信することと、
前記レコードの前記受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させることと、単一のリデューサーによって、前記マッパー集合内の各マッパーからの前記出力を集約してタスク結果を決定することと、を実行するように構成されている、コンピュータ読み取り可能記憶媒体、
を含む、コンピュータ・プログラム。
【請求項１１】
前記コンピュータ読み取り可能プログラム・コードが、前記コンピュータの前記少なくとも１つのプロセッサによって実行された場合、
元のデータセットの少なくとも１つの特徴に基づいて、潜在的サブタスクの最大数を計算することと、
前記実際のサブタスクの実行に利用可能な前記マッパー集合内のマッパー数と前記潜在的サブタスクの最大数とに基づいて、実行される前記実際のタスク集合内の実際のサブタスク数を計算することと、
を実行するように構成されている、請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
前記コンピュータ読み取り可能プログラム・コードが、前記コンピュータの前記少なくとも１つのプロセッサによって実行された場合、
Ｍ個の実際のサブタスクとして示される前記実際のサブタスク数を計算することを実行するように構成され、Ｍ＝２ｍであり、Ｍ≦Ｌおよびｍ＜ｋ−ｌであり、Ｌは、前記実際のサブタスクの計算に利用可能な前記マッパー集合内の前記マッパー数であり、ｋは予測子の数である、請求項１０に記載のコンピュータ・プログラム。
【請求項１３】
前記コンピュータ読み取り可能プログラム・コードが、前記コンピュータの前記少なくとも１つのプロセッサによって実行された場合、
前記予測子を、先行インデックス予測子と共通インデックス予測子とに分割することを実行するように構成されている、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
前記コンピュータ読み取り可能プログラム・コードが、前記コンピュータの前記少なくとも１つのプロセッサによって実行された場合、
グローバル検索シーケンスをＭ個の多数のローカル検索シーケンスに分割することと、
前記ローカル検索シーケンスの各々について、前記先行インデックス予測子から先行インデックス・シーケンスを識別することと、
Ｍ個のレコードを用いて一時入力ファイルを生成することと、を実行するように構成され、前記レコードの各々が先行インデックス・シーケンスを含み、前記レコードの各々が、共通インデックス予測子およびスイープ動作を適用する行列に対する参照を含む、請求項１３に記載のコンピュータ・プログラム。
【請求項１５】
前記コンピュータ読み取り可能プログラム・コードが、前記コンピュータの前記少なくとも１つのプロセッサによって実行された場合、
前記マッパー集合内の各マッパーにおいて、前記ローカル検索シーケンスの１つの先行インデックス・シーケンスを受信することと、
処理データ集合の各レコードにおける前記参照を介して共通インデックス予測子および前記行列を受信することと、
前記共通インデックス予測子を用いて共通インデックス・シーケンスを発生させることと、
前記先行インデックス・シーケンスに従って前記行列にスイープ動作を実行することと、
前記共通インデックス・シーケンスに従って、結果として得られた前記行列にスイープ動作を実行することと、
前記出力を識別することと、を実行するように構成され、前記出力がローカル回帰モデルである、請求項１４に記載のコンピュータ・プログラム。
【請求項１６】
前記共通インデックス・シーケンスを送信することなく、前記先行インデックス・シーケンスを前記マッパー集合内の各マッパーに送信することが、ネットワーク・トラフィックを軽減する、請求項１５に記載のコンピュータ・プログラム。
【請求項１７】
サース（ＳａａＳ：Software as a Service）が、前記コンピュータ・プログラムの動作を実行するように構成されている、請求項１０に記載のコンピュータ・プログラム。
【請求項１８】
コンピュータ・システムであって、
プロセッサと、
前記プロセッサに接続された記憶デバイスと、を備え、前記記憶デバイスがプログラムを記憶しており、前記プロセッサが前記プログラムの命令を実行して動作を実行するように構成され、前記動作が、
レコードの処理データ集合を生成することであって、前記レコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、前記実際のサブタスク集合によって共有されるデータに対する参照を含み、前記レコードの数が、前記実際のサブタスク集合内の前記実際のサブタスクの数に相当する、ことと、
マッパー集合における各マッパーによって、前記処理データ集合の前記レコードの１つを受信することと、前記レコードの前記受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させることと、
単一のリデューサーによって、前記マッパー集合内の各マッパーからの前記出力を集約してタスク結果を決定することと、
を含む、コンピュータ・システム。
【請求項１９】
前記動作が更に、
元のデータセットの少なくとも１つの特徴に基づいて、潜在的サブタスクの最大数を計算することと、
前記実際のサブタスクの実行に利用可能な前記マッパー集合内のマッパー数と前記潜在的サブタスクの最大数とに基づいて、実行される前記実際のタスク集合内の実際のサブタスク数を計算することと、
を含む、請求項１８に記載のコンピュータ・システム。
【請求項２０】
前記動作が更に、
Ｍ個の実際のサブタスクとして示される前記実際のサブタスク数を計算することを含み、Ｍ＝２ｍであり、Ｍ≦Ｌおよびｍ＜ｋ−ｌであり、Ｌは、前記実際のサブタスクの計算に利用可能な前記マッパー集合内の前記マッパー数であり、ｋは予測子の数である、請求項１８に記載のコンピュータ・システム。
【請求項２１】
前記動作が更に、
前記予測子を、先行インデックス予測子と共通インデックス予測子とに分割することを含む、請求項２０に記載のコンピュータ・システム。
【請求項２２】
前記動作が更に、
グローバル検索シーケンスをＭ個の多数のローカル検索シーケンスに分割することと、
前記ローカル検索シーケンスの各々について、前記先行インデックス予測子から先行インデックス・シーケンスを識別することと、
Ｍ個のレコードを用いて一時入力ファイルを生成することと、を含み、前記レコードの各々が先行インデックス・シーケンスを含み、前記レコードの各々が、共通インデックス予測子およびスイープ動作を適用する行列に対する参照を含む、請求項２１に記載のコンピュータ・システム。
【請求項２３】
前記動作が更に、
前記マッパー集合内の各マッパーにおいて、前記ローカル検索シーケンスの１つの先行インデックス・シーケンスを受信することと、
処理データ集合の各レコードにおける前記参照を介して共通インデックス予測子および前記行列を受信することと、
前記共通インデックス予測子を用いて共通インデックス・シーケンスを発生させることと、
前記先行インデックス・シーケンスに従って前記行列にスイープ動作を実行することと、
前記共通インデックス・シーケンスに従って、結果として得られた前記行列にスイープ動作を実行することと、
前記出力を識別することと、を含み、前記出力がローカル回帰モデルである、請求項２２に記載のコンピュータ・システム。
【請求項２４】
前記共通インデックス・シーケンスを送信することなく、前記先行インデックス・シーケンスを前記マッパー集合内の各マッパーに送信することが、ネットワーク・トラフィックを軽減する、請求項２３に記載のコンピュータ・システム。
【請求項２５】
サース（ＳａａＳ：Software as a Service）が、前記システムの動作を実行するように設けられている、請求項１８に記載のコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、マップ・リデュース（map-reduce）フレームワークにおけるスイープ（sweep）動作を用いた可能な回帰モデルの計算に関する。
【背景技術】
【０００２】
１つの目標変数（Ｙ）と予測変数（Ｘ）のリストとの間の関係を分析するために、通常、多数の線形回帰モデルが用いられる。ｋ個の予測子の大きい集合から、他の予測子よりも大きくターゲットに影響するいくつかの予測子を選択するために、変数増加法（forward selection）、変数減少法（backward elimination）、変数増加法（forward stepwise）等、多数の技法が提案されている。
【０００３】
予測子は、予測回帰モデルにおいてターゲットを予測するかまたはターゲットに影響するフィールド（field）と称することができる。ターゲットは、回帰モデルにおいて１つまたは複数の予測子によって予測されるかまたは影響されるフィールドと称することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
最良回帰を見出す１つの方法は、自由度調整済み決定係数（adjusted R square）等の選択した基準に基づいて全ての２ｋの回帰モデルを実行することである。この技法は「全数検索（exhaustive search）」とも呼ばれる。ｋが大きい場合、全ての可能な回帰の実行は、計算時間がｋと共に指数関数的に長くなるために現実的でないことがある。これまで性能向上の取り組みが行われており、それらは概ね２つの経路をたどる。すなわち、（１）逐次的な戦略を利用し、ある回帰モデルから別の回帰モデルに移動すること、および（２）並列計算戦略を利用して集中的な計算を分散させること、である。
【０００５】
マップ・リデュース・フレームワークは、インターネット時代にますます一般的になっている分散データ・ソースにおいてペタバイト単位のデータを処理することができるので、人気のあるパラダイムとなっている。マップ・リデュース・フレームワークは、アプリケーションが分散クラスタにおける数千のノードと共に動作することを可能とする。典型的なマップ・リデュース・ジョブは通常、多数のマッパー（mapper）を用いて、異なるデータ・スプリット／ブロックに対する計算を行い、１つまたは複数のリデューサー（reducer）を用いて、最終的な結果／統計データがデータ全体に基づいたものになるようにマッパーの結果をマージする。
【課題を解決するための手段】
【０００６】
タスク結果を計算するための方法、コンピュータ・プログラム、およびシステムを提供する。レコードの処理データ集合を生成し、このレコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、実際のサブタスク集合によって共有されるデータに対する参照を含み、レコードの数が、実際のサブタスク集合内の実際のサブタスクの数に相当する。マッパー集合における各マッパーによって、処理データ集合のレコードの１つを受信し、レコードの受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させる。単一のリデューサーによって、マッパー集合内の各マッパーからの出力を集約して（reduce）タスク結果を決定する。
【図面の簡単な説明】
【０００７】
これより図面を参照する。図面全体を通して、同様の参照番号は対応する部分を表す。
【０００８】
【図１】いくつかの実施形態に従ったマップ・リデュース・フレームワークを示す。
【図２】いくつかの実施形態に従った回帰モデルのシーケンスを表で示す。
【図３】いくつかの実施形態に従った、可能な回帰モデルを計算するための全体的なプロセスを示す。
【図４】いくつかの実施形態に従った、グローバル・シーケンスをローカル・シーケンスに分割する例を示す。
【図５】いくつかの実施形態に従った、マップ・リデュース・フレームワークの実施の一例を示す。
【図６Ａ】マップ／リデュース・フレームワークを用いて元のデータセットに対してタスクを実行するための動作をフロー図で示す。
【図６Ｂ】マップ／リデュース・フレームワークを用いて元のデータセットに対してタスクを実行するための動作をフロー図で示す。
【図７】いくつかの実施形態に従ったクラウド計算ノードを示す。
【図８】いくつかの実施形態に従ったクラウド計算環境を示す。
【図９】いくつかの実施形態に従った抽象回帰モデルレイヤを示す。
【発明を実施するための形態】
【０００９】
本発明の様々な実施形態の記載は、例示のために提示するが、網羅的であることも、開示する実施形態に限定されることも意図していない。記載する実施形態の範囲から逸脱することなく、当業者には多くの変更および変形が明らかであろう。本明細書において用いる用語は、実施形態の原理、実際的な用途、もしくは市場に存在する技術に対する技術的な改良を最も良く説明するため、または、本明細書に開示する実施形態を当業者が理解することを可能とするために、選択したものである。
【００１０】
実施形態は、マップ・リデュース・フレームワークを利用し、スイープ動作を用いることによって、ｋ個の予測子について２ｋの可能な回帰モデルを計算する。実施形態は、多数のノード（マッパー）を用いてローカル回帰モデル（例えばローカル最良回帰モデル）を並列に計算し、次いで１つのノード（リデューサー）を用いて多数のノードからの結果を組み合わせて、ローカル回帰モデルから１つのグローバル回帰モデル（例えばグローバル最良回帰モデル）を選択する。実施形態は、グローバル検索シーケンスを多数のローカル検索シーケンスに体系的に分解し、これらのローカル検索シーケンスは多数のノード上で別個に実行することができる。ローカル検索シーケンスは、グローバル検索シーケンスからのサブシーケンスと呼ぶことができる。
【００１１】
ノードは、クラスタ内の１つの中央処理装置（ＣＰＵ）コアに関連付けた実行ユニットと呼ぶことができる。クラスタは、多数のノードを有するものと説明することができ、これらのノードは同一または異なるコンピュータ上に存在し得る。いくつかの実施形態において、１つのノードは１つのマップまたはリデュースのタスクを実行することができる。
【００１２】
いくつかの実施形態において、多数のマッパーおよび単一のリデューサーが、多数のＣＰＵコアを有する単一のコンピュータ／マシン上で動作することができる。いくつかの実施形態では、多数のマッパーおよび単一のリデューサーが異なるコンピュータ／マシン上で動作することができる。
【００１３】
実施形態は、グローバル検索シーケンス／空間を、Ｍ（＝２ｍ）個（ｍ＜ｋ−１）のローカル検索シーケンス／空間に分解し、２ｋ−ｍのスイープピボットのローカル検索シーケンス上でスイープ動作を適用し、これによって２ｋ−ｍの回帰モデルを得る。ピボットは、スイープ動作が適用される行列の特定の対角成分に相当する。そして、実施形態は、Ｍ個のマッパーにおいて並列にローカル回帰モデルを見出し、１つのリデューサーを用いてそれらのマッパーからの結果を組み合わせてグローバル回帰モデルを見出す。図１は、いくつかの実施形態に従ったマップ・リデュース・フレームワーク１００を示す。いくつかの実施形態において、計算アーキテクチャを用いて、マップ・リデュース・フレームワーク１００における全ての可能な回帰モデルを計算する。マップ・リデュース・フレームワーク１００は、入力としてグローバル検索空間１１０を受信し、グローバル回帰モデル１６０を出力する。マップ・リデュース・フレームワーク１００は、マッパー１２０、１３０、．．．１４０、およびリデューサー１５０を含む。グローバル検索空間１１０は、複数のローカル検索空間に分割される。各マッパー１２０、１３０、．．．１４０は、１つのローカル検索空間を受信し、１つのローカル回帰モデルをリデューサー１５０に出力する。リデューサー１５０は、各マッパー１２０、１３０、．．．１４０からのローカル回帰モデルを用いてグローバル回帰モデルを識別し、これがグローバル回帰モデル１６０として出力される。
【００１４】
実施形態は、回帰モデル解決策を講じるにあたってマップ・リデュース・フレームワーク１００を活用する。また、実施形態はスイープ動作を用いる。
【００１５】
スイープ動作
単に実施形態の理解を深めるためであるが、ここでスイープ動作の特性について述べる。
【００１６】
回帰モデルにおいて、予測子は、連続フィールドまたはカテゴリ・フィールドである場合がある。カテゴリ・フィールドは、有限数の名目カテゴリまたは序数カテゴリを値として有するものと呼ぶことができる。パラメータ化技法に基づいて、Ｊ個のカテゴリを有する各カテゴリ予測子をＪ個のダミー変数によって拡張することができ、従って、回帰モデルにおいては１つのカテゴリ予測子に対応するＪ個の係数がある。
【００１７】
予測子Ｘ行列にｋ個の効果（effects）があると仮定する。ｋ個の効果は連続予測子およびカテゴリ予測子の双方を含み得るので（実際、ｋ個の効果の一部はいくつかの予測子の組み合わせであり得るが、簡単にするためにかつ一般性を失うことなく、それらは除外されるので、ｋ個の効果はｋ個の予測子とする）、回帰モデルにおける係数の数、例えばｐは、ｋよりも大きくなり得る。標準方程式
【数１】
2016507093.tif 000003
に基づいて、回帰係数
【数２】
2016507093.tif 000004
には閉形式解がある。ここでＹはｎ×１ベクトルであり、ｎはレコード数であり、Ｘはｋ個の予測子から導出されたｎ×ｐ行列であり、
【数３】
2016507093.tif 000005
は係数推定値のｐ×１ベクトルである。
【数４】
2016507093.tif 000006
を得るための技法がスイープ動作である。スイープ動作は以下のように機能する。すなわち、交差積（ｐ＋１）×（ｐ＋１）行列
【数５】
2016507093.tif 000007
で、第１のｐ個のピボットまたはピボット要素についてスイープを行い、その結果が以下である。
【数６】
2016507093.tif 000008
ここで、残差平方和（ＳＳＥ）は、回帰モデルを選択する際に用いる基準の計算において通常必要となる残差平方和である。一般に、第１のｐ個のピボット要素のいずれかのサブセットについてＣをスイープすると、Ｘのそのサブセットに対するＹの回帰に相当する回帰係数の推定値が得られる。
【００１８】
スイープ動作には２つの特性がある。すなわち、（１）可逆的である（同一のピボット要素を用いた２回の連続スイープはヌル動作と同じである）、および（２）可換である（ｒ番目のピボット要素に、次いでｓ番目のピボット要素についてスイープを行うと、逆の順序のスイープと同じ結果が得られる）。これらの特性を利用して、（連続予測子について）特定の行および列に、または（カテゴリ予測子に対応するＪ個のダミー変数の集合について）Ｃの特定のＪ個の行および列の集合に、スイープ動作をそれぞれ適用すると、適合した回帰モデルに予測子が導入されるか、または、予測子がすでにモデル内に存在する場合は予測子が除去される。すなわち、１つの予測子に対する各スイープ動作によって１つの回帰モデルが得られる。いくつかの実施形態では、以下のように、２ｋ−１のスイープ動作のシーケンスによって、可能な２ｋ−１の回帰を得ることができる。
・ｋ＝１である場合、２ｋ−１＝１であり、第１の予測子に対応するピボット要素（複数のピボット要素）についてスイープを行うことで単一の回帰を実行する。ピボットのシーケンスはＳ１＝｛１｝である。
・ｋ＝２である場合、第１の予測子についてスイープを行うことで第１の回帰を実行する。そして、第２の予測子についてスイープを行うと、第１および第２の予測子の双方を含む新しい回帰が生成される。次に再び第１の予測子についてスイープを行うと、第１の予測子は削除され、第２の予測子のみを含む回帰が生成される。ピボットのシーケンスＳ２＝｛１２１｝についてＣ行列をスイープすることで、全ての２ｋ−１＝３の回帰モデルが生成される。
・ｋ＝３である場合、シーケンスＳ２において第１の回帰が３つ得られる。そして、第３の予測子についてスイープを行うと、シーケンスＳ２により生成された回帰に第３の予測子を追加した新しい回帰が生成される。シーケンスＳ２は、第３の予測子を含まない３つの別個の回帰を生成したので、シーケンスＳ２を繰り返すと、第３の予測子を含む別の３つの回帰が生成される。次いで、ピボットのシーケンスＳ３＝｛Ｓ２，３，Ｓ２｝＝｛１２１３１２１｝についてＣ行列をスイープすることで、２ｋ−１＝７の回帰モデルが生成される。
・第１のｋ−１個の予測子のシーケンスＳｋ−１で、ｋ−１個の予測子に対する全ての２ｋ−１の可能な回帰が得られると想定する。そして、ｋ番目の予測子についてスイープを行うと、シーケンスＳｋ−１により生成された回帰モデルにｋ番目の予測子を追加した新しい回帰モデルが生成される。次いでシーケンスＳｋ−１を繰り返すと、ｋ番目の予測子を含む別の２ｋ−１の別個の回帰モデルが生成される。従って、ピボットのシーケンスＳｋ＝｛Ｓｋ−１，ｋ，Ｓｋ−１｝についてＣ行列をスイープすることで、２ｋ−１の回帰モデルが生成される。
【００１９】
図２は、いくつかの実施形態に従った回帰モデルのシーケンスを表２００で示す。図２において、Ｓｌは、ピボットとされる予測子の指数を識別する。図２において、３列目の各カッコは回帰モデルを表す。カッコ内の数は、その回帰モデルに含まれる予測子を示す。
【００２０】
表２００から、４個の予測子のシーケンスは、Ｓ４＝｛１２１３１２１４１２１３１２１｝（２列目）と表され、１５の回帰モデルを生成する（３列目）（インターセプトのみの回帰モデルが含まれる場合は回帰モデルは１６である）。検索シーケンスのサイズは１５である。
【００２１】
シーケンスＳｋ、すなわち
【数７】
2016507093.tif 000009
等を構築するための１つの技法は帰納的プロセスであり、２ｋ−１の回帰モデルを順次生成することができる。一方、シーケンスＳｋをいくつかのサブシーケンスに分解可能であることは容易に理解でき、その後に各サブセットから２ｋ−１の回帰モデルのサブセットを生成することができる。例えば、シーケンス
【数８】
2016507093.tif 000010
を４個のサブシーケンスまたはローカル・シーケンスに分解すると、｛１２１｝、｛３１２１｝、｛３４１２１｝、｛４１２１｝であり、これら４つのサブシーケンスによって１５の回帰モデルを並列に生成することができる。
【００２２】
回帰モデル
スイープ動作を用いて回帰モデルを発生させるため、実施形態は最初に、ＸおよびＹに基づいた（ｐ＋１）×（ｐ＋１）行列である交差積行列Ｃを計算する。この計算は、大きい分散データ・ソースのためのマップ・リデュース・フレームワークにおいて行われる。次いで、２ｋの回帰モデルの計算により、Ｃ行列に繰り返しスイープ動作を適用する。このような計算はデータ・ソースに基づかないので、典型的なマップ・リデュース・ジョブではない。従って実施形態は、２ｋの回帰モデルを計算するために、マップ・リデュース・フレームワークにおける並列計算の潜在機能を活用する。
【００２３】
実施形態では、（１）クラスタ内の利用可能ノードを充分かつ効果的に利用するために適正な数のマッパーを指定し、（２）２ｋの回帰モデルのサブセットを正しく実行するために最少量の入力を各マッパーに供給する。
【００２４】
Ｌは、分散クラスタにおいて利用可能な中央処理装置（ＣＰＵ）コアの数であり、既知であると仮定すると、マッパーまたは実際のサブタスクの数Ｍは、以下の２つのルールに基づいて指定される。
（ａ）Ｍ≦Ｌ  いくつかの実施形態では、効率を上げるためにこれを用いる。代替的な実施形態では、Ｍ＞Ｌを用いる。
（ｂ）Ｍ＝２ｍ、ｍ＜ｋ−１  各ローカル検索シーケンスのサイズが２ｋ−ｍであると、Ｍ個のマッパーは２ｋの回帰モデルをカバーすることができる。
【００２５】
典型的なマップ・リデュース・ジョブにおいて、マッパーに対する入力はスプリット／ブロックからのデータであるので、データ・スプリットの数がマッパーの数を決定する。スプリットは、固定サイズの部分に分割される大きいデータセットのサブセットと称することができる。例えば実施形態は、各スプリットに１つのマップタスクを生成し、スプリット内の各レコードでユーザ指定のマップ機能を実行する。いくつかの実施形態では、ほとんどのジョブについて、良好なスプリット・サイズは、Ｈａｄｏｏｐ分散ファイル・システム（ＨＤＦＳ）ブロックのサイズである傾向があり、デフォルトで６４ＭＢであるが、これはクラスタのために（全ての新しく生成されたファイルについて）変更したり、各ファイルを生成する際に指定したりすることができる。
【００２６】
ここでの２ｋの回帰モデルの計算は、元のデータ・スプリットに基づいていない。代わりに実施形態は、Ｍ行を有する一時的な入力ファイルを生成し、スプリット・サイズを１行のサイズとして構成することでＭ個のスプリットを生成し、Ｍ個のマッパーを導出することによって、Ｍ個のマッパーが存在するように制御を行うことができる。
【００２７】
一時的な入力ファイル内の１行の情報は、１つの入力スプリットおよび１つのマッパーに送信される。この行の情報はローカル検索シーケンスを含み、これはマッパーに対して、回帰モデルのシーケンスを得るためにどのようにスイープ動作の順序を適用するかを教える。ローカル検索シーケンスは、マッパーによって異なり、ローカル・シーケンスを組み合わせることで２ｋの可能な回帰モデルが生成されるようになっている。いくつかの実施形態では、異なるマッパーにローカル検索シーケンス全体をそれぞれ送信すると、ｋが大きい場合はネットワーク・トラフィックが増大する可能性がある。このため実施形態は、異なるマッパーに、各ローカル検索シーケンスの一部分（すなわち先行インデックス・シーケンス）を送信することで、ネットワーク・トラフィックを軽減する。これが実行可能である理由は、ローカル検索シーケンスを２つの部分、すなわち（ｉ）「共通インデックス・シーケンス」および（ｉｉ）「先行インデックス・シーケンス」に、更に分解可能であるからである。
【００２８】
共通インデックス・シーケンスは、全てのローカル検索シーケンスについて同一であり、同じ予測子グループ（「共通インデックス予測子」と呼ばれる）に関連付けられているので、共通インデックス・シーケンスは、ネットワークを介して送信されずに、各マッパー内で発生させることができる。
【００２９】
先行インデックス・シーケンスは、ローカル検索シーケンスによって異なり、異なる予測子（「先行インデックス予測子」と呼ばれる）に関連付けられているので、それらの各々は異なるマッパーに送信される。いくつかの実施形態では、先行インデックス・シーケンスは共通インデックス・シーケンスよりも著しく小さいので、（先行インデックス・シーケンスおよび共通インデックス・シーケンスの双方でなく）先行インデックス・シーケンスのみを送信することで、ネットワーク・トラフィックを軽減することができる。
【００３０】
異なるマッパーに送信される個々の情報の他に、入力の第２の部分は、全てのマッパーについて同一であり、交差積行列Ｃ、共通インデックス予測子等を含む。共通インデックス・シーケンスは、共通インデックス予測子に基づいて各マッパー内で発生させることができる。
【００３１】
マップ・リデュース・フレームワークを利用する実施形態は、はるかに多くの予測子を用いて全ての可能な回帰モデルを実行するか、または固定数の予測子について性能を向上させることができる。従って、実施形態はスケーラブルであり、予測子の数ｋが大きい場合に最良回帰モデルを見出す能力が向上する。実施形態は、マッパーの数を制御することで高効率となり、ネットワークを介して伝達する情報のサイズを縮小する。実施形態は、マッパー間に作業負荷を均等に分散することができるので、バランスがとれる。
【００３２】
実施形態は、マップ・リデュース・フレームワーク１００内に２ｋの可能な回帰モデルの計算を適合させるために、２つの部分から成る。すなわち、（１）Ｍ＝２ｍのマッパーの各々が、２ｋの可能な回帰モデルのサブセットを実行するための命令を受信し、ローカル回帰モデルをリデューサーに送信する、および（２）リデューサーが、（例えば分散ファイル・システムに）出力するグローバル回帰モデルを見出すために、ローカル回帰モデルを選択する。回帰モデルは、他のいずれかの予測モデルと同様、ターゲットと予測子集合との間の関係の予測または発見あるいはその両方、および解釈を行うために用いることができる。
【００３３】
実施形態は、マップ・リデュース・フレームワーク１００および分散ファイル・システム（例えばＨａｄｏｏｐ分散ファイル・システム（ＨＤＦＳ）によって実施することができる。図３は、いくつかの実施形態に従った、可能な回帰モデルを計算するためのプロセス全体を示す。いくつかの実施形態では、全ての可能な回帰モデルを計算する。図３は、ローカル・ファイル・システム３００、分散ファイル・システム３１０、およびマップ・リデュース・ジョブ３３０を含む。
【００３４】
ローカル・ファイル・システム３００は、（１）先行インデックス・シーケンスである固有入力情報、（２）共通インデックス予測子、Ｃ行列、および他の入力（例えばレコード数）を含む共有入力情報、ならびに（３）分散ファイル・システム３１０内で共有入力情報の位置を識別する共有入力情報に対する参照、を記憶している。いくつかの実施形態では、この参照はＵＲＩ（Uniform Resource Identifier）であり、分散ファイル・システム３１０内で共有入力情報の名前またはリソースを識別するために用いられる文字列である。分散ファイル・システム３１０は、（１）スプリット１、スプリット２、．．．スプリットＭ（Ｍ行）を含む一時ファイル（各スプリットが固有先行インデックス・シーケンスおよび共有入力情報に対する参照を含む）、ならびに（２）ローカル・ファイル・システムからアップロードされた共有入力情報、を含む。マップ・リデュース・ジョブ３３０は、マッパー１  ３３２、マッパー２  ３３４、．．．マッパーＭ  ３３６、およびリデューサー３３８を含む。
【００３５】
共有入力情報は、ローカル・ファイル・システム３００から分散ファイル・システム３１０にアップロードされる。同時に、分散ファイル・システム内の共有入力情報に対する参照が記録される。次いで、分散ファイル・システム３１０において、Ｍ行を有する一時ファイルが生成される。一時ファイルの１行内に、１つの先行インデックス・シーケンスおよび共有入力情報に対する参照が書き込まれる。一時ファイルの１行のサイズとして１つの入力スプリットのサイズが構成され、これは、指定数（Ｍ）のマッパーによるマップ・リデュース・ジョブを駆動するために用いられる。従って、１行は１つのスプリットおよび１つのマッパーに対応する。マッパー３３２、３３４、．．．３３６が駆動されると、マッパー３３２、３３４、．．．３３６は、各入力スプリット内の内容を抽出する。マッパー３３２、３３４、．．．３３６は、参照によって分散ファイル・システム３１０内の共有入力情報の位置を識別し、共有入力情報をそのローカル・ファイル・システムにダウンロードする。固有先行インデックス・シーケンスおよび共有入力情報を用いて、マッパーはローカル検索を実行し、ローカル回帰モデルを発生させ、これがリデューサー３３８に出力される。リデューサー３３８は、マッパー３３２、３３４、．．．３３６からのローカル回帰モデルからの結果を比較し、グローバル回帰モデルを分散ファイル・システム３５０に出力する。いくつかの実施形態では、分散ファイル・システム３１０、３５０は同一の分散ファイル・システムであり、他の実施形態では、分散ファイル・システム３１０、３５０は異なる分散ファイル・システムである。
【００３６】
いくつかの実施形態においては、参照を一時ファイルに記憶する必要はない。いくつかの実施形態では、参照は、構成のインスタンスにプロパティとして記憶し、Ｈａｄｏｏｐフレームワーク内の構成アプリケーション・プログラミング・インタフェース（ＡＰＩ）を介して各マッパーに渡すことができる。次いで、全てのマッパーがこの参照を受信し、ＨＤＦＳにおいてどこで共有入力情報を抽出するかを知る。他の実施形態では、参照は記憶され、マップ・リデュース・フレームワークのための一時ファイルを介して渡される。
【００３７】
分散クラスタにおいて利用可能なＣＰＵコアの数Ｌが与えられると共に、ｋ個の予測子の指数（１、．．．、ｋと表される）が与えられると、マッパーの数Ｍは、Ｍ≦ＬおよびＭ＝２ｍと指定することができる（ｍ＜ｋ−１）。ｋ個の予測子は、ｍ個の先行インデックス予測子およびｋ−ｍ個の共通インデックス予測子に分割することができる。２ｋのサイズのグローバル検索シーケンスは、２ｋ−ｍのサイズのＭ個のローカル検索シーケンスに分解されて、各マッパーにおいて２ｋ−ｍ個の回帰モデルを生成する。
【００３８】
典型的なマップ・リデュース・ジョブにおいて、入力は分散ファイル・システムに記憶されたデータセットである。多数のノードに計算を分散させるため、データは多数のピースに分割され、各ピースは入力スプリットと呼ばれる。デフォルトの入力スプリット・サイズは、分散ファイル・システムのデフォルトのブロック・サイズである。このため、マッパーの数は、入力データセットのデータ・ブロック数によって決定される。換言すると、マッパーの数は入力データのボリュームによって決定される。すなわち、データセットが大きくなればなるほどマッパーの数が増える。
【００３９】
実施形態では、２ｋの回帰モデルの計算は元のデータ・スプリットに基づかないので、実施形態は、駆動される指定マップ・リデュース・ジョブにおけるマッパーの数を制御するために、Ｍ行の一時入力ファイルを生成し、入力スプリット・サイズを１行のサイズとして再構成する。１行の内容を１つのマッパーに送信して、２ｋ−ｍの回帰モデルを生成する。行の内容の候補として当然のものはローカル検索シーケンスである。しかしながら、ｋが大きいと、ローカル検索シーケンスのサイズ（２ｋ−ｍ）はまだ大きいことがある。従って実施形態は、各行にローカル検索シーケンスの小さい一部分（すなわちｍの先行インデックス予測子に基づいて発生させた先行インデックス・シーケンス）を含む。ローカル検索シーケンスの他の部分（すなわちｋ−ｍの共通インデックス予測子に基づいて発生させた共通インデックス・シーケンス）は、各マッパー内で発生させる。一般に、ｋが大きい場合、先行インデックス・シーケンスのサイズ（ｍ）は共通インデックス・シーケンスのサイズ（２ｋ−ｍ−１）より小さく、従って、先行インデックス・シーケンスのみを異なるマッパーに送信することで、ネットワーク・トラフィックが著しく軽減する。
【００４０】
マップ・リデュース・ジョブを駆動する前に、先行インデックス・シーケンスおよび共有入力情報に対する参照を、Ｍ行の単一ファイルに書き込む。各行が、１つの先行インデックス・シーケンスおよび共有入力情報に対する参照を表す。それらの先行インデックス・シーケンスのための空間を小さいサイズにすることで、各行の長さを同一に保つ。ファイルは、マッパーの入力として分散ファイル・システムにセーブされる。入力スプリット・サイズは１行のサイズとして構成されるので、Ｍ行の入力ファイルからＭ個のスプリットを導出することができ、Ｍ個のスプリットはＭ個のマッパーを決定する。更に、１行に対応するように入力キー／値を定義する。キーは行のオフセットであり、値はファイル内の対応する行の内容である。従って、各マッパーは１つのキー／値対を受信し、次いで１つの固有先行インデックス・シーケンスおよび共有入力情報に対する参照を抽出する。
【００４１】
入力の第２の部分は、マッパーのための共有（同一）入力情報である。入力の第２の部分は、（１）ピボットとしての先行インデックス・シーケンスおよび共通インデックス・シーケンスに従ってＣ行列にスイープ動作を適用することによって異なる回帰モデルを発生するために用いられるＣ行列、（２）（ＳＳＥに加えて）基準値を計算するために用いられるレコードの数、ならびに（３）マッパー内で共通インデックス・シーケンスを発生するために用いられる共通インデックス予測子のリスト、を含む。共有入力情報がネットワーク内で正しく伝送されることを保証するため、共有入力情報は、ファイル（またはファイル・ストリーム）内にシリアル化し、分散ファイル・システムに記憶することができる。次いで、全てのマッパーは、共有入力情報に対する参照によって、分散ファイル・システムからマッパー内のローカル・システムに共有入力情報をコピーすることができる。
【００４２】
入力のこれら２つの部分を用いて、各マッパーは以下のタスクを実行する。すなわち、（１）そのマッパーに割り当てられた先行インデックス・シーケンス全体についてＣ行列にスイープ動作を適用して、１つの回帰モデルと、結果として得られるＣ行列（Ｃ＊である）とを生成する。（２）共通インデックス予測子に基づいて共通インデックス・シーケンスを発生させる。（３）順次、共通インデックス・シーケンスに従ってＣ＊行列内のピボットについてスイープして、２ｋ−ｍ−１の回帰モデルを生成する。（４）２ｋ−ｍの回帰モデルから基準値に基づいてローカル回帰モデルを見出す（例えば基準が自由度調整済み決定係数である場合、最大の自由度調整済み決定係数を有するローカル回帰モデルを選択する）。（５）ローカル回帰モデルにキーを割り当て、ローカル回帰モデルの結果を値として指定する。（６）出力キー／値の対を介してローカル回帰モデルをリデューサーに渡す。
【００４３】
リデューサーは、入力キー／値の対を介してローカル回帰モデルを集めて、Ｍ個の回帰モデル間でグローバル回帰モデルを見出し、このグローバル回帰モデルを、出力キー／値の対を介して分散ファイル・システムにエクスポートする。マッパー、リデューサー、および分散ファイル・システム間で回帰モデルを受け渡しするため、マッパーの出力キー／値の対ならびにリデューサーの入力および出力キー／値の対は同じタイプとして定義することができる。１つのキー／値の対は１つの回帰モデルに対応し、キーは１つの回帰モデルの識別子（ＩＤ）として定義され、値は回帰モデルの関連する結果として定義される。
【００４４】
分散コンピューティングも並列コンピューティングも行わずに可能な回帰モデルを実行する時間計算量（time complexity）は、ｋ個の予測子でＯ（２ｋ）である。一方、Ｍ個のマッパーを用いた同じ計算の時間計算量は約Ｏ（２ｋ−ｍ）であり、リデューサーの時間計算量は約Ｏ（Ｍ）である。従って、マップ・リデュース・フレームワークにおける全体的な時間計算量は、約Ｏ（２ｋ−ｍ）＋Ｏ（Ｍ）≒Ｏ（２ｋ−ｍ）である。マッパーの数が増えれば増えるほど、性能は向上する。
【００４５】
ｍ個の先行インデックス予測子およびｋ−ｍ個の共通インデックス予測子を含むｋ個の予測子があると仮定する。事前順序付け（pre-ordering）動作を実行する。すなわち、まず、連続予測子（１つのカテゴリを有する）を選択し、次いで、カテゴリ予測子をカテゴリ数の昇順にソートする。一般性を失うことなく、実施形態は、ｋ個の事前順序付け予測子の指数を１、．．．、ｋに割り当てるので、予測子ｋはカテゴリ数が最大となる。更に、最初のｋ−ｍ個の事前順序付け予測子を共通インデックス予測子に割り当て、最後のｍ個の予測子を先行インデックス予測子に割り当てる。この動作によって、２ｋの回帰モデルを実行するために用いるスイープ動作数が最小限に抑えられることが確実となる。
【００４６】
Ｍ＝２ｍ個のマッパーを指定すると仮定する。２ｋのサイズのグローバル検索シーケンスは、２ｋ−ｍのサイズのＭ個のローカル検索シーケンスに分解され、各ローカル検索シーケンスは、更に２つの部分に分解される。すなわち、（１）ｋ−ｍ個の共通インデックス予測子に関連付けられ、全てのマッパーについて同一である「共通インデックス・シーケンス」、および（２）ｍ個の先行インデックス予測子に関連付けられ、マッパーによって異なる「先行インデックス・シーケンス」である。上述したスイープ動作のための帰納的技法に基づいて、共通インデックス・シーケンスはｋ−ｍ個の共通インデックス予測子から導出され、２ｋ−ｍ−１のサイズのＳｋ−ｍである。先行インデックス・シーケンスの集合は、全てのｌ（ｌ＝０、．．．、ｍ）についてｍ個の先行インデックス予測子のｌの組み合わせの集合として構築されるので、それらは２ｍとなり、Ｍ＝２ｍ個のマッパーに送信される。このため、任意の先行インデックス・シーケンスの最大サイズはｍであり、ｋが大きい場合は共通インデックス・シーケンスのサイズ（２ｋ−ｍ−１）より小さい。そして、先行インデックス・シーケンスをマッパーに送信し、各マッパー内で共通インデックス・シーケンスを発生させることによって、ネットワーク・トラフィックを軽減することができる。
【００４７】
図４は、いくつかの実施形態に従ったローカル・シーケンスの一例を示す。単に理解を深めるため、本明細書に一例を提供する。この例は、５個の予測子および４個のマッパーを有し、ローカル検索シーケンス、先行インデックス・シーケンス、および共通インデックス・シーケンスについて示すと共に、それらの対応するサイズを示す。
【００４８】
実施形態を用いず、並列コンピューティングを利用しない状況において、５個の予測子があり、グローバル検索シーケンスを、｛１２１３１２１４１２１３１２１５１２１３１２１４１２１３１２１｝として発生させて、３２＝２５の回帰モデルを順次生成する。
【００４９】
図４において、パネル４００は並列コンピューティングを利用する状況を示す。５個の予測子は事前順序付けされ、先行インデックス予測子４、５と共通インデックス予測子１、２、３とに分割されている。先行インデックス・シーケンス集合は、先行インデックス予測子４および５のうち０個、１個、および２個の組み合わせの集合である。すなわち、｛０｝（スイープ動作を行わないことを意味する）、｛４｝、｛５｝、および｛４５｝であるので、最大サイズは２である。先行インデックス・シーケンスは、｛００｝｛４０｝｛０５｝｛４５｝と書かれ、一次入力ファイルの４つの行で同一のサイズを保つことができる。共通インデックス・シーケンスは、Ｓ３＝｛１２１３１２１｝であるので、サイズは７である。次いで４個のローカル・シーケンスを構築する。各ローカル・シーケンスは、１つの先行インデックス・シーケンス（１つの回帰モデルを生成する）および共通インデックス・シーケンス（７個の回帰モデルを生成する）を有し、４個のローカル・シーケンスが３２の回帰モデルを並列に生成するようになっている。
【００５０】
先行インデックス・シーケンスまたは共通インデックス・シーケンスにおける１つの値は、（連続予測子について）特定の行および列に、または（カテゴリ予測子に対応するＪ個のダミー変数の集合について）特定のＪ個の行および列の集合に、スイープ動作を適用することを示す。４個のローカル・シーケンスにおいて、共通インデックス予測子１、２、および３は、それぞれ１６回、８回、および４回現れるので、それらにスイープ動作はそれぞれ１６回、８回、および４回適用される。先行インデックス予測子４および５は２回現れ、２回スイープされる。予測子１が連続予測子である場合、スイープ動作数は１６である。しかし、予測子１がＪ個のカテゴリを有するカテゴリ予測子である場合、その数は１６Ｊになる。このように、事前順序付け予測子動作を実行して、スイープ動作の合計数が最小限であり、ある程度の計算時間を節約可能であることを保証する。
【００５１】
図４の例は、共通インデックス・シーケンスのサイズ（２ｋ−ｍ−１）が通常は先行インデックス・シーケンスのサイズ（ｍ）より大きいことを明示している。また、図４は、先行インデックス・シーケンス（および共通インデックス・シーケンスでない）が、Ｍ行の一時入力ファイルに含まれて異なるマッパーに送信された場合、ネットワーク・トラフィックが軽減される（共通インデックス・シーケンスを送信しないので）ことを示す。更に図４の例に示すように、事前順序付け動作が、実行するスイープ動作数を最小限に抑えることができる。
【００５２】
実施形態は、マップ・リデュース特性を利用して、（ａ）マップ・リデュース・フレームワークを構成するためのＭ行の入力ファイルを生成して、この入力ファイルをＭ個の入力スプリットに設定し、次いでこれを用いて指定されたマップ・リデュース・ジョブのためのＭ個のマッパーを導出し、（ｂ）入力を、２つの部分、すなわち、キー／値の対によってパースされて正しい命令が各マッパーに送信されるようになっている、共有入力情報に対する参照と一緒になった個別情報と、ファイルにシリアル化されることで情報がネットワークを介してマッパーによって正しく引き出されるようになっている共有情報と、に分割し、更に、（ｃ）各マッパーの出力ならびにリデューサーの入力および出力のためのキー／値の対を同じタイプで定義することで、選択された回帰モデルをネットワーク内で正しく伝達可能とする。
【００５３】
実施形態は、マッパーに先行インデックス・シーケンスを送信するが、共通インデックス・シーケンスは送信しないので、（ａ）先行インデックス・シーケンス集合が、全てのｌ（ｌ＝０、．．．、ｍ）についてｍ個の先行インデックス予測子のｌ個の組み合わせの集合である場合、（ｂ）いくつかのカテゴリ予測子が存在する場合に事前順序付け動作によってカテゴリ予測子を先行インデックス予測子に割り当て、最小数のスイープ動作を実行することを保証した場合、ネットワーク・トラフィックを軽減することができる。
【００５４】
図５は、いくつかの実施形態に従ったマップ・リデュース・フレームワーク実施の一例を示す。図５は、図４を参照して検討したものと同じ例を参照して検討する。この場合も、この例では、５個の予測子および４個のマッパーがあると想定する。図５は、ローカル・ファイル・システム５００、分散ファイル・システム５１０、およびマップ・リデュース・ジョブ５３０を含む。
【００５５】
予測子１、２、および３は共通インデックス予測子であり、対応する共通インデックス・シーケンスは｛１２１３１２１｝である。図５では、共通インデックス予測子のみを４個のマッパー全てに送信し、次いで共通インデックス予測子に基づいて各マッパーによって共通インデックス・シーケンスを発生させる。
【００５６】
予測子４および５は先行インデックス予測子であるが、対応する先行インデックス・シーケンスは異なるので、マッパーに送信される入力が異なるようになっている。図５のマップ・リデュース・フレームワークでは、先行インデックス・シーケンスは｛０｝、｛４｝、｛４５｝、｛５｝であり、それらはファイル内に４行として含まれてマッパーに送信され、次いで各マッパーは１つの特定のシーケンスに対してＣ行列をスイープして、結果としてＣ＊行列を得る。
【００５７】
マップ・リデュース・フレームワークでは、各マッパーは８個の回帰モデルを生成し、１つのローカル回帰モデルを選択し、次いで４個のマッパーからのローカル回帰モデルがリデューサーに送信され、リデュースサーはグローバル回帰モデルを選択し、これが分散ファイル・システムに送信される。
【００５８】
マップ・リデュース・フレームワークは、２ｋの回帰モデルを実行するためにクラスタ内でいかなる数のノードも利用可能であるので、スケーラブルである。
【００５９】
図６Ａおよび図６Ｂは、マップ・リデュース・フレームワークにおいて並列計算の潜在能力を利用するために、マップ・リデュース・フレームワークを用いて元のデータセットにタスクを実行するための動作をフロー図で示す。いくつかの実施形態では、タスクは、Ｃ行列をスイープして全ての可能な２ｋの回帰モデルを計算することによって線形回帰モデルを選択することである。このような実施形態では、Ｃ行列が元のデータセットである。
【００６０】
制御はブロック６００において開始し、元のデータセットの少なくとも１つの特徴に基づいて、タスクの潜在的サブタスクの最大数Ｎを計算する。いくつかの実施形態では、タスクの潜在的サブタスクの最大数はＮ＝２ｋである。可能な回帰モデルを計算するための元のデータセットの特徴は、ｋに関連するＣ行列（元のデータセット）の次元である。Ｃ行列はＸおよびＹに基づいて構築され、Ｘにおける予測子数がｋであるからである。
【００６１】
ブロック６０２において、利用可能なマッパーの数Ｌを決定する。いくつかの実施形態では、数Ｌはクラスタ内で利用可能なＣＰＵコアの数である。
【００６２】
ブロック６０４において、ＬおよびＮに基づいて、実際のサブタスクＴの数Ｍを計算する。ここで、各サブタスクはＴ１、．．．、ＴＭとして識別される。各サブタスク（Ｔｉ）は、マッパーが２ｋ−ｍの回帰モデル間でローカル線形回帰モデルを見出そうとすることにより実行される。
【００６３】
いくつかの実施形態では、実際のサブタスクの数ＭはＭ＝２ｍであり、ｍ＜ｋ−１であるので、Ｍ＜Ｎ（＝２ｋ）である。更に、実際のサブタスクの数Ｍは、効率を上げるために、マッパーの数Ｌ以下に指定される（すなわちＭ≦Ｌ）。従って、ほとんどの状況では、Ｍ、Ｌ、およびＮ間の関係は、Ｍ≦Ｌ＜Ｎである。
【００６４】
しかしながら、いくつかの実施形態では、実際のサブタスクの数Ｍがマッパーの数Ｌよりも大きい場合がある（すなわちＭ＞Ｌ）。このような実施形態では、ＣＰＵがそれらのサブタスクの各々の処理に利用可能となるまで、いくつかのサブタスクはキューで待機する場合がある。
【００６５】
ブロック６０６において、処理データセットを生成する。この場合データセットは、Ｒ１、．．．、ＲＭとして識別されるＭ個のレコードを含み、レコードＲｉの各々はサブタスクＴｉに固有のデータを含み、レコードＲｉの各々は実際のサブタスクの全てに適用可能なデータに対する参照を含み、元のデータセットからの少なくとも一部の情報を含む。いくつかの実施形態では、処理データセットは一時入力ファイルであり、このファイルはＲ１、．．．、ＲＭとして識別されるＭ行を含み、各レコードＲｉは各サブタスクＴｉについての別個の先行インデックス・シーケンス（最大サイズはｍ）を含み、各レコードＲｉは、Ｃ行列に対する参照、（ｋ−ｍの）共通インデックス予測子のリスト、および全てのサブタスクに適用可能な他の入力を含む。いくつかの実施形態では、参照は、Ｈａｄｏｏｐフレームワークの構成ＡＰＩを介して各マッパーに渡すことができる。
【００６６】
ブロック６０８において、マップ／リデュース・フレームワークを構成して、設定した処理データの１つのレコードＲｉを処理のためにキー／値の対を介して各マッパーに送信する。
【００６７】
ブロック６０８（図６Ａ）から、処理は続いてブロック６１０に移る（図６Ｂ）。
【００６８】
ブロック６１０において、タスクをマップ／リデュース・フレームワークにサブミットし、各マッパーは、処理データセットのレコードＲｉ内のデータに基づいて割り当てられたサブタスクＴｉを実行して、出力（例えばローカル回帰モデル）を発生する。いくつかの実施形態では、サブタスクＴｉはマップ／リデュース・フレームワークにおいて実行され、各マッパーはレコードＲｉを取得してサブタスクＴｉを実行するが、この際に、（ａ）先行インデックス・シーケンスに対してＣ行列にスイープ動作を適用する、（ｂ）共通インデックス予測子に基づいて共通インデックス・シーケンスを発生する、（ｃ）共通インデックス・シーケンスに対してスイープ動作を適用する、そして（ｄ）ローカル回帰モデルを見出す。
【００６９】
ブロック６１２において、リデューサーは、マッパーからの出力を集約して、タスク結果（例えばグローバル回帰モデル）を決定する。タスク結果は、異なる実施形態において様々に変動する可能性がある。例えばタスク結果は、解決しようとする問題によって単純または複雑なものであり得る。いくつかの実施形態では、Ｍ個のローカル回帰モデルをマッパーからリデューサーに送信してグローバル回帰モデルを識別する。
【００７０】
クラウド・コンピューティング
本開示はクラウド・コンピューティングに関する詳細な記述を含むが、本明細書に述べる教示の実施はクラウド・コンピューティング環境に限定されないことは予め理解されるであろう。本発明の実施形態は、現在既知であるかまたは今後開発される他のいかなるタイプのコンピューティング環境とも関連付けて実施することができる。
【００７１】
クラウド・コンピューティングは、サービス配信の回帰モデルであり、構成可能コンピューティング・リソースの共有プール（例えばネットワーク、ネットワーク帯域幅、サーバ、処理、メモリ、記憶装置、アプリケーション、仮想マシン、およびサービス）に対して便利なオンデマンド・ネットワーク・アクセスを可能とし、管理上の労力またはサービス・プロバイダとの相互作用を最小限に抑えながら、迅速にプロビジョニング（provision）およびリリースすることができる。このクラウド回帰モデルは、少なくとも５つの特徴、少なくとも３つのサービス回帰モデル、および少なくとも４つの展開回帰モデルを含むことができる。
【００７２】
特徴は以下の通りである。
【００７３】
オンデマンド・セルフサービス：クラウド消費者は、必要に応じて自動的に、サーバ時間およびネットワーク記憶装置等のコンピューティング機能を一方的にプロビジョニングすることができ、サービス・プロバイダとの人の相互作用は必要ない。
【００７４】
広範なネットワーク・アクセス：機能は、ネットワークを介して利用可能であり、異種のシック（thick）またはシン（thin）・クライアント・プラットフォーム（例えば移動電話、ラップトップ・コンピュータ、およびＰＤＡ）による使用を推進する標準的な機構を介してアクセスされる。
【００７５】
リソースのプール：プロバイダのコンピューティング・リソースはプールされて、マルチテナント回帰モデルを用いて多数の消費者に供給され、異なる物理リソースおよび仮想リソースが需要に応じて動的に割り当ておよび再割り当てされる。一般に消費者は提供されるリソースの正確な位置について制御しないし知ることもないが、もっと高い抽象レベルでは位置を指定可能であり得るという点で、位置独立の感覚がある。
【００７６】
素早い順応性：機能は、場合によっては自動的に、素早くかつ順応性高くプロビジョニングして迅速にスケールアウトし、素早くリリースして迅速にスケールインすることができる。消費者にとって、プロビジョニングに利用可能な機能は無限のように見えることが多く、いつでもいかなる量でも購入することができる。
【００７７】
測定されたサービス：クラウド・システムは、サービスのタイプ（例えば記憶装置、処理、帯域幅、およびアクティブなユーザ・アカウント）に適した一定の抽象レベルで計測機能を活用することで、リソース使用を自動的に制御し最適化する。リソース使用を監視、制御、および報告することで、利用されたサービスのプロバイダおよび消費者の双方に透明性を与えることができる。
【００７８】
サービス回帰モデルは以下の通りである。
【００７９】
サース（ＳａａＳ：Software as a Service）：消費者に提供される機能は、クラウド・インフラストラクチャ上で動作しているプロバイダのアプリケーションを用いることである。アプリケーションは、ウェブ・ブラウザ等のシン・クライアント・インタフェース（例えばウェブ・ベースの電子メール）を介して様々なクライアント・デバイスからアクセス可能である。消費者は、ネットワーク、サーバ、オペレーティング・システム、記憶装置、または個々のアプリケーション機能をも含めて、基礎にあるクラウド・インフラストラクチャを管理することも制御することもないが、例外的にあり得るのは、限られたユーザ固有のアプリケーション構成設定である。
【００８０】
パース（ＰａａＳ：Platform as a Service）：消費者に提供される機能は、プロバイダによりサポートされるプログラミング言語およびツールを用いて生成された、消費者が生成または取得したアプリケーションを、クラウド・インフラストラクチャ上に展開することである。消費者は、ネットワーク、サーバ、オペレーティング・システム、または記憶装置を含む、基礎にあるクラウド・インフラストラクチャを管理することも制御することもないが、展開したアプリケーションを制御し、場合によってはアプリケーション・ホスティング環境構成も制御する。
【００８１】
イアース（ＩａａＳ：Infrastructure as a Service）：消費者に提供される機能は、消費者が、オペレーティング・システムおよびアプリケーションを含み得る、任意のソフトウェアを展開および実行することができる処理、記憶装置、ネットワーク、および他の基本的なコンピューティング・リソースをプロビジョニングすることである。消費者は、基礎にあるクラウド・インフラストラクチャを管理することも制御することもないが、オペレーティング・システム、記憶装置、展開したアプリケーションを制御し、場合によってはネットワーク・コンポーネント（例えばホスト・ファイアウォール）の選択において限られた制御を有する。
【００８２】
展開回帰モデルは以下の通りである。
【００８３】
プライベート・クラウド：クラウド・インフラストラクチャは１つの組織のためにのみ操作される。これは、その組織または第三者によって管理することができ、構内または構外に存在し得る。
【００８４】
コミュニティ・クラウド：クラウド・インフラストラクチャはいくつかの組織によって共有され、共通の関心事（例えば任務、セキュリティ要求、政策、およびコンプライアンスの問題）を持つ特定のコミュニティをサポートする。これは、その組織または第三者によって管理することができ、構内または構外に存在し得る。
【００８５】
パブリック・クラウド：クラウド・インフラストラクチャは、一般大衆または大きい業界団体に利用可能とされ、クラウド・サービスを販売する組織によって所有される。
【００８６】
ハイブリッド・クラウド：クラウド・インフラストラクチャは、２つ以上のクラウド（プライベート、コミュニティ、またはパブリック）の複合であり、独自のエンティティのままであるが、データおよびアプリケーションのポータビリティを可能とする標準化技術または独自の技術によって結合される（例えば、クラウド間でのロード・バランシングのめのクラウド・バースト（cloud bursting））。
【００８７】
クラウド・コンピューティング環境はサービス指向型であり、ステートレス（statelessness）、低結合、モジュール性、および意味相互運用性に焦点を当てている。クラウド・コンピューティングの中核は、相互接続されたノードのネットワークを含むインフラストラクチャである。
【００８８】
ここで図７を参照すると、クラウド・コンピューティング・ノードの一例の概略が示されている。クラウド・コンピューティング・ノード７１０は、適切なクラウド・コンピューティング・ノードの一例に過ぎず、本明細書に記載する本発明の実施形態の使用または機能性の範囲について限定を示唆することは意図していない。ともかく、クラウド・コンピューティング・ノード７１０は、上述の機能性のいずれも実施または実行あるいはその両方を行うことができる。
【００８９】
クラウド・コンピューティング・ノード７１０には、コンピュータ・システム／サーバ７１２があり、これは多数の他の汎用または特殊用途コンピューティング・システム環境または構成と共に動作する。コンピュータ・システム／サーバ７１２と共に用いるのに適切であり得る周知のコンピューティング・システム、環境、または構成あるいはそれら全ての例は、限定ではないが、パーソナル・コンピュータ・システム、サーバ・コンピュータ・システム、シン・クライアント、シック・クライアント、ハンドヘルド・デバイスまたはラップトップ・デバイス、マルチプロセッサ、システム、マイクロプロセッサ・ベースのシステム、セット・トップ・ボックス、プログラマブル家庭用電子機器、ネットワークＰＣ、ミニコンピュータ・システム、メインフレーム・コンピュータ・システム、および上記のシステムまたはデバイスのいずれかを含む分散型クラウド・コンピューティング環境等を含む。
【００９０】
コンピュータ・システム／サーバ７１２は、コンピュータ・システムによって実行される、プログラム・モジュール等のコンピュータ・システム実行可能命令の一般的な状況で記述することができる。一般に、プログラム・モジュールは、特定のタスクを実行するかまたは特定の抽象データ・タイプを実施するルーチン、プログラム、オブジェクト、コンポーネント、論理、データ構造等を含むことができる。コンピュータ・システム／サーバ７１２は、通信ネットワークを介してリンクされたリモート処理デバイスによってタスクが実行される分散型クラウド・コンピューティング環境において実現可能である。分散型クラウド・コンピューティング環境において、プログラム・モジュールは、メモリ記憶デバイスを含むローカルおよびリモートの双方のコンピュータ・システム記憶媒体に配置することができる。
【００９１】
図７に示すように、クラウド・コンピューティング・ノード７１０におけるコンピュータ・システム／サーバ７１２は、汎用コンピューティング・デバイスの形態で示す。コンピュータ・システム／サーバ７１２のコンポーネントは、限定ではないが、１つまたは複数のプロセッサまたは処理ユニット７１６と、システム・メモリ７２８と、システム・メモリ７２８を含む様々なシステム・コンポーネントをプロセッサまたは処理ユニット７１６に結合するバス７１８と、を含むことができる。
【００９２】
バス７１８は、多種多様なバス・アーキテクチャのいずれかを用いた、メモリ・バスまたはメモリ・コントローラ、周辺バス、アクセラレーテッド・グラフィックス・ポート（ＡＧＰ）、およびプロセッサまたはローカル・バスを含むいくつかのタイプのバス構造のいずれかの１つまたは複数を表す。限定ではなく一例として、そのようなアーキテクチャは、業界標準アーキテクチャ（ＩＳＡ：Industry Standard Architecture）・バス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）・バス、エンハンストＩＳＡ（ＥＩＳＡ）バス、ベザ（ＶＥＳＡ：Video Electronics Standards Association）ローカル・バス、および周辺コンポーネント相互接続（ＰＣＩ）バスを含む。
【００９３】
コンピュータ・システム／サーバ７１２は典型的に、多種多様なコンピュータ・システム読み取り可能媒体を含む。そのような媒体は、コンピュータ・システム／サーバ７１２によってアクセス可能ないずれかの利用可能媒体であればよく、揮発性および不揮発性の媒体、着脱可能および固定（non-removable）の媒体の双方を含む。
【００９４】
システム・メモリ７２８は、ランダム・アクセス・メモリ（ＲＡＭ）７３０またはキャッシュ・メモリ７３２あるいはその両方等、揮発性メモリの形態のコンピュータ・システム読み取り可能媒体を含むことができる。コンピュータ・システム／サーバ７１２は更に、他の着脱可能／固定、揮発性／不揮発性のコンピュータ・システム読み取り可能媒体を含んでもよい。一例に過ぎないが、固定の不揮発性磁気媒体（図示せず。典型的には「ハード・ドライブ」と呼ばれる）からの読み取りおよびこれへの書き込みのために、記憶システム７３４を設けることができる。図示しないが、着脱可能な不揮発性磁気ディスク（例えば「フレキシブルディスク」）からの読み取りおよびこれへの書き込みのための磁気ディスク・ドライブと、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、または他の光媒体等の着脱可能な不揮発性光ディスクへの読み取りおよびこれへの書き込みのための光ディスク・ドライブと、を設けることができる。そのような例では、各々を１つまたは複数のデータ媒体インタフェースによってバス７１８に接続することができる。以下で更に図示し記載するように、メモリ７２８は、本発明の実施形態の機能を実行するように構成されたプログラム・モジュールのセット（少なくとも１つ）を有する少なくとも１つのプログラムを含んでもよい。
【００９５】
限定ではなく一例として、メモリ７２８に、プログラム・モジュール７４２のセット（少なくとも１つ）を有するプログラム／ユーティリティ７４０を記憶することができ、更に、オペレーティング・システム、１つまたは複数のアプリケーション・プログラム、他のプログラム・モジュール、およびプログラム・データも記憶することができる。オペレーティング・システム、１つまたは複数のアプリケーション・プログラム、他のプログラム・モジュール、およびプログラム・データの各々、またはそれらの何らかの組み合わせは、ネットワーキング環境の実施を含むことができる。プログラム・モジュール７４２は一般に、本明細書に記載したような本発明の実施形態の機能または方法あるいはその両方を実行する。
【００９６】
また、コンピュータ・システム／サーバ７１２は、キーボード、ポインティング・デバイス等の１つまたは複数の外部デバイス７１４、ディスプレイ７２４等、ユーザとコンピュータ・システム／サーバ７１２との相互作用を可能にする１つまたは複数のデバイス、またはコンピュータ・システム／サーバ７１２が１つまたは複数の他のコンピューティング・デバイスと通信することを可能とするいずれかのデバイス（例えばネットワーク・カード、モデム等）、あるいはそれら全てと通信を行うことができる。このような通信は、入出力（Ｉ／Ｏ）インタフェース７２２を介して実行することができる。更に、コンピュータ・システム／サーバ７１２は、ネットワーク・アダプタ７２０を介して、ローカル・エリア・ネットワーク（ＬＡＮ）、一般ワイド・エリア・ネットワーク（ＷＡＮ）、またはパブリック・ネットワーク（例えばインターネット）あるいはそれら全てのような１つまたは複数のネットワークと通信することができる。図示のように、ネットワーク・アダプタ７２０は、バス７１８を介してコンピュータ・システム／サーバ７１２の他のコンポーネントと通信する。図示しないが、コンピュータ・システム／サーバ７１２と関連付けて、他のハードウェア・コンポーネントまたはソフトウェア・コンポーネントあるいはその両方も使用可能であることは理解されよう。その例は、限定ではないが、マイクロコード、デバイス・ドライバ、冗長処理ユニット、外部ディスク・ドライブ・アレイ、ＲＡＩＤシステム、テープ・ドライブ、およびデータ・アーカイブ記憶システム等を含む。
【００９７】
ここで図８を参照すると、例示的なクラウド・コンピューティング環境８５０が示されている。図示のように、クラウド・コンピューティング環境８５０は１つまたは複数のクラウド・コンピューティング・ノード７１０を含み、これは、クラウド消費者により用いられるローカル・コンピューティング・デバイスと通信を行うことができる。このデバイスは、例えばパーソナル・デジタル・アシスタント（ＰＤＡ）または携帯電話８５４Ａ、デスクトップ・コンピュータ８５４Ｂ、ラップトップ・コンピュータ８５４Ｃ、または自動車コンピュータ・システム８５４Ｎあるいはそれら全てである。ノード７１０は、相互に通信を行うことも可能である。それらは、上述したようなプライベート・クラウド、コミュニティ・クラウド、パブリック・クラウド、もしくはハイブリッド・クラウド、またはそれらの組み合わせ等の１つまたは複数のネットワークに、物理的または仮想的にグループ化（図示せず）することができる。これによって、クラウド・コンピューティング環境８５０は、インフラストラクチャ、プラットフォーム、またはソフトウェアあるいはそれら全てをサービスとして提供することができ、それらについてクラウド消費者はローカル・コンピューティング・デバイス上にリソースを維持する必要はない。図８に示すコンピューティング・デバイス８５４Ａ〜８５４Ｎのタイプが例示のみを意図していること、更に、コンピューティング・ノード７１０およびクラウド・コンピューティング環境８５０がいずれかのタイプのネットワークまたはネットワークアドレス可能接続あるいはその両方を介して（例えばウェブ・ブラウザを用いて）いかなるタイプのコンピュータ化デバイスとも通信可能であることは理解されよう。
【００９８】
ここで図９を参照すると、クラウド・コンピューティング環境８５０（図８）が提供する機能抽象レイヤ集合が示されている。図９に示すコンポーネント、レイヤ、および機能が例示に過ぎず、本発明の実施形態がこれらに限定されないことは予め理解されるであろう。図示のように、以下のレイヤおよび対応する機能が提供される。
【００９９】
ハードウェアおよびソフトウェア・レイヤ９６０は、ハードウェアおよびソフトウェア・コンポーネントを含む。ハードウェア・コンポーネントの例は、一例ではＩＢＭ（Ｒ）ｚＳｅｒｉｅｓ（Ｒ）システムであるメイン・フレーム、一例ではＩＢＭ（Ｒ）ｐＳｅｒｉｅｓ（Ｒ）システムであるリスク（ＲＩＳＣ：Reduced Instruction Set Computer）アーキテクチャ・ベースのサーバ、ＩＢＭｘＳｅｒｉｅｓ（Ｒ）システム、ＩＢＭＢｌａｄｅＣｅｎｔｅｒ（Ｒ）システム、記憶デバイス、ネットワークおよびネットワーキング・コンポーネントを含む。ソフトウェア・コンポーネントの例は、一例ではＩＢＭ  ＷｅｂＳｐｈｅｒｅ（Ｒ）アプリケーション・サーバ・ソフトウェアであるネットワーク・アプリケーション・サーバ・ソフトウェア、一例ではＩＢＭ  ＤＢ２（Ｒ）データベース・ソフトウェアであるデータベース・ソフトウェアを含む。（ＩＢＭ、ｚＳｅｒｉｅｓ、ｐＳｅｒｉｅｓ、ｘＳｅｒｉｅｓ、ＢｌａｄｅＣｅｎｔｅｒ、ＷｅｂＳｐｈｅｒｅ、およびＤＢ２は、世界の多くの管轄区域で登録されたインターナショナル・ビジネス・マシーンズ・コーポレーションの商標である。）
【０１００】
仮想化レイヤ９６２は抽象レイヤを提供し、ここから以下の仮想エンティティを提供することができる。その例には、仮想サーバ、仮想記憶装置、仮想プライベート・ネットワークを含む仮想ネットワーク、仮想アプリケーションおよびオペレーティング・システム、ならびに仮想クライアントが挙げられる。
【０１０１】
一例において、管理レイヤ９６４は以下に記載する機能を提供することができる。リソース・プロビジョニングは、クラウド・コンピューティング環境内でタスクを実行するために利用されるコンピューティング・リソースおよび他のリソースの動的な調達を行う。計測および価格付けは、クラウド・コンピューティング環境内でリソースが利用される際にコスト追跡を行い、これらのリソースの消費について課金または送り状作成を行う。一例では、これらのリソースはアプリケーション・ソフトウェア・ライセンスを含む場合がある。セキュリティは、クラウド消費者およびタスクについてアイデンティティ検証を行い、更にデータおよび他のリソースの保護を行う。ユーザ・ポータルは、消費者およびシステム管理者にクラウド・コンピューティング環境へのアクセスを与える。サービス・レベル管理は、必要なサービス・レベルを満足させるようにクラウド・コンピューティング・リソースの割り当ておよび管理を行う。サービス・レベル合意書（ＳＬＡ）計画および実行は、ＳＬＡに従って、将来の必要性が予測されるクラウド・コンピューティング・リソースのための事前取り決めおよびその調達を行う。
【０１０２】
作業負荷レイヤ９６６は、クラウド・コンピューティング環境を利用することができる機能の例を与える。このレイヤから提供され得る作業負荷および機能の例は、マッピングおよびナビゲーション、ソフトウェア開発およびライフサイクル管理、仮想教室教育配信、データ分析処理、トランザクション処理、ならびに回帰モデルの計算を含む。
【０１０３】
従って、いくつかの実施形態において、本明細書に記載した実施形態に従って回帰モデルの計算を実施するソフトウェアまたはプログラムが、クラウド環境におけるサービスとして提供される。
【０１０４】
クラウド環境においていくつかの実施形態を実施する。いくつかの代替的な実施形態はクラウド環境では実施されない。
【０１０５】
追加の実施形態の詳細
当業者によって認められるように、本発明の態様は、システム、方法、またはコンピュータ・プログラムとして具現化することができる。従って、本発明の態様は、全体的にハードウェアの実施形態、全体的にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、または、ソフトウェアおよびハードウェアの態様を組み合わせた実施形態という形態を取ることができ、それらは全て本明細書において、「回路」、「モジュール」、または「システム」と一般的に称することができる。更に、本発明の態様は、具現化されたコンピュータ読み取り可能プログラム・コードを有する１つまたは複数のコンピュータ読み取り可能媒体（複数の媒体）において具現化されたコンピュータ・プログラムの形態を取ることも可能である。
【０１０６】
１つまたは複数のコンピュータ読み取り可能媒体（複数の媒体）のあらゆる組み合わせを利用することができる。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。コンピュータ読み取り可能記憶媒体は例えば、限定ではないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、デバイス、または前述のもののいずれかの適切な組み合わせとすることができる。コンピュータ読み取り可能記憶媒体の更に具体的な例（非網羅的な列挙）は、以下を含む。すなわち、１つまたは複数のワイヤを有する電気的接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、携帯型コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光記憶デバイス、磁気記憶デバイス、固体メモリ、磁気テープ、または前述のもののいずれかの適切な組み合わせである。この文書の文脈において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを含有または記憶することが可能ないずれかの有形の（tangible）媒体とすることができる。
【０１０７】
コンピュータ読み取り可能信号媒体は、例えばベースバンドにおいてまたは搬送波の一部として、具現化されたコンピュータ読み取り可能プログラム・コードを有する伝播データ信号を含むことができる。かかる伝播信号は様々な形態のいずれかを取ることができ、それらは限定ではないが、電磁、光、またはそれらのいずれかの適切な組み合わせを含む。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体でないが、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを伝達、伝播、または転送することが可能ないずれかのコンピュータ読み取り可能媒体とすることができる。
【０１０８】
コンピュータ読み取り可能媒体上で具現化されるプログラム・コードは、限定ではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、または前述のもののいずれかの適切な組み合わせを含むいずれかの適切な媒体を用いて伝送することができる。
【０１０９】
本発明の態様の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のオブジェクト指向プログラミング言語および「Ｃ」プログラミング言語または同様のプログラミング言語等の従来の手順プログラミング言語を含む１つまたは複数のプログラミング言語のいずれかの組み合わせにおいて記述することができる。プログラム・コードは、全体的にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンドアロンのソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でおよび部分的にリモート・コンピュータ上で、または全体的にリモート・コンピュータもしくはサーバ上で、実行することができる。後者の場合、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを介してユーザのコンピュータに接続することができ、または、接続は、（例えばインターネット・サービス・プロバイダを用いてインターネットを介して）外部コンピュータに対して行うことができる。
【０１１０】
本発明の実施形態に従った方法、装置（システム）、およびコンピュータ・プログラムのフローチャート図またはブロック図あるいはその両方を参照して、本発明の実施形態の態様について以下に記載する。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実施可能であることは理解されよう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊目的コンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供されて機械を生成することができ、これによって、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサによって実行される命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施するための手段を生成するようになっている。
【０１１１】
また、これらのコンピュータ・プログラム命令はコンピュータ読み取り可能媒体に記憶することができ、これによって、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスに特定の方法で機能するように指示することができ、これにより、コンピュータ読み取り可能媒体に記憶された命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施する命令を含む製造品を生成するようになっている。
【０１１２】
また、コンピュータ・プログラム命令を、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスにロードして、そのコンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作処理（例えば動作またはステップ）を実行させてコンピュータ実施プロセスを生成することができ、これによって、コンピュータまたは他のプログラマブル装置上で実行する命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施するためのプロセスを提供するようになっている。
【０１１３】
更に、前述の動作を実施するコードは、ハードウェア論理または回路（例えば集積回路チップ、プログラマブル・ゲート・アレイ（ＰＧＡ）、特定用途向けＩＣ（ＡＳＩＣ）等）で実施することができる。ハードウェア論理をプロセッサに結合して動作を実行することができる。
【０１１４】
明示的に指定する場合を除いて、相互に連通しているデバイスは、相互に連続的に連通している必要はない。更に、相互に連通しているデバイスは、直接にまたは１つまたは複数の媒介部を介して間接的に通信を行うことができる。
【０１１５】
相互に連通したいくつかのコンポーネントを有する実施形態の記載は、そのようなコンポーネントが全て必須であることを示唆するわけではない。むしろ、本発明の幅広い可能な実施形態を例示するために、多種多様な任意選択のコンポーネントを記載している。
【０１１６】
更に、プロセス・ステップ、方法ステップ、アルゴリズム等は、連続した順序で記載することができるが、そのようなプロセス、方法、およびアルゴリズムは代替的な順序で動作するように構成することも可能である。換言すると、記載され得るステップのいかなるシーケンスまたは順序も、必ずしもそれらのステップをその順序で実行することを要求するわけではない。本明細書に記載するプロセスのステップは、他のいずれの順序の実施においても実行可能である。更に、いくつかのステップは同時に実行される場合もある。
【０１１７】
本明細書において単一のデバイスまたは物品を記載する場合、単一のデバイス／物品の代わりに２つ以上のデバイス／物品（それらが共働するものであろうとなかろうと）を使用可能であることは容易に認められよう。同様に、本明細書において２つ以上のデバイス（それらが共働するものであろうとなかろうと）または物品を記載する場合、２つ以上のデバイスもしくは物品の代わりに単一のデバイス／物品を使用可能であること、または示した数のデバイスもしくはプログラムの代わりに異なる数のデバイス／物品を使用可能であることは、容易に明らかとなろう。デバイスの機能性または特性（features）あるいはその両方は、そのような機能性／特性を有すると明示的に記載されていない１つまたは複数の他のデバイスによって代替的に具現化することができる。従って、本発明の他の実施形態は、デバイス自体を含むことは必須ではない。
【０１１８】
フロー図に示した動作は、いくつかのイベントが一定の順序で発生することを示す。代替的な実施形態では、いくかの動作は異なる順序で実行されるか、変更されるか、または除去される場合がある。また、動作を上述の論理に追加することができ、その場合も記載した実施形態に適合させることができる。更に、本明細書に記載した動作は順次発生することがあり、または、いくつかの動作は並列処理される場合がある。また、動作は、単一の処理ユニットによってまたは分散型処理ユニットによって実行することができる。
【０１１９】
本明細書において用いた用語は、特定の実施形態を記載する目的のためだけのものであり、本発明を限定することは意図していない。本明細書において用いたように、単数形「１つの（a）、（an）、（the）」は、文脈によって明らかに他の場合が示されない限り、複数形を含むことが意図されている。また、「含む（comprises）」または「含んでいる（comprising）」という言葉あるいはその両方は、本明細書において用いられた場合、述べた特性、整数、ステップ、動作、要素、またはコンポーネントあるいはそれら全ての存在を規定するが、１つまたは複数の他の特性、整数、ステップ、動作、要素、コンポーネント、またはそれらのグループあるいはそれら全ての存在または追加を除外するものではないことは、理解されよう。
【０１２０】
「一実施形態」、「実施形態」、「複数の実施形態」、「その実施形態」、「それらの実施形態」、「１つまたは複数の実施形態」、「いくつかの実施形態」、および「１つの実施形態」という言葉は、明示的に指定する場合を除いて、「本発明（複数の本発明）の１つまたは複数の（ではあるが全てではない）実施形態」を意味する。
【０１２１】
「含んでいる（including）」、「含んでいる（comprising）」、「有している（having）」という言葉およびそれらの変形は、明示的に指定する場合を除いて、「限定ではないが、以下を含む」という意味である。
【０１２２】
明示的に指定する場合を除いて、項目の列挙は、それらの項目のいずれかまたは全てが相互に排他的であることを示唆するものではない。
【０１２３】
以下の特許請求の範囲における全てのミーンズまたはステップ・プラス・ファンクション要素の対応する構造、材料、行為、および均等物は、具体的に特許請求したような他の特許請求した要素と組み合わせて機能を実行するためのいずれかの構造、材料、または行為を含むことが意図されている。本発明の実施形態の記載は、例示および記述の目的のために提示したが、網羅的であることや、開示した形態に本発明を限定することは、意図していない。本発明の範囲から逸脱することなく、当業者には多くの変更および変形が明らかであろう。実施形態は、本開示の原理および実際的な用途を最良に説明するため、更に、想定される特定の用途に適した様々な変更と共に様々な実施形態に関して当業者が本発明を理解することを可能とするために、選択し記載したものである。
【０１２４】
図面におけるフローチャートおよびブロック図は、本発明の様々な実施形態に従ったシステム、方法、およびコンピュータ・プログラムの可能な実施のアーキテクチャ、機能性、および動作を例示する。この点で、フローチャートまたはブロック図における各ブロックは、規定された論理機能（複数の論理機能）を実施するための１つまたは複数の実行可能命令を含むコードのモジュール、セグメント、または一部を表すことができる。また、いくつかの代替的な実施において、ブロックに明記した機能は、図面に明記した順序通りでなく発生する場合があることに留意すべきである。例えば、関与する機能性に応じて、連続して示した２つのブロックは実際には実質的に同時に実行されることがあり、またはブロックは時に逆の順序で実行される場合がある。また、ブロック図またはフローチャート図あるいはその両方の各ブロック、およびブロック図またはフローチャート図あるいはその両方におけるブロックの組み合わせは、規定された機能もしくは行為を実行する特殊目的ハードウェア・ベースのシステム、または特殊目的ハードウェアおよびコンピュータ命令の組み合わせによって実施可能であることに留意すべきである。
【０１２５】
本発明の実施形態の前述の記載は、例示および記述の目的のために提示したものである。網羅的であることや、開示した形態そのものに本発明を限定することは意図していない。上述の教示に照らし合わせて、多くの変更および変形が可能である。実施形態の範囲は、この詳細に記載によって限定されるのではなく、添付の特許請求の範囲によって限定されることが意図される。この明細書、例示、およびデータは、実施形態の構成の製造および使用の完全な記述を提供する。本発明の範囲から逸脱することなく多くの実施形態を生成可能であるので、実施形態は、添付の特許請求の範囲または全ての以降提出される特許請求の範囲およびそれらの均等物において存在する。
【図１】
2016507093.tif 000011
【図２】
2016507093.tif 000012
【図３】
2016507093.tif 000013
【図４】
2016507093.tif 000014
【図５】
2016507093.tif 000015
【図６Ａ】
2016507093.tif 000016
【図６Ｂ】
2016507093.tif 000017
【図７】
2016507093.tif 000018
【図８】
2016507093.tif 000019
【図９】
2016507093.tif 000020
【手続補正書】
【提出日】平成27年8月6日(2015.8.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
レコードの処理データ集合を生成することであって、前記レコードの各々が、実際のサブタスク集合からの１つのサブタスクに固有のデータを含み、更に、前記実際のサブタスク集合によって共有されるデータに対する参照を含み、前記レコードの数が、前記実際のサブタスク集合内の前記実際のサブタスクの数に相当する、ことと、
マッパー集合における各マッパーによって、前記処理データ集合の前記レコードの１つを受信することと、
前記レコードの前記受信した１つを用いて割り当てられたサブタスクを実行して出力を発生させることと、
単一のリデューサーによって、前記マッパー集合内の各マッパーからの前記出力を集約してタスク結果を決定することと、
を含むコンピュータ・システムによって実行される方法。
【請求項２】
元のデータセットの少なくとも１つの特徴に基づいて、潜在的サブタスクの最大数を計算することと、
前記実際のサブタスクの実行に利用可能な前記マッパー集合内のマッパー数と前記潜在的サブタスクの最大数とに基づいて、実行される前記実際のタスク集合内の実際のサブタスク数を計算することと、
を更に含む、請求項１に記載の方法。
【請求項３】
Ｍ個の実際のサブタスクとして示される前記実際のサブタスク数を計算することを更に含み、Ｍ＝２ｍであり、Ｍ≦Ｌおよびｍ＜ｋ−ｌであり、Ｌは、前記実際のサブタスクの計算に利用可能な前記マッパー集合内の前記マッパー数であり、ｋは予測子の数である、請求項２に記載の方法。
【請求項４】
前記予測子を、先行インデックス予測子と共通インデックス予測子とに分割することを更に含む、請求項３に記載の方法。
【請求項５】
グローバル検索シーケンスをＭ個の多数のローカル検索シーケンスに分割することと、
前記ローカル検索シーケンスの各々について、前記先行インデックス予測子から先行インデックス・シーケンスを識別することと、
Ｍ個のレコードを用いて一時入力ファイルを生成することと、を更に含み、前記レコードの各々が先行インデックス・シーケンスを含み、前記レコードの各々が、共通インデックス予測子およびスイープ動作を適用する行列に対する参照を含む、請求項４に記載の方法。
【請求項６】
前記マッパー集合内の各マッパーにおいて、
前記ローカル検索シーケンスの１つの先行インデックス・シーケンスを受信することと、
処理データ集合の各レコードにおける前記参照を介して共通インデックス予測子および前記行列を受信することと、
前記共通インデックス予測子を用いて共通インデックス・シーケンスを発生させることと、
前記先行インデックス・シーケンスに従って前記行列にスイープ動作を実行することと、
前記共通インデックス・シーケンスに従って、結果として得られた前記行列にスイープ動作を実行することと、
前記出力を識別することと、を更に含み、前記出力がローカル回帰モデルである、請求項５に記載の方法。
【請求項７】
前記共通インデックス・シーケンスを送信することなく、前記先行インデックス・シーケンスを前記マッパー集合内の各マッパーに送信することが、ネットワーク・トラフィックを軽減する、請求項６に記載の方法。
【請求項８】
前記タスク結果がグローバル回帰モデルである、請求項６に記載の方法。
【請求項９】
クラウド環境におけるサービスとしてソフトウェアが提供される、請求項１に記載の方法。
【請求項１０】
コンピュータの少なくとも１つのプロセッサによって実行される場合に、請求項１ないし請求項７までのいずれかに記載の方法のすべてのステップを実行させるよう構成されているコンピュータ・プログラム。
【請求項１１】
サース（ＳａａＳ：Software as a Service）が、前記コンピュータ・プログラムの動作を実行するように構成されている、請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
コンピュータ・システムであって、
プロセッサと、
前記プロセッサに接続された記憶デバイスと、を備え、前記記憶デバイスがプログラムを記憶しており、前記プロセッサが前記プログラムの命令を実行して動作を実行するように構成され、
前記動作が請求項１ないし請求項７までのいずれかに記載の方法のすべてのステップを実行するよう構成されているコンピュータ・システム。
【請求項１３】
サース（ＳａａＳ：Software as a Service）が、前記システムの動作を実行するように設けられている、請求項１２に記載のコンピュータ・システム。
【国際調査報告】
2016507093.tif 000021
2016507093.tif 000022