【手続補正書】
【提出日】平成29年9月22日(2017.9.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
推奨演算を最適化する、コンピュータで実行可能な方法であって、
互いに素な第１の頂点の集合と、第２の頂点の集合と、を含む２部グラフを、記憶装置から取得するステップと、
前記第１の頂点の集合から前記第２の頂点の集合への第１のグラフの探査を、プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、
前記第１の頂点の集合の、第１の互いに素な部分集合を各プロセッサのみに割り当てる  ことがさらに含まれ、前記第１の互いに素な部分集合の割り当てには、
前記第１の頂点の集合内の頂点の総数をプロセッサの総数で割ることにより、各プロセッサに割り当てられる最大数の頂点を推定することと、
前記推定された最大数に基づいて、前記第１の頂点の集合を前記プロセッサの集合の間で割り当てることと、がさらに含まれる、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第１の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第１の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第１のグラフの探査を実行するステップと、
前記第２の頂点の集合から前記第１の頂点の集合への第２のグラフの探査を、前記プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第２の頂点の集合のみを割り当てることであって、前記第２の頂点の集合の、第２の互いに素な部分集合を、前記プロセッサの集合内の同一の前記各プロセッサのみに割り当てることが含まれ、
前記第２の互いに素な頂点の部分集合と前記第１の互いに素な部分集合には共通する頂点がなく、
前記第２の互いに素な頂点の部分集合の割り当てが、前記第２の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第２の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第２の互いに素な部分集合から、最先端の頂点の集合を選択することと、
前記各プロセッサに関して選択された前記最先端の頂点の集合から、前記２部グラフの１つ以上の辺によって前記最先端の頂点の集合のいずれかに関連する、前記第１の頂点の集合の、第２の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第２のグラフの探査を実行するステップと、
前記第１の頂点の集合から前記第２の頂点の集合への第３のグラフの探査を、前記プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、前記第１の頂点の集合の、第３の互いに素な部分集合を、同一の前記各プロセッサのみに割り当てることがさらに含まれ、
前記第３の互いに素な頂点の部分集合と前記第２の互いに素な部分集合には共通する頂点がなく、
前記第３の互いに素な頂点の部分集合の割り当てが、前記第３の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第３の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第３の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第３のグラフの探査を実行するステップと、
少なくとも、前記第２の頂点の集合の、前記第３の終点の部分集合の計数に基づいて推奨を生成するステップと、を含む方法。
【請求項２】
前記各プロセッサに関して選択された前記最先端の頂点の集合からの前記グラフの探査には、
プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空ではない場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「１」となり、プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空の場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「０」となるよう、ビットマスク「ＭＵ」を生成することと、
ＭＵ［ｐ］が「１」の場合、グラフ探査解析を実行するよう前記プロセッサ「ｐ」に命令することと、が含まれる、請求項１に記載の方法。
【請求項３】
頂点の各集合の互いに素な部分集合を前記各プロセッサに割り当てるステップには、
式「（ｕｍａｘ-ｕｍｉｎ＋１）／Ｐ」に従って、各プロセッサに割り当てられる頂点の最大数を推定することであって、「Ｐ」はプロセッサの数であり、「ｕｍａｘ」は頂点∈Ｕに関する最大整数識別子であり、「ｕｍｉｎ」は頂点∈Ｕに関する最小整数識別子であり、「Ｕ」は前記第１の頂点の集合を表す、ことと、
各プロセッサに割り当てられる、前記推定された頂点の最大数に基づいて、前記頂点の各集合を前記プロセッサの集合の間で均一に分割することと、がさらに含まれる、請求項１に記載の方法。
【請求項４】
頂点の各集合の互いに素な部分集合を各プロセッサに割り当てるステップには、
前記頂点の各集合を前記プロセッサの集合の間で非均一に分割することがさらに含まれる、請求項１に記載の方法。
【請求項５】
前記第１の頂点の集合は顧客を表し、前記第２の頂点の集合は商品を表し、前記生成された推奨は顧客に対する商品の推奨である、請求項１に記載の方法。
【請求項６】
次の探査に関して統計値「ｎｍｉｎ−ｓｒｃ」および「ｎｍａｘ−ｓｒｃ」の注釈を前記グラフに付けるステップであって、「ｎｍｉｎ−ｓｒｃ」は前記次の探査において源点として作用する頂点の集合の間で最小頂点ＩＤを指定し、「ｎｍａｘ−ｓｒｃ」は前記次の探査において源点として作用する前記頂点の集合の間で最大頂点ＩＤを指定する、注釈を付けるステップと、
各プロセッサに割り当てられる前記頂点が前記次のグラフ探査の際に最先端の頂点を含むかどうかを示すよう、ビットマスクを更新するステップと、がさらに含まれる、請求項１に記載の方法。
【請求項７】
少なくとも１つの追加のグラフ探査がさらに含まれ、前記少なくとも１つの追加のグラフ探査には、
前記少なくとも１つの追加のグラフ探査を実行する予定である前記プロセッサの集合の間で頂点の集合を割り当てることであって、前記頂点の集合の互いに素な部分集合を前記各プロセッサのみに割り当てることがさらに含まれる、頂点の集合の割り当てと、
前記各プロセッサのみに割り当てられた前記頂点の集合の前記互いに素な部分集合から、前記頂点の集合の、追加の終点の部分集合へのグラフを、各プロセッサによって探査することと、がさらに含まれる、請求項１に記載の方法。
【請求項８】
コンピュータにより実行されると、前記コンピュータが、推奨演算を最適化する方法を行う命令を格納する、コンピュータ可読記憶媒体であって、前記方法が、
互いに素な第１の頂点の集合と、第２の頂点の集合と、を含む２部グラフにおいて、前記第１の頂点の集合から前記第２の頂点の集合への第１のグラフの探査を、プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、
前記第１の頂点の集合の、第１の互いに素な部分集合を各プロセッサのみに割り当てる  ことがさらに含まれ、前記第１の互いに素な部分集合の割り当てには、
前記第１の頂点の集合内の頂点の総数をプロセッサの総数で割ることにより、各プロセッサに割り当てられる最大数の頂点を推定することと、
前記推定された最大数に基づいて、前記第１の頂点の集合を前記プロセッサの集合の間で割り当てることと、がさらに含まれる、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第１の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第１の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第１のグラフの探査を実行するステップと、
前記第２の頂点の集合から前記第１の頂点の集合への第２のグラフの探査を、前記プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第２の頂点の集合のみを割り当てることであって、前記第２の頂点の集合の、第２の互いに素な部分集合を、前記プロセッサの集合内の同一の前記各プロセッサのみに割り当てることが含まれ、
前記第２の互いに素な頂点の部分集合と前記第１の互いに素な部分集合には共通する頂点がなく、
前記第２の互いに素な頂点の部分集合の割り当てが、前記第２の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第２の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第２の互いに素な部分集合から、最先端の頂点の集合を選択することと、
前記各プロセッサに関して選択された前記最先端の頂点の集合から、前記２部グラフの１つ以上の辺によって前記最先端の頂点の集合のいずれかに関連する、前記第１の頂点の集合の、第２の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第２のグラフの探査を実行するステップと、
前記第１の頂点の集合から前記第２の頂点の集合への第３のグラフの探査を、前記プロセッサの集合によって実行するステップであって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、前記第１の頂点の集合の、第３の互いに素な部分集合を、同一の前記各プロセッサのみに割り当てることがさらに含まれ、
前記第３の互いに素な頂点の部分集合と前記第２の互いに素な部分集合には共通する頂点がなく、
前記第３の互いに素な頂点の部分集合の割り当てが、前記第３の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第３の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第３の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第３のグラフの探査を実行するステップと、
少なくとも、前記第２の頂点の集合の、前記第３の終点の部分集合の計数に基づいて推奨を生成するステップと、を含む、コンピュータ可読記憶媒体。
【請求項９】
前記各プロセッサに関して選択された前記最先端の頂点の集合からの前記グラフの探査には、
プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空ではない場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「１」となり、プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空の場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「０」となるよう、ビットマスク「ＭＵ」を生成することと、
ＭＵ［ｐ］が「１」の場合、グラフ探査解析を実行するよう前記プロセッサ「ｐ」に命令することと、が含まれる、請求項８に記載のコンピュータ可読記憶媒体。
【請求項１０】
頂点の各集合の互いに素な部分集合を前記各プロセッサに割り当てるステップには、
式「（ｕｍａｘ-ｕｍｉｎ＋１）／Ｐ」に従って、各プロセッサに割り当てられる頂点の最大数を推定することであって、「Ｐ」はプロセッサの数であり、「ｕｍａｘ」は頂点∈Ｕに関する最大整数識別子であり、「ｕｍｉｎ」は頂点∈Ｕに関する最小整数識別子であり、「Ｕ」は前記第１の頂点の集合を表す、ことと、
各プロセッサに割り当てられる、前記推定された頂点の最大数に基づいて、前記頂点の各集合を前記プロセッサの集合の間で均一に分割することと、がさらに含まれる、請求項８に記載のコンピュータ可読記憶媒体。
【請求項１１】
頂点の各集合の互いに素な部分集合を各プロセッサに割り当てるステップには、
前記頂点の各集合を前記プロセッサの集合の間で非均一に分割することがさらに含まれる、請求項８に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記第１の頂点の集合は顧客を表し、前記第２の頂点の集合は商品を表し、前記生成された推奨は顧客に対する商品の推奨である、請求項８に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記方法には少なくとも１つの追加のグラフ探査が含まれ、前記少なくとも１つの追加のグラフ探査には、
前記少なくとも１つの追加のグラフ探査を実行する予定である前記プロセッサの集合の間で頂点の集合を割り当てることであって、前記頂点の集合の互いに素な部分集合を前記各プロセッサのみに割り当てることがさらに含まれる、頂点の集合の割り当てと、
前記各プロセッサのみに割り当てられた前記頂点の集合の前記互いに素な部分集合から、前記頂点の集合の、追加の終点の部分集合へのグラフを、各プロセッサによって探査することと、がさらに含まれる、請求項８に記載のコンピュータ可読記憶媒体。
【請求項１４】
推奨演算を最適化する演算システムであって、
プロセッサの集合と、
前記プロセッサの集合と接続するコンピュータ可読媒体であって、その中に命令が格納され、前記命令が、前記プロセッサの集合により実行されると、前記プロセッサの集合が動作を実行する、コンピュータ可読媒体と、を含み、前記動作には、
互いに素な第１の頂点の集合と、第２の頂点の集合と、を含む２部グラフにおいて、前記第１の頂点の集合から前記第２の頂点の集合への第１のグラフの探査を実行する動作であって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、前記第１の頂点の集合の、第１の互いに素な部分集合を各プロセッサのみに割り当てることがさらに含まれ、前記第１の互いに素な部分集合の割り当てには、
前記第１の頂点の集合内の頂点の総数をプロセッサの総数で割ることにより、各プロセッサに割り当てられる最大数の頂点を推定することと、
前記推定された最大数に基づいて、前記第１の頂点の集合を前記プロセッサの集合の間で割り当てることと、がさらに含まれる、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第１の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第１の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれ、
前記第２の頂点の集合から前記第１の頂点の集合への第２のグラフの探査を実行する動作であって、
前記プロセッサの集合の間で前記第２の頂点の集合のみを割り当てることであって、前記第２の頂点の集合の、第２の互いに素な部分集合を、前記プロセッサの集合内の同一の前記各プロセッサのみに割り当てることが含まれ、
前記第２の互いに素な頂点の部分集合と前記第１の互いに素な部分集合には共通する頂点がなく、
前記第２の互いに素な頂点の部分集合の割り当てが、前記第２の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第２の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第２の互いに素な部分集合から、最先端の頂点の集合を選択することと、
前記各プロセッサに関して選択された前記最先端の頂点の集合から、前記２部グラフの１つ以上の辺によって前記最先端の頂点の集合のいずれかに関連する、前記第１の頂点の集合の、第２の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれ、
前記第１の頂点の集合から前記第２の頂点の集合への第３のグラフの探査を実行する動作であって、
前記プロセッサの集合の間で前記第１の頂点の集合のみを割り当てることであって、前記第１の頂点の集合の、第３の互いに素な部分集合を、同一の前記各プロセッサのみに割り当てることがさらに含まれ、
前記第３の互いに素な頂点の部分集合と前記第２の互いに素な部分集合には共通する頂点がなく、
前記第３の互いに素な頂点の部分集合の割り当てが、前記第３の互いに素な頂点の部分集合内の頂点の総数をプロセッサの総数で割ったものに基づいている、前記第１の頂点の集合のみの割り当てと、
前記各プロセッサに割り当てられた前記第３の互いに素な頂点の部分集合から、前記第２の頂点の集合の、第３の終点の部分集合へのグラフを、前記各プロセッサによって探査することと、が含まれる、前記第３のグラフの探査を実行する動作と、
少なくとも、前記第２の頂点の集合の、前記第３の終点の部分集合の計数に基づいて推奨を生成する動作と、が含まれる演算システム。
【請求項１５】
前記各プロセッサに関して選択された前記最先端の頂点の集合からの前記グラフの探査には、
プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空ではない場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「１」となり、プロセッサ「ｐ」に関して選択された前記最先端の頂点の集合が空の場合、「ｐ」番目のビット値であるＭＵ［ｐ］が「０」となるよう、ビットマスク「ＭＵ」を生成することと、
ＭＵ［ｐ］が「１」の場合、グラフ探査解析を実行するよう前記プロセッサ「ｐ」に命令することと、が含まれる、請求項１４に記載の演算システム。
【請求項１６】
頂点の各集合の互いに素な部分集合を前記各プロセッサに割り当てる動作には、
式「（ｕｍａｘ-ｕｍｉｎ＋１）／Ｐ」に従って、各プロセッサに割り当てられる頂点の最大数を推定することであって、「Ｐ」はプロセッサの数であり、「ｕｍａｘ」は頂点∈Ｕに関する最大整数識別子であり、「ｕｍｉｎ」は頂点∈Ｕに関する最小整数識別子であり、「Ｕ」は前記第１の頂点の集合を表す、ことと、
各プロセッサに割り当てられる、前記推定された頂点の最大数に基づいて、前記頂点の各集合を前記プロセッサの集合の間で均一に分割することと、がさらに含まれる、請求項１４に記載の演算システム。
【請求項１７】
頂点の各集合の互いに素な部分集合を各プロセッサに割り当てる動作には、
前記頂点の各集合を前記プロセッサの集合の間で非均一に分割することがさらに含まれる、請求項１４に記載の演算システム。
【請求項１８】
前記第１の頂点の集合は顧客を表し、前記第２の頂点の集合は商品を表し、前記生成された推奨は顧客に対する商品の推奨である、請求項１４に記載の演算システム。
【請求項１９】
前記動作には少なくとも１つの追加のグラフ探査が含まれ、前記少なくとも１つの追加のグラフ探査には、
前記少なくとも１つの追加のグラフ探査を実行する予定である前記プロセッサの集合の間で頂点の集合を割り当てることであって、前記頂点の集合の互いに素な部分集合を前記各プロセッサのみに割り当てることがさらに含まれる、頂点の集合の割り当てと、
前記各プロセッサのみに割り当てられた前記頂点の集合の前記互いに素な部分集合から、前記頂点の集合の、追加の終点の部分集合へのグラフを、各プロセッサによって探査することと、がさらに含まれる、請求項１４に記載の演算システム。