集合の類似性に基づく拡張性に富むユーザクラスタリング
【課題】拡張性に富むユーザクラスタリングを提供する。
【解決手段】ユーザのクラスタリングを可能にする方法および装置であって、システムおよびコンピュータプログラムを含んでおり、そこでは、ユーザは各々品目を表わす要素からなる集合で表わされる。ある態様では、プログラムは、複数ユーザの各々についてそれぞれの興味集合を取得し、各興味集合はそれぞれのユーザが興味を示した品目を表わし、ユーザの各々についてそれぞれの興味集合のｋ個のハッシュ値を決定し、第ｉのハッシュ値は対応する第ｉのハッシュ関数の最小値であり、そして複数ユーザの各々をそれぞれのユーザに対して確立されたそれぞれのｋ個のクラスタの各々に割り当て、第ｉのクラスタは第ｉのハッシュ値により表わされる。ユーザの各々についてのｋ個のクラスタへの割り当ては、その他のどのユーザについてのｋ個のクラスタへの割り当てにも無関係に実行される。
【解決手段】ユーザのクラスタリングを可能にする方法および装置であって、システムおよびコンピュータプログラムを含んでおり、そこでは、ユーザは各々品目を表わす要素からなる集合で表わされる。ある態様では、プログラムは、複数ユーザの各々についてそれぞれの興味集合を取得し、各興味集合はそれぞれのユーザが興味を示した品目を表わし、ユーザの各々についてそれぞれの興味集合のｋ個のハッシュ値を決定し、第ｉのハッシュ値は対応する第ｉのハッシュ関数の最小値であり、そして複数ユーザの各々をそれぞれのユーザに対して確立されたそれぞれのｋ個のクラスタの各々に割り当て、第ｉのクラスタは第ｉのハッシュ値により表わされる。ユーザの各々についてのｋ個のクラスタへの割り当ては、その他のどのユーザについてのｋ個のクラスタへの割り当てにも無関係に実行される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタルデータ処理に関し、より詳細にはコンピュータアプリケーションまたはシステムのユーザ（user）をクラスタ（cluster）にグループ分けすることに関する。
【背景技術】
【０００２】
ユーザをクラスタにグループ分けすることは様々な目的で行われる。ユーザの個人性への適合化を達成するため、例えば、既知の技術の１つである協調フィルタリング（collaborative filtering）は、ユーザをクラスタリングすることおよびユーザにそのユーザクラスタ中の他のユーザが興味を示した品目（item）を推奨することを含む。通常、例えば、ある品目をクリックした、それを購入した、またはそれを買い物カゴに入れた等の様々な様子から、ユーザはその品目に興味を示したとみなされてよい。推奨は様々な形をとることができ、例えば、ユーザに検索結果の一部として提示する、ユーザが読みたいかもしれないニュース記事として示す、ユーザが購入したいかもしれない品目を特定する、等々、がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】J. Deans and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Proceedings of the 6th Symposium on Operating Systems Design and Implementation, pp.137-150 (December 6, 2004)
【非特許文献２】Charikar, Similarity Estimation Technique from Rounding Algorithms, 34th ACM Symposium on Theory of Computing, May 19-21, 2002, Montreal, Quebec, Canada
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユーザのクラスタリングを達成する１つのやり方は、２ユーザ間の距離測度を定義し、次にｋ平均法（k-means）または階層的凝集型クラスタリング（hierarchical agglomerative clustering、ＨＡＣ）等の既知のクラスタリングアルゴリズムを使用して彼らをクラスタリングすることである。しかし、そのような技術には欠点がある。例えば、ＨＡＣは実行時間がＯ（ｎ２）であり、数億になるｎの値については手に負えず、またｋ平均法アルゴリズムではデータ点の平均値を提示する必要があるが、これはデータ点が集合の場合、不可能である。
【課題を解決するための手段】
【０００５】
本発明は、特定の実施では、拡張性に富むユーザのクラスタリングを提供することができ、そこでは、各ユーザは品目母集団からの品目を表す要素からなる集合で表わされる。
【０００６】
例えば、コンピュータシステムとの相互作用を通してユーザが選択できる品目の母集団が与えられたとき、各ユーザは品目の部分集合それぞれへの彼らの興味を様々な行動によって表現してもよく、それは、品目をクリックする、品目を購入する、品目を買い物リストに追加する、品目を眺める、等々である。本発明の特定の実施では、同じクラスタ中のユーザは彼らそれぞれの品目部分集合間に大きい重なりを有する可能性が大きいやり方で、ユーザをクラスタリングする（すなわち、ユーザをクラスタに割り当てる）。
【０００７】
ある態様では、本発明の実施によるコンピュータプログラム製品は、データ処理装置に、複数ユーザの各々についてそれぞれの興味集合を取得させることができ、各興味集合はそれぞれのユーザがデータ処理システムとの相互作用を通して興味を示した品目を表わし、本製品はまた、データ処理装置に、複数ユーザの各々についてそれぞれの興味集合のｋ個のハッシュ（hash）値を決定させることができ、第ｉのハッシュ値は対応する第ｉのハッシュ関数の下でのそれぞれの興味集合中の最小値であり、ｉは１とｋの間の整数であり、ｋは１以上の整数であり、本製品はさらに、データ処理装置に、複数ユーザの各々をそれぞれのユーザについて第ｉのクラスタは第ｉのハッシュ値によって表わされるように確立されたそれぞれのｋ個のクラスタの各々に割り当てさせることができ、複数ユーザの各々のｋ個のクラスタへの割り当ては他のどのユーザについてのｋ個のクラスタへの割り当てとも無関係に行われる。
【０００８】
好適な実施は以下の特徴の１つ以上を含むことができる。本製品は、データ処理装置にユーザの興味を表わす動作をログに記録させるようにでき、また複数ユーザについての興味集合を生成するためそのログを使用させることができる。
【０００９】
本製品は、データ処理装置に、複数ユーザ中の第１のユーザについて変化のあった興味集合を取得させることができ、第１のユーザについて変化のあった興味集合を使用してｋ個のハッシュ値を決定させることができ、そして第１のユーザを、変化のあった興味集合を使用して決定されたｋ個のハッシュ値によって表わされるそれぞれのｋ個のクラスタの各々にのみ、他の複数ユーザのクラスタへの割り当てを変化させることなく、割り当てさせることができる。
【００１０】
別の態様では、本発明の実施によるコンピュータプログラム製品は、データ処理装置に、あるユーザについて興味集合を取得させることができ、その興味集合はそのユーザがデータ処理システムとの相互作用を通して興味を示した品目を表わす。本製品はまた、データ処理装置に、興味集合のｋ個のハッシュ値を決定させることができ、第ｉのハッシュ値は対応する第ｉのハッシュ関数の下での興味集合中の最小値であり、ｉは１とｋの間の整数であり、ｋは１以上の整数である。本製品はさらに、データ処理装置に、ユーザをｋ個のクラスタの各々に割り当てさせることができ、第ｉのクラスタは第ｉのハッシュ値により表わされる。
【００１１】
好適な実施は以下の特徴の１つ以上を含むことができる。興味集合はｍ個の要素を持っており、第ｉのハッシュ値は一方向ハッシュ関数をｍ回適用したときの最小値であり、ここで、ｍ回適用の各々は第ｉシード値（seed value）と興味集合のｍ個の要素のそれぞれの１つをハッシュする。本製品は、ユーザのための協調フィルタリングを実行するために、データ処理装置にｋ個のユーザクラスタを使用させることができる。
【００１２】
別の態様では、本発明の実施によるシステムは、データ処理システムを使用する複数ユーザにより選択された品目のログと、複数ユーザの各々をｋ個（ここでｋは１以上の整数）のクラスタに割り当てるために指紋（fingerprint）関数および品目のログを使用する手段と、ｋ個のクラスタの１つ以上への第１のユーザの割り当てに基づいて複数ユーザ中の第１のユーザに情報を提供できる協調フィルタリングのコンピュータプログラムアプリケーションとを含む。
【００１３】
好適な実施は以下の特徴の１つ以上を含むことができる。その情報は推奨、予測、またはランク付けの少なくとも１つを含む。
【００１４】
別の態様では、本発明の実施によるコンピュータプログラム製品は、データ処理システムのユーザを同定するために、データ処理装置にｋ個の要素からなる順序集合を使用させることができ、ｋは１より大きい整数であり、ｋ個の要素の各々は興味集合中の要素に対応し、興味集合中の各要素はデータ処理システムを使用するユーザによる行動を通してユーザが興味を示した品目を表す。
【００１５】
好適な実施は以下の特徴の１つ以上を含むことができる。本製品は、ユーザについての協調フィルタリングの実行においてユーザを同定するために、データ処理装置にｋ個の要素からなる順序集合を使用させることができる。協調フィルタリングは、ユーザへの品目の推奨またはユーザへの品目のランク付けを含むことができる。本製品は、データ処理装置に、再編された興味集合を生成するためにデータ処理システムがその入力に応えて興味集合から要素を除去するような入力を、ユーザから受信させることができ、本製品はまた、データ処理装置に、ｋ個の要素からなる再編された順序集合を決定させることができ、ｋ個の要素の各々は再編された興味集合中の要素に対応しており、本製品はさらに、ユーザを同定するために、データ処理装置に、ｋ個の要素からなる初期の順序集合ではなく、ｋ個の要素からなる再編された順序集合を使用させることができる。ｋ個の要素からなる順序集合は、ｋ個のユーザクラスタの各々に属するものとしてユーザを同定する。本製品は、データ処理装置に、ユーザの興味を表す行動をログに記録させ、またユーザについての興味集合を生成するためにログを使用させることができる。データ処理システムはウェブサイトを含み、またユーザについての興味集合は、ユーザがウェブページでクリックした品目、ユーザがオンライン小売店から購入した品目、ユーザが買い物カートに追加した品目の１つ以上の表現を含む。品目への興味を表すユーザによる行動は、興味を暗に示す行動を含む。品目への興味を表すユーザによる行動は、興味を陽に示す行動を含む。ユーザはユーザのログオンによって同定される個人である。ユーザはクッキーによって同定される個人である。ユーザは観測される属性が共通する１人以上の個人であり、その属性は１人以上の個人の各々によりデータ処理システムに提示される属性である。ユーザはデータ処理システムと相互作用する個人のセッションである。興味集合中の各要素は、データ処理システムとの相互作用においてユーザが選択した品目である。
【００１６】
さらに別の態様では、本発明の実施は先述のプログラムおよびシステムに対応する方法、ならびに先述のシステムに対応するプログラムを含むことができる。
【発明の効果】
【００１７】
本発明は、以下の長所の１つ以上を実感するように実施することができる。クラスタリングの計算が拡張性に富む。計算は数億人の個々のユーザによって使用されるアプリケーションについて実行可能であり、個々のユーザは、数十、数百またはそれ以上の品目を彼らの興味集合中に表示させることができる。クラスタリングされたエンティティが品目の母集団の部分集合で表される場合、クラスタリングは実行可能である。母集団が予め定義される必要は無い。クラスタリングは集合の類似性測度に基づく。新しいユーザのクラスタリングは既存のクラスタリングを変更することなく行われる。あるユーザのクラスタリングは、他のユーザがどうクラスタリングされたかまたはクラスタリングされつつあるかを考慮せずに行われる。しかし、例えば、シード値または順列（permutation）等の幾つかの広域的値は、クラスタリング間で共有されてもよい。例えば、品目の選択を実効的に廃棄または追加する等、選択を変更することにより、ユーザは彼らが割り当てられたクラスタを変更することができ、その場合、クラスタはその後計算または再計算される。新しいユーザまたは興味集合を修正したユーザがどのクラスタに属するかは、他のユーザからのデータを使用することなく計算可能である。クラスタリングの計算は、個人であるユーザのクラスタリングに限定されない。クラスタリングは、例えば、各ユーザが個人であるか、各ユーザが個人の集団であるか、各ユーザがシステムとの相互作用であるか、またはそれらの何らかの組合せであるかに関わらず、効率的に実行可能である。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態による、ユーザをクラスタリングする第１の方法を示すフローチャートである。
【図２】本発明の実施形態による、ユーザをクラスタリングする第２の方法を示すフローチャートである。
【図３】本発明の実施形態による、ユーザクラスタを使用する推奨者システムの動作を示すフローチャートである。
【図４】本発明の一実施形態による、ニュース推奨エンジンを有するニュースサービスを示す概略図である。
【発明を実施するための形態】
【００１９】
本発明の１つ以上の実施形態について、添付の図面および以下の記述において説明する。本発明のその他の特徴および長所はそれらの記述、図面、および特許請求の範囲から明らかとなろう。
【００２０】
図面を通して、同じ参照番号および記号表示は同じ要素を示すものとする。
【００２１】
図１は、ユーザをクラスタリングするミンハッシュ（minhash）法に関する以下の論理的説明を図示したものである。本方法は実施可能であるが、ここでは説明の目的から原理を示すことにする。膨大な数のユーザを持つシステムにおいてユーザをクラスタリングする実際的な実施については後ほど図２を参照して説明されよう。
【００２２】
図１に示すように、ミンハッシュ法への入力は、Ｕで示される品目母集団１１０と、p1, p2, ..., pkで示されるｋ個の順列からなる集合１１２と、ユーザＡについてＸ＿Ａで示されるユーザの興味集合１１４とである。
【００２３】
順列はＵ上の順列であり、各順列は他の順列と同等に選択されるようＵ上の全ての順列の集合から均等に選ばれる。順列は各々ＵからＵへの１対１写像（全単射）である。そのような順列はＵが固定しておりかつ可算である場合のみ実現可能である。整数ｋは選択可能なパラメータである。一般にｋの値は５から１０の範囲であろう。しかし、それは１またはそれ以上の任意の整数であってよい。本方法はユーザにｋ個のクラスタを割り当てよう。これらをC1, ..., Ckで示す。順列が選択されユーザのクラスタへの割り当てに使用された後では、順列が変更された場合、全てのクラスタリングは再計算されなければならない。
【００２４】
興味集合は母集団Ｕからの品目を表す要素からなる集合である。要素が品目それ自体である今説明中の用法では、興味集合は母集団Ｕからの品目のユーザによる選択の集合、Ｘ＿Ａ、である。これらは先述のようにして選択できる。本明細書での便宜のため、用語「品目（item）」は、興味集合の要素かまたはユーザによる実際の選択かを指すことができるが、その意味は文脈から明らかであろう。
【００２５】
このデータを使用して、ユーザについてｋ個、各順列について１個のハッシュ値が決定される（ステップ１２０）。順列piについて、ハッシュ値をｈｉ（Ｘ＿Ａ）で示す。順列piについてのハッシュ値は、順列piの下でのＸ＿Ａからの最小要素、すなわちミンハッシュ値である。その最小値は、要素の値から、またはＵの順序付けから決定することができる。
【００２６】
各ミンハッシュ値はクラスタの識別子の役を果たし、ユーザはクラスタの各々へ割り当てられる。ユーザはｋ個のクラスタに属し、第ｉのクラスタは第ｉのミンハッシュ値によって同定される。このようにして、所与の順列piについて、２つのユーザは、この順列の下での興味集合のミンハッシュ値が同じであり、かつその場合のみ、同じクラスタに属する。
【００２７】
各データ要素にハッシュ値を対応付けるこのミンハッシュ技術は、ローカリティセンシティブハッシング（locality sensitive hashing、局所性に敏感なハッシング）技術と呼ばれるクラスの技術の１つであり、これは２つのデータ要素は２つのデータ要素間の類似性に直接比例するある確率で同じハッシュ値を有するという望ましい特性を有する。現在のケースでは、２人のユーザＡ、Ｂ（それらの興味集合Ｘ＿Ａ、Ｘ＿Ｂで表される）間の類似性は、（Ｘ＿ＡとＸ＿Ｂの積集合）の大きさを（Ｘ＿ＡとＸ＿Ｂの和集合）の大きさで除したものと定義され、そこで、ミンハッシュ技術は、２人のユーザＡとＢについてのミンハッシュ値が同じである確率（使用される実際の順列がそこから選ばれる順列集合上で定義される）は、以上で定義した類似性測度に等しいという特性を有する。こうして、ミンハッシュ法は、ユーザ達は彼らの類似性に等しい確率で同じクラスタに落ち込むという、確率的クラスタリングを達成する。
【００２８】
ｋ個のクラスタが同定される（ステップ１２２）ので、２人のユーザが同一クラスタ中にある確率がｐ（０≦ｐ≦１）の場合、あるクラスタリングでは彼らは同じクラスタに割り当てられなかったとしても、割合ｐのクラスタリングでは彼らは同じクラスタに割り当てられよう。これは、各ユーザはｋ個の異なるクラスタリングに均等に属し、各クラスタリングについては他の類似したユーザと同じクラスタに割り当てられるという平滑作用を与える。パラメータｋは効率（小さいｋはより高い効率を与える）と品質（大きいｋはより高い品質を与える）との間のトレードオフを最適化するように選択されるべきである。厳格に必然というのではないが、数値ｋは通常定数であって、１０程度の小さい値でよい結果が得られる。
【００２９】
このミンハッシュクラスタリング法は、非常に拡張性に富んでおり、また幾つかの他の長所を有する。例えば、本方法の実行時間はデータの大きさ（すなわち、(user, item)対（pair）の総数）に比例する。
【００３０】
また、各ユーザは個々に、すなわち、他の全てのユーザとは独立にクラスタリングされる。これは四六時中ユーザが追加され、抹消され、そして更新されるウェブ領域においては特に興味深い。これに伴う長所は、従来のクラスタリングアルゴリズムでは困難な幾つかのケースを容易にまた追加的に処理できることである。ユーザがスパム的（spammy）である、すなわち、クラスタリングを使用するシステムに影響を及ぼす目的で見せかけの興味を示していると判別された場合、そのユーザを他のどのユーザにも影響させずに、すなわち、残りのクラスタリングは不変のままで、抹消することができる。また、自分の選択を明かしてこなかったユーザがそれを明かそうと決心した場合、またはそのシステムに新しいユーザが追加された場合、他のユーザを再クラスタリングすることなく、そのユーザをクラスタに追加することができる。最後に、ユーザが自分のプロフィールを、自分の興味集合を事実上編集することにより変えようと決心した場合、そのユーザについてのクラスタリングを、バッチ処理による更新とは対照的に、実時間で更新することができ、これを考慮に入れると、他のどのユーザのクラスタリングにも影響を与えない。
【００３１】
図２は、数億に上る膨大な数のユーザを有し、また各ユーザの興味集合中に、事実上または現実上可算でない品目母集団上で、数百以上の品目を有することもあるシステムにおいて、ユーザをクラスタリングする実際的な実施を示す。この実施はMapReduceプログラミングモデルおよび技術を使用するが、これについては後で説明する。
【００３２】
この実施への入力は、記号Ｄで示される、特別な秩序もなく蓄積されたデータ要素（例えば、結果のクリックログ、購入ログ等）の寄集め（collection）２１０と、s1, s2, ..., skで示されるｋ個のシード値からなる順序集合と、指紋関数２１４とである。各データ要素は、特定のユーザ（user）がある品目（item）に興味を示したことを示す(user, item)対と考えることができる。オプションとして、そのユーザがそのように行動した頻度を把握するために、そのデータ要素がそのユーザが興味を示した第１、第２等々の事例に言及するかどうかを示すサフィックスを、品目の原形に付すことができる。好都合なことに、品目の形式はテキスト列であり、そのため、任意のウェブアプリケーションを通しての、すなわち、ユーザにユーザインタフェースを提示するウェブブラウザを使用する任意のアプリケーションを通しての、興味を表すどのようなユーザ行動も、そのような品目は容易に表現することができる。
【００３３】
興味を表すユーザ行動は、明白であることもあり、例えば、ユーザの興味を知らせる情報を、オンライン質問表への回答の形等でユーザがシステムに与えるとき、または暗黙的であることもある、例えば、ニュースサイトで読むニュース記事をユーザが選択するとき。
【００３４】
ｋ個のシード値s1, s2, ..., skは、例えば、２進表現でのビットが「０」、「１」均等で、ランダムに見えるように選ばれたビット列と考えられる数である。
【００３５】
指紋関数はシード値および（興味集合からの）品目を、例えば、６４ビットまたは１２８ビットの、大きい数に写像する。
【００３６】
ある実施では、シード値はＵＮＩＸ（登録商標）のrand関数を使用して生成され、ｋ個の３２ビット整数値を生成する。rand関数は、１個のシード値の生成に１度以上呼び出さなければならないかもしれない。この実施では、指紋関数はＭＤ５一方向ハッシュアルゴリズムを実装しており、品目（これは一般にテキスト列または２進データであろう）と連結したシード値をハッシュして１２８ビットの値を作る。
【００３７】
シード値と指紋関数は、図１を参照して説明したｋ個の順列p1, ..., pkに論理的に対応しており、品目の可算母集団を必要とせずに、品目の順序付けと順列を提供する。
【００３８】
寄集めＤはマップリデュース（MapReduce）の枠組みを使用して処理される。これについては後で説明する。
【００３９】
mapフェーズ２２０では、各(user, item)対について、key=userかつvalue=itemとした(key, value)対が分散的に出力される。
【００４０】
reduceフェーズ２２２では、同じkey(user)を有するような全ての(key, value)対が集められて、reduceルーチンに与えられ、これは各々の個別のkey(user)について１度、分散的に実行される。
【００４１】
（特定のユーザについて）reduceルーチンはそのユーザの興味集合中の全ての品目を処理する。これの説明のため、これらのｍ個の品目をi1, i2, ..., imで示す。各シード値siについて、reduceルーチンは、品目とシード値の指紋、すなわち、fingerprint(si, il)、であるｍ個（各品目について１つ）の値を計算する。ｍ個の品目についてのこれらのfingerprintの最小値が計算され、それが第ｉのシードsiに対応する第ｉのミンハッシュ値となる。
【００４２】
ユーザは、このようにして算出されたｋ個のミンハッシュ値によって表わされる。これらは、そのユーザが属するｋ個のクラスタを表現し、そのユーザはこれらのクラスタに割り当てられたと称される。
【００４３】
図３に示すように、推奨者コンピュータプログラムアプリケーションは、本明細書で説明される任意の方法で生成されるユーザクラスタを使用してよい。
【００４４】
ある実施では、システムはユーザによってなされた選択をログに記録する（ステップ３１０）。そのログは、ディスク駆動装置またはファイルサーバに、例えば、無構造のテキスト行または構造化されたデータベース中のレコード等、どのような形式で蓄積されてもよい。システムは、検索結果、広告、購買選択、そのサイトの内部または外部のページへの単純なリンク、またはその他の品目、をサービスするウェブサイトであってよい。ログされた選択は、そのシステムのユーザによってなされた全ての選択であってもよいが、そうである必要もない。例えば、アプリケーションは全サイトというよりはニュースサイトのみの選択に、または示された全品目というより購買目的の品目のみの選択に、興味を持っているのかもしれない。さらに、システムは、種々の推奨者アプリケーション用の異なる種類の複数の選択ログを保持することができ、推奨者アプリケーションはそれら自身のそれぞれのユーザのクラスタリングを計算できる。例えば、シードおよびfingerprint関数を使用する方法では、別個のクラスタリングの各々はそれ自身の別個のシード列およびfingerprint関数を持つことができる。
【００４５】
システムは、ユーザ登録とログオンにより、クッキーによるかまたは他のやり方で個人をユーザとして判別可能である。オプションとして、もし個々のユーザに関する情報をシステムとの相互作用の複数セッションに跨って保持することが望ましくない場合は、システムは、ユーザセッションをクラスタリング目的用のユーザとして扱うことができる。クッキーをセッションの維持に使用することもできる。（クッキーは、サーバによってウェブブラウザへ送られ、その後ブラウザによってサーバへのアクセスの都度送り戻されるパケット型の情報である。）オプションとして、システムは、ロギングに参加するか否か、すなわち、自分自身を選択のロギングに含めるか除くかを、個人が決定できるようにできる。
【００４６】
オプションとして、システムは、ユーザとしてシステムと相互作用する個人のある属性または属性の組合せを処理することができる。属性はシステムによって観測できてもよく、例えば、使用されるＩＰ（インターネットプロトコル）アドレスまたは使用される言語、または個人が提供する情報、例えば、住所の都市または国、またはシステムが提供するサービスへの加入であってもよい。こうして、例えば、システムはクパーティノからの個人を一ユーザとして、またレドモンドからの個人を別のユーザとして処理することもできよう。そのような寄集め型のクラスタリングの利点は、ログインまたは登録を要求することなく、システムのある程度の個人性への適合化が可能になることである。さらに、オプションとして、システムは全ての種類のユーザ、例えば、個人または集団を、同じクラスタに一緒にクラスタリングすることもでき、または別の種類のユーザについては別のクラスタを確立することもできる。
【００４７】
システムのユーザが行う選択は、単純な選択であることができ、またはオプションとして、複合的な選択であることができる。複合的な選択は一連の選択であり、例えば、第１のウェブページへナビゲート（navigate）し、それから直接に第２のウェブページへナビゲートする一連のナビゲーションである。ウェブページはリソース、通常はＨＴＭＬ（Hypertext Markup Language、ハイパーテキストマークアップ言語）文書、であり、ウェブサーバによってウェブブラウザにサービスされる。ウェブサーバは、通常はネットワークを介して受信されるＨＴＴＰ（Hypertext Transfer Protocol、ハイパーテキスト転送プロトコル）要求を受け付けるコンピュータプログラムであり、要求者に対してＨＴＴＰ応答を与える。ＨＴＴＰ応答は通常ＨＴＭＬ文書を含むが、テキストファイル、動画、または何らかのその他のタイプの文書であってもよい。
【００４８】
ログされた選択に基づいて、ユーザは各々ｋ個のクラスタに割り当てられる（ステップ３１２）が、これについては本明細書の別の箇所で説明されている。このユーザのクラスタリングは、システムに新しいユーザが現れたとき、および選択がログに追加または除去されたときに、更新することができる。オプションとして、ある状況では必ずしも全てのユーザがｋ個のクラスタに割り当てられるとは限らない。そのような状況では、特定のユーザへの推奨を見つけるために、１個以上でｋ個より少ないクラスタ識別子を取得することができる。例えば、一連の選択を持つ新しいユーザに推奨を提供する要求をシステムが受けると、オプションとして、システムはそれらの選択を使用して第１のクラスタの識別子を計算し、推奨を見つけるためにそれを使用し、続けて第２のクラスタを同様に計算して使用し、等々、システム定義による十分な数の推奨が見つかるまで続けることができる。
【００４９】
推奨者アプリケーションは次いで、特定ユーザへの推奨を行うためにそのユーザのクラスタを使用することができる（ステップ３１４）。各ユーザの単一クラスタへのグループ分けに基づいて推奨を行うどのような方法も、本明細書で説明された複数クラスタとともに使用することができる。例えば、そのような方法はｋ回適用可能であり、そのユーザについての推奨品目の和集合を得るためにｋ個の結果がマージされる。あるいは、ある品目が出現する結果の数をその品目のランク付けに使用することができる。または、ユーザに多様な推奨を提供するために、クラスタに基づく推奨結果の各々から若干ずつの品目をそのユーザに提供することができる。ユーザが割り当てられた複数のクラスタは、システムを使用する際にユーザが持った様々な種類の興味を反映しているかもしれず、そこでユーザにそのような多様な推奨を与えることは、単一のクラスタが使用された場合より、推奨がユーザのそのときの興味に触れる何かを含む可能性を高めることになる。
【００５０】
推奨者アプリケーションは協調フィルタリングの一例であり、本明細書で説明されたユーザのクラスタリングの方法は別の種類の協調フィルタリングにも同様に適用することができる。協調フィルタリングでは現ユーザに類似のユーザが見つかり、かれらの嗜好または行動から現ユーザ向けのランク付け、推奨または予測が行われる。ユーザを複数のクラスタへグループ分けすることにより、システムは暗黙裡にユーザの嗜好を判別し、ユーザのグループ分けを通して品目をグループ分けする。
【００５１】
図４に概略的に示されるように、本明細書で説明されたユーザをクラスタに割り当てる技術は、ユーザ４０２ａ、４０２ｂに提示されるニュース記事の推奨を、それらのユーザによって以前になされた記事の選択に基づいて提供することができるニュース推奨エンジン４１０において実施することができる。ユーザ４０２ａ、４０２ｂは、彼等それぞれのブラウザを通し、例えば、ローカル、広域、または仮想プライベートネットワーク、もしくはインターネット等の通信ネットワーク４０４を介して、１つ以上のウェブサーバ４３０と通信する。ニュースサービス４２０は、サーバ（１つまたは複数）４３０に収容されたコンピュータプログラムとして実施され、ユーザの要求に応えてユーザ４０２ａ、４０２ｂにウェブページをサービスする。ニュースサービス４２０によってサービスされるページには、ユーザが１つまたは複数のニュースを選択してユーザのブラウザで表示できるページが存在する。ユーザの選択に応えて、ニュースサービス４２０はユーザが選択した記事をサービスする（機能４２４）。ニュース推奨エンジン４１０が特定ユーザについて推奨を提供した場合、そのユーザについての推奨に応じて、ニュースサービスはそのユーザによる選択のための記事を表示するページをサービスすることができる（機能４２２）。
【００５２】
ニュース推奨エンジン４１０はサーバ（１つまたは複数）４３０で実行されるコンピュータプログラムとして実施される。ニュース推奨エンジン４１０はニュースサービス４２０のユーザから選択を受信し、それらの選択をログ４４０にログする（機能４１２）。本明細書の別の箇所での説明のように、ログ４４０中の情報を使用して、エンジンはユーザをクラスタに割り当てる（機能４１４）。クラスタに割り当てられたいずれの特定のユーザについても、エンジンはそのユーザが割り当てられたクラスタに基づいて推奨を決定し（機能４１６）、それらの推奨をニュースサービス４２０に提供する。
【００５３】
特定のユーザについてなされる推奨の決定に際して、エンジンはその特定ユーザと同じクラスタ（１つまたは複数）に割り当てられた他のユーザによってなされた選択を考慮する。可能性のある推奨の中から、オプションとして、エンジンはユーザが既に選択したニュース記事を消去することができる。エンジンまたはサービスは、あるニュース記事がそのユーザが割り当てられたクラスタに割り当てられている他のユーザによって選択された回数、そのニュース記事がどの程度新しいものか、問題のニュース記事の主題に関する記事を有するソースの数、等の種々の基準に基づいて推奨をランク付けすることができる。このようにして、ニュースサービスはそのユーザに対して個人性に適合化されたニュース記事の提示およびランク付けを提供することができる。
【００５４】
ある実施では、ニュース推奨エンジン４１０はユーザを個人として同定しており、そこで個人性に適合化した推奨を得るべく、ユーザにログインし登録するよう要求する。別の実施では、本明細書の別の箇所での説明のように、ユーザを暗黙裡にまたは寄集めグループとして同定することができる。
【００５５】
その他の種類のサービス、例えば、動画、ブログ、または買い物情報等の選択を提供するサービスの個人性への適合化をサポートするために、推奨エンジンをこの線に沿って実施することができる。
【００５６】
図４では別モジュールとして示されているが、エンジンおよびサービスの機能はこのようなやり方で実施される必要はなく、特に、エンジンはサービスの実施の一部として実施することができる。
【００５７】
以下の段落では、MapReduceプログラミングモデルおよび大きいデータ集合を処理し生成するためのモデルの実装について説明する。モデルおよびそれのライブラリの実装をともにMapReduceと呼ぶものとする。MapReduceを使用して、プログラマは、key/value対を処理して中間key/value対の集合を生成するmap関数、および同じ中間keyに対応する全ての中間valueを１つにまとめるreduce関数、の仕様を定める。この関数スタイルで作成されたプログラムは自動的に並列化され、日用品的コンピュータの大集団（cluster）上で実行することができる。ランタイムシステムまたはフレームワークは、入力データを分割し、一連のマシーン全域でのプログラム実行をスケジュールし、マシーン障害を処理し、そしてマシーン間で必要な通信を管理するように実装することができる。
【００５８】
MapReduce計算は一連の入力key/value対を取り込み、一連の出力key/value対を生成する。ユーザはその計算を２つの関数、mapとreduceで表現する。
【００５９】
map、ユーザにより作成、は入力key/value対を取り込み、一連の中間key/value対を生成する。MapReduceライブラリは同じ中間key Iに対応する全ての中間valueをまとめてグループ化し、それらをreduce関数に渡す。
【００６０】
reduce関数、これもユーザにより作成、は中間key Iとそのkeyに対応する一連のvalueを受け取る。それはこれらのvalueを一緒にマージして、可能性としてはより小さ目のvalue集合を形成する。通常はreduceを呼ぶ度に０または１個の出力valueが生成される。中間valueはイテレータ（iterator）を通してユーザのreduce関数に供給される。このようにして、大き過ぎてメモリに収まらないvalueのリストも手に負えるようになる。
【００６１】
文書の大量集積について各語の生起回数を計数する問題を考えよう。ユーザは以下の擬似コードに似たコードを作成することになろう。
map (String key, String value):
// key: document name
// value: document contents
for each word w in value:
Emitlntermediate (w, "1") ;
reduce (String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += Parselnt (v) ;
Emit (AsString (result) ) ;
【００６２】
map関数は各語および対応する生起回数（この簡単な例では只の「１」）を併せて出力する。reduce関数は特定の語について出力された全ての回数を足し合わせる。
【００６３】
ある実施では、計算を実行するために、ユーザは入力ファイルおよび出力ファイルの名前とともに仕様目的ならびにオプションの調整用パラメータを記入するコードを作成する。ユーザはそこでMapReduce関数を呼び出し、それに仕様目的を渡す。ユーザのコードはMapReduceライブラリと併せてリンクされる。
【００６４】
上記の擬似コードは入出力が文字列であるとして書かれたものであるが、概念上はユーザが提供するmap関数およびreduce関数は関連したタイプを有しており、
map(k1, v1)→list(k2, v2)
reduce(k2, list(v2))→list(v2)
すなわち、入力keyおよび入力valueは、出力keyおよび出力valueとは別のドメインから引き出される。さらに、中間keyおよび中間valueは、出力keyおよび出力valueと同じドメインから引き出される。
【００６５】
MapReduceモデルについては多くの異なった実装が可能である。
【００６６】
以下の段落では、スイッチ機能付きイーサネット（登録商標）で相互接続された日用品的パソコンの大集団からなる計算環境を目標とする実装について説明する。この環境では、マシーンはマシーン当り通常２から４ＧＢ（ギガバイト）のメモリを有し、集団は数百または数千のマシーンを有し、外部メモリは個々のマシーンに装着された低廉なＩＤＥ（Integrated Drive Electronics standard）ディスクにより与えられ、これらのディスクは低信頼度のハードウェア上で可用性および信頼性を備えるために複製を使用するが、そこに蓄積されたデータを管理するために分散型のファイルシステムが使用され、ユーザはスケジューリングシステムにジョブを提出する。各ジョブは一連の仕事からなり、スケジューリングシステムのスケジューラによって、集団中の一連の利用可能なマシーンへと計画的に割り振られる。
【００６７】
mapの呼び出しは、入力データを一連のＭ個のスプリット（split）へ自動的に分割することにより、複数マシーンにわたって分散化される。入力スプリットを異なるマシーンにより並行処理することができる。reduceの呼び出しは、分割関数（例えば、hash(key) mod R）を使用して中間key空間をＲ個に分割することにより分散化される。分割数（Ｒ）および分割関数はユーザが指定する。
【００６８】
ユーザプログラムがMapReduce関数を呼ぶと、以下の一連の動作が行われる。
【００６９】
１．ユーザプログラム中のMapReduceライブラリは、先ず、入力ファイルを１個当り（ユーザが制御可能な）通常１６メガバイトから６４メガバイト（ＭＢ）のＭ個へと分割する。それから、プログラムのコピー多数をマシーン集団上で起動する。
【００７０】
２．プログラムのコピーの内の１つはマスタ（master）である。残りは、マスタ（master）によって作業を割り付けられるワーカ（worker）である。割り付けるべきＭ個のmapタスクとＲ個のreduceタスクが存在する。マスタはアイドル状態（idle）のワーカを選び、各々にmapタスクまたはreduceタスクを割り付ける。
【００７１】
３．mapタスクを割り付けられたワーカは対応する入力スプリットの内容を読む。それは入力データからkey/value対を構文解析し、各対をユーザ定義のmap関数へ渡す。map関数によって生成された中間key/value対はメモリにバッファされる。
【００７２】
４．周期的に、バッファされた対は、分割関数によってＲ個の領域に分割（partition）されたローカルディスクへ書き込まれる。これらのバッファされた対のローカルディスク上の位置はマスタに戻され、マスタはこれらの位置をreduceワーカへ責任をもって転送する。
【００７３】
５．reduceワーカがマスタによってこれらの位置について知らされると、それは遠隔手順呼出しを使用して、バッファされたデータをmapワーカのローカルディスクから読み取る。全ての中間データを読み取ると、reduceワーカはそれを中間keyによってソート（sort）し、同一keyの全オカーレンス（occurrence）をグループにまとめる。通常多くの異なるkeyが同一のreduceタスクに割り振られるので、このソートが役に立つ。中間データの量が多過ぎてメモリに収まらない場合は、外付けのソートが使用される。
【００７４】
６．reduceワーカはソートされた中間データに対して繰り返し動作し、目新しい中間keyに出会う都度、そのkeyおよび対応する中間valueの集合をユーザのreduce関数に渡す。reduce関数の出力はこのreduceパーティションについての最終出力ファイルに付加される。
【００７５】
７．全てのmapタスクおよびreduceタスクが完了すると、マスタはユーザプログラムを呼び起こす。この時点で、ユーザプログラム中でのMapReduce呼出しはユーザコードへ戻る。
【００７６】
成功裏に完了した後、実行出力はＲ個の出力ファイル（reduceタスク当り１個、ユーザが指定したファイル名で）で利用可能となる。ユーザはこれらのＲ個の出力ファイルを１個のファイルに結合する必要はなく、これらのファイルを別のMapReduce呼び出しへの入力として渡すか、またはそれらを複数ファイルに分割された入力を処理可能な他の分散アプリケーションから使用することができる。
【００７７】
マスタは幾つかのデータ構造を保持する。各々のmapタスクおよびreduceタスクについて、マスタは状態（アイドル、進行中、または完了）および（非アイドルタスクについての）ワーカマシーンの識別子を蓄積する。
【００７８】
マスタは、中間ファイル領域の位置をmapタスクからreduceタスクへ伝えるパイプの役を果たす。したがって、完了したmapタスクの各々について、マスタはそのmapタスクによって生成されたＲ個の中間ファイル領域の位置と大きさを蓄積する。この位置と大きさの情報への更新は、mapタスクが完了したときに受信される。その情報は進行中reduceタスクを有するワーカに追加的に押し込まれる。
【００７９】
このMapReduceライブラリの実装は数百または数千のマシーンを使用して膨大な量のデータを処理するように設計されるので、このライブラリはマシーン故障にも耐用性がある。
【００８０】
マスタはどのワーカに対しても周期的に接続確認信号を発する（ping）。ある時間内にワーカから返答が受信されない場合、マスタはそのワーカに故障の印を付ける。そのワーカが完了したどのmapタスクもリセットされて初期のアイドル状態に戻され、したがって他のワーカ上でスケジューリングできるようになる。同様に、故障したワーカ上で進行中のどのmapタスクまたはreduceタスクもアイドル状態にリセットされ、再スケジュールできるようになる。
【００８１】
故障時には完了したmapタスクは再実行される。というのは、それらの出力が故障マシーンのローカルディスクに蓄積されており、アクセスできないからである。完了したreduceタスクは、それらの出力がグローバルファイルシステムに蓄積されるので再実行の必要はない。
【００８２】
Mapタスクが初めにワーカＡによって実行され、その後、（ワーカＡが故障したため）ワーカＢによって実行された場合、reduceタスクを実行する全てのワーカにその再実行が知らされる。ワーカＡからのデータ読み出しを実行済みでない全てのreduceタスクは、ワーカＢからデータを読み出すことになる。
【００８３】
マスタは１つしか存在しないのでそれの故障は滅多にない。したがって、マスタが故障した場合、MapReduce計算は打ち切りとなる。ユーザまたはユーザプログラムは、この状況をチェックすることができ、かれらが望む場合、MapReduceの動作を再試行する。
【００８４】
ユーザ提供のmapおよびreduceオペレータ（operator）がそれらへの入力値の決定性関数である場合、この分散的実装は、全プログラムを故障なしで順番に実行することによって生成されるのと同じ出力を生成する。各進行中タスクはその出力を自分だけの一時ファイルへ書き出す。mapタスクが完了すると、ワーカはマスタにメッセージを送信し、そのメッセージ中にＲ個の一時ファイルの名前を含ませる。マスタが既に完了したmapタスクについて完了メッセージを受信した場合、そのメッセージを無視する。そうでない場合、マスタはＲ個の一時ファイルの名前をマスタのデータ構造中に記録する。reduceタスクが完了すると、reduceワーカはそれの一時出力ファイルを最終出力ファイルに原子レベルで名前変更する。同じreduceタスクが複数のマシーンで実行される場合、同じ最終出力ファイルについて複数の名前変更要求が実行されることになる。基盤的なファイルシステムによって提供される原子レベルの名前変更動作は、最終ファイルシステムの状態がreduceタスクの１回の実行によって生成されるデータだけを含むことを保証する。
【００８５】
本実装は、集団を構成するマシーンのローカルディスクに入力データを蓄積するという事実を活用して、ネットワーク帯域幅の浪費を防いでいる。ファイルシステムは各ファイルを６４ＭＢブロックに分割し、各ブロックのコピーを別々のマシーンに蓄積する。MapReduceマスタは、入力ファイルの位置情報を考慮にいれて、対応する入力データの複製を含むマシーン上のmapタスクのスケジュールを試みる。それに失敗すると、そのタスクの入力データの複製に近い（すなわち、そのデータを含むマシーンと同じネットワークスイッチ上にあるワーカマシーン上の）mapタスクのスケジュールを試みる。
【００８６】
負荷を動的に均衡させるためには、ＭおよびＲはワーカマシーンの数より遥かに大きくあるべきである。先に述べたように、マスタはＯ（Ｍ＋Ｒ）のスケジュール判断を実行し、Ｏ（Ｍ×Ｒ）の状態をメモリ中に保持しなければならないので、この実装においてＭおよびＲをどの程度に大きくできるかには実用上の限界がある。さらに、各reduceタスクの出力は別々の出力ファイル中で閉じているので、Ｒはユーザによってしばしば制限される。実用上は、Ｍは、先述の局地最適性が最も効果的となるよう個々のタスクの各々が大まかに１６ＭＢから６４ＭＢの入力ファイルを有するように選ばれ、Ｒは使用を期待できるワーカマシーン数の小さい倍数となろう。
【００８７】
MapReduceの実行にかかる総時間は、落ちこぼれ、すなわち、計算における最後の幾つかのmapまたはreduceタスクの１つを完了するのに異常に長時間を要するマシーン、によって大きく影響され得る。落ちこぼれ問題を軽減するために、MapReduceの実行が完了に近づくと、マスタはまだ進行中のタスクの支援実行をスケジュールする。本来の実行かまたは支援実行かが完了する都度、タスクは完了の印が付けられる。
【００８８】
以上の基本機能に加えて、本実装は以下の有用な拡張機能を提供する。
【００８９】
幾つかのケースでは、keyの何か特定の機能によりデータを分割するのが有用である。これをサポートするために、MapReduceライブラリのユーザは分割関数を提供することができる。
【００９０】
本実装は、所与のパーティション内では、中間key/value対がkeyの昇順に処理されることを保証する。これは、パーティション毎のソートされた出力ファイルの生成を容易化して、出力ファイルの形式がkeyによる効率的なランダムアクセス検索サポートする必要がある場合、または出力のユーザにとってデータがソートされていると好都合な場合に役に立つ。
【００９１】
幾つかのケースでは、各mapタスクによって生成される中間keyにおける繰り返しが膨大で、そしてユーザ仕様によるreduce関数が可換でありかつ結合法則が成立する。これの例は先述の語数を計数する例である。各mapタスクは<the, 1>の形式の数百または数千のレコードを生成する場合もある。これらの計数値は全て、ネットワークを介して単一のreduceタスクへ、そしてreduce関数によって総和を取られ１つの数を生成するために、送信される。そのようなケースに備えるため、本実装は、オプションとして、ネットワークを介してデータを送信する前にそれを部分的にマージするcombiner関数をユーザが指定できるようにする。
【００９２】
combiner関数は、mapタスクを実行する各マシーン上で実行される。combiner関数およびreduce関数の両者の実装に同じコードを使用できる。reduce関数とcombiner関数との間の唯一の違いは、MapReduceライブラリが関数の出力をどう処理するかである。reduce関数の出力は最終出力ファイルに書き出される。combiner関数の出力は、reduceタスクへ送信される中間ファイルに書き出される。
【００９３】
MapReduceライブラリは、複数の異なったフォーマットの入力データの読み取りをサポートする。例えば、「テキスト」モードの入力は各行をkey/value対として処理し、ここで、keyはファイル中のオフセット（offset）であり、valueは行の内容である。もう１つの一般的にサポートされるフォーマットは、keyでソートされた一連のkey/value対を蓄積する。入力タイプの各実装は、そのタイプのデータを、個別のmapタスクとして処理する意味がある領域に分割する方法を知っている（例えば、テキストモードの領域分割では、領域の分割は、確実に行の境界でのみ行われる）。ユーザは、簡単なreaderインタフェースの実装を提供することにより、新しい入力タイプへのサポートを追加できる。さらに、readerはファイルから読み出されたデータの提供に限定されない。例えば、readerはデータベースまたはメモリ中に割り振られたデータ構造からレコードを読み出すことができる。
【００９４】
同様のやり方で、本実装は様々なフォーマットでデータを生成する一連の出力タイプをサポートし、またユーザが新しい出力タイプのサポートを追加するためにコードを書くことは容易である。
【００９５】
ユーザまたは第３者のコード中のバグにより、map関数またはreduce関数があるレコードで決定的に機能停止することも時にはある。例えば、大きいデータ集合の統計的解析を行っているとき等、若干のレコードを無視することが受容可能な場合もある。本実装は、MapReduceライブラリが決定的機能停止を引き起こしたレコードを検出し、前進するためにこれらのレコードをスキップする、オプションとしての実行モードを提供する。
【００９６】
このモードのために、各ワーカのプロセスは、セグメンテーション違反およびバス誤りを捕捉する信号ハンドラ（handler）を組み込んでいる。ユーザのmapまたはreduceの実行を呼び出す前に、MapReduceライブラリは引数の順序番号をグローバル変数中に蓄積する。ユーザコードが信号を発生する場合、信号ハンドラはその順序番号を含む「最後のあえぎ（last gasp）」ＵＤＰ（User Datagram Protocol）パケットをMapReduceマスタに送信する。特定のレコードについて１つ以上の故障を見つけると、マスタは対応するmapまたはreduceタスクの次の再実行の指令発出に際して、そのレコードをスキップ（skip）するべきことを知らせる。
【００９７】
MapReduceに関するさらに多くの情報は、その内容が参照によって本明細書に組み込まれた非特許文献１で見つけることができる。
【００９８】
ローカリティセンシティブハッシュ体系を使用してユーザを複数のクラスタにクラスタリングするもう１つの方法についてここで簡単に説明しよう。この方法では、各ユーザは、ユーザを特徴付ける高次元のベクトルで表現されたプロフィールを有する。そのようなベクトル上で動作する一連のｋ個のハッシュ関数が選択される。ユーザプロフィールについての第ｉのハッシュ値はユーザが割り当てられる第ｉのクラスタを表す。本方法に有用なローカリティセンシティブハッシュ関数については非特許文献２に説明がある。
【００９９】
そのような方法のある実装では、ユーザは<term, weight>対のリストにより表現される。先述と同様、ｋはクラスタの数およびユーザに対して計算されるハッシュ値の数である。シード値の数は説明では８ｋで与えられようが、定数で与えられている８は一般にはパラメータである。８ｋ個のランダムなシード値は、s_1, s_2, ..., s_8kで示す文字列で表現され、例えば、２進表現でのビットの「０」または「１」が均等で、ランダムに見えるように選択される。どのユーザについても、第ｉのハッシュ値は以下のように計算される。
【０１００】
For b from 1 to 8:
do
initialize sum = 0;
for all <term_j, weight_j> pairs in the user's list:
do
if (fingerprint (term_j + s_((i-l)*8 + b)) has least significant bit = 1)
sum = sum + weight_j
else
sum = sum - weight_j
done
if (sum > 0)
b-th bit of i-th hash value is set to 1.
else
b-th bit of i-th hash value is set to 0.
done.
【０１０１】
fingerprint (term_j + s_((i-l)*8 + b)なる項は、シード文字列s_((i-l)*8 + b)、すなわち第((i-l)*8 + b)のシード文字列と連結された第ｊ項(term_j)のfingerprint関数（先述のように計算される）を表わす。
【０１０２】
本発明の実施形態および本明細書で説明した全ての機能的動作は、本明細書で開示された構造またはそれらの構造的等価物もしくはそれらの組合せを含む、デジタル電子回路、もしくはコンピュータソフトウェア、ファームウェア、またはハードウェアで実施可能である。本発明の実施形態は、１つ以上のコンピュータプログラム製品、すなわち、例えば、マシーン可読蓄積装置、マシーン可読蓄積媒体、メモリ装置、またはマシーン可読伝播信号、等のコンピュータ可読媒体上にコード化された、データ処理装置による実行に使用されるか、またはその動作を制御する、コンピュータプログラム命令の１つ以上のモジュールとして実施可能である。用語「データ処理装置」は、例として、プログラム可能プロセッサ、コンピュータ、もしくは多重プロセッサまたは多重コンピュータを含む、データを処理するための全ての装置およびマシーンを包含する。装置は、ハードウェアに加えて、問題になっているコンピュータプログラムのための実行環境を創り出すコード、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらの組合せを構成するコード、を含む。伝播信号は、例えば、機械により発生された電気的、光学的または電磁的信号等の人工的に発生された信号であり、好適な受信装置への転送用に情報を符号化するために発生される。
【０１０３】
コンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる）は、コンパイルまたはインタープリタ言語を含むどのような形式のプログラミング言語ででも書くことができ、スタンドアローンプログラムとしてもしくはモジュール、コンポーネント、サブルーチン、またはコンピュータ環境での使用に好適なその他の単位を含む任意の形式で配備できる。コンピュータプログラムは必ずしもファイルシステム中のファイルに対応しなくてもよい。プログラムは、他のプログラムまたはデータを保持するファイルの一部に（例えば、マークアップ言語文書中に蓄積された１つ以上のスクリプト）、問題になっているプログラムに専用の単一のファイルに、または複数の組織的なファイル（例えば、１つ以上のモジュール、サブプログラム、またはコードの一部を蓄積するファイル）に、蓄積することができる。コンピュータプログラムは、１つのコンピュータで、もしくは１つのサイトに配置された、または複数サイトにわたって分散され、通信ネットワークによって相互接続された、複数のコンピュータで、実行するために配備することができる。
【０１０４】
本明細書で説明したプロセスおよび論理の流れは、入力データに対して動作して出力を生成することにより機能を実行する１つ以上のコンピュータプログラムを実行する、１つ以上のプログラム可能なプロセッサによって実行することができる。例えば、ＦＰＧＡ（Field Programmable Gate Array、フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（Application-Specific Integrated Circuit、特定用途向け集積回路）等の特定用途論理回路により、そのプロセスおよび論理の流れを実行することもでき、装置を実装することもできる。
【０１０５】
コンピュータプログラムの実行に好適なプロセッサには、例として、汎用および特定目的用の両方のマイクロプロセッサ、ならびに任意の種類のデジタルコンピュータの任意の１つ以上のプロセッサが含まれる。一般に、プロセッサは読み出し専用メモリまたはランダムアクセスメモリもしくはその両方から命令とデータを受け取るであろう。コンピュータの本質的要素は、命令を実行するプロセッサおよび命令とデータを蓄積する１つ以上のメモリである。コンピュータはまた、一般に、データを蓄積するための１つ以上の大容量記憶装置、例えば、磁気、磁気光学ディスク、または光学ディスク、を含むか、またはそれらからデータを受信しまたはそれらへデータを送信しもしくはその両方を実行できるようそれらに接続されよう。しかし、コンピュータはそのような装置を持たなくてもよい。さらに、コンピュータは別の装置、幾つか名前を上げれば、例えば、移動電話機、携帯情報端末（ＰＤＡ、personal digital assistant）、携帯オーディオプレーヤ、全地球測位システム（ＧＰＳ、Global Positioning System）受信機、等に埋め込むこともできる。コンピュータプログラム命令およびデータを具体化するのに好適な情報担体には、全ての形態の不揮発性メモリ、例としては、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリ装置等の半導体メモリ装置、内蔵ハードディスクまたは取り外し可能ディスク等の磁気ディスク装置、磁気光学ディスク、およびＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスク、が含まれる。プロセッサおよびメモリは特定用途論理回路で補足することができ、またはそれに組み込むことができる。
【０１０６】
ユーザとの相互作用に備えて、本発明の実施形態は、情報をユーザに提示するための表示装置、例えば、ＣＲＴ（cathode ray tube、陰極線管）またはＬＣＤ（liquid crystal display、液晶ディスプレイ）モニタ、ならびにユーザがコンピュータに入力を与えることができるキーボードおよび指示装置、例えば、マウスまたはトラックボール、を有するコンピュータ上で実施することができる。その他の種類の装置もまたユーザとの相互作用に備えて使用することができ、例えば、ユーザに提供されるフィードバックは、例えば、視覚的フィードバック、聴覚的フィードバック、または触覚的フィードバック等の任意の形式の感覚フィードバックであってよく、またユーザからの入力は、音響、音声または触覚入力を含む任意の形式で受信されてよい。
【０１０７】
本発明の実施形態は、バックエンド構成要素、例えば、データサーバ等、を含む、またはミドルウェア構成要素、例えば、アプリケーションサーバ、を含む、またはフロントエンド構成要素、例えば、本発明の実装と相互作用できるようにするためのグラフィカルユーザインタフェースまたはウェブブラウザを有するクライアントコンピュータ、を含むコンピュータシステム中で実施することができ、もしくはそのようなバックエンド、ミドルウェア、またはフロントエンド構成要素の任意の組合せで実施することができる。システムの構成要素は、任意の形態または媒体の、通信ネットワーク等のデジタルデータ通信により相互接続することができる。通信ネットワークの例には、ローカルエリアネットワーク（「ＬＡＮ」）およびインターネット等の広域ネットワーク（「ＷＡＮ」）が含まれる。
【０１０８】
コンピュータシステムはクライアントおよびサーバを含むことができる。クライアントおよびサーバは、一般には相互に遠く離れており、通常は通信ネットワークを通して相互作用する。クライアントおよびサーバの関係は、それぞれのコンピュータ上で実行され、相互にクライアント−サーバ関係にあるコンピュータプログラムによって、発生する。
【０１０９】
本発明の特定の実施形態について説明をおこなった。その他の実施形態は添付の特許請求の範囲に含まれる。例えば、特許請求の範囲で列挙されるステップは、別の順序で実行することもでき、それでも所望の結果を得ることができる。
【符号の説明】
【０１１０】
４０２ａ、４０２ｂ ユーザ
４０４ 通信ネットワーク
４１０ ニュース推奨エンジン
４２０ ニュースサービス
４３０ ウェブサーバ
４４０ ログ
【技術分野】
【０００１】
本発明はデジタルデータ処理に関し、より詳細にはコンピュータアプリケーションまたはシステムのユーザ（user）をクラスタ（cluster）にグループ分けすることに関する。
【背景技術】
【０００２】
ユーザをクラスタにグループ分けすることは様々な目的で行われる。ユーザの個人性への適合化を達成するため、例えば、既知の技術の１つである協調フィルタリング（collaborative filtering）は、ユーザをクラスタリングすることおよびユーザにそのユーザクラスタ中の他のユーザが興味を示した品目（item）を推奨することを含む。通常、例えば、ある品目をクリックした、それを購入した、またはそれを買い物カゴに入れた等の様々な様子から、ユーザはその品目に興味を示したとみなされてよい。推奨は様々な形をとることができ、例えば、ユーザに検索結果の一部として提示する、ユーザが読みたいかもしれないニュース記事として示す、ユーザが購入したいかもしれない品目を特定する、等々、がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】J. Deans and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Proceedings of the 6th Symposium on Operating Systems Design and Implementation, pp.137-150 (December 6, 2004)
【非特許文献２】Charikar, Similarity Estimation Technique from Rounding Algorithms, 34th ACM Symposium on Theory of Computing, May 19-21, 2002, Montreal, Quebec, Canada
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユーザのクラスタリングを達成する１つのやり方は、２ユーザ間の距離測度を定義し、次にｋ平均法（k-means）または階層的凝集型クラスタリング（hierarchical agglomerative clustering、ＨＡＣ）等の既知のクラスタリングアルゴリズムを使用して彼らをクラスタリングすることである。しかし、そのような技術には欠点がある。例えば、ＨＡＣは実行時間がＯ（ｎ２）であり、数億になるｎの値については手に負えず、またｋ平均法アルゴリズムではデータ点の平均値を提示する必要があるが、これはデータ点が集合の場合、不可能である。
【課題を解決するための手段】
【０００５】
本発明は、特定の実施では、拡張性に富むユーザのクラスタリングを提供することができ、そこでは、各ユーザは品目母集団からの品目を表す要素からなる集合で表わされる。
【０００６】
例えば、コンピュータシステムとの相互作用を通してユーザが選択できる品目の母集団が与えられたとき、各ユーザは品目の部分集合それぞれへの彼らの興味を様々な行動によって表現してもよく、それは、品目をクリックする、品目を購入する、品目を買い物リストに追加する、品目を眺める、等々である。本発明の特定の実施では、同じクラスタ中のユーザは彼らそれぞれの品目部分集合間に大きい重なりを有する可能性が大きいやり方で、ユーザをクラスタリングする（すなわち、ユーザをクラスタに割り当てる）。
【０００７】
ある態様では、本発明の実施によるコンピュータプログラム製品は、データ処理装置に、複数ユーザの各々についてそれぞれの興味集合を取得させることができ、各興味集合はそれぞれのユーザがデータ処理システムとの相互作用を通して興味を示した品目を表わし、本製品はまた、データ処理装置に、複数ユーザの各々についてそれぞれの興味集合のｋ個のハッシュ（hash）値を決定させることができ、第ｉのハッシュ値は対応する第ｉのハッシュ関数の下でのそれぞれの興味集合中の最小値であり、ｉは１とｋの間の整数であり、ｋは１以上の整数であり、本製品はさらに、データ処理装置に、複数ユーザの各々をそれぞれのユーザについて第ｉのクラスタは第ｉのハッシュ値によって表わされるように確立されたそれぞれのｋ個のクラスタの各々に割り当てさせることができ、複数ユーザの各々のｋ個のクラスタへの割り当ては他のどのユーザについてのｋ個のクラスタへの割り当てとも無関係に行われる。
【０００８】
好適な実施は以下の特徴の１つ以上を含むことができる。本製品は、データ処理装置にユーザの興味を表わす動作をログに記録させるようにでき、また複数ユーザについての興味集合を生成するためそのログを使用させることができる。
【０００９】
本製品は、データ処理装置に、複数ユーザ中の第１のユーザについて変化のあった興味集合を取得させることができ、第１のユーザについて変化のあった興味集合を使用してｋ個のハッシュ値を決定させることができ、そして第１のユーザを、変化のあった興味集合を使用して決定されたｋ個のハッシュ値によって表わされるそれぞれのｋ個のクラスタの各々にのみ、他の複数ユーザのクラスタへの割り当てを変化させることなく、割り当てさせることができる。
【００１０】
別の態様では、本発明の実施によるコンピュータプログラム製品は、データ処理装置に、あるユーザについて興味集合を取得させることができ、その興味集合はそのユーザがデータ処理システムとの相互作用を通して興味を示した品目を表わす。本製品はまた、データ処理装置に、興味集合のｋ個のハッシュ値を決定させることができ、第ｉのハッシュ値は対応する第ｉのハッシュ関数の下での興味集合中の最小値であり、ｉは１とｋの間の整数であり、ｋは１以上の整数である。本製品はさらに、データ処理装置に、ユーザをｋ個のクラスタの各々に割り当てさせることができ、第ｉのクラスタは第ｉのハッシュ値により表わされる。
【００１１】
好適な実施は以下の特徴の１つ以上を含むことができる。興味集合はｍ個の要素を持っており、第ｉのハッシュ値は一方向ハッシュ関数をｍ回適用したときの最小値であり、ここで、ｍ回適用の各々は第ｉシード値（seed value）と興味集合のｍ個の要素のそれぞれの１つをハッシュする。本製品は、ユーザのための協調フィルタリングを実行するために、データ処理装置にｋ個のユーザクラスタを使用させることができる。
【００１２】
別の態様では、本発明の実施によるシステムは、データ処理システムを使用する複数ユーザにより選択された品目のログと、複数ユーザの各々をｋ個（ここでｋは１以上の整数）のクラスタに割り当てるために指紋（fingerprint）関数および品目のログを使用する手段と、ｋ個のクラスタの１つ以上への第１のユーザの割り当てに基づいて複数ユーザ中の第１のユーザに情報を提供できる協調フィルタリングのコンピュータプログラムアプリケーションとを含む。
【００１３】
好適な実施は以下の特徴の１つ以上を含むことができる。その情報は推奨、予測、またはランク付けの少なくとも１つを含む。
【００１４】
別の態様では、本発明の実施によるコンピュータプログラム製品は、データ処理システムのユーザを同定するために、データ処理装置にｋ個の要素からなる順序集合を使用させることができ、ｋは１より大きい整数であり、ｋ個の要素の各々は興味集合中の要素に対応し、興味集合中の各要素はデータ処理システムを使用するユーザによる行動を通してユーザが興味を示した品目を表す。
【００１５】
好適な実施は以下の特徴の１つ以上を含むことができる。本製品は、ユーザについての協調フィルタリングの実行においてユーザを同定するために、データ処理装置にｋ個の要素からなる順序集合を使用させることができる。協調フィルタリングは、ユーザへの品目の推奨またはユーザへの品目のランク付けを含むことができる。本製品は、データ処理装置に、再編された興味集合を生成するためにデータ処理システムがその入力に応えて興味集合から要素を除去するような入力を、ユーザから受信させることができ、本製品はまた、データ処理装置に、ｋ個の要素からなる再編された順序集合を決定させることができ、ｋ個の要素の各々は再編された興味集合中の要素に対応しており、本製品はさらに、ユーザを同定するために、データ処理装置に、ｋ個の要素からなる初期の順序集合ではなく、ｋ個の要素からなる再編された順序集合を使用させることができる。ｋ個の要素からなる順序集合は、ｋ個のユーザクラスタの各々に属するものとしてユーザを同定する。本製品は、データ処理装置に、ユーザの興味を表す行動をログに記録させ、またユーザについての興味集合を生成するためにログを使用させることができる。データ処理システムはウェブサイトを含み、またユーザについての興味集合は、ユーザがウェブページでクリックした品目、ユーザがオンライン小売店から購入した品目、ユーザが買い物カートに追加した品目の１つ以上の表現を含む。品目への興味を表すユーザによる行動は、興味を暗に示す行動を含む。品目への興味を表すユーザによる行動は、興味を陽に示す行動を含む。ユーザはユーザのログオンによって同定される個人である。ユーザはクッキーによって同定される個人である。ユーザは観測される属性が共通する１人以上の個人であり、その属性は１人以上の個人の各々によりデータ処理システムに提示される属性である。ユーザはデータ処理システムと相互作用する個人のセッションである。興味集合中の各要素は、データ処理システムとの相互作用においてユーザが選択した品目である。
【００１６】
さらに別の態様では、本発明の実施は先述のプログラムおよびシステムに対応する方法、ならびに先述のシステムに対応するプログラムを含むことができる。
【発明の効果】
【００１７】
本発明は、以下の長所の１つ以上を実感するように実施することができる。クラスタリングの計算が拡張性に富む。計算は数億人の個々のユーザによって使用されるアプリケーションについて実行可能であり、個々のユーザは、数十、数百またはそれ以上の品目を彼らの興味集合中に表示させることができる。クラスタリングされたエンティティが品目の母集団の部分集合で表される場合、クラスタリングは実行可能である。母集団が予め定義される必要は無い。クラスタリングは集合の類似性測度に基づく。新しいユーザのクラスタリングは既存のクラスタリングを変更することなく行われる。あるユーザのクラスタリングは、他のユーザがどうクラスタリングされたかまたはクラスタリングされつつあるかを考慮せずに行われる。しかし、例えば、シード値または順列（permutation）等の幾つかの広域的値は、クラスタリング間で共有されてもよい。例えば、品目の選択を実効的に廃棄または追加する等、選択を変更することにより、ユーザは彼らが割り当てられたクラスタを変更することができ、その場合、クラスタはその後計算または再計算される。新しいユーザまたは興味集合を修正したユーザがどのクラスタに属するかは、他のユーザからのデータを使用することなく計算可能である。クラスタリングの計算は、個人であるユーザのクラスタリングに限定されない。クラスタリングは、例えば、各ユーザが個人であるか、各ユーザが個人の集団であるか、各ユーザがシステムとの相互作用であるか、またはそれらの何らかの組合せであるかに関わらず、効率的に実行可能である。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態による、ユーザをクラスタリングする第１の方法を示すフローチャートである。
【図２】本発明の実施形態による、ユーザをクラスタリングする第２の方法を示すフローチャートである。
【図３】本発明の実施形態による、ユーザクラスタを使用する推奨者システムの動作を示すフローチャートである。
【図４】本発明の一実施形態による、ニュース推奨エンジンを有するニュースサービスを示す概略図である。
【発明を実施するための形態】
【００１９】
本発明の１つ以上の実施形態について、添付の図面および以下の記述において説明する。本発明のその他の特徴および長所はそれらの記述、図面、および特許請求の範囲から明らかとなろう。
【００２０】
図面を通して、同じ参照番号および記号表示は同じ要素を示すものとする。
【００２１】
図１は、ユーザをクラスタリングするミンハッシュ（minhash）法に関する以下の論理的説明を図示したものである。本方法は実施可能であるが、ここでは説明の目的から原理を示すことにする。膨大な数のユーザを持つシステムにおいてユーザをクラスタリングする実際的な実施については後ほど図２を参照して説明されよう。
【００２２】
図１に示すように、ミンハッシュ法への入力は、Ｕで示される品目母集団１１０と、p1, p2, ..., pkで示されるｋ個の順列からなる集合１１２と、ユーザＡについてＸ＿Ａで示されるユーザの興味集合１１４とである。
【００２３】
順列はＵ上の順列であり、各順列は他の順列と同等に選択されるようＵ上の全ての順列の集合から均等に選ばれる。順列は各々ＵからＵへの１対１写像（全単射）である。そのような順列はＵが固定しておりかつ可算である場合のみ実現可能である。整数ｋは選択可能なパラメータである。一般にｋの値は５から１０の範囲であろう。しかし、それは１またはそれ以上の任意の整数であってよい。本方法はユーザにｋ個のクラスタを割り当てよう。これらをC1, ..., Ckで示す。順列が選択されユーザのクラスタへの割り当てに使用された後では、順列が変更された場合、全てのクラスタリングは再計算されなければならない。
【００２４】
興味集合は母集団Ｕからの品目を表す要素からなる集合である。要素が品目それ自体である今説明中の用法では、興味集合は母集団Ｕからの品目のユーザによる選択の集合、Ｘ＿Ａ、である。これらは先述のようにして選択できる。本明細書での便宜のため、用語「品目（item）」は、興味集合の要素かまたはユーザによる実際の選択かを指すことができるが、その意味は文脈から明らかであろう。
【００２５】
このデータを使用して、ユーザについてｋ個、各順列について１個のハッシュ値が決定される（ステップ１２０）。順列piについて、ハッシュ値をｈｉ（Ｘ＿Ａ）で示す。順列piについてのハッシュ値は、順列piの下でのＸ＿Ａからの最小要素、すなわちミンハッシュ値である。その最小値は、要素の値から、またはＵの順序付けから決定することができる。
【００２６】
各ミンハッシュ値はクラスタの識別子の役を果たし、ユーザはクラスタの各々へ割り当てられる。ユーザはｋ個のクラスタに属し、第ｉのクラスタは第ｉのミンハッシュ値によって同定される。このようにして、所与の順列piについて、２つのユーザは、この順列の下での興味集合のミンハッシュ値が同じであり、かつその場合のみ、同じクラスタに属する。
【００２７】
各データ要素にハッシュ値を対応付けるこのミンハッシュ技術は、ローカリティセンシティブハッシング（locality sensitive hashing、局所性に敏感なハッシング）技術と呼ばれるクラスの技術の１つであり、これは２つのデータ要素は２つのデータ要素間の類似性に直接比例するある確率で同じハッシュ値を有するという望ましい特性を有する。現在のケースでは、２人のユーザＡ、Ｂ（それらの興味集合Ｘ＿Ａ、Ｘ＿Ｂで表される）間の類似性は、（Ｘ＿ＡとＸ＿Ｂの積集合）の大きさを（Ｘ＿ＡとＸ＿Ｂの和集合）の大きさで除したものと定義され、そこで、ミンハッシュ技術は、２人のユーザＡとＢについてのミンハッシュ値が同じである確率（使用される実際の順列がそこから選ばれる順列集合上で定義される）は、以上で定義した類似性測度に等しいという特性を有する。こうして、ミンハッシュ法は、ユーザ達は彼らの類似性に等しい確率で同じクラスタに落ち込むという、確率的クラスタリングを達成する。
【００２８】
ｋ個のクラスタが同定される（ステップ１２２）ので、２人のユーザが同一クラスタ中にある確率がｐ（０≦ｐ≦１）の場合、あるクラスタリングでは彼らは同じクラスタに割り当てられなかったとしても、割合ｐのクラスタリングでは彼らは同じクラスタに割り当てられよう。これは、各ユーザはｋ個の異なるクラスタリングに均等に属し、各クラスタリングについては他の類似したユーザと同じクラスタに割り当てられるという平滑作用を与える。パラメータｋは効率（小さいｋはより高い効率を与える）と品質（大きいｋはより高い品質を与える）との間のトレードオフを最適化するように選択されるべきである。厳格に必然というのではないが、数値ｋは通常定数であって、１０程度の小さい値でよい結果が得られる。
【００２９】
このミンハッシュクラスタリング法は、非常に拡張性に富んでおり、また幾つかの他の長所を有する。例えば、本方法の実行時間はデータの大きさ（すなわち、(user, item)対（pair）の総数）に比例する。
【００３０】
また、各ユーザは個々に、すなわち、他の全てのユーザとは独立にクラスタリングされる。これは四六時中ユーザが追加され、抹消され、そして更新されるウェブ領域においては特に興味深い。これに伴う長所は、従来のクラスタリングアルゴリズムでは困難な幾つかのケースを容易にまた追加的に処理できることである。ユーザがスパム的（spammy）である、すなわち、クラスタリングを使用するシステムに影響を及ぼす目的で見せかけの興味を示していると判別された場合、そのユーザを他のどのユーザにも影響させずに、すなわち、残りのクラスタリングは不変のままで、抹消することができる。また、自分の選択を明かしてこなかったユーザがそれを明かそうと決心した場合、またはそのシステムに新しいユーザが追加された場合、他のユーザを再クラスタリングすることなく、そのユーザをクラスタに追加することができる。最後に、ユーザが自分のプロフィールを、自分の興味集合を事実上編集することにより変えようと決心した場合、そのユーザについてのクラスタリングを、バッチ処理による更新とは対照的に、実時間で更新することができ、これを考慮に入れると、他のどのユーザのクラスタリングにも影響を与えない。
【００３１】
図２は、数億に上る膨大な数のユーザを有し、また各ユーザの興味集合中に、事実上または現実上可算でない品目母集団上で、数百以上の品目を有することもあるシステムにおいて、ユーザをクラスタリングする実際的な実施を示す。この実施はMapReduceプログラミングモデルおよび技術を使用するが、これについては後で説明する。
【００３２】
この実施への入力は、記号Ｄで示される、特別な秩序もなく蓄積されたデータ要素（例えば、結果のクリックログ、購入ログ等）の寄集め（collection）２１０と、s1, s2, ..., skで示されるｋ個のシード値からなる順序集合と、指紋関数２１４とである。各データ要素は、特定のユーザ（user）がある品目（item）に興味を示したことを示す(user, item)対と考えることができる。オプションとして、そのユーザがそのように行動した頻度を把握するために、そのデータ要素がそのユーザが興味を示した第１、第２等々の事例に言及するかどうかを示すサフィックスを、品目の原形に付すことができる。好都合なことに、品目の形式はテキスト列であり、そのため、任意のウェブアプリケーションを通しての、すなわち、ユーザにユーザインタフェースを提示するウェブブラウザを使用する任意のアプリケーションを通しての、興味を表すどのようなユーザ行動も、そのような品目は容易に表現することができる。
【００３３】
興味を表すユーザ行動は、明白であることもあり、例えば、ユーザの興味を知らせる情報を、オンライン質問表への回答の形等でユーザがシステムに与えるとき、または暗黙的であることもある、例えば、ニュースサイトで読むニュース記事をユーザが選択するとき。
【００３４】
ｋ個のシード値s1, s2, ..., skは、例えば、２進表現でのビットが「０」、「１」均等で、ランダムに見えるように選ばれたビット列と考えられる数である。
【００３５】
指紋関数はシード値および（興味集合からの）品目を、例えば、６４ビットまたは１２８ビットの、大きい数に写像する。
【００３６】
ある実施では、シード値はＵＮＩＸ（登録商標）のrand関数を使用して生成され、ｋ個の３２ビット整数値を生成する。rand関数は、１個のシード値の生成に１度以上呼び出さなければならないかもしれない。この実施では、指紋関数はＭＤ５一方向ハッシュアルゴリズムを実装しており、品目（これは一般にテキスト列または２進データであろう）と連結したシード値をハッシュして１２８ビットの値を作る。
【００３７】
シード値と指紋関数は、図１を参照して説明したｋ個の順列p1, ..., pkに論理的に対応しており、品目の可算母集団を必要とせずに、品目の順序付けと順列を提供する。
【００３８】
寄集めＤはマップリデュース（MapReduce）の枠組みを使用して処理される。これについては後で説明する。
【００３９】
mapフェーズ２２０では、各(user, item)対について、key=userかつvalue=itemとした(key, value)対が分散的に出力される。
【００４０】
reduceフェーズ２２２では、同じkey(user)を有するような全ての(key, value)対が集められて、reduceルーチンに与えられ、これは各々の個別のkey(user)について１度、分散的に実行される。
【００４１】
（特定のユーザについて）reduceルーチンはそのユーザの興味集合中の全ての品目を処理する。これの説明のため、これらのｍ個の品目をi1, i2, ..., imで示す。各シード値siについて、reduceルーチンは、品目とシード値の指紋、すなわち、fingerprint(si, il)、であるｍ個（各品目について１つ）の値を計算する。ｍ個の品目についてのこれらのfingerprintの最小値が計算され、それが第ｉのシードsiに対応する第ｉのミンハッシュ値となる。
【００４２】
ユーザは、このようにして算出されたｋ個のミンハッシュ値によって表わされる。これらは、そのユーザが属するｋ個のクラスタを表現し、そのユーザはこれらのクラスタに割り当てられたと称される。
【００４３】
図３に示すように、推奨者コンピュータプログラムアプリケーションは、本明細書で説明される任意の方法で生成されるユーザクラスタを使用してよい。
【００４４】
ある実施では、システムはユーザによってなされた選択をログに記録する（ステップ３１０）。そのログは、ディスク駆動装置またはファイルサーバに、例えば、無構造のテキスト行または構造化されたデータベース中のレコード等、どのような形式で蓄積されてもよい。システムは、検索結果、広告、購買選択、そのサイトの内部または外部のページへの単純なリンク、またはその他の品目、をサービスするウェブサイトであってよい。ログされた選択は、そのシステムのユーザによってなされた全ての選択であってもよいが、そうである必要もない。例えば、アプリケーションは全サイトというよりはニュースサイトのみの選択に、または示された全品目というより購買目的の品目のみの選択に、興味を持っているのかもしれない。さらに、システムは、種々の推奨者アプリケーション用の異なる種類の複数の選択ログを保持することができ、推奨者アプリケーションはそれら自身のそれぞれのユーザのクラスタリングを計算できる。例えば、シードおよびfingerprint関数を使用する方法では、別個のクラスタリングの各々はそれ自身の別個のシード列およびfingerprint関数を持つことができる。
【００４５】
システムは、ユーザ登録とログオンにより、クッキーによるかまたは他のやり方で個人をユーザとして判別可能である。オプションとして、もし個々のユーザに関する情報をシステムとの相互作用の複数セッションに跨って保持することが望ましくない場合は、システムは、ユーザセッションをクラスタリング目的用のユーザとして扱うことができる。クッキーをセッションの維持に使用することもできる。（クッキーは、サーバによってウェブブラウザへ送られ、その後ブラウザによってサーバへのアクセスの都度送り戻されるパケット型の情報である。）オプションとして、システムは、ロギングに参加するか否か、すなわち、自分自身を選択のロギングに含めるか除くかを、個人が決定できるようにできる。
【００４６】
オプションとして、システムは、ユーザとしてシステムと相互作用する個人のある属性または属性の組合せを処理することができる。属性はシステムによって観測できてもよく、例えば、使用されるＩＰ（インターネットプロトコル）アドレスまたは使用される言語、または個人が提供する情報、例えば、住所の都市または国、またはシステムが提供するサービスへの加入であってもよい。こうして、例えば、システムはクパーティノからの個人を一ユーザとして、またレドモンドからの個人を別のユーザとして処理することもできよう。そのような寄集め型のクラスタリングの利点は、ログインまたは登録を要求することなく、システムのある程度の個人性への適合化が可能になることである。さらに、オプションとして、システムは全ての種類のユーザ、例えば、個人または集団を、同じクラスタに一緒にクラスタリングすることもでき、または別の種類のユーザについては別のクラスタを確立することもできる。
【００４７】
システムのユーザが行う選択は、単純な選択であることができ、またはオプションとして、複合的な選択であることができる。複合的な選択は一連の選択であり、例えば、第１のウェブページへナビゲート（navigate）し、それから直接に第２のウェブページへナビゲートする一連のナビゲーションである。ウェブページはリソース、通常はＨＴＭＬ（Hypertext Markup Language、ハイパーテキストマークアップ言語）文書、であり、ウェブサーバによってウェブブラウザにサービスされる。ウェブサーバは、通常はネットワークを介して受信されるＨＴＴＰ（Hypertext Transfer Protocol、ハイパーテキスト転送プロトコル）要求を受け付けるコンピュータプログラムであり、要求者に対してＨＴＴＰ応答を与える。ＨＴＴＰ応答は通常ＨＴＭＬ文書を含むが、テキストファイル、動画、または何らかのその他のタイプの文書であってもよい。
【００４８】
ログされた選択に基づいて、ユーザは各々ｋ個のクラスタに割り当てられる（ステップ３１２）が、これについては本明細書の別の箇所で説明されている。このユーザのクラスタリングは、システムに新しいユーザが現れたとき、および選択がログに追加または除去されたときに、更新することができる。オプションとして、ある状況では必ずしも全てのユーザがｋ個のクラスタに割り当てられるとは限らない。そのような状況では、特定のユーザへの推奨を見つけるために、１個以上でｋ個より少ないクラスタ識別子を取得することができる。例えば、一連の選択を持つ新しいユーザに推奨を提供する要求をシステムが受けると、オプションとして、システムはそれらの選択を使用して第１のクラスタの識別子を計算し、推奨を見つけるためにそれを使用し、続けて第２のクラスタを同様に計算して使用し、等々、システム定義による十分な数の推奨が見つかるまで続けることができる。
【００４９】
推奨者アプリケーションは次いで、特定ユーザへの推奨を行うためにそのユーザのクラスタを使用することができる（ステップ３１４）。各ユーザの単一クラスタへのグループ分けに基づいて推奨を行うどのような方法も、本明細書で説明された複数クラスタとともに使用することができる。例えば、そのような方法はｋ回適用可能であり、そのユーザについての推奨品目の和集合を得るためにｋ個の結果がマージされる。あるいは、ある品目が出現する結果の数をその品目のランク付けに使用することができる。または、ユーザに多様な推奨を提供するために、クラスタに基づく推奨結果の各々から若干ずつの品目をそのユーザに提供することができる。ユーザが割り当てられた複数のクラスタは、システムを使用する際にユーザが持った様々な種類の興味を反映しているかもしれず、そこでユーザにそのような多様な推奨を与えることは、単一のクラスタが使用された場合より、推奨がユーザのそのときの興味に触れる何かを含む可能性を高めることになる。
【００５０】
推奨者アプリケーションは協調フィルタリングの一例であり、本明細書で説明されたユーザのクラスタリングの方法は別の種類の協調フィルタリングにも同様に適用することができる。協調フィルタリングでは現ユーザに類似のユーザが見つかり、かれらの嗜好または行動から現ユーザ向けのランク付け、推奨または予測が行われる。ユーザを複数のクラスタへグループ分けすることにより、システムは暗黙裡にユーザの嗜好を判別し、ユーザのグループ分けを通して品目をグループ分けする。
【００５１】
図４に概略的に示されるように、本明細書で説明されたユーザをクラスタに割り当てる技術は、ユーザ４０２ａ、４０２ｂに提示されるニュース記事の推奨を、それらのユーザによって以前になされた記事の選択に基づいて提供することができるニュース推奨エンジン４１０において実施することができる。ユーザ４０２ａ、４０２ｂは、彼等それぞれのブラウザを通し、例えば、ローカル、広域、または仮想プライベートネットワーク、もしくはインターネット等の通信ネットワーク４０４を介して、１つ以上のウェブサーバ４３０と通信する。ニュースサービス４２０は、サーバ（１つまたは複数）４３０に収容されたコンピュータプログラムとして実施され、ユーザの要求に応えてユーザ４０２ａ、４０２ｂにウェブページをサービスする。ニュースサービス４２０によってサービスされるページには、ユーザが１つまたは複数のニュースを選択してユーザのブラウザで表示できるページが存在する。ユーザの選択に応えて、ニュースサービス４２０はユーザが選択した記事をサービスする（機能４２４）。ニュース推奨エンジン４１０が特定ユーザについて推奨を提供した場合、そのユーザについての推奨に応じて、ニュースサービスはそのユーザによる選択のための記事を表示するページをサービスすることができる（機能４２２）。
【００５２】
ニュース推奨エンジン４１０はサーバ（１つまたは複数）４３０で実行されるコンピュータプログラムとして実施される。ニュース推奨エンジン４１０はニュースサービス４２０のユーザから選択を受信し、それらの選択をログ４４０にログする（機能４１２）。本明細書の別の箇所での説明のように、ログ４４０中の情報を使用して、エンジンはユーザをクラスタに割り当てる（機能４１４）。クラスタに割り当てられたいずれの特定のユーザについても、エンジンはそのユーザが割り当てられたクラスタに基づいて推奨を決定し（機能４１６）、それらの推奨をニュースサービス４２０に提供する。
【００５３】
特定のユーザについてなされる推奨の決定に際して、エンジンはその特定ユーザと同じクラスタ（１つまたは複数）に割り当てられた他のユーザによってなされた選択を考慮する。可能性のある推奨の中から、オプションとして、エンジンはユーザが既に選択したニュース記事を消去することができる。エンジンまたはサービスは、あるニュース記事がそのユーザが割り当てられたクラスタに割り当てられている他のユーザによって選択された回数、そのニュース記事がどの程度新しいものか、問題のニュース記事の主題に関する記事を有するソースの数、等の種々の基準に基づいて推奨をランク付けすることができる。このようにして、ニュースサービスはそのユーザに対して個人性に適合化されたニュース記事の提示およびランク付けを提供することができる。
【００５４】
ある実施では、ニュース推奨エンジン４１０はユーザを個人として同定しており、そこで個人性に適合化した推奨を得るべく、ユーザにログインし登録するよう要求する。別の実施では、本明細書の別の箇所での説明のように、ユーザを暗黙裡にまたは寄集めグループとして同定することができる。
【００５５】
その他の種類のサービス、例えば、動画、ブログ、または買い物情報等の選択を提供するサービスの個人性への適合化をサポートするために、推奨エンジンをこの線に沿って実施することができる。
【００５６】
図４では別モジュールとして示されているが、エンジンおよびサービスの機能はこのようなやり方で実施される必要はなく、特に、エンジンはサービスの実施の一部として実施することができる。
【００５７】
以下の段落では、MapReduceプログラミングモデルおよび大きいデータ集合を処理し生成するためのモデルの実装について説明する。モデルおよびそれのライブラリの実装をともにMapReduceと呼ぶものとする。MapReduceを使用して、プログラマは、key/value対を処理して中間key/value対の集合を生成するmap関数、および同じ中間keyに対応する全ての中間valueを１つにまとめるreduce関数、の仕様を定める。この関数スタイルで作成されたプログラムは自動的に並列化され、日用品的コンピュータの大集団（cluster）上で実行することができる。ランタイムシステムまたはフレームワークは、入力データを分割し、一連のマシーン全域でのプログラム実行をスケジュールし、マシーン障害を処理し、そしてマシーン間で必要な通信を管理するように実装することができる。
【００５８】
MapReduce計算は一連の入力key/value対を取り込み、一連の出力key/value対を生成する。ユーザはその計算を２つの関数、mapとreduceで表現する。
【００５９】
map、ユーザにより作成、は入力key/value対を取り込み、一連の中間key/value対を生成する。MapReduceライブラリは同じ中間key Iに対応する全ての中間valueをまとめてグループ化し、それらをreduce関数に渡す。
【００６０】
reduce関数、これもユーザにより作成、は中間key Iとそのkeyに対応する一連のvalueを受け取る。それはこれらのvalueを一緒にマージして、可能性としてはより小さ目のvalue集合を形成する。通常はreduceを呼ぶ度に０または１個の出力valueが生成される。中間valueはイテレータ（iterator）を通してユーザのreduce関数に供給される。このようにして、大き過ぎてメモリに収まらないvalueのリストも手に負えるようになる。
【００６１】
文書の大量集積について各語の生起回数を計数する問題を考えよう。ユーザは以下の擬似コードに似たコードを作成することになろう。
map (String key, String value):
// key: document name
// value: document contents
for each word w in value:
Emitlntermediate (w, "1") ;
reduce (String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += Parselnt (v) ;
Emit (AsString (result) ) ;
【００６２】
map関数は各語および対応する生起回数（この簡単な例では只の「１」）を併せて出力する。reduce関数は特定の語について出力された全ての回数を足し合わせる。
【００６３】
ある実施では、計算を実行するために、ユーザは入力ファイルおよび出力ファイルの名前とともに仕様目的ならびにオプションの調整用パラメータを記入するコードを作成する。ユーザはそこでMapReduce関数を呼び出し、それに仕様目的を渡す。ユーザのコードはMapReduceライブラリと併せてリンクされる。
【００６４】
上記の擬似コードは入出力が文字列であるとして書かれたものであるが、概念上はユーザが提供するmap関数およびreduce関数は関連したタイプを有しており、
map(k1, v1)→list(k2, v2)
reduce(k2, list(v2))→list(v2)
すなわち、入力keyおよび入力valueは、出力keyおよび出力valueとは別のドメインから引き出される。さらに、中間keyおよび中間valueは、出力keyおよび出力valueと同じドメインから引き出される。
【００６５】
MapReduceモデルについては多くの異なった実装が可能である。
【００６６】
以下の段落では、スイッチ機能付きイーサネット（登録商標）で相互接続された日用品的パソコンの大集団からなる計算環境を目標とする実装について説明する。この環境では、マシーンはマシーン当り通常２から４ＧＢ（ギガバイト）のメモリを有し、集団は数百または数千のマシーンを有し、外部メモリは個々のマシーンに装着された低廉なＩＤＥ（Integrated Drive Electronics standard）ディスクにより与えられ、これらのディスクは低信頼度のハードウェア上で可用性および信頼性を備えるために複製を使用するが、そこに蓄積されたデータを管理するために分散型のファイルシステムが使用され、ユーザはスケジューリングシステムにジョブを提出する。各ジョブは一連の仕事からなり、スケジューリングシステムのスケジューラによって、集団中の一連の利用可能なマシーンへと計画的に割り振られる。
【００６７】
mapの呼び出しは、入力データを一連のＭ個のスプリット（split）へ自動的に分割することにより、複数マシーンにわたって分散化される。入力スプリットを異なるマシーンにより並行処理することができる。reduceの呼び出しは、分割関数（例えば、hash(key) mod R）を使用して中間key空間をＲ個に分割することにより分散化される。分割数（Ｒ）および分割関数はユーザが指定する。
【００６８】
ユーザプログラムがMapReduce関数を呼ぶと、以下の一連の動作が行われる。
【００６９】
１．ユーザプログラム中のMapReduceライブラリは、先ず、入力ファイルを１個当り（ユーザが制御可能な）通常１６メガバイトから６４メガバイト（ＭＢ）のＭ個へと分割する。それから、プログラムのコピー多数をマシーン集団上で起動する。
【００７０】
２．プログラムのコピーの内の１つはマスタ（master）である。残りは、マスタ（master）によって作業を割り付けられるワーカ（worker）である。割り付けるべきＭ個のmapタスクとＲ個のreduceタスクが存在する。マスタはアイドル状態（idle）のワーカを選び、各々にmapタスクまたはreduceタスクを割り付ける。
【００７１】
３．mapタスクを割り付けられたワーカは対応する入力スプリットの内容を読む。それは入力データからkey/value対を構文解析し、各対をユーザ定義のmap関数へ渡す。map関数によって生成された中間key/value対はメモリにバッファされる。
【００７２】
４．周期的に、バッファされた対は、分割関数によってＲ個の領域に分割（partition）されたローカルディスクへ書き込まれる。これらのバッファされた対のローカルディスク上の位置はマスタに戻され、マスタはこれらの位置をreduceワーカへ責任をもって転送する。
【００７３】
５．reduceワーカがマスタによってこれらの位置について知らされると、それは遠隔手順呼出しを使用して、バッファされたデータをmapワーカのローカルディスクから読み取る。全ての中間データを読み取ると、reduceワーカはそれを中間keyによってソート（sort）し、同一keyの全オカーレンス（occurrence）をグループにまとめる。通常多くの異なるkeyが同一のreduceタスクに割り振られるので、このソートが役に立つ。中間データの量が多過ぎてメモリに収まらない場合は、外付けのソートが使用される。
【００７４】
６．reduceワーカはソートされた中間データに対して繰り返し動作し、目新しい中間keyに出会う都度、そのkeyおよび対応する中間valueの集合をユーザのreduce関数に渡す。reduce関数の出力はこのreduceパーティションについての最終出力ファイルに付加される。
【００７５】
７．全てのmapタスクおよびreduceタスクが完了すると、マスタはユーザプログラムを呼び起こす。この時点で、ユーザプログラム中でのMapReduce呼出しはユーザコードへ戻る。
【００７６】
成功裏に完了した後、実行出力はＲ個の出力ファイル（reduceタスク当り１個、ユーザが指定したファイル名で）で利用可能となる。ユーザはこれらのＲ個の出力ファイルを１個のファイルに結合する必要はなく、これらのファイルを別のMapReduce呼び出しへの入力として渡すか、またはそれらを複数ファイルに分割された入力を処理可能な他の分散アプリケーションから使用することができる。
【００７７】
マスタは幾つかのデータ構造を保持する。各々のmapタスクおよびreduceタスクについて、マスタは状態（アイドル、進行中、または完了）および（非アイドルタスクについての）ワーカマシーンの識別子を蓄積する。
【００７８】
マスタは、中間ファイル領域の位置をmapタスクからreduceタスクへ伝えるパイプの役を果たす。したがって、完了したmapタスクの各々について、マスタはそのmapタスクによって生成されたＲ個の中間ファイル領域の位置と大きさを蓄積する。この位置と大きさの情報への更新は、mapタスクが完了したときに受信される。その情報は進行中reduceタスクを有するワーカに追加的に押し込まれる。
【００７９】
このMapReduceライブラリの実装は数百または数千のマシーンを使用して膨大な量のデータを処理するように設計されるので、このライブラリはマシーン故障にも耐用性がある。
【００８０】
マスタはどのワーカに対しても周期的に接続確認信号を発する（ping）。ある時間内にワーカから返答が受信されない場合、マスタはそのワーカに故障の印を付ける。そのワーカが完了したどのmapタスクもリセットされて初期のアイドル状態に戻され、したがって他のワーカ上でスケジューリングできるようになる。同様に、故障したワーカ上で進行中のどのmapタスクまたはreduceタスクもアイドル状態にリセットされ、再スケジュールできるようになる。
【００８１】
故障時には完了したmapタスクは再実行される。というのは、それらの出力が故障マシーンのローカルディスクに蓄積されており、アクセスできないからである。完了したreduceタスクは、それらの出力がグローバルファイルシステムに蓄積されるので再実行の必要はない。
【００８２】
Mapタスクが初めにワーカＡによって実行され、その後、（ワーカＡが故障したため）ワーカＢによって実行された場合、reduceタスクを実行する全てのワーカにその再実行が知らされる。ワーカＡからのデータ読み出しを実行済みでない全てのreduceタスクは、ワーカＢからデータを読み出すことになる。
【００８３】
マスタは１つしか存在しないのでそれの故障は滅多にない。したがって、マスタが故障した場合、MapReduce計算は打ち切りとなる。ユーザまたはユーザプログラムは、この状況をチェックすることができ、かれらが望む場合、MapReduceの動作を再試行する。
【００８４】
ユーザ提供のmapおよびreduceオペレータ（operator）がそれらへの入力値の決定性関数である場合、この分散的実装は、全プログラムを故障なしで順番に実行することによって生成されるのと同じ出力を生成する。各進行中タスクはその出力を自分だけの一時ファイルへ書き出す。mapタスクが完了すると、ワーカはマスタにメッセージを送信し、そのメッセージ中にＲ個の一時ファイルの名前を含ませる。マスタが既に完了したmapタスクについて完了メッセージを受信した場合、そのメッセージを無視する。そうでない場合、マスタはＲ個の一時ファイルの名前をマスタのデータ構造中に記録する。reduceタスクが完了すると、reduceワーカはそれの一時出力ファイルを最終出力ファイルに原子レベルで名前変更する。同じreduceタスクが複数のマシーンで実行される場合、同じ最終出力ファイルについて複数の名前変更要求が実行されることになる。基盤的なファイルシステムによって提供される原子レベルの名前変更動作は、最終ファイルシステムの状態がreduceタスクの１回の実行によって生成されるデータだけを含むことを保証する。
【００８５】
本実装は、集団を構成するマシーンのローカルディスクに入力データを蓄積するという事実を活用して、ネットワーク帯域幅の浪費を防いでいる。ファイルシステムは各ファイルを６４ＭＢブロックに分割し、各ブロックのコピーを別々のマシーンに蓄積する。MapReduceマスタは、入力ファイルの位置情報を考慮にいれて、対応する入力データの複製を含むマシーン上のmapタスクのスケジュールを試みる。それに失敗すると、そのタスクの入力データの複製に近い（すなわち、そのデータを含むマシーンと同じネットワークスイッチ上にあるワーカマシーン上の）mapタスクのスケジュールを試みる。
【００８６】
負荷を動的に均衡させるためには、ＭおよびＲはワーカマシーンの数より遥かに大きくあるべきである。先に述べたように、マスタはＯ（Ｍ＋Ｒ）のスケジュール判断を実行し、Ｏ（Ｍ×Ｒ）の状態をメモリ中に保持しなければならないので、この実装においてＭおよびＲをどの程度に大きくできるかには実用上の限界がある。さらに、各reduceタスクの出力は別々の出力ファイル中で閉じているので、Ｒはユーザによってしばしば制限される。実用上は、Ｍは、先述の局地最適性が最も効果的となるよう個々のタスクの各々が大まかに１６ＭＢから６４ＭＢの入力ファイルを有するように選ばれ、Ｒは使用を期待できるワーカマシーン数の小さい倍数となろう。
【００８７】
MapReduceの実行にかかる総時間は、落ちこぼれ、すなわち、計算における最後の幾つかのmapまたはreduceタスクの１つを完了するのに異常に長時間を要するマシーン、によって大きく影響され得る。落ちこぼれ問題を軽減するために、MapReduceの実行が完了に近づくと、マスタはまだ進行中のタスクの支援実行をスケジュールする。本来の実行かまたは支援実行かが完了する都度、タスクは完了の印が付けられる。
【００８８】
以上の基本機能に加えて、本実装は以下の有用な拡張機能を提供する。
【００８９】
幾つかのケースでは、keyの何か特定の機能によりデータを分割するのが有用である。これをサポートするために、MapReduceライブラリのユーザは分割関数を提供することができる。
【００９０】
本実装は、所与のパーティション内では、中間key/value対がkeyの昇順に処理されることを保証する。これは、パーティション毎のソートされた出力ファイルの生成を容易化して、出力ファイルの形式がkeyによる効率的なランダムアクセス検索サポートする必要がある場合、または出力のユーザにとってデータがソートされていると好都合な場合に役に立つ。
【００９１】
幾つかのケースでは、各mapタスクによって生成される中間keyにおける繰り返しが膨大で、そしてユーザ仕様によるreduce関数が可換でありかつ結合法則が成立する。これの例は先述の語数を計数する例である。各mapタスクは<the, 1>の形式の数百または数千のレコードを生成する場合もある。これらの計数値は全て、ネットワークを介して単一のreduceタスクへ、そしてreduce関数によって総和を取られ１つの数を生成するために、送信される。そのようなケースに備えるため、本実装は、オプションとして、ネットワークを介してデータを送信する前にそれを部分的にマージするcombiner関数をユーザが指定できるようにする。
【００９２】
combiner関数は、mapタスクを実行する各マシーン上で実行される。combiner関数およびreduce関数の両者の実装に同じコードを使用できる。reduce関数とcombiner関数との間の唯一の違いは、MapReduceライブラリが関数の出力をどう処理するかである。reduce関数の出力は最終出力ファイルに書き出される。combiner関数の出力は、reduceタスクへ送信される中間ファイルに書き出される。
【００９３】
MapReduceライブラリは、複数の異なったフォーマットの入力データの読み取りをサポートする。例えば、「テキスト」モードの入力は各行をkey/value対として処理し、ここで、keyはファイル中のオフセット（offset）であり、valueは行の内容である。もう１つの一般的にサポートされるフォーマットは、keyでソートされた一連のkey/value対を蓄積する。入力タイプの各実装は、そのタイプのデータを、個別のmapタスクとして処理する意味がある領域に分割する方法を知っている（例えば、テキストモードの領域分割では、領域の分割は、確実に行の境界でのみ行われる）。ユーザは、簡単なreaderインタフェースの実装を提供することにより、新しい入力タイプへのサポートを追加できる。さらに、readerはファイルから読み出されたデータの提供に限定されない。例えば、readerはデータベースまたはメモリ中に割り振られたデータ構造からレコードを読み出すことができる。
【００９４】
同様のやり方で、本実装は様々なフォーマットでデータを生成する一連の出力タイプをサポートし、またユーザが新しい出力タイプのサポートを追加するためにコードを書くことは容易である。
【００９５】
ユーザまたは第３者のコード中のバグにより、map関数またはreduce関数があるレコードで決定的に機能停止することも時にはある。例えば、大きいデータ集合の統計的解析を行っているとき等、若干のレコードを無視することが受容可能な場合もある。本実装は、MapReduceライブラリが決定的機能停止を引き起こしたレコードを検出し、前進するためにこれらのレコードをスキップする、オプションとしての実行モードを提供する。
【００９６】
このモードのために、各ワーカのプロセスは、セグメンテーション違反およびバス誤りを捕捉する信号ハンドラ（handler）を組み込んでいる。ユーザのmapまたはreduceの実行を呼び出す前に、MapReduceライブラリは引数の順序番号をグローバル変数中に蓄積する。ユーザコードが信号を発生する場合、信号ハンドラはその順序番号を含む「最後のあえぎ（last gasp）」ＵＤＰ（User Datagram Protocol）パケットをMapReduceマスタに送信する。特定のレコードについて１つ以上の故障を見つけると、マスタは対応するmapまたはreduceタスクの次の再実行の指令発出に際して、そのレコードをスキップ（skip）するべきことを知らせる。
【００９７】
MapReduceに関するさらに多くの情報は、その内容が参照によって本明細書に組み込まれた非特許文献１で見つけることができる。
【００９８】
ローカリティセンシティブハッシュ体系を使用してユーザを複数のクラスタにクラスタリングするもう１つの方法についてここで簡単に説明しよう。この方法では、各ユーザは、ユーザを特徴付ける高次元のベクトルで表現されたプロフィールを有する。そのようなベクトル上で動作する一連のｋ個のハッシュ関数が選択される。ユーザプロフィールについての第ｉのハッシュ値はユーザが割り当てられる第ｉのクラスタを表す。本方法に有用なローカリティセンシティブハッシュ関数については非特許文献２に説明がある。
【００９９】
そのような方法のある実装では、ユーザは<term, weight>対のリストにより表現される。先述と同様、ｋはクラスタの数およびユーザに対して計算されるハッシュ値の数である。シード値の数は説明では８ｋで与えられようが、定数で与えられている８は一般にはパラメータである。８ｋ個のランダムなシード値は、s_1, s_2, ..., s_8kで示す文字列で表現され、例えば、２進表現でのビットの「０」または「１」が均等で、ランダムに見えるように選択される。どのユーザについても、第ｉのハッシュ値は以下のように計算される。
【０１００】
For b from 1 to 8:
do
initialize sum = 0;
for all <term_j, weight_j> pairs in the user's list:
do
if (fingerprint (term_j + s_((i-l)*8 + b)) has least significant bit = 1)
sum = sum + weight_j
else
sum = sum - weight_j
done
if (sum > 0)
b-th bit of i-th hash value is set to 1.
else
b-th bit of i-th hash value is set to 0.
done.
【０１０１】
fingerprint (term_j + s_((i-l)*8 + b)なる項は、シード文字列s_((i-l)*8 + b)、すなわち第((i-l)*8 + b)のシード文字列と連結された第ｊ項(term_j)のfingerprint関数（先述のように計算される）を表わす。
【０１０２】
本発明の実施形態および本明細書で説明した全ての機能的動作は、本明細書で開示された構造またはそれらの構造的等価物もしくはそれらの組合せを含む、デジタル電子回路、もしくはコンピュータソフトウェア、ファームウェア、またはハードウェアで実施可能である。本発明の実施形態は、１つ以上のコンピュータプログラム製品、すなわち、例えば、マシーン可読蓄積装置、マシーン可読蓄積媒体、メモリ装置、またはマシーン可読伝播信号、等のコンピュータ可読媒体上にコード化された、データ処理装置による実行に使用されるか、またはその動作を制御する、コンピュータプログラム命令の１つ以上のモジュールとして実施可能である。用語「データ処理装置」は、例として、プログラム可能プロセッサ、コンピュータ、もしくは多重プロセッサまたは多重コンピュータを含む、データを処理するための全ての装置およびマシーンを包含する。装置は、ハードウェアに加えて、問題になっているコンピュータプログラムのための実行環境を創り出すコード、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらの組合せを構成するコード、を含む。伝播信号は、例えば、機械により発生された電気的、光学的または電磁的信号等の人工的に発生された信号であり、好適な受信装置への転送用に情報を符号化するために発生される。
【０１０３】
コンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる）は、コンパイルまたはインタープリタ言語を含むどのような形式のプログラミング言語ででも書くことができ、スタンドアローンプログラムとしてもしくはモジュール、コンポーネント、サブルーチン、またはコンピュータ環境での使用に好適なその他の単位を含む任意の形式で配備できる。コンピュータプログラムは必ずしもファイルシステム中のファイルに対応しなくてもよい。プログラムは、他のプログラムまたはデータを保持するファイルの一部に（例えば、マークアップ言語文書中に蓄積された１つ以上のスクリプト）、問題になっているプログラムに専用の単一のファイルに、または複数の組織的なファイル（例えば、１つ以上のモジュール、サブプログラム、またはコードの一部を蓄積するファイル）に、蓄積することができる。コンピュータプログラムは、１つのコンピュータで、もしくは１つのサイトに配置された、または複数サイトにわたって分散され、通信ネットワークによって相互接続された、複数のコンピュータで、実行するために配備することができる。
【０１０４】
本明細書で説明したプロセスおよび論理の流れは、入力データに対して動作して出力を生成することにより機能を実行する１つ以上のコンピュータプログラムを実行する、１つ以上のプログラム可能なプロセッサによって実行することができる。例えば、ＦＰＧＡ（Field Programmable Gate Array、フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（Application-Specific Integrated Circuit、特定用途向け集積回路）等の特定用途論理回路により、そのプロセスおよび論理の流れを実行することもでき、装置を実装することもできる。
【０１０５】
コンピュータプログラムの実行に好適なプロセッサには、例として、汎用および特定目的用の両方のマイクロプロセッサ、ならびに任意の種類のデジタルコンピュータの任意の１つ以上のプロセッサが含まれる。一般に、プロセッサは読み出し専用メモリまたはランダムアクセスメモリもしくはその両方から命令とデータを受け取るであろう。コンピュータの本質的要素は、命令を実行するプロセッサおよび命令とデータを蓄積する１つ以上のメモリである。コンピュータはまた、一般に、データを蓄積するための１つ以上の大容量記憶装置、例えば、磁気、磁気光学ディスク、または光学ディスク、を含むか、またはそれらからデータを受信しまたはそれらへデータを送信しもしくはその両方を実行できるようそれらに接続されよう。しかし、コンピュータはそのような装置を持たなくてもよい。さらに、コンピュータは別の装置、幾つか名前を上げれば、例えば、移動電話機、携帯情報端末（ＰＤＡ、personal digital assistant）、携帯オーディオプレーヤ、全地球測位システム（ＧＰＳ、Global Positioning System）受信機、等に埋め込むこともできる。コンピュータプログラム命令およびデータを具体化するのに好適な情報担体には、全ての形態の不揮発性メモリ、例としては、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリ装置等の半導体メモリ装置、内蔵ハードディスクまたは取り外し可能ディスク等の磁気ディスク装置、磁気光学ディスク、およびＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスク、が含まれる。プロセッサおよびメモリは特定用途論理回路で補足することができ、またはそれに組み込むことができる。
【０１０６】
ユーザとの相互作用に備えて、本発明の実施形態は、情報をユーザに提示するための表示装置、例えば、ＣＲＴ（cathode ray tube、陰極線管）またはＬＣＤ（liquid crystal display、液晶ディスプレイ）モニタ、ならびにユーザがコンピュータに入力を与えることができるキーボードおよび指示装置、例えば、マウスまたはトラックボール、を有するコンピュータ上で実施することができる。その他の種類の装置もまたユーザとの相互作用に備えて使用することができ、例えば、ユーザに提供されるフィードバックは、例えば、視覚的フィードバック、聴覚的フィードバック、または触覚的フィードバック等の任意の形式の感覚フィードバックであってよく、またユーザからの入力は、音響、音声または触覚入力を含む任意の形式で受信されてよい。
【０１０７】
本発明の実施形態は、バックエンド構成要素、例えば、データサーバ等、を含む、またはミドルウェア構成要素、例えば、アプリケーションサーバ、を含む、またはフロントエンド構成要素、例えば、本発明の実装と相互作用できるようにするためのグラフィカルユーザインタフェースまたはウェブブラウザを有するクライアントコンピュータ、を含むコンピュータシステム中で実施することができ、もしくはそのようなバックエンド、ミドルウェア、またはフロントエンド構成要素の任意の組合せで実施することができる。システムの構成要素は、任意の形態または媒体の、通信ネットワーク等のデジタルデータ通信により相互接続することができる。通信ネットワークの例には、ローカルエリアネットワーク（「ＬＡＮ」）およびインターネット等の広域ネットワーク（「ＷＡＮ」）が含まれる。
【０１０８】
コンピュータシステムはクライアントおよびサーバを含むことができる。クライアントおよびサーバは、一般には相互に遠く離れており、通常は通信ネットワークを通して相互作用する。クライアントおよびサーバの関係は、それぞれのコンピュータ上で実行され、相互にクライアント−サーバ関係にあるコンピュータプログラムによって、発生する。
【０１０９】
本発明の特定の実施形態について説明をおこなった。その他の実施形態は添付の特許請求の範囲に含まれる。例えば、特許請求の範囲で列挙されるステップは、別の順序で実行することもでき、それでも所望の結果を得ることができる。
【符号の説明】
【０１１０】
４０２ａ、４０２ｂ ユーザ
４０４ 通信ネットワーク
４１０ ニュース推奨エンジン
４２０ ニュースサービス
４３０ ウェブサーバ
４４０ ログ
【特許請求の範囲】
【請求項１】
１つまたは複数のコンピュータと、該１つまたは複数のコンピュータに接続され、命令が記憶されたコンピュータ読み取り可能な媒体と、を備えるシステムであって、
前記命令は、前記１つまたは複数のコンピュータによって実行されるとき、前記１つまたは複数のコンピュータに動作を実行させ、
前記動作は、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得し、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成することを含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記動作は、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされるシステム。
【請求項２】
前記データ要素はテキスト列または２進データである請求項１に記載のシステム。
【請求項３】
前記指紋関数およびｋ個の異なるシード値を適用することは、
前記データ要素の各々に指紋関数およびそれぞれのシード値を適用することによって、前記ｋ個の異なるシード値の各々についてｉ個のハッシュ値を生成し、
前記ｋ個の異なるシード値の各々について、前記それぞれのシード値について生成されたｉ個のハッシュ値の中から最小のハッシュ値を選択し、
前記ｋ個のそれぞれの最小のハッシュ値をｋ個のミンハッシュ値の集合と定めることをさらに含み、
ｉは前記集合におけるデータ要素の数を表わす請求項１に記載のシステム。
【請求項４】
ｋは、５と１０を含む、５と１０の間の整数パラメータである請求項１に記載のシステム。
【請求項５】
各々の品目は、前記特定のユーザが選択した検索結果またはニュース記事である請求項１に記載のシステム。
【請求項６】
各々の品目は、前記特定のユーザが購入した、または、買い物カートに追加した品目である請求項１に記載のシステム。
【請求項７】
各々の品目は、ウェブページ間をナビゲートするために前記特定のユーザによってなされた一連の選択を表わす請求項１に記載のシステム。
【請求項８】
前記動作は、データの対の寄集めを取得することをさらに含み、各々のデータの対は、ユーザおよび該ユーザが興味を示した品目を識別し、
前記データ要素の集合を取得することは、前記特定のユーザを識別するデータをキーとして使用するreduceルーチンによって前記データの対の寄集めを処理することをさらに含む請求項１に記載のシステム。
【請求項９】
前記指紋関数はRAND関数であり、かつ、ハッシュ値は３２ビットの整数値であるか、または、
前記指紋関数はＭＤ５一方向ハッシュアルゴリズムを実行する関数であり、かつ、ハッシュ値は１２８ビットの値である請求項１に記載のシステム。
【請求項１０】
前記特定のユーザをｋ個のクラスタに割り当てることは、他のいずれのユーザをｋ個のクラスタのいずれに割り当てること、または、割り当てないことにも影響せずに行われる請求項１に記載のシステム。
【請求項１１】
前記動作は、
前記特定のユーザが前記品目に見せかけの興味を示したと判定し、
他のいずれのユーザをｋ個のクラスタのいずれに割り当てることにも影響せずに、前記ｋ個のミンハッシュ値によって表わされるｋ個のクラスタから前記特定のユーザを割り当て解除することをさらに含む請求項１に記載のシステム。
【請求項１２】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１に記載のシステム。
【請求項１３】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが編集したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが編集したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１に記載のシステム。
【請求項１４】
コンピュータに実装される方法であって、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得するステップと、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成するステップと、を含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記方法は、１つまたは複数のコンピュータにより、前記特定のユーザをｋ個のクラスタに割り当てるステップをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされる方法。
【請求項１５】
コンピュータプログラムで符号化されたコンピュータ記憶媒体であって、
前記コンピュータプログラムは、１つまたは複数のコンピュータによって実行されるとき、前記１つまたは複数のコンピュータに動作を実行させる命令を含み、
前記動作は、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得し、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成することを含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記動作は、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされるコンピュータ記憶媒体。
【請求項１６】
前記指紋関数およびｋ個の異なるシード値を適用することは、
前記データ要素の各々に指紋関数およびそれぞれのシード値を適用することによって、前記ｋ個の異なるシード値の各々についてｉ個のハッシュ値を生成し、
前記ｋ個の異なるシード値の各々について、前記それぞれのシード値について生成されたｉ個のハッシュ値の中から最小のハッシュ値を選択し、
前記ｋ個のそれぞれの最小のハッシュ値をｋ個のミンハッシュ値の集合と定めることをさらに含み、
ｉは前記集合におけるデータ要素の数を表わす請求項１５に記載のコンピュータ記憶媒体。
【請求項１７】
前記動作は、データの対の寄集めを取得することをさらに含み、各々のデータの対は、ユーザおよび該ユーザが興味を示した品目を識別し、
前記データ要素の集合を取得することは、前記特定のユーザを識別するデータをキーとして使用するreduceルーチンによって前記データの対の寄集めを処理することをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項１８】
前記特定のユーザをｋ個のクラスタに割り当てることは、他のいずれのユーザをｋ個のクラスタのいずれに割り当てること、または、割り当てないことにも影響せずに行われる請求項１５に記載のコンピュータ記憶媒体。
【請求項１９】
前記動作は、
前記特定のユーザが前記品目に見せかけの興味を示したと判定し、
他のいずれのユーザをｋ個のクラスタのいずれに割り当てることにも影響せずに、前記ｋ個のミンハッシュ値によって表わされるｋ個のクラスタから前記特定のユーザを割り当て解除することをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項２０】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項２１】
指紋関数、ランダムに選択されたｋ個の要素からなる順序集合、および各ユーザの興味集合中の要素を用いて値を計算し、計算された値のうち前記順序集合の各要素に対する最小値を使用してデータ処理システムのユーザをｋ個のクラスタに割り当てるステップを含み、ｋは１より大きい整数であり、前記興味集合中の各要素は、前記データ処理システムを使用する前記ユーザによる行動を通して前記ユーザが興味を示した品目を表わす
ことを特徴とするデータ処理システムの作動方法。
【請求項２２】
データ処理システムを使用する複数ユーザによって選択された品目のログと、
指紋関数、ランダムに選択されたｋ個のシード値、および各ユーザによって選択された品目のログを用いて値を計算し、計算された値のうち各シード値に対する最小値を使用して前記複数ユーザの各々をｋ個（ここでｋは１より大きい整数）のクラスタに割り当てる手段と、
ｋ個のクラスタの１つ以上への第１のユーザの前記割り当てに基づいて前記複数ユーザ中の前記第１のユーザに情報を提供できる協調フィルタリングのコンピュータプログラムアプリケーションと
を含むことを特徴とするシステム。
【請求項１】
１つまたは複数のコンピュータと、該１つまたは複数のコンピュータに接続され、命令が記憶されたコンピュータ読み取り可能な媒体と、を備えるシステムであって、
前記命令は、前記１つまたは複数のコンピュータによって実行されるとき、前記１つまたは複数のコンピュータに動作を実行させ、
前記動作は、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得し、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成することを含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記動作は、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされるシステム。
【請求項２】
前記データ要素はテキスト列または２進データである請求項１に記載のシステム。
【請求項３】
前記指紋関数およびｋ個の異なるシード値を適用することは、
前記データ要素の各々に指紋関数およびそれぞれのシード値を適用することによって、前記ｋ個の異なるシード値の各々についてｉ個のハッシュ値を生成し、
前記ｋ個の異なるシード値の各々について、前記それぞれのシード値について生成されたｉ個のハッシュ値の中から最小のハッシュ値を選択し、
前記ｋ個のそれぞれの最小のハッシュ値をｋ個のミンハッシュ値の集合と定めることをさらに含み、
ｉは前記集合におけるデータ要素の数を表わす請求項１に記載のシステム。
【請求項４】
ｋは、５と１０を含む、５と１０の間の整数パラメータである請求項１に記載のシステム。
【請求項５】
各々の品目は、前記特定のユーザが選択した検索結果またはニュース記事である請求項１に記載のシステム。
【請求項６】
各々の品目は、前記特定のユーザが購入した、または、買い物カートに追加した品目である請求項１に記載のシステム。
【請求項７】
各々の品目は、ウェブページ間をナビゲートするために前記特定のユーザによってなされた一連の選択を表わす請求項１に記載のシステム。
【請求項８】
前記動作は、データの対の寄集めを取得することをさらに含み、各々のデータの対は、ユーザおよび該ユーザが興味を示した品目を識別し、
前記データ要素の集合を取得することは、前記特定のユーザを識別するデータをキーとして使用するreduceルーチンによって前記データの対の寄集めを処理することをさらに含む請求項１に記載のシステム。
【請求項９】
前記指紋関数はRAND関数であり、かつ、ハッシュ値は３２ビットの整数値であるか、または、
前記指紋関数はＭＤ５一方向ハッシュアルゴリズムを実行する関数であり、かつ、ハッシュ値は１２８ビットの値である請求項１に記載のシステム。
【請求項１０】
前記特定のユーザをｋ個のクラスタに割り当てることは、他のいずれのユーザをｋ個のクラスタのいずれに割り当てること、または、割り当てないことにも影響せずに行われる請求項１に記載のシステム。
【請求項１１】
前記動作は、
前記特定のユーザが前記品目に見せかけの興味を示したと判定し、
他のいずれのユーザをｋ個のクラスタのいずれに割り当てることにも影響せずに、前記ｋ個のミンハッシュ値によって表わされるｋ個のクラスタから前記特定のユーザを割り当て解除することをさらに含む請求項１に記載のシステム。
【請求項１２】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１に記載のシステム。
【請求項１３】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが編集したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが編集したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１に記載のシステム。
【請求項１４】
コンピュータに実装される方法であって、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得するステップと、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成するステップと、を含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記方法は、１つまたは複数のコンピュータにより、前記特定のユーザをｋ個のクラスタに割り当てるステップをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされる方法。
【請求項１５】
コンピュータプログラムで符号化されたコンピュータ記憶媒体であって、
前記コンピュータプログラムは、１つまたは複数のコンピュータによって実行されるとき、前記１つまたは複数のコンピュータに動作を実行させる命令を含み、
前記動作は、
特定のユーザが１つまたは複数のウェブアプリケーションとの相互作用を通して興味を示した品目を表わすデータ要素の集合を取得し、
前記データ要素の各々に指紋関数およびｋ個の異なるシード値を適用してｋ個のミンハッシュ値の集合を生成することを含み、ｋは整数のパラメータであり、各々のミンハッシュ値は前記データ要素の集合のそれぞれのデータ要素に対応し、
前記動作は、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含み、ｋ個のクラスタの各々は前記ｋ個のミンハッシュ値のうちそれぞれ対応する１つによって表わされるコンピュータ記憶媒体。
【請求項１６】
前記指紋関数およびｋ個の異なるシード値を適用することは、
前記データ要素の各々に指紋関数およびそれぞれのシード値を適用することによって、前記ｋ個の異なるシード値の各々についてｉ個のハッシュ値を生成し、
前記ｋ個の異なるシード値の各々について、前記それぞれのシード値について生成されたｉ個のハッシュ値の中から最小のハッシュ値を選択し、
前記ｋ個のそれぞれの最小のハッシュ値をｋ個のミンハッシュ値の集合と定めることをさらに含み、
ｉは前記集合におけるデータ要素の数を表わす請求項１５に記載のコンピュータ記憶媒体。
【請求項１７】
前記動作は、データの対の寄集めを取得することをさらに含み、各々のデータの対は、ユーザおよび該ユーザが興味を示した品目を識別し、
前記データ要素の集合を取得することは、前記特定のユーザを識別するデータをキーとして使用するreduceルーチンによって前記データの対の寄集めを処理することをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項１８】
前記特定のユーザをｋ個のクラスタに割り当てることは、他のいずれのユーザをｋ個のクラスタのいずれに割り当てること、または、割り当てないことにも影響せずに行われる請求項１５に記載のコンピュータ記憶媒体。
【請求項１９】
前記動作は、
前記特定のユーザが前記品目に見せかけの興味を示したと判定し、
他のいずれのユーザをｋ個のクラスタのいずれに割り当てることにも影響せずに、前記ｋ個のミンハッシュ値によって表わされるｋ個のクラスタから前記特定のユーザを割り当て解除することをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項２０】
前記動作は、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定することをさらに含み、
前記特定のユーザをｋ個のクラスタに割り当てることは、前記特定のユーザが興味を示した品目を前記特定のユーザが明かそうと決心したと判定したことに応答して、前記特定のユーザをｋ個のクラスタに割り当てることをさらに含む請求項１５に記載のコンピュータ記憶媒体。
【請求項２１】
指紋関数、ランダムに選択されたｋ個の要素からなる順序集合、および各ユーザの興味集合中の要素を用いて値を計算し、計算された値のうち前記順序集合の各要素に対する最小値を使用してデータ処理システムのユーザをｋ個のクラスタに割り当てるステップを含み、ｋは１より大きい整数であり、前記興味集合中の各要素は、前記データ処理システムを使用する前記ユーザによる行動を通して前記ユーザが興味を示した品目を表わす
ことを特徴とするデータ処理システムの作動方法。
【請求項２２】
データ処理システムを使用する複数ユーザによって選択された品目のログと、
指紋関数、ランダムに選択されたｋ個のシード値、および各ユーザによって選択された品目のログを用いて値を計算し、計算された値のうち各シード値に対する最小値を使用して前記複数ユーザの各々をｋ個（ここでｋは１より大きい整数）のクラスタに割り当てる手段と、
ｋ個のクラスタの１つ以上への第１のユーザの前記割り当てに基づいて前記複数ユーザ中の前記第１のユーザに情報を提供できる協調フィルタリングのコンピュータプログラムアプリケーションと
を含むことを特徴とするシステム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１３−３３５５１（Ｐ２０１３−３３５５１Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１２−２５２０５６（Ｐ２０１２−２５２０５６）
【出願日】平成２４年１１月１６日（２０１２．１１．１６）
【分割の表示】特願２００８−５２７０６９（Ｐ２００８−５２７０６９）の分割
【原出願日】平成１８年８月１５日（２００６．８．１５）
【出願人】（５０７１０３８０２）グーグル・インコーポレーテッド (191)
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願日】平成２４年１１月１６日（２０１２．１１．１６）
【分割の表示】特願２００８−５２７０６９（Ｐ２００８−５２７０６９）の分割
【原出願日】平成１８年８月１５日（２００６．８．１５）
【出願人】（５０７１０３８０２）グーグル・インコーポレーテッド (191)
[ Back to top ]