(57)【特許請求の範囲】
【請求項１】
１又はそれ以上のコンピュータ装置によって、
１又はそれ以上のコンテンツ作成者の各々に関して、前記コンテンツ作成者が１又はそれ以上のコンテンツ項目を作成するコンテンツ作成率にアクセスするステップと、
１又はそれ以上のコンテンツ消費者の各々に関して、前記コンテンツ消費者が１又はそれ以上のコンテンツ項目を消費するコンテンツ消費率にアクセスするステップと、
前記コンテンツ作成者の１つと、該コンテンツ作成者をフォローする前記コンテンツ消費者の１つとを含む複数の消費者／作成者ペアの各々に関して、前記コンテンツ消費者の前記コンテンツ消費率及び前記コンテンツ作成者の前記コンテンツ作成率に基づいて、前記コンテンツ作成者から前記コンテンツ消費者に１又はそれ以上のコンテンツ項目を配信するためのプッシュ方式とプル方式の間で選択を行うステップと、
を含み、
前記プッシュ方式では、前記コンテンツ作成者が前記コンテンツ項目を作成したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信され、
前記プル方式では、前記コンテンツ消費者が前記コンテンツ項目を消費したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信される、
ことを特徴とする方法。
【請求項２】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が閾値よりも大きい場合には前記プッシュ方式を選択し、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が前記閾値よりも小さい場合には前記プル方式を選択する、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、全体的一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記全体的一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする全ての前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で前記コンテンツ項目が配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃがフォローする、ｐを含む全ての前記コンテンツ作成者をＰｃとし、
Ｐc内のコンテンツ作成者をｐjとし、
ｃの前記コンテンツ消費率をφcとし、
ｐjの前記コンテンツ作成率をφpjとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
0005450841.tif 000013
の場合、前記プッシュ方式を選択し、
0005450841.tif 000014
の場合、前記プル方式を選択する、
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、作成者ごとの一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記作成者ごとの一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする前記コンテンツ作成者の各々からのコンテンツ項目が、前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃの前記コンテンツ消費率をφcとし、
ｐの前記コンテンツ作成率をφpとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
（φc／φp）≧Ｃpush／Ｃpullの場合、前記方式を選択し、
（φc／φp）＜Ｃpush／Ｃpullの場合、前記プル方式を選択する、
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、レイテンシサービスレベル合意をさらに満たすことによって選択され、
前記レイテンシサービスレベル合意が満たされない場合、
前記プル方式を有する前記消費者／作成者ペアの１又はそれ以上を選択するステップと、
前記選択された消費者／作成者ペアを前記プッシュ方式に移行させるステップと、
をさらに含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記コンテンツ消費者の第１の消費者に関して、期間に関するコンテンツ消費パターンにアクセスするステップと、
前記第１のコンテンツ消費者と、前記コンテンツ作成者の１つとを含む前記消費者／作成者ペアの第１のペアに関して、前記第１のコンテンツ消費者の前記コンテンツ消費パターン及び前記コンテンツ項目が配信された時刻にさらに基づいて、前記コンテンツ作成者からの１又はそれ以上のコンテンツ項目を前記第１のコンテンツ消費者に配信するための前記プッシュ方式と前記プル方式の間で選択を行うステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
１又はそれ以上のプロセッサにより実行可能な命令を含むメモリと、
前記メモリに結合されて前記命令を実行する１又はそれ以上のプロセッサと、
を備えたシステムであって、前記１又はそれ以上のプロセッサが、前記命令の実行時に、
１又はそれ以上のコンテンツ作成者の各々に関して、前記コンテンツ作成者が１又はそれ以上のコンテンツ項目を作成するコンテンツ作成率にアクセスし、
１又はそれ以上のコンテンツ消費者の各々に関して、前記コンテンツ消費者が１又はそれ以上のコンテンツ項目を消費するコンテンツ消費率にアクセスし、
前記コンテンツ作成者の１つと、該コンテンツ作成者をフォローする前記コンテンツ消費者の１つとを含む複数の消費者／作成者ペアの各々に関して、前記コンテンツ消費者の前記コンテンツ消費率及び前記コンテンツ作成者の前記コンテンツ作成率に基づいて、前記コンテンツ作成者から前記コンテンツ消費者に１又はそれ以上のコンテンツ項目を配信するためのプッシュ方式とプル方式の間で選択を行い、
前記プッシュ方式では、前記コンテンツ作成者が前記コンテンツ項目を作成したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信され、
前記プル方式では、前記コンテンツ消費者が前記コンテンツ項目を消費したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信される、
ことを特徴とするシステム。
【請求項１０】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が閾値よりも大きい場合には前記プッシュ方式を選択し、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が前記閾値よりも小さい場合には前記プル方式を選択する、
ことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、全体的一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記全体的一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする全ての前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で前記コンテンツ項目が配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項９に記載のシステム。
【請求項１２】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃがフォローする、ｐを含む全ての前記コンテンツ作成者をＰｃとし、
Ｐc内のコンテンツ作成者をｐjとし、
ｃの前記コンテンツ消費率をφcとし、
ｐjの前記コンテンツ作成率をφpjとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
0005450841.tif 000015
の場合、前記プッシュ方式を選択し、
0005450841.tif 000016
の場合、前記プル方式を選択する、
ことを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、作成者ごとの一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記作成者ごとの一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする前記コンテンツ作成者の各々からのコンテンツ項目が、前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項９に記載のシステム。
【請求項１４】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃの前記コンテンツ消費率をφcとし、
ｐの前記コンテンツ作成率をφpとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
（φc／φp）≧Ｃpush／Ｃpullの場合、前記方式を選択し、
（φc／φp）＜Ｃpush／Ｃpullの場合、前記プル方式を選択する、
ことを特徴とする請求項１３に記載のシステム。
【請求項１５】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、レイテンシサービスレベル合意をさらに満たすことによって選択され、
前記１又はそれ以上のプロセッサが、前記命令の実行時にさらに、
前記レイテンシサービスレベル合意が満たされない場合、
前記プル方式を有する前記消費者／作成者ペアの１又はそれ以上を選択し、
前記選択された消費者／作成者ペアを前記プッシュ方式に移行させる、
ことを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記１又はそれ以上のプロセッサが、前記命令の実行時にさらに、
前記コンテンツ消費者の第１の消費者に関して、期間に関するコンテンツ消費パターンにアクセスし、
前記第１のコンテンツ消費者と、前記コンテンツ作成者の１つとを含む前記消費者／作成者ペアの第１のペアに関して、前記第１のコンテンツ消費者の前記コンテンツ消費パターン及び前記コンテンツ項目が配信された時刻にさらに基づいて、前記コンテンツ作成者からの１又はそれ以上のコンテンツ項目を前記第１のコンテンツ消費者に配信するための前記プッシュ方式と前記プル方式の間で選択を行う、
ことを特徴とする請求項９に記載のシステム。
【請求項１７】
ソフトウェアを具体化する１又はそれ以上のコンピュータ可読有形記憶媒体であって、前記ソフトウェアが、１又はそれ以上のコンピュータシステムによる実行時に、
１又はそれ以上のコンテンツ作成者の各々に関して、前記コンテンツ作成者が１又はそれ以上のコンテンツ項目を作成するコンテンツ作成率にアクセスし、
１又はそれ以上のコンテンツ消費者の各々に関して、前記コンテンツ消費者が１又はそれ以上のコンテンツ項目を消費するコンテンツ消費率にアクセスし、
前記コンテンツ作成者の１つと、該コンテンツ作成者をフォローする前記コンテンツ消費者の１つとを含む複数の消費者／作成者ペアの各々に関して、前記コンテンツ消費者の前記コンテンツ消費率及び前記コンテンツ作成者の前記コンテンツ作成率に基づいて、前記コンテンツ作成者から前記コンテンツ消費者に１又はそれ以上のコンテンツ項目を配信するためのプッシュ方式とプル方式の間で選択を行い、
前記プッシュ方式では、前記コンテンツ作成者が前記コンテンツ項目を作成したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信され、
前記プル方式では、前記コンテンツ消費者が前記コンテンツ項目を消費したときに、前記コンテンツ項目の各々が前記コンテンツ作成者から前記コンテンツ消費者に配信される、
ことを特徴とする１又はそれ以上のコンピュータ可読有形記憶媒体。
【請求項１８】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が閾値よりも大きい場合には前記プッシュ方式を選択し、
前記コンテンツ消費者の前記コンテンツ消費率と前記コンテンツ作成者の前記コンテンツ作成率の間の比率が前記閾値よりも小さい場合には前記プル方式を選択する、
ことを特徴とする請求項１７に記載の媒体。
【請求項１９】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、全体的一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記全体的一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする全ての前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で前記コンテンツ項目が配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項１７に記載の媒体。
【請求項２０】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃがフォローする、ｐを含む全ての前記コンテンツ作成者をＰｃとし、
Ｐc内のコンテンツ作成者をｐjとし、
ｃの前記コンテンツ消費率をφcとし、
ｐjの前記コンテンツ作成率をφpjとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
0005450841.tif 000017
の場合、前記プッシュ方式を選択し、
0005450841.tif 000018
の場合、前記プル方式を選択する、
ことを特徴とする請求項１９に記載の媒体。
【請求項２１】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、作成者ごとの一貫性を維持しながらコストを最小化することによって選択され、
前記コストが、前記消費者／作成者ペア間で前記コンテンツ項目を配信する総リソースコストであり、
前記作成者ごとの一貫性が、前記コンテンツ消費者の各々に関して、前記コンテンツ消費者がフォローする前記コンテンツ作成者の各々からのコンテンツ項目が、前記コンテンツ作成者が作成した全ての前記コンテンツ項目のタイムスタンプに従う順序で配信されることを保証し、各コンテンツ項目の前記タイムスタンプが、前記コンテンツ項目が作成された時刻を示す、
ことを特徴とする請求項１７に記載の媒体。
【請求項２２】
前記消費者／作成者ペアの各々に関して、
前記コンテンツ消費者をｃとし、
前記コンテンツ作成者をｐとし、
ｃの前記コンテンツ消費率をφcとし、
ｐの前記コンテンツ作成率をφpとし、
ｃにコンテンツ項目をプッシュするためのコストをＣpushとし、
ｐから一定数のコンテンツ項目をプルするためのコストをＣpullとして、
（φc／φp）≧Ｃpush／Ｃpullの場合、前記方式を選択し、
（φc／φp）＜Ｃpush／Ｃpullの場合、前記プル方式を選択する、
ことを特徴とする請求項２１に記載の媒体。
【請求項２３】
前記消費者／作成者ペアの各々に関して、前記プッシュ方式又は前記プル方式が、レイテンシサービスレベル合意をさらに満たすことによって選択され、
前記１又はそれ以上のプロセッサが、前記命令の実行時にさらに、
前記レイテンシサービスレベル合意が満たされない場合、
前記プル方式を有する前記消費者／作成者ペアの１又はそれ以上を選択し、
前記選択された消費者／作成者ペアを前記プッシュ方式に移行させる、
ことを特徴とする請求項２２に記載の媒体。
【請求項２４】
前記１又はそれ以上のプロセッサが、前記命令の実行時にさらに、
前記コンテンツ消費者の第１の消費者に関して、期間に関するコンテンツ消費パターンにアクセスし、
前記第１のコンテンツ消費者と、前記コンテンツ作成者の１つとを含む前記消費者／作成者ペアの第１のペアに関して、前記第１のコンテンツ消費者の前記コンテンツ消費パターン及び前記コンテンツ項目が配信された時刻にさらに基づいて、前記コンテンツ作成者からの１又はそれ以上のコンテンツ項目を前記第１のコンテンツ消費者に配信するための前記プッシュ方式と前記プル方式の間で選択を行う、
ことを特徴とする請求項１７に記載の媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
〔関連出願〕
本出願は、２０１０年３月１日に出願された米国特許本出願第１２／７１４，８７６号に対して優先権を主張するＰＣＴ出願であり、この特許本出願はその全体が引用により本明細書に組み入れられる。
【０００２】
本開示は、一般に、複数のコンテンツ作成者と複数のコンテンツ消費者の間に複数のコンテンツフィードを構築することに関し、より詳細には、コンテンツフィードの各々を分析して、コンテンツフィードのためのプッシュ方式とプル方式の間で選択を行うことに関する。
【背景技術】
【０００３】
インターネットユーザは、起きていることに関する最新情報を得たいと思っている。この目的のために、Ｔｗｉｔｔｅｒ及びＦａｃｅｂｏｏｋなどのソーシャルネットワーキングサイトは、あるユーザの友人が作成したステータスアップデート、投稿写真、動画レビューなどのフィードをユーザに提供する。Ｍｙ  Ｙａｈｏｏ及びｉＧｏｏｇｌｅなどのコンテンツアグリゲータは、複数のＲＳＳソースからのカスタマイズされたウェブページ集約フィードを提供する。同様に、Ｄｉｇｇ及びＲｅｄｄｉｔなどのニュースアグリゲータは、「娯楽」及び「技術」などのトピックに関する最新記事のフィードを提供し、ＣＮＮ．ｃｏｍなどのニュースサイトは、「健康討論」などの細分化されたトピックをフォローする機能を提供する。
【０００４】
近リアルタイムのコンテンツフィードは、多くの人気のあるウェブアプリケーションの重要な特徴になってきている。一例として、Ｔｗｉｔｔｅｒ及びＦａｃｅｂｏｏｋ上でユーザが作成したイベント、及びｉＧｏｏｇｌｅ及びＭｙ  Ｙａｈｏｏ上の特定のトピックに関するニュース記事がある。この結果、これらのウェブアプリケーションは、ユーザのフィードからの最新コンテンツを表示するウェブページを効率的に構成できることがますます重要になっている。このようなフィードの構築は、ウェブページが素早くロードを行うように高速でなければならない。しかしながら、コンテンツの広いファンアウト（例えば、ソースによっては多くのフォロワーが存在すること）及び高いスキュー（例えば、ファンアウト及び速度が大きく変化すること）により、このようなアプリケーションをスケーリングすることが困難になる。
【発明の概要】
【課題を解決するための手段】
【０００５】
本開示は、一般に、複数のコンテンツ作成者と複数のコンテンツ消費者の間に複数のコンテンツフィードを構築することに関し、より詳細には、コンテンツフィードの各々を分析して、コンテンツフィードのためのプッシュ方式とプル方式の間で選択を行うことに関する。
【０００６】
特定の実施形態では、１又はそれ以上のコンテンツ作成者の各々に関して、コンテンツ作成者が１又はそれ以上のコンテンツ項目を作成するコンテンツ作成率にアクセスし、１又はそれ以上のコンテンツ消費者の各々に関して、コンテンツ消費者が１又はそれ以上のコンテンツ項目を消費するコンテンツ消費率にアクセスする。コンテンツ作成者の１つと、このコンテンツ作成者をフォローするコンテンツ消費者の１つとを含む複数の消費者／作成者ペアの各々に関して、コンテンツ消費者のコンテンツ消費率及びコンテンツ作成者のコンテンツ作成率に基づいて、コンテンツ作成者からコンテンツ消費者に１又はそれ以上のコンテンツ項目を配信するためのプッシュ方式とプル方式の間で選択を行う。プッシュ方式では、コンテンツ作成者がコンテンツ項目を作成したときに、コンテンツ項目の各々がコンテンツ作成者からコンテンツ消費者に配信される。プル方式では、コンテンツ消費者がコンテンツ項目を消費したときに、コンテンツ項目の各々がコンテンツ作成者からコンテンツ消費者に配信される。
【０００７】
以下の詳細な説明において、及び以下の図に関連して、本開示のこれらの及びその他の特徴、態様、及び利点をより詳細に説明する。
【図面の簡単な説明】
【０００８】
【図１】個々のコンテンツフィードの方式を決定する方法例を示す図である。
【図２】接続ネットワーク例を示す図である。
【図３】個々のコンテンツフィードの方式を決定するためのシステムアーキテクチャ例を示す図である。
【図４】ネットワーク環境例を示す図である。
【図５】コンピュータシステム例を示す図である。
【発明を実施するための形態】
【０００９】
以下、添付図面に示す本開示のいくつかの実施形態を参照しながら本開示についてより詳細に説明する。以下の説明では、本開示を完全に理解できるように数多くの特定の詳細を示している。しかしながら、当業者には、これらの特定の詳細の一部又は全部を伴わずに本開示を実施できることが明らかである。その他の場合、本開示を不必要に曖昧にしないために、周知の処理ステップ及び／又は構造については詳しく説明していない。また、本開示を特定の実施形態に関連して説明しているが、この説明は、説明する実施形態に本開示を限定するものではないと理解されたい。逆に、この説明は、添付の特許請求の範囲に定める本開示の思想及び範囲に含まれ得るような代替物、修正物、及び同等物も対象とすることを意図している。
【００１０】
コンテンツフィードは、ウェブフィード又は単純に「フィード」とも呼ばれ、コンテンツ、特に頻繁に更新されるコンテンツをネットワークユーザ間で配信するための機構のことである。コンテンツフィードは、様々なフォーマットをとることができる。例えば、ＲＳＳ（「リアリー・シンプル・シンジケーション」として最も一般的に展開されている）は、コンテンツを配信するために広く使用されているウェブフィードフォーマットのファミリである。同様に、限定ではなく一例として、ブログエントリ、ニュースの見出し、イベント、オーディオ、及びビデオなどの、コンテンツフィードを介して配信されるコンテンツも様々なフォーマットをとることができる。本開示では、あらゆる適用可能なコンテンツフィード及びコンテンツを考慮する。コンテンツフィードは、コンテンツ作成者とコンテンツ消費者をそれぞれの末端において概念的に接続する。特定の実施形態では、コンテンツ作成者、又は単純には作成者を、１又はそれ以上のコンテンツ消費者が消費できるコンテンツを作成するエンティティとする。一方で、コンテンツ消費者、又は単純には消費者を、１又はそれ以上のコンテンツ作成者が作成したコンテンツを消費するエンティティとする。この意味において、消費者は、１又はそれ以上の作成者が作成したコンテンツを「フォローする」、又はこのコンテンツのフォロワーであると言うことができる。コンテンツは、作成者と消費者を接続するフィードを介して作成者から消費者に配信することができる。なお、１つのエンティティが、ある時には他方が消費するコンテンツを作成し、別の時には他方が作成したコンテンツを消費することもあるので、１つのエンティティを作成者と消費者の両方とすることもできる。従って、一方のエンティティがもう一方のエンティティのためにコンテンツを作成する場合のフィードについては、このエンティティを作成者と呼び、同じエンティティがもう一方のエンティティからのコンテンツを消費する場合の別のフィードについては、このエンティティを消費者と呼ぶ。時には、エンティティＡ及びエンティティＢという２つのエンティティを、互い同士の作成者及び消費者とすることもできる。すなわち、エンティティＢが消費するコンテンツをエンティティＡが作成できる場合もあれば、エンティティＡが消費するコンテンツをエンティティＢが作成できる場合もある。従って、両方ともにエンティティＡとエンティティＢを接続する２つの別個のフィードが存在することができる。一方のフィードでは、エンティティＡが作成者であってエンティティＢが消費者であり、もう一方のフィードでは、エンティティＢが作成者であってエンティティＡが消費者である。また、作成者は、この作成者が作成するコンテンツのオリジナル制作者であってもよく、又はそうでなくてもよい。例えば、作成者は、元々は他のニュースレポーターが書いたニュース記事を作成してもよく、元々は他の写真家が撮影したデジタル写真を作成してもよく、或いはこの作成者自身が記録したビデオクリップを作成してもよい。
【００１１】
特定の実施形態では、フォローアプリケーションが、限定ではなく一例として、別のユーザ又はコンテンツカテゴリ又はトピックとすることができる１又はそれ以上の関心を、ユーザがフォローできるようにする。この場合、関心をフォローするユーザが消費者である。フォローアプリケーションの目的は、ユーザがフォローしている全ての作成者にわたる最近の又は最新のコンテンツを組み合わせたリストである、関心をフォローするユーザ（すなわち、消費者）のためのフィードを作成することである。例えば、フィードは、ソーシャルサイト上のユーザの友人全員からの最近のステータスアップデート、又はコンテンツ集約サイト上のユーザのトピック全てに関する最近の記事を組み合わせることができる。場合によっては、ユーザは、ソーシャルアップデートとトピックアップデートをいずれも含む組み合わせたフィードの方を好むことがある。特定の実施形態では、フォローアプリケーションに関連して、作成者が、特定のフォロー可能な関心に関する、人間が読める一連の時系列のコンテンツを生成することができる。従って、ユーザ（すなわち、消費者）にとっては、作成者は、友人であっても、ウェブサイトであっても、或いは複数のソースから収集された特定のトピックに関するコンテンツのアグリゲータであってもよい。
【００１２】
フォローアプリケーションは、スケーリングが難しいことで知られている。このアプリケーションは、高スループットのコンテンツに継続的に対応しなければならない。例えば、Ｔｗｉｔｔｅｒの技術者が、システムの人気が高まるにつれて急速に増加するスループットに対応するようにＴｗｉｔｔｅｒのバックエンドを何度も設計し直したと記述していることは有名である。同時に、関心をフォローするユーザは、ユーザのフィードページにおける素早いロードを期待しており、このことは、レイテンシを厳密に制限しなければならないことを意味する。この結果、多くの場合、具現化及びキャッシングが広範囲に及び、資本支出及び経常支出が増大する。例えば、Ｄｉｇｇは、大量のデータを非正規化して具現化することを選んで、自社の（例えば、自分の友人がどの記事を発掘したかをフォローする）「グリーンバッジアプリケーション」のレイテンシを短縮し、結果的に記憶データが数十ギガバイトから３テラバイトにまで膨らんだ。
【００１３】
このようなフォローアプリケーションのスケーリングが難しいことにはいくつかの理由がある。まず、コンテンツがファンアウトして、システム内に負荷に倍数的な影響をもたらす。例えば、アシュトン・カッチャーが「ツイート」すると、彼のステータスアップデートは常に３８０万人のフォロワーに伝播される。より中程度の平均的なファンアウトでも、スケーリングの問題を引き起こすことがある。次に、このファンアウトのスキューが高く、適切な方式を選ぶのが難しくなる。例えば、報道によれば、Ｆａｃｅｂｏｏｋは、ファンアウトの狭い大半のユーザと比較してファンアウトの広いバンド及び政治家などのユーザには、異なるフィード具現化方式を採用している。
【００１４】
例えば、フォローアプリケーションが直面する問題の少なくともいくつかに対処してアプリケーション性能を向上させるために、特定の実施形態は、各消費者のフィードを選択的に具現化する。特定の実施形態では、率の高い作成者からのコンテンツをクエリ時に検索し（すなわち、プル方式）、率の低い作成者からのコンテンツを事前に具現化する（すなわち、プッシュ方式）。さらに、形式的な問題分析では、適切な方式は、所与の作成者のコンテンツ作成率と所与の消費者のコンテンツ消費率の比率（ページビュー率など）に依存すると示されている。従って、一部の作成者を一部の消費者のために具現化してその他は具現化せず、消費者のフィードのいくつかの部分を具現化して他の部分を具現化しないようにすることができる。実際のウェブデータベースインフラストラクチャを使用した実験結果では、このハイブリッド方式によってシステム負荷が最低になり、従って様々な作業負荷においてスケーラビリティが向上することが示されている。
【００１５】
上述したように、作成者は、１又はそれ以上の消費者が消費するコンテンツを作成することができ、消費者は、１又はそれ以上の作成者が作成したコンテンツを消費することができる。さらに、コンテンツは、作成者と消費者を接続するフィードを介して作成者から消費者に配信される。理論的には、作成者がコンテンツを作成した時刻と消費者がコンテンツを消費した時刻の間のあらゆる時点において、所与のコンテンツを作成者から消費者に配信することができる。コンテンツについては、作成者がコンテンツを作成した時刻を、「具現化」タイム（すなわち、コンテンツが具現化される）と呼ぶことができ、消費者がコンテンツを消費した時刻を、「クエリ」タイム（すなわち、消費者がコンテンツを消費するためにクエリ又は要求を行う）と呼ぶことができる。
【００１６】
特定の実施形態では、作成者と消費者の間でコンテンツを管理するための方式として、プッシュ及びプルの２つが存在する。特定の実施形態では、プッシュ方式の場合、作成者がコンテンツを作成した時点で、コンテンツをフォローする消費者の各々にコンテンツが配信（すなわちプッシュ）され、従ってこのプッシュ方式を、従来のデータベース用語を使用して「具現化」方式と呼ぶことができる。対照的に、プル方式の場合、消費者が消費するためにコンテンツを要求した時点で、コンテンツを作成した作成者の各々から消費者がフォローするコンテンツが検索（すなわち、プル）され、従ってこのプル方式を、従来のデータベース用語を使用して「クエリ」方式と呼ぶことができる。時にはプッシュ方式の方が良いこともあり、消費者が、フォローしているコンテンツを消費する（フォローアプリケーションを使用してコンテンツにクエリを行う）準備ができている場合、消費者のフィードが事前に計算されて、システム負荷及びレイテンシが減少するようになる。対照的に、作成者がコンテンツを作成する率に比べて、消費者がコンテンツを消費する頻度が低い場合にはプル方式の方が良い。通常は、最も新しいＮ個のコンテンツしか表示する必要がないので、消費者にこれらを消費する（例えば、見る又はダウンロードする）機会が来る前に、後で新しいコンテンツに取って代わられる大量のコンテンツをプッシュ及び具現化することは無駄である。
【００１７】
特定の実施形態の方法は、同じアプリケーション内であっても、プッシュの方が良い場合もあれば、プルの方が良い場合もあるという見識に基づく。実際に、特定の実施形態では、特定の消費者のフィードをプッシュとプル両方の組み合わせとすることができる。これは、コンテンツ作成率におけるスキューに起因する。例えば、１時間に１回コンテンツを要求する特定の消費者は、１つの作成者のコンテンツ作成率よりも高い頻度でコンテンツを消費し（すなわち、消費者のコンテンツ消費率が１つの作成者のコンテンツ作成率よりも高く、従ってプッシュの方が良い）、別の作成者のコンテンツ作成率よりも低い頻度でコンテンツを消費している（すなわち、消費者のコンテンツ消費率が別の作成者のコンテンツ作成率よりも低く、従ってプルの方が良い）ことがある。特定の実施形態は、作成者をｐとし、消費者をｃとする、（ｐ，ｃ）ごとにプッシュ／プルの決定を行う。実際のフォローアプリケーションを使用した実験及び経験では、この方法の方が、純粋なプッシュシステム又は純粋なプルシステムよりも上手くスケーリングを行うことが示されている。当然ながら、この作成者と消費者の相対的なコンテンツ作成とコンテンツ消費の割合に基づいて（ｐ，ｃ）ごとにプッシュ／プルの決定をそれぞれ行うという概念は、フォローアプリケーション以外にも、あらゆる消費者／作成者タイプのアプリケーションに適用されるように拡張することができる。
【００１８】
このフォローの問題は、以前に研究されたデータベースシステムの問題に類似している。例えば、インデックス及びビュー選択の背景では、「具現化か否か」という議論が頻繁に検討される。しかしながら、このフォローの問題の背景では、いずれのビューを作成するかではなく、１つの「フィード」ビューのどれだけを具現化するかが議論となる。特定の実施形態は、部分的に具現化されたビュー及びインデックスに関する研究から、概念の一部（例えば、頻繁にアクセスされるデータを具現化すること）を借用することができる。しかしながら、以前の研究とは異なり、所与の基本タプルに関して単一の「具現化か否か」の決定を行うことはできず、代わりに、各消費者／作成者ペアに関して、これらの相対的なコンテンツ作成とコンテンツ消費の割合に基づいて決定を行う必要がある。
【００１９】
図１に、個々のコンテンツフィードの方式を決定する方法例を示す。簡単に言えば、特定の実施形態は、作成者から消費者にコンテンツを配信するためのプッシュコスト及びプルコストを計算し（ステップ１１０）、消費者／作成者ペアに関して、プッシュ方式又はプル方式のいずれかの配信コストが低い方を選択する（ステップ１２０）。この２つのステップを、作成者と消費者の固有のペアごとに繰り返すことができる。
【００２０】
以下の表１に、本開示で使用する表記法を示す。個々の概念については、以下でより詳細に説明する。
0005450841.tif 000002
表１：表記法
【００２１】
特定の実施形態では、作成者の組が生成したコンテンツストリームをフォローしている消費者の組（フォローアプリケーションのユーザなど）が存在する。各消費者は、フォローしたいと思う作成者を選択することができる。特定の実施形態では、消費者が特定の作成者をフォローすることを選択した場合、この作成者が作成したコンテンツが、適当な時点で消費者に配信される。特定の実施形態では、作成者が、人間が読めるタイムスタンプ付きの一連の名前を付けたコンテンツを生成することができる。作成者の例として、「アシュトン・カッチャーのツイート」又は「地球温暖化に関するニュース記事」を挙げることができる。作成者は、人（フォローアプリケーションのユーザなど）であっても、ウェブサイト（ニュースサイト又はブログなど）であっても、又は複数のソースから得られるコンテンツのアグリゲータであってもよい。特定の実施形態は、異なるトピックのコンテンツが同じウェブサイト又はデータソース（すなわち、同じエンティティ）から来たものであっても、図１のステップを説明する場合には、各フォロー可能な「トピック」（「地球温暖化」又は「健康討論」など）を別個の作成者として扱う。すなわち、１つの作成者が複数のコンテンツストリームを作成した場合、各コンテンツストリームは別個に分析される。特定の実施形態では、作成された時刻によってコンテンツに順序が付けられるが、代替の実施形態では、他の順序付け方法を使用することができる。
【００２２】
特定の実施形態は、頂点の組をＶ、フォローエッジの組をＦとする有向グラフＧ（Ｖ，Ｆ）としての接続ネットワークを定義することができる。特定の実施形態では、各頂点ｖi∈Ｖが、消費者又は作成者のいずれかを表し、ｃiがｐjをフォローする（例えば、ｐjが作成したコンテンツをｃiが消費する）場合、作成者頂点ｐjと消費者頂点ｃiの間にフォローエッジｆi,j∈Ｆが存在する。図２に、複数の作成者頂点及び複数の消費者頂点を有する接続ネットワーク例２００を示す。当然ながら、接続ネットワークは、あらゆる数の作成者及び消費者を含むことができ、個々の作成者と消費者の間にはあらゆる数の接続（すなわち、フォローエッジ）が存在することができる。ソーシャルネットワークは、接続ネットワークの１つの種類の一例であるが、あらゆる消費者／作成者グラフを接続ネットワークとすることができ、本開示は、あらゆる適用可能な接続ネットワークを考慮する。特定の実施形態は、接続ネットワークを、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ（Ｐｒｏｄｕｃｅｒ，Ｃｏｎｓｕｍｅｒ）の関係と見なすことができる。
【００２３】
特定の実施形態では、この接続ネットワークを、作成者、消費者、又はこれらの両方による効率的な検索をサポートする形で明示的に記憶することができる。例えば、１又はそれ以上の関心を持った消費者に対して作成者ｐjからコンテンツをプッシュするには、特定の実施形態では、接続ネットワーク内でｐjを検索して、このコンテンツをフォローする消費者の組を検索することができ、このことが｛ｃi：ｆi,j∈Ｆ｝として示される。対照的に、１又はそれ以上の作成者から消費者ｃiのためのコンテンツをプルするには、特定の実施形態では、接続ネットワーク内でｃiを検索して、この消費者がフォローする作成者の組を検索することができ、このことが｛ｐj：ｆi,j∈Ｆ｝として示される。この後者の場合、特定の実施形態は、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ（Ｐｒｏｄｕｃｅｒ，Ｃｏｎｓｕｍｅｒ）としての関係を実際に定義して、消費者によるクラスタリングをサポートすることができる。作成者を介したアクセス経路と消費者を介したアクセス経路を両方ともサポートするために、特定の実施形態は、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋの関係に加えてインデックスを構築することができる。
【００２４】
特定の実施形態では、コンテンツ自体が、Ｃｏｎｔｅｎｔ（ＣｏｎｔｅｎｔＩＤ，Ｐｒｏｄｕｃｅｒ，Ｔｉｍｅｓｔａｍｐ，Ｐａｙｌｏａｄ）としての関係を論理的に形成する。効率化のために、特定の実施形態は、（１）作成者中心：コンテンツが作成者によってＰｒｏｄｕｃｅｄＰｉｖｏｔｅｄ（Ｐｒｏｄｕｃｅｒ，ＣｏｎｔｅｎｔＩＤ，Ｔｉｍｅｓｔａｍｐ，Ｐａｙｌｏａｄ）の関係でクラスタ化される、及び（２）消費者中心：コンテンツが消費者ごとにＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄ（Ｃｏｎｓｕｍｅｒ，Ｐｒｏｄｕｃｅｒ，ＣｏｎｔｅｎｔＩＤ，Ｔｉｍｅｓｔａｍｐ，Ｐａｙｌｏａｄ）の関係で複製されクラスタ化される、という方法の一方又は両方でコンテンツを記憶することができる。
【００２５】
作成者中心のモデルは、プル方式をサポートする。コンテンツの組を検索して消費者に表示するために、特定の実施形態は、消費者がフォローしている対応する作成者の組を（例えば、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋから）検索し、次にＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄテーブル内の各作成者を調べて最近のコンテンツを検索する（例えば、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ  ＪＯＩＮ  ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄの統合）。対照的に、消費者中心のモデルは、プッシュ方式をサポートする。プッシュの場合、特定の実施形態は、コンテンツの作成者をフォローしている各消費者のタプルを挿入することにより、コンテンツをＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄの関係に具現化する。この場合、消費者のフィードの検索は、消費者の全てのタプルの範囲スキャンとなる。実際には、特定の実施形態は、Ｃｏｎｔｅｎｔｓを明示的に記憶する必要はなく、代わりに特定の実施形態は、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄの関係を記憶してこれにクエリを行い、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ  ＪＯＩＮ  ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄの統合のビューとしてＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄを具現化することができる。
【００２６】
上述したように、特定の実施形態は、どの作成者が作成したコンテンツをどの消費者がフォローしているかを示すフォローエッジごとに、プッシュ方式とプル方式の間で個別に選択を行う。換言すれば、特定の実施形態は、ＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄに具現化されるコンテンツもあれば、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄに記憶だけされて必要時にプルされるコンテンツもあるというハイブリッド方式を検討する。ここでも、接続ネットワーク内の消費者／作成者ペアごとにこの決定が行われる。
【００２７】
特定の実施形態は、コンテンツが（例えば、消費者が使用するネットワーク装置を介して）消費者に配信又は表示された場合には常に、消費者がそのコンテンツフィード（又は単純にフィード）を検索したと言うことができる。このコンテンツ検索は、消費者がウェブサイトにログオンすること、又はウェブサイト上のページをリフレッシュすることなどの様々な要因によってトリガすることができる。特定の実施形態では、例えば、Ａｊａｘ、Ｆｌａｓｈ又は他のいずれかの適当な技術を使用して、消費者の更新されたフィードを自動的に検索することができる。特定の実施形態では、このフィード自体が、消費者によりフォローされる作成者の１又はそれ以上からの順序付けられた一群のコンテンツを表示する。通常、フィードは、Ｎ個の最新のコンテンツしか表示しないが、消費者は、（例えば、「次」をクリックすることにより）以前のコンテンツを要求することができる。
【００２８】
特定の実施形態は、自身のフィードに関する消費者の期待値を獲得するいくつかの特性を定義することができる。まず、フィードは時系列で並ぶべきであり、すなわちフィード内のコンテンツをタイムスタンプ順に表示して、フィード内のいずれか２つのコンテンツｃｔ1及びｃｔ2に関して、Ｔｉｍｅｓｔａｍｐ（ｃｔ1）＜Ｔｉｍｅｓｔａｍｐ（ｃｔ2）の場合、コンテンツを古い順で表示した場合には、フィード内でｃｔ1がｃｔ2の前に表示され、コンテンツを新しい順で表示した場合には、フィード内でｃｔ2がｃｔ1の前に表示されるようにすべきである。例えば、コンテンツがウェブページ内に表示される場合、先に表示されたコンテンツの方が、後から表示されたコンテンツよりもウェブページの上部に近い。次に、フィード内のコンテンツはギャップレスとすべきであり、すなわち特定の作成者からのコンテンツをギャップなしで表示して、作成者ｐからのコンテンツにｃｔ1及びｃｔ2の２つが存在し、フィード内でｃｔ1がｃｔ2に先行し、ｃｔ1の後に続きｃｔ2に先行するｐからのコンテンツがフィード内にない場合、ｐが作成したコンテンツにｃｔ1よりも大きくｃｔ2よりも小さなタイムスタンプを有するものがない（古い順で表示した場合）ようにすべきである。３番目に、フィード内にコンテンツの複製が存在してはならず、すなわちフィード内に２回以上現れるコンテンツｃｔkは存在してはならない。
【００２９】
消費者が、自身のフィードを２回検索した場合、１回目の検索と２回目の検索の間でフィードがどのように変化したかに関する何らかの期待が存在し得る。例えば、消費者が、１回目の検索から特定の順序のいくつかのコンテンツを確認した場合、この消費者は、通常、２回目の検索からもこれらのコンテンツが同じ順序で表示されることを期待する。例えば、Ｎ＝５個のコンテンツを含むフィード例について検討する。午後２時に検索された消費者のフィードは、以下を含むことができる。
0005450841.tif 000003
表２：第１のフィード例
【００３０】
消費者は、午後２：０２に、自身のウェブページをリフレッシュして新たなバージョンのフィード検索されるようにすることができる。午後２：００から午後２：０２の間に、アリスからの２つの新たなコンテンツが作成されたと仮定する。
0005450841.tif 000004
表３：第２のフィード例（全体的一貫性を使用）
【００３１】
第２のフィード例では、アリスが作成した２つの新たなコンテンツｃｔ6及びｃｔ7により、２つの最も古いコンテンツｃｔ1及びｃｔ2がフィードから消される一方で、全てのコンテンツの全体的な順序が、消費者の作成者全体にわたって保たれている。この特性（すなわち、全てのコンテンツの全体的な順序を保つこと）を「全体的一貫性」と呼ぶことができ、すなわちフィード内のコンテンツの順序は、消費者の作成者からの全てのコンテンツの潜在的なタイムスタンプ順に一致し、１つのフィードのビューから次のビューまでにコンテンツの順序は入れ替わられない。このモデルは、電子メールを時系列で表示するほとんどの電子メールリーダに類似しており、Ｔｗｉｔｔｅｒなどのフォローアプリケーションで使用されている。
【００３２】
しかしながら、場合によっては、全体的一貫性が望ましくないこともある。表３のフィード例について検討する。アリスのコンテンツは多いが、ボブのコンテンツはない。一部の作成者のコンテンツ率が、他の作成者よりも一時的に又は持続的に高くなった場合、異なる作成者が作成したコンテンツという意味におけるこのような多様性の欠如が生じ得る。フィードの多様性については、以下でより詳細に説明する。多様性を保つために、消費者は、「作成者ごとの一貫性」を選ぶことができ、この場合、所与の作成者からのコンテンツの順序は保たれるが、異なる作成者間のコンテンツの相対的順序に関する保証はされない。作成者ごとの一貫性の下では、消費者が自身のフィードを午後２：０２にリフレッシュした場合、消費者が目にするのは以下の通りである。
0005450841.tif 000005
表４：第３のフィード例（作成者ごとの一貫性を使用）
【００３３】
この第３のフィード例は、追加されたアリスのコンテンツｃｔ6及びｃｔ7によってボブのコンテンツｃｔ2が第３のフィード例から消されていないので多様性を保っている。しかしながら、第２のフィード例では、ボブのコンテンツｃｔ2とチャドのコンテンツｃｔ4の間にアリスのコンテンツｃｔ3が存在するが、第３のフィード例では存在しない。このコンテンツの「消失」は、全体的一貫性の下では可能でないが、多様性の保持に役立てるために作成者ごとの一貫性の下では可能となる。
【００３４】
コンテンツ作成率又はコンテンツ消費率には、多くの消費者／作成者アプリケーション（フォローアプリケーションなど）に固有のスキューが存在するので、特定の実施形態は、多様性を保つための明示的なステップをとる必要がある。例えば、１日に１回アプリケーションにログインするユーザ（「ユーザ」は、消費者／作成者アプリケーションのユーザを意味し、作成者又は消費者又はこれらの両方のいずれであってもよい）、デービッドについて検討する。彼の父親（例えば、第２のユーザ）ボブは、１日に１回だけコンテンツを作成することができ、彼の姉（例えば、第３のユーザ）アリスは、１時間に１回新たなコンテンツを生成する。デービッドは、ログインすると、アリスからの最近のコンテンツの方がはるかに多いにもかかわらず、父親ボブの最新のコンテンツを見たいと思う。
【００３５】
特定の実施形態では、多様性を定義するための単純な方法は、消費者のフィードが、消費者がフォローする作成者の各々からのコンテンツを一般的には少なくとも１個又はそれ以上、少なくともｋ個含まなければならないと指定することである。しかしながら、消費者は、フィードのスロットよりも多くの作成者をフォローすることがあり、全ての作成者からのコンテンツを少なくともｋ個表示することは不可能である。さらに、特定の実施形態は、この制約を満たすだけのために、必ずしも極端に古いコンテンツを表示したいとは思わない。例えば、ボブの最新のコンテンツが１年前のものである場合、極端に古いコンテンツは消費者にとって陳腐な又は無意味なものとなりがちであるため、特定の実施形態は、たとえボブのコンテンツがゼロであることが示されるとしても、デービッドのフィードにこれを含めたいとは思わない。
【００３６】
従って、特定の実施形態は、ｋ，ｔ−多様性の概念を定義する。特定の実施形態では、上記の例を非形式的に使用して、ｋ，ｔ−多様性により、最後のｔ個の時間単位内にボブからのコンテンツが存在する場合、ボブのコンテンツがフィード内に表示されない場合にはフィード内にアリスからのコンテンツをｋ個しか表示しないようにすべきであると指定する。より形式的には、消費者ｃがフォローする２つの作成者ｐj及びｐjについて検討する。特定の実施形態は、ｔ秒よりも古くない作成者ｐからのコンテンツの数としてＣａｎｄｉｄａｔｅ（ｐ，ｔ）を、ｃのフィード内に表示される作成者ｐからのコンテンツの数としてＣｏｕｎｔ（ｐ）を定義する。次に、ｋ，ｔ−多様性を、Ｃａｎｄｉｄａｔｅ（ｐi，ｔ）＞０、かつＣｏｕｎｔ（ｐi）＝０の場合、Ｃｏｕｎｔ（ｐj）≦ｋ、と定義することができる。
【００３７】
再び、第１、第２、及び第３のフィード例について検討する。ｔ＝６００秒及びｋ＝１と指定されていると仮定する。この場合、（表３に示す）第２のフィード例は、Ｃａｎｄｉｄａｔｅ（ボブ，６００秒）＝１及びＣｏｕｎｔ（ボブ）＝０であるが、Ｃｏｕｎｔ（アリス）＞１となるので認められない。しかしながら、第３のフィード例は認められる。なお、場合によっては、より強力な多様性の概念が好ましい。例えば、実際にボブのコンテンツが多く存在する場合、フィード内にアリスのコンテンツを１０個表示し、ボブのコンテンツを１個しか表示しないのは好ましくない場合がある。従って、特定の実施形態は、表示するコンテンツ内で何らかの「エントロピー」の概念を最大化したいと望むことができる。しかしながら、本開示では、ｋ，ｔ−多様性が最小の多様性概念を捉え、最小の多様性概念でさえ全体的一貫性の保証と衝突することを示している。
【００３８】
フィードの生成にはシステム処理が必要である。例えば、プルの場合はクエリ時に、又はプッシュの場合はコンテンツ作成時に作業が行われる。この処理によってシステムにかかる作業負荷の種類（すなわち、必要なシステムリソースの量）はアーキテクチャに依存する。例えば、データをディスク上で具現化する場合、主なコストは、メモリとの間でデータの読み取り及び書き込みを行うことから生じる入力／出力（Ｉ／Ｏ）コストとなる可能性が高い。一方、多くの消費者／作成者アプリケーション（フォローアプリケーションなど）では、データが、実行のためにランダムアクセスメモリ（ＲＡＭ）内でのみ具現化される。この場合、主なコストは、プロセッサ（ＣＰＵなど）コストとなる可能性が高い。
【００３９】
特定の実施形態は、システムのボトルネックリソース（Ｉ／Ｏ又はＣＰＵなど）の総使用量としてＣｏｓｔ（）を形式的に定義する。この使用量は、作成時におけるコンテンツの処理、及びクエリ時におけるフィードの生成をいずれも含むことができる。この場合、特定の実施形態では、消費者／作成者アプリケーションの一般的な最適化問題を、Ｃｏｓｔ（）を最小化する一方で、（１）時系列の、ギャップレスな、複製されていないフィードを提供すること、（２）選択した一貫性レベル（全体的又は作成者ごとなど）を尊重すること、及び（３）作成者ごとの一貫性を使用する場合にはｋ，ｔ−多様性を保証すること、として定義することができる。また、特定の実施形態は、消費者／作成者アプリケーションを最適化する際にレイテンシを（例えば、付加的な制約として）考慮することができ、この場合、レイテンシを短縮するために何らかの追加のシステムコストを取引することができる。消費者／作成者アプリケーションのレイテンシ制約の最適化問題は、Ｃｏｓｔ（）を最小化する一方で、（１）時系列の、ギャップレスな、複製されていないフィードを提供すること、（２）選択した一貫性レベル（全体的又は作成者ごとなど）を尊重すること、（３）作成者ごとの一貫性を使用する場合にはｋ，ｔ−多様性を保証すること、及び（４）ＮパーセンタイルレイテンシがＬ未満であることを保証すること、として定義することができる。１つの事例では、９９パーセンタイルレイテンシが５０ミリ秒未満となるように指定することができる。この制約は、コンテンツをプッシュするか、それともプルするかに関する様々な決定を行うこと（例えば、より多くのコンテンツをプッシュして、クエリ時間レイテンシが制約を満たすようにすること）につながり得る。
【００４０】
作成者は、原子エンティティ（アプリケーションユーザ又はニュースウェブサイトなど）であっても、又は他の複数のサイトのアグリゲータであってもよい。アグリゲータは、複数のソースからの所与のトピックに関する単一のコンテンツストリームを作成できるので、一部の消費者／作成者アプリケーションにとっては重要である。さらに、アグリゲータは、通常は新たなコンテンツをプッシュしないソースから情報を抽出することができる。特定の実施形態は、原子作成者とアグリゲート作成者を同様に扱い、これらのコンテンツ作成率及びファンアウトのみを考慮する。しかしながら、特定の実施形態では、より一般的な問題を、アグリゲータが行わなければならない決定、すなわち、所与のアップストリームソースに関して、アグリゲータがプッシュを使用すべきか、それともプルを使用すべきかを調査することとすることができる。この決定は、ある消費者／作成者ペアに関してプッシュするか、それともプルするかを決定するときに特定の実施形態が行う決定に類似する場合もあるが、（例えば、どれほど頻繁にプルするか、及びプッシュコスト又はプルコストが異なるアップストリームソースをどのように処理するかなどの）さらなる複雑性も存在する。
【００４１】
上述したように、特定の実施形態は、コンテンツを処理するために、プッシュ及びプルという２つの方式を考慮することができる。特定の実施形態では、これらの方式を細かい粒度で選択することが取り組みとなる。特定の実施形態は、所与の消費者に関して、（コンテンツ作成の観点から）比較的頻度の低い作成者の場合はプッシュすることを選択し、（コンテンツ作成の観点から）比較的頻度の高い作成者の場合はプルすることを選択することができる。コンテンツ消費頻度又はコンテンツクエリ頻度は異なるが作成者は同じであるという消費者に関しては、異なる決定を行うことができる。特定の実施形態は、所与の（消費者、作成者）ペアに関して、作成者のコンテンツ作成頻度と消費者のコンテンツ消費頻度の間の比率を調べることができる。この比率の値が閾値要件を満たすかどうかに応じて、特定の実施形態は、この特定の（消費者、作成者）ペアに関してプッシュ方式又はプル方式のいずれかを選択することができる。特定の実施形態では、この比率に関する閾値要件を実験に基づいて決定することができる。例えば、１つの実施構成では、実験結果に基づいて、ある（消費者、作成者）ペアに関して、コンテンツ作成頻度とコンテンツ消費頻度の比率が約３よりも大きい場合にはプッシュ方式が選択され、それ以外はプル方式が選択される。
【００４２】
時には、特定の消費者又は作成者が、ある期間（例えば、１日又は１週間）にわたり、そのコンテンツ消費又はコンテンツ作成活動に関して、異なるけれども予測可能な行動パターンを示すことがある。特定の実施形態は、各（消費者、作成者）ペアに関してプッシュ方式とプル方式の間で選択を行うときに、このような行動パターンを考慮することができる。より詳細には、特定の実施形態は、コンテンツ作成頻度又はコンテンツ消費頻度とともに、又はこれの代わりに時間に基づいてプッシュとプルの間で決定を行うことができる。例えば、ある消費者が、通常は頻繁にコンテンツを消費していると仮定すると、この相対的に高いコンテンツ消費頻度からは、一般にこの消費者に関してはプッシュ方式を使用すべきであると提案がなされる。しかしながら、消費者の行動パターンが、消費者が毎日深夜から午前７：００の間にはコンテンツを全く要求（すなわち、消費）しないことを示すこともある。従って、いずれかのコンテンツが深夜から午前７：００の間に作成された場合には、プル方式を使用してこのコンテンツを配信することができる。さらに、消費者が午前７：００以降に行う最初の要求に関してもプル方式を使用することができる。
【００４３】
作成者は、１又はそれ以上のコンテンツを、（例えば、１日にｎj個のコンテンツを作成するなどの）特定のコンテンツ作成頻度のペースφpjで作成することができ、消費者は、（必ずしも同じ作成者が作成したものではない）１又はそれ以上のコンテンツを、（例えば、１日にｎi個のコンテンツを消費するなどの）特定のコンテンツ消費頻度のペースφciで消費することができる。当然ながら、現実的には、作成者及び消費者は、必ずしもこのような一貫したルーチンには従わず、各エンティティが作成又は消費する実際のコンテンツ数は、その日その日で異なることがある。従って、特定の実施形態は、ある期間にわたる各作成者及び消費者の統計値を表す平均的又は中間的コンテンツ作成頻度又はコンテンツ消費頻度を使用することができる。
【００４４】
特定の実施形態では、各（作成者、消費者）ペアにプッシュ又はプルの決定を割り当てることにより、上記で定めた「Ｃｏｓｔ（）を最小化する」という課題を、作成者ごとの一貫性及び全体的一貫性の場合の両方に関して解決することができる。特定の実施形態では、次にクエリレイテンシを制約として加えることができ、この制約を満たすために必要な追加コストを最小化する。最後に、特定の実施形態は、「エンティティ」が上流の作成者の消費者及び下流の消費者への作成者の両方として機能するようにする消費者／作成者アプリケーションの最適化問題のより一般的な公式化を検討することができる。
【００４５】
特定の実施形態では、接続ネットワークＧ（Ｖ，Ｆ）が、作成者から消費者への２部グラフである。消費者ｃiがコンテンツを求めるクエリを実行した場合、ｃiのフィードにいくつかのコンテンツを提供する必要がある。このシナリオに関して、上述した両方の一貫性の場合について検討する。全体的一貫性の場合には、特定の実施形態は、Ｆi（すなわち、ｃiがフォローする作成者の組）内の全ての作成者にわたる最新のπg個のコンテンツを供給する。作成者ごとの一貫性の場合には、特定の実施形態は、Ｆi内の各作成者の最新のπp個のコンテンツを供給する。
【００４６】
あらゆるシステムには、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄのコンテンツストア及びＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄのフィードビューストアの記憶量の決定に応じて独自のプッシュ及びプルコストが伴う。ｃiのフィードにコンテンツをプッシュするコストをＨiとし、作成者ｐjから一定数のコンテンツをプルするコストをＬjとする。大抵の場合、特定の実施形態は、πgとπpがいずれも十分に小さいので、Ｌjが各々にとって同じになると仮定することができる。特定の実施形態は、プルを使用して単一の作成者から複数のコンテンツを検索できるとさらに仮定することができる。これにより、コンテンツが作成者によってクラスタ化され、単一の遠隔手順呼出しによって複数のコンテンツを検索でき、（例えば、ディスク検索がコストを占めるので）少数のコンテンツの場合にはコンテンツを検索するためのディスクコスト（あるとすれば）が一定であると仮定する。
【００４７】
特定の実施形態は、コンテンツが個別にシステムに到着し、コンテンツを取り込んでＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄテーブルに書き込むためのコストを考慮せず、このコストを、考えられる全てのポリシーに関して同じとすることができる単純なモデルを仮定することができる。従って、プッシュ／プルの決定を行うことができる粒度は、コンテンツごと、消費者ごとであり、特定の実施形態は、このようなペアごとにプッシュ又はプルを個別に選択することができる。同様に、システムコストもこの粒度で分析することができる。
【００４８】
さらに、特定の実施形態は、システム内で負荷が増加した場合でも、Ｈi及びＬjのコストが一定であると仮定することができる。しかしながら、コンテンツ率又は作成者のファンアウトが増えるにつれてシステムボトルネックが変化した場合、この仮定は真でなくなることもある。例えば、特定の実施形態は、メモリ内のデータを具現化すると決定することができる。一方で、メインメモリの量が制限されており、ＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄの合計サイズがシステムの集約ＲＡＭを超えて増大した場合、データがディスクに溢れて、プッシュ及びプルコストがディスクアクセスを含むように変化する可能性がある。通常、実際のところは、消費者／作成者アプリケーションが十分なリソース（メモリ、帯域幅、ＣＰＵなど）を提供して、これらのボトルネックの変化を避けてＨi及びＬjを一定に保つことができる。特定の実施形態では、分析により、データが完全にメモリ内に存在すると仮定することはないが、システムが拡張するときにコストが一定であると仮定する。
【００４９】
まず、作成者ごとの一貫性に関するコスト最適化について詳細に説明する。消費者ｃi、作成者ｐj、及びコンテンツｃｔj,kに関して、特定の実施形態は、ｃｔj,kをｃiに配信するための生涯コストを導出する。特定の実施形態では、ｃｔj,kの寿命は、これが作成されてから、ｐjが次のπp個のコンテンツを作成したときまでの時間である。
【００５０】
特定の実施形態は、以下の観察を行う。
【００５１】
観察１。プルコストが、１回のプルで取得した全てのコンテンツにわたって償却され、プッシュ及びプルコストが一定であると仮定する。ｐjによるｃiへのコンテンツのプッシュ及びプルの生涯コストは、消費者のコンテンツクエリ率φci及び作成者のコンテンツ作成率φpjに依存する。
Ｐｕｓｈ＝Ｈi
Ｐｕｌｌ＝Ｌj（φci／φpj）
【００５２】
観察１は、以下のように証明することができる。プッシュコストは、コンテンツの寿命を意識せず、特定のコンテンツに対してＨiが１回支払われる。一方、プルコストは、コンテンツの寿命に依存する。コンテンツｃｔj,kは、πp／φpjという寿命を有する。この寿命にわたって、ｃiがｃｔj,kを見る回数は、φci（πp／φpj）である。ｃｔj,kをプルするためのコストは、Ｌj／πpである（Ｌjは、個々のプルされたコンテンツにわたって償却される）。従って、ｃｔj,kの生涯コストは、Ｌj（φci／φpj）＝（Ｌj／πp）φci（πp／φpj）となる。
【００５３】
この結果、特定の実施形態は、所与の（作成者、消費者）ペアに関して、プッシュコストの方がプルコストよりも低い場合にはコンテンツをプッシュすべきであり、プルコストの方がプッシュコストよりも低い場合にはコンテンツをプルすべきであると結論付けることができる。特定の実施形態は、結果として生じる不均衡から、以下のような最適な決定ルールを導出することができる。
【００５４】
補助定理１。
（φci／φpj）≧Ｈi／Ｌjの場合、ｐjによる全てのコンテンツをプッシュする。
（φci／φpj）＜Ｈi／Ｌjの場合、ｐjによる全てのコンテンツをプルする。
この場合、プッシュかプルかの決定は、観察１におけるコストから直接引き出される。
【００５５】
次に、全体的一貫性に関するコスト最適化についてより詳細に説明する。全体的一貫性要件では、消費者ｃiのフィードが、Ｆi（すなわち、ｃiがフォローする全ての作成者の組）内の全ての作成者にわたるπg個の最新コンテンツを含む。
【００５６】
特定の実施形態は以下の観察を行う。
【００５７】
観察２。プッシュコスト及びプルコストが一定であると仮定する。
Ｐｕｓｈ＝Ｈi
0005450841.tif 000006
【００５８】
観察２は、いくつかの重要な違いはあるが、作成者ごとの場合と同様に証明することができる。作成者のコンテンツ作成頻度は、Ｆi：
0005450841.tif 000007
の全てにわたる集合である。コンテンツｃｔj,kの寿命はπg／φFiであり、その償却されるプルコストはＬj／πgである。これらの項を、作成者ごとの分析に代入して、全体的一貫性のプッシュコスト及びプルコストに至ることができる。
【００５９】
次に、特定の実施形態は、全体的一貫性の場合における最適な（作成者、消費者）ペアの決定ルールを以下のように導出することができる。
【００６０】
補助定理２。
0005450841.tif 000008
の場合、ｐjによる全てのコンテンツをプッシュする。
0005450841.tif 000009
の場合、ｐjによる全てのコンテンツをプルする。
この場合、プッシュかプルかの決定は、観察２におけるコストから直接引き出される。
【００６１】
補助定理１及び２からの主な発見は、以下のように要約することができる。作成者ごとの一貫性の下では、特定の消費者にコンテンツを配信するための生涯コストが、消費者のコンテンツ消費頻度及びコンテンツの作成者のコンテンツ作成頻度の両方に依存する。全体的一貫性の下では、消費者にコンテンツを配信するための生涯コストが、消費者のコンテンツ消費頻度及び消費者がフォローする作成者の集約コンテンツ作成頻度の両方に依存する。この結果、特定の実施形態は、以下の２つの定理を提案する。
【００６２】
定理１。作成者ごとの一貫性では、補助定理１により決定された（作成者、消費者）ペアごとのプッシュとプルの比較を使用して、各（作成者、消費者）ペアに関してプッシュ又はプルを別個に選択することにより、システムコストを最小化する全体的最適計画が導出される。
【００６３】
作成者ごとの一貫性の場合、特定の実施形態は、コンテンツごとに支払われるコストを最小化することによって全体的コストを最小化する。同様に、特定の実施形態は、そのコンテンツに支払われるコストを消費者ごとに最小化することによってコンテンツのコストを最小化する。補助定理１は、消費者と作成者の間のエッジ上にある単一のコンテンツに支払われるコストを最小化するように各エッジを割り当てる。さらに、いずれか１つのエッジに割り当てが行われなければ、他のいずれかのエッジに行うことができる割り当てにいずれかの制約が課される。従って、消費者及びコンテンツごとのコストを最小化することにより、全体的コストが最小化される。
【００６４】
定理２。全体的一貫性では、補助定理２により決定された消費者ごとのプッシュとプルの比較を使用して、各消費者に関してプッシュ又はプルを別個に選択することにより、システムコストを最小化する全体的最適計画が導出される。
【００６５】
全体的一貫性の場合、補助定理１は、全てのエッジをプッシュ又はプルのいずれかに割り当てる。ここでも、エッジ割り当てがなければ、他のいずれかのエッジの割り当てが制限される。従って、消費者及びコンテンツごとのコストを最小化することにより、全体的コストが最小化される。以下、ＭｉｎＣｏｓｔは、最小コストを表すものとする。
【００６６】
定理１及び２は、重要な実用的意義を有する。いずれのシステムも、異なるコンテンツクエリ率及びコンテンツ作成率、及びこれらの率にいずれの消費者又は作成者が最も多く貢献するかを制御するスキューの影響を受ける可能性がある。実際には、システムコストを最適化するために、これらのパターンを抽出又は理解する必要はない。代わりに、プッシュかプルかの決定を最適に行うために、特定の実施形態は、消費者のコンテンツクエリ率を個別に測定し、消費者がフォローする作成者のコンテンツ作成率と個別に又は全体的に比較すればよい。
【００６７】
３番目に、コスト最適化問題が、追加のクエリレイテンシ制約（すなわち、クエリレイテンシを最適化するとともにコストを最小化する）の下で分析され、これをレイテンシサービスレベル合意（ＳＬＡ）を満たすものとして表すことができる。コンピュータネットワークの背景では、ＳＬＡを使用して、個々のネットワークエンティティ又は構成要素によるコンピューティングリソースの割り当て及び使用を制御することができる。例えば、特定のフォローアプリケーションは、フィードクエリの９５％が１００ｍｓ未満で実行することを強要することができる。場合によっては、最小のプッシュコスト対プルコスト方式がＳＬＡを満たすことも可能である。しかしながら、場合によってはそうでないこともあり、この場合、特定の実施形態は、プッシュとプルを取引（コンテンツクエリ時にはプッシュがあまり機能しないように撤回）し、従ってシステムコストは上がるがレイテンシを下げることができる。いくつかの事例では、特定の実施形態が、プッシュのみの方式に移行して、極めて厳しいＳＬＡを満たさなくてもよい。以下、ＬａｔｅｎｃｙＣｏｎｓｔｒａｉｎｅｄＭｉｎＣｏｓｔは、クエリレイテンシ制約も満たす最小コストを表すものとする。
【００６８】
フォローイング分析は、プッシュすることが役立つけれどコストがかかるという中間の場合を対象とする。実際には、所与のシステムがＳＬＡを満たすためにどれほどの追加プッシュを行うかを推測的に予測するのは困難である。従って、特定の実施形態は、結果がＳＬＡに収束するまで、追加プッシュの量を増分的に調整できる欲張りアルゴリズムを利用することができる。最適ではないが、多くの実際の設定ではこの方法が合理的である。フォローイング分析では、特定の実施形態において、目標プッシュ量の認識を仮定する。
【００６９】
Ｍｉｎｃｏｓｔがλmのレイテンシを生み出すものとする。この分析は、ＳＬＡを満たすためには、全てのクエリが行われた（消費者、作成者）ペアの一部λlをプッシュする必要があり、最小コストの解決策がペアの一部λoをプッシュし、この場合λo≦λlであるという仮定に基づくものである。特定の実施形態は、（消費者、作成者）ペアをプルからプッシュに移行させるときに支払われるコスト面でのペナルティとしてεを定義する。形式的には、作成者ごとの一貫性では、εi,j＝φpj（Ｈ−Ｌj（φci／φpj））となる。これは、コンテンツごとに支払われる、プルの代わりにプッシュを行うための追加コストにｐjのコンテンツ作成率を乗じたものである。
【００７０】
消費者／作成者エッジｆi,jをプルからプッシュに移行させる利点は、コンテンツクエリ時（すなわち、消費者がコンテンツを消費する時点）にコンテンツの取得にかかる時間を短縮することによってもたらされ、φciが全体的なコンテンツクエリ率に寄与するクエリの割合に依存する。直観的には、コンテンツクエリ頻度の低い消費者よりもコンテンツクエリ頻度の高い消費者に対してプッシュを行った方が多くの利益を得ることができる。なお、このことは、λlの値を推測できないことを意味するが、これはλlのサイズが、いずれのエッジが最終的にプッシュに変換されるかに依存するためである。
【００７１】
特定の実施形態では、いずれの（消費者、作成者）ペアをプルからプッシュに移行させるかを選択することが問題である。特定の実施形態は、この問題を「ナップサック問題」の例に単純化することができる。通常、ナップサック問題の目標は、各々が特定の「スコア」に貢献するオブジェクトでナップサックを満たすことである。各オブジェクトは「重み」を有し、この重み制限を超えずにスコアの和を最大にすることが目的である。特定の実施形態は、（作成者、消費者）ペアを「オブジェクト」として概念化する（すなわち、各（作成者、消費者）ペアをオブジェクトと見なす）。オブジェクトοkはスコアφk及び重みεkを有し、この場合、φkは、消費者のコンテンツクエリ率に等しく、εkは（プルからプッシュに移行することにより生じる追加コストなどの）ペナルティである。全てのオブジェクトのλlの割合がプッシュされるように、十分なオブジェクトをプルからプッシュに移行することが目標となる。従って、特定の実施形態は、最適解でプルされるオブジェクトのうち、総スコアがλl−λoのオブジェクトをプッシュに移行させる必要がある。
【００７２】
Ｍｉｎｃｏｓｔでプルされるエッジの組について検討する。ＬａｔｅｎｃｙＣｏｎｓｔｒａｉｎｅｄＭｉｎＣｏｓｔを発見するには、プッシュに移行させるためのこれらのエッジのサブセットＳを、
0005450841.tif 000010
及び
0005450841.tif 000011
が最小化されるように選択することが課題となる。Ｓの値を直接求める問題は、ナップサック問題に類似しているが、微妙に異なる。「容量」の制約はない。レイテンシを少なくともλm−λlだけ減少させる必要がある一方で、レイテンシをさらに減少させることもできる。この問題はナップサック問題に類似する。
【００７３】
検討していない実施上の問題が２つある。まず、ナップサック問題はＮＰ困難である。次に、理論上は、ｆi,jをプッシュに移行させることによるレイテンシの短縮としてσi,jが定義されるが、実際には、エッジをプッシュに移行させることによって得られる利益を正確に予測するのは非常に困難である。特定の実施形態は、これらの２つの問題を適応的アルゴリズムで解決することができる。エッジをプッシュに移行させることによる正確なレイテンシの短縮を把握することは難しいが、直観では、コンテンツ消費頻度の高い消費者を選択すれば、より多くのフィード検索のレイテンシが短縮されるので、短縮が大きくなるはずであると考えられる。次に、特定の実施形態は、プロキシとしてσi,j＝φciを設定する。このプロキシを使用した結果、エッジの相対的利益は分かるが、エッジの組の候補Ｓがレイテンシをλm−λlだけ短縮するかどうかは直接的には分からない。従って、特定の実施形態は、レイテンシをλm−λlだけ短縮するΣφciを推定してＳの値を求めることから開始し、次に、ＳからＬａｔｅｎｃｙＣｏｎｓｔｒａｉｎｅｄＭｉｎＣｏｓｔの解が得られる（すなわち、ＳＬＡを厳密に満たす）かどうかを実際に測定する。レイテンシが依然として高すぎる場合には、より大きなΣφciの値を求める必要があり、レイテンシがＳＬＡよりも低い場合には、より小さなΣφciの値を求める必要がある。従って、直ぐに正しい解が得られる可能性は低い。
【００７４】
特定の実施形態は、目標のΣφciが調整されたときにのみ増分コストを負担する解を探す。さらに、ナップサック問題はＮＰ困難であるため、この解が、最適解の好適な近似をもたらす必要がある。特定の実施形態は、この両方の問題に対処するために、最適解の欲張り近似を生成する適応的アルゴリズムを使用する。このような欲張り近似は、実際に有効であると期待される。特定の実施形態は、φci／σi,jによってプルエッジを降順にソートし、次に上位にランクされたいくつかのエッジをプッシュに移行させることができる。レイテンシがＳＬＡよりも高い場合、上位にランクされたプルエッジを増分的にプッシュに移行させることができる。レイテンシがＳＬＡよりも低い場合、下位にランクされたプッシュエッジを増分的にプルに移行させることができる。なお、特定の実施形態は、エッジがＭｉｎｃｏｓｔでプッシュに割り当てられている場合には、決してこれらのエッジをプルに移行させることはない。
【００７５】
適応的アルゴリズムは、開始点としてＭｉｎｃｏｓｔから実行することができる。特定の実施形態は、このアルゴリズムを定期的に繰り返して、ＬａｔｅｎｃｙＣｏｎｓｔｒａｉｎｅｄＭｉｎＣｏｓｔの解が得られることを確実にする。例えば、複数の消費者が新たな関心（例えば、新たな（作成者、消費者）ペア）を追加し、Ｍｉｎｃｏｓｔのために最適化を行うシステムが、これらに対してプル方式を選択したと仮定する。これらの新たな（作成者、消費者）ペアは、たとえ既存の（作成者、消費者）ペアに関してプッシュ／プルの決定が変更されなかった場合でも、レイテンシを増大させる可能性がある。従って、システムを再度ＬａｔｅｎｃｙＣｏｎｓｔｒａｉｎｅｄＭｉｎＣｏｓｔに移行させるために、適応的アルゴリズムを繰り返してエッジをプッシュに移行させる必要がある。
【００７６】
このアルゴリズムが常に最適解を発見するとは限らないが、実際に適切かつはるかに実用的である可能性が最も高い。特定の実施形態では、プッシュかプルかの決定がシステムに組み込まれる。欲張り解は、異なる目標レイテンシに効率的に適合するという利点を有する。ＳＬＡを満たすために、このシステムは、所望のレイテンシに達するまで単純にＳにオブジェクトを追加することができる。
【００７７】
また、欲張りアルゴリズムにより発見される解は、接続ネットワークの特定のインスタンスに特有のものである。具体的には、レイテンシのために最適化が行われた後、消費者が、（例えば、新たな消費者／作成者ペアを設定して）新たな関心を示すことがあり、システムが、プッシュかプルかの決定基準に基づいて、これらのペアに関してプル方式を選択することがある。このような場合、これらの新たな消費者／作成者ペアは、既存の消費者／作成者ペアに関してプッシュ／プルの決定が変化していなくても、平均又は９５パーセンタイルレイテンシを増加させることがある。従って、特定の実施形態は、欲張りアルゴリズムを定期的に繰り返して、接続ネットワークが変化したときにもレイテンシＳＬＡが満たされることを確実にする。
【００７８】
個々の（消費者、作成者）ペアをプルからプッシュに移行させることに代わる特定の実施形態では、消費者をプルからプッシュにブロックとして移動させることができる。すなわち、（消費者、作成者）ペアをプルからプッシュに移動させる場合、特定の実施形態は、いくつかのプル（消費者、作成者）ペアを有する消費者を選択し、これらの全てを一気にプルからプッシュに移動させる。より詳細には、消費者は、各々がこの消費者によりフォローされる複数の作成者が作成したコンテンツを消費できるので、（消費者、作成者）ペアが存在する。従って、特定の消費者に関して、その（消費者、作成者）ペアのいくつかがプル方式を有するように決定し、その（消費者、作成者）ペアの残りがプッシュ方式を有するように決定することができる。特定の実施形態は、このような消費者を選択し、その（消費者、作成者）ペアを全てプッシュに移行させることができる。直観では、単一の消費者コンテンツクエリを低レイテンシで実行するには、この消費者に関する全ての作成者をプッシュに移動させる必要があり、そうでなければ、たった１つの作成者であっても、この作成者からプルする時間が消費者のコンテンツクエリ時間を占めるようになる。この場合、特定の実施形態は、消費者ｃi全体のεを
0005450841.tif 000012
として計算する。さらに、λlは、全てのクエリが行われた（消費者、作成者）ペアの一部であることから、全ての消費者クエリの一部であることに移行する。これらの変化でも、ナップサックの低減は変わらない。
【００７９】
消費者を大規模に移動させることは、クエリ時に各消費者にわずかな「ロングポール」しか残さないという利点を有する。しかしながら、その弱点は、自由度が減少してしまうので、レイテンシを最適化するのが困難になる可能性があるという点である。具体的には、場合によっては、特定の（作成者、消費者）ペアをプッシュに移動させたいと望むことはできるが、消費者全体を移動させるとシステムコストが過度に増加するので、これを行うのが不可能な場合もある。なお、方式の区別は、消費者がフォローする作成者を特定の実施形態が別個のオブジェクトに分解するか、それともブロックとして処理するかによってもたらされる。従って、この議題は、作成者ごとの一貫性にのみ存在する。全体的一貫性では、コンテンツの寿命が、消費者の作成者全てのコンテンツ作成頻度の関数であるため、消費者の作成者は全て、同じ利点（すなわち、消費者のコンテンツ消費頻度）及び同じペナルティ（すなわち、プルされた作成者の集約コンテンツ作成頻度）を有する。従って、全体的一貫性の場合、特定の実施形態がオブジェクトを（消費者、作成者）ペアとして定義するか、それとも消費者ブロックとして定義するかは重要でない。
【００８０】
最後に、エンティティが消費者（例えば、上流の作成者に対して）でもあり作成者（例えば、下流の消費者に対して）でもある状況について簡単に説明する。ここまでは、主に各ノードが作成者又は消費者のいずれかである単純な接続ネットワークに焦点を当てて分析してきた。すなわち、このネットワークは２部グラフである。最適化の基本は、このグラフ内の各エッジを個別に最適化し、さらに全体的な最適化を達成できるようにすることである。代わりに、いくつかのノードが、上流のコンテンツソース（すなわち、上流の作成者）に対する消費者でもあり、下流の消費者に対する作成者でもあることができる複合接続ネットワークが存在すると仮定する。例えば、いくつかのソースから「マドンナ」のコンテンツを集約し、次にこれらをダウンストリーム消費者が利用できるようにするノードがグラフ内に存在することがある。特定の実施形態では、エッジにプッシュ又はプルを割り当ててシステムコストを最小化することが依然として最適化問題である。しかしながら、プッシュかプルかの決定をエッジごとに個別に行うことができないというリスクがある。
【００８１】
このリスクの特徴を明らかにするために、「ネットワーク実行可能性」の特性について検討する。特定の実施形態では、ネットワークが、プッシュが割り当てられている各エッジに関して、各隣接する上流のエッジにもプッシュが割り当てられている場合かつこの場合に限り実行可能である。実行不可能なネットワークの例として、プッシュエッジの上流にプルエッジが存在するエッジのペアについて検討する。プッシュエッジは、その関連する作成者からのコンテンツを、これらが生成されたときにその関連する消費者へ送信するつもりであるが、上流のプルエッジは、コンテンツが生成されたときにこれらを配信しない。
【００８２】
特定の実施形態では、このリスクに対処するために追加の制約を加えて、プッシュコストとプルコスト、及びコンテンツ作成頻度とコンテンツ消費頻度のいずれかを解決することで実行可能な解も保証し、或いは最小コストの実行可能解の近似を発見するようにする。
【００８３】
図３に、本開示の実施形態を実施するのに適したシステムアーキテクチャ例３００を示す。特定の実施形態では、システム３００が、（ビューメンテナなどの）ビューメンテナンス機構３１０及びウェブサービングデータベース３３０を含む。特定の実施形態では、具現化の決定がビューメンテナンス機構３１０にカプセル化され、ウェブサービングデータベース３３０が、更新及びフィードビューの処理などのその他のタスクを処理する。
【００８４】
特定の実施形態では、ウェブサービングデータベース３３０が、弾性的にスケーリング可能であり、あらゆる数の記憶サーバを含むことができる。作成者がコンテンツを生成すると、このコンテンツは、作成者によりクラスタ化された記憶サーバに記憶される。作成者は、例えば、アプリケーション層（例えば、ユーザが直接コンテンツを生成する場合）であっても、又はクローラ／インジェスト層（例えば、外部ソースからコンテンツを検索するための）であってもよい。コンテンツがシステム３００に入ると、システム３００は、ビューメンテナ３１０に通知を送ることができる。ビューメンテナ３１０は、この新たなコンテンツを１又はそれ以上の消費者フィード記録にプッシュするかどうかを決定することによってこの通知に応答する。特定の実施形態では、この決定が作成者のコンテンツ作成率及び消費者のコンテンツクエリ率に依存するので、ビューメンテナ３１０は、ウェブサービングデータベース３３０からこの情報を読み取ることができる。コンテンツがプッシュされた場合、これが再び記憶サーバに書き込まれ、この時刻が消費者クラスタ化フィードビューに書き込まれる。
【００８５】
特定の実施形態は、主にインデックス及びビューメンテナンスを駆動するために、（更新が約束されたときは常に発射されるという理由で）単純なトリガに類似する「通知」機構を使用する。代替の実施形態は、元々の更新トランザクションの一部としてビューを更新すること、データベースログを探索することなどの他の機構を使用してビューメンテナ３１０を変更することができる。通知には、ビューメンテナンスが非同期的に行われるという利点があり、従って特定の実施形態は、元々の更新トランザクションにレイテンシを加えることなく、作成者及び消費者の率を読み取ることを含む潜在的にコストのかかる具現化を行うことができる。この通知方法の欠点は、具現化されるビューが、基本コンテンツストアに比べてわずかに古くさいかもしれない点であるが、通常、ウェブアプリケーション（フォローアプリケーションを含む）では、わずかな程度の古くささであれば許容することができる。
【００８６】
特定の実施形態では、消費者がそのビューを検索すると（例えば、ユーザがユーザのページにログインし、又はこれをリフレッシュすると）、クエリプロセッサ３２０にクエリが行われる。クエリプロセッサ３２０は、（１）既に具現化された（プッシュされた）コンテンツを検索し、（２）いずれの作成者からコンテンツをプルする必要があるかを決定するために、ＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄから消費者の記録を読み取る。次に、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄに対して平行読み取りを行って、これらのコンテンツをプルすることができる。特定の実施形態では、消費者のフィードビュー記録が、具現化されたコンテンツ、及び消費者がフォローしている具現化されていない作成者のリストの両方を含む。
【００８７】
特定の実施形態は、（作成者がクラスタ化した）基本コンテンツストア、及び（消費者がクラスタ化した）具現化されたフィードビューを、いずれも同じデータベースインフラストラクチャに記憶することができる。或いは、特定の実施形態は、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄを一方のデータベースに、ＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄをもう一方のデータベースに記憶することができる。
【００８８】
特定の実施形態では、ウェブサービングデータベース３３０が、個々の記録の読み取り及び書き込みを低レイテンシで行うように設計される。（このような多くの読み取り及び書き込み動作を処理する）スループットは、「スケールアウト」を通じて、すなわちシステムにより多くのサーバを追加することによって増加する。特定の実施形態では、システム３００が、記録を順序付けて記憶することにより、狭い範囲の記録を効率的に検索できるようになる。効率的なプッシュ及びプル動作にとっては、範囲スキャンが特に重要となり得る。特定の実施形態は、関連データを記憶するのに十分なメインメモリを準備することを選択して低レイテンシを保証することができるが、データは、故障に耐え抜くためにディスクにも保持される。
【００８９】
特定の実施形態では、作成者がコンテンツを生成した場合、このコンテンツをＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄテーブルに書き込む必要がある。場合によっては、作成者が、コンテンツを記憶層に直接書き込むことができる。その他の場合には、作成者が、上流のコンテンツのアグリゲータとなることができる。上流のソースが、コンテンツをアグリゲータにプッシュすることもあり、或いはアグリゲータがコンテンツをプルする必要がある場合もあり、いずれの場合にも、例えば適当なアプリケーションプログラムインターフェイス（ＡＰＩ）を使用する。
【００９０】
特定の実施形態では、作成者が新たなコンテンツを作成した場合、このコンテンツを１又はそれ以上の消費者記録内で具現化することによってプッシュするかどうかを決定するのはビューメンテナ３１０の責任である。従って、ビューメンテナ３１０は、補助定理１及び補助定理２の決定ルールをカプセル化する。特定の実施形態では、ビューメンテナ３１０が、データベース３３０からのテーブルの更新を定期的に読み取り、必要時に再びデータベース３３０に記録を書き込む。
【００９１】
特定の実施形態は、限定ではなく一例として、テーブルなどの適当なデータ構造に関連データ（ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋ、ＰｒｏｄｕｃｅｒＰｉｖｏｔｅｄ、又はＣｏｎｓｕｍｅｒＰｉｖｏｔｅｄなど）を記憶することができる。例えば、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋテーブルを使用して、消費者と作成者の間の接続グラフを記憶することができる。このテーブルの要点は、合成（作成者、優先度、消費者）である。補助定理１及び２に従って、消費者のコンテンツクエリ率及び作成者のコンテンツ作成率から優先度が計算される。ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋテーブルを作成者ごとに、次に優先度ごとにソートして、コンテンツをプッシュするかどうかに関する意思決定を容易にすることができる。新たなコンテンツが到着すると、特定の実施形態は、導出された最適な閾値（Ｈi／Ｌjなど）をＲとする優先度Ｒから開始するプレフィクスをコンテンツの作成者によって付けられた記録にわたって範囲クエリを行う。これにより、コンテンツを具現化すべき対象消費者の組である、Ｒよりも優先度の高い（作成者、消費者）ペアのみを迅速に検索できるようになる。
【００９２】
別の例として、コンテンツをＣｏｎｔｅｎｔｓＢｙＰｒｏｄｕｃｅｒテーブルに記憶することができる。このテーブルの要点は、コンテンツが作成者ごとにクラスタ化され、作成者の中の作成時刻によって順序付けられるようにする（作成者、タイムスタンプ）である。このような順序付けにより、所与の作成者から最新コンテンツを効率的に検索できるようになる。（通常、フィードは、最新のＮ個のコンテンツしか表示しないので）この検索は、検索するコンテンツ数の制限が指定された範囲スキャンによって実施することができる。
【００９３】
さらに別の例として、各消費者の具現化されたフィード記録をＦｅｅｄテーブルに記憶することができる。このテーブルの要点は、消費者がフォローする作成者ごとに別個の記録が存在するようにする（消費者、作成者）である。消費者が新たな作成者をフォローすると決めた場合、最初はコンテンツを含まない新たなＦｅｅｄ記録が挿入される。ビューメンテナ３１０は、新たなコンテンツを通知されると、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋテーブルに範囲スキャンを行って、コンテンツをプッシュすべき消費者のリストを発見し、消費者ごとに適当なＦｅｅｄ記録を更新する。この結果、いくつかのフィード記録は具現化されたコンテンツを有し、その他のフィード記録はヌルを有するようになる。このＦｅｅｄ記録は、（消費者、作成者）ペアに関する優先度を含むこともでき、この優先度は、ＣｏｎｎｅｃｔｉｏｎＮｅｔｗｏｒｋテーブルに記憶された優先度と同じものである。Ｆｅｅｄ記録がコンテンツを有していない（例えば、ヌル）場合、特定の実施形態は、優先度が閾値Ｈi／Ｌj未満の場合には、ＣｏｎｔｅｎｔｓＢｙＰｒｏｄｕｃｅｒからのみプルすればよい。優先度が閾値よりも高いヌル記録は、コンテンツがプッシュされることを示すが、作成者はまだ何も作成していない。また、Ｆｅｅｄテーブル内の「コンテンツ」のために確保されている列には、潜在的に複数のコンテンツが記憶され、作成者のファンアウトによって生じた複数の消費者のために同じコンテンツを記憶することができる。
【００９４】
作成者のコンテンツ作成率及び消費者のコンテンツクエリ率が変化するにつれ、特定の実施形態は、（消費者、作成者）ペアに関する優先度を適応させることができる。各作成者の率の統計値は、対応するＣｏｎｔｅｎｔｓＢｙＰｒｏｄｕｃｅｒ記録内に保持することができ、各消費者の率の統計値は、対応するＦｅｅｄ記録内に保持することができる。統計値及び優先度を更新する際には、観察を緩めるべきである。統計値を更新するための書き込み数を低減するために、特定の実施形態は近似統計値を保持し、各コンテンツ又はクエリに関する何らかの確率でのみ、これらを更新することができる。優先度を更新するための書き込み数を低減するために、特定の実施形態は、古い優先度と新しい優先度がプッシュ閾値をまたいで存在する場合にのみ更新を行うことができる。
【００９５】
特定の実施形態は、ネットワーク環境で実施することができる。図４に、ソフトウェアの妥当性確認をサービスとして行うのに適したネットワーク環境例４００を示す。ネットワーク環境４００は、１又はそれ以上のサーバ４２０と１又はそれ以上のクライアント４３０を互いに接続するネットワーク４１０を含む。特定の実施形態では、ネットワーク４１０が、イントラネット、エクストラネット、仮想プライベートネットワーク（ＶＰＮ）、ローカルエリアネットワーク（ＬＡＮ）、無線ＬＡＮ（ＷＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、インターネットの一部、又は別のネットワーク４１０、或いは２又はそれ以上のこのようなネットワーク４１０の組み合わせである。本開示は、あらゆる適当なネットワーク４１０を考慮する。
【００９６】
１又はそれ以上のリンク４５０が、サーバ４２０又はクライアント４３０をネットワーク４１０に接続する。特定の実施形態では、１又はそれ以上のリンク４５０の各々が、１又はそれ以上の有線、無線、又は光学リンク４５０を含む。特定の実施形態では、１又はそれ以上のリンク４５０の各々が、イントラネット、エクストラネット、ＶＰＮ、ＬＡＮ、ＷＬＡＮ、ＷＡＮ、ＭＡＮ、インターネットの一部、又は別のリンク４５０、或いは２又はそれ以上のこのようなリンク４５０の組み合わせを含む。本開示は、サーバ４２０及びクライアント４３０をネットワーク４１０に接続するあらゆる適当なリンク４５０を考慮する。
【００９７】
特定の実施形態では、各サーバ４２０が、単一のサーバであってもよく、或いは複数のコンピュータ又は複数のデータセンタにわたる分散サーバであってもよい。サーバ４２０は、限定ではなく一例として、ウェブサーバ、ニュースサーバ、メールサーバ、メッセージサーバ、広告サーバ、ファイルサーバ、アプリケーションサーバ、交換サーバ、データベースサーバ、又はプロキシサーバなどの様々なタイプであってよい。特定の実施形態では、各サーバ４２０が、ハードウェア、ソフトウェア、又は組み込み論理要素、或いはサーバ４２０により実施又はサポートされる適当な機能を実行するための２又はそれ以上のこのような構成要素の組み合わせを含むことができる。例えば、ウェブサーバは、一般にウェブページ又は特定のウェブページ要素を含むウェブサイトをホストすることができる。より詳細には、ウェブサーバは、ＨＴＭＬファイル又はその他のファイルタイプをホストすることができ、或いは要求時にファイルを動的に作成又は構成し、クライアント４３０からのＨＴＴＰ又はその他の要求に応じてこれらをクライアント４３０に通信することができる。メールサーバは、一般に様々なクライアント４３０に電子メールサービスを提供することができる。データベースサーバは、一般に１又はそれ以上のデータストアに記憶されたデータを管理するためのインターフェイスを提供することができる。
【００９８】
特定の実施形態では、１又はそれ以上のデータ記憶装置４４０を、１又はそれ以上のリンク４５０を介して１又はそれ以上のサーバ４２０に通信可能にリンクさせることができる。特定の実施形態では、データ記憶装置４４０を使用して、様々な種類の情報を記憶することができる。特定の実施形態では、データ記憶装置４４０に記憶された情報を、特定のデータ構造に従って体系化することができる。特定の実施形態では、各データ記憶装置４４０をリレーショナルデータベースとすることができる。特定の実施形態は、サーバ４２０又はクライアント４３０が、データ記憶装置４４０に記憶された情報を管理（例えば、検索、修正、追加、又は削除）できるようにするインターフェイスを提供することができる。
【００９９】
特定の実施形態では、各クライアント４３０を、ハードウェア、ソフトウェア、又は組み込み論理要素、或いは２又はそれ以上のこのような構成要素の組み合わせを含み、クライアント４３０が実施又はサポートする適当な機能を実行できる電子装置とすることができる。限定ではなく一例として、クライアント４３０は、デスクトップコンピュータシステム、ノートブックコンピュータシステム、ネットブックコンピュータシステム、ハンドヘルド電子装置、又は携帯電話であってもよい。本開示は、あらゆる好適なクライアント４３０を考慮する。クライアント４３０は、クライアント４３０のネットワークユーザがネットワーク４３０にアクセスできるようにすることができる。クライアント４３０は、そのユーザが、他のクライアント４３０の他のユーザと通信できるようにすることができる。
【０１００】
クライアント４３０は、ＭＩＣＲＯＳＯＦＴ  ＩＮＴＥＲＮＥＴ  ＥＸＰＬＯＲＥＲ、ＧＯＯＧＬＥ  ＣＨＲＯＭＥ又はＭＯＺＩＬＬＡ  ＦＩＲＥＦＯＸなどのウェブブラウザ４３２を有することができ、ＴＯＯＬＢＡＲ又はＹＡＨＯＯ  ＴＯＯＬＢＡＲなどの、１又はそれ以上のアドオン、プラグイン、又はその他の拡張機能を有することができる。クライアント４３０のユーザは、ユニフォームリソースロケータ（ＵＲＬ）、又はウェブブラウザ４３２をサーバ４２０に向けるその他のアドレスを入力することができ、ウェブブラウザ４３２は、ハイパーテキスト転送プロトコル（ＨＴＴＰ）要求を生成して、このＨＴＴＰ要求をサーバ４２０に通信することができる。サーバ４２０は、ＨＴＴＰ要求を受け入れ、このＨＴＴＰ要求に応答してクライアント４３０に１又はそれ以上のハイパーテキストマークアップ言語（ＨＴＭＬ）ファイルを通信することができる。クライアント４３０は、サーバ４２０からのＨＴＭＬファイルに基づいて、ユーザに提示するためのウェブページを表示することができる。本開示は、あらゆる好適なウェブページファイルを考慮する。限定ではなく一例として、ウェブページは、特定の必要性に基づいて、ＨＴＭＬファイル、拡張可能ハイパーテキストマークアップ言語（ＸＨＴＭＬ）ファイル、又は拡張可能マークアップ言語（ＸＭＬ）ファイルから表示を行うことができる。このようなページは、限定ではなく一例として、ＪＡＶＡＳＣＲＩＰＴ（登録商標）、ＪＡＶＡ（登録商標）、ＭＩＣＲＯＳＯＦＴ  ＳＩＬＶＥＲＬＩＧＨＴ、ＡＪＡＸ（非同期ＪＡＶＡＳＣＲＩＰＴ（登録商標）及びＸＭＬ）などのマークアップ言語とスクリプトの組み合わせなどで書かれたようなスクリプトを実行することもできる。本明細書では、必要に応じて、ウェブページへの言及は、（ブラウザがウェブページを表示するために使用できる）１又はそれ以上の対応するウェブページファイルを含み、逆もまた同様である。
【０１０１】
特定の実施形態は、１又はそれ以上のコンピュータシステム上で実施することができる。図５に、コンピュータシステム例５００を示す。特定の実施形態では、１又はそれ以上のコンピュータシステム５００が、本明細書で説明又は例示した１又はそれ以上の方法の１又はそれ以上のステップを実行する。特定の実施形態では、１又はそれ以上のコンピュータシステム５００が、本明細書で説明又は例示した機能を提供する。特定の実施形態では、１又はそれ以上のコンピュータシステム５００上で実行されるソフトウェアが、本明細書で説明又は例示した１又はそれ以上の方法の１又はそれ以上のステップを実行し、又は本明細書で説明又は例示した機能を提供する。特定の実施形態は、１又はそれ以上のコンピュータシステム５００の１又はそれ以上の部分を含む。
【０１０２】
本開示は、あらゆる好適な数のコンピュータシステム５００を考慮する。本開示は、コンピュータシステム５００があらゆる好適な物理的形状をとることを考慮する。限定ではなく一例として、コンピュータシステム５００は、埋め込みコンピュータシステム、システムオンチップ（ＳＯＣ）、（例えば、コンピュータオンモジュール（ＣＯＭ）又はシステムオンモジュール（ＳＯＭ）などの）単一基板コンピュータシステム（ＳＢＣ）、デスクトップコンピュータシステム、ラップトップ又はノートブックコンピュータシステム、対話型キオスク、メインフレーム、コンピュータシステムのメッシュ、携帯電話、携帯情報端末（ＰＤＡ）、サーバ、又はこれらの２又はそれ以上の組み合わせであってもよい。必要に応じて、コンピュータシステム５００は、１又はそれ以上のコンピュータシステム５００を含むことができ、単一又は分散型とすることができ、複数の場所にわたることができ、複数の機械にわたることができ、或いは１又はそれ以上のネットワーク内の１又はそれ以上のクラウド構成要素を含むことができるクラウド内に常駐することができる。必要に応じて、１又はそれ以上のコンピュータシステム５００は、本明細書で説明又は例示した１又はそれ以上の方法の１又はそれ以上のステップを、大きな空間的又は時間的制限を伴わずに実行することができる。限定ではなく一例として、１又はそれ以上のコンピュータシステム５００は、本明細書で説明又は例示した１又はそれ以上の方法の１又はそれ以上のステップをリアルタイムで又はバッチモードで実行することができる。１又はそれ以上のコンピュータシステム５００は、必要に応じて、本明細書で説明又は例示した１又はそれ以上の方法の１又はそれ以上のステップを異なる時点又は異なる場所で実行することができる。
【０１０３】
特定の実施形態では、コンピュータシステム５００が、プロセッサ５０２、メモリ５０４、記憶装置５０６、入力／出力（Ｉ／Ｏ）インターフェイス５０８、通信インターフェイス５１０、及びバス５１２を含む。本開示では、特定の構成内に特定の数の特定の構成要素を有する特定のコンピュータシステムを説明及び例示しているが、本開示は、あらゆる好適な構成内にあらゆる好適な数のあらゆる好適な構成要素を有するあらゆる好適なコンピュータシステムを考慮する。
【０１０４】
特定の実施形態では、プロセッサ５０２が、コンピュータプログラムを構築するような命令を実行するためのハードウェアを含む。限定ではなく一例として、プロセッサ５０２は、命令を実行するために、内部レジスタ、内部キャッシュ、メモリ５０４、又は記憶装置５０６から命令を検索（又はフェッチ）し、これらの命令を復号して実行し、さらに１又はそれ以上の結果を、内部レジスタ、内部キャッシュ、メモリ５０４、又は記憶装置５０６に書き込むことができる。特定の実施形態では、プロセッサ５０２が、データ、命令又はアドレスのための１又はそれ以上の内部キャッシュを含むことができる。本開示は、プロセッサ５０２が、必要に応じてあらゆる好適な数のあらゆる好適な内部キャッシュを含むことを考慮する。限定ではなく一例として、プロセッサ５０２は、１又はそれ以上の命令キャッシュ、１又はそれ以上のデータキャッシュ、及び１又はそれ以上の変換索引バッファ（ＴＬＢ）を含むことができる。命令キャッシュ内の命令は、メモリ５０４又は記憶装置５０６内の命令の複製であってもよく、この命令キャッシュは、プロセッサ５０２によるこれらの命令の検索を迅速化することができる。データキャッシュ内のデータは、メモリ５０４又は記憶装置５０６内の、プロセッサ５０２で実行される命令のためのデータの複製、プロセッサ５０２で実行される次の命令がアクセスするための、或いはメモリ５０４又は記憶装置５０６に書き込むための、プロセッサ５０２で実行された以前の命令の結果、又はその他の好適なデータであってもよい。データキャッシュは、プロセッサ５０２による読み取り又は書き込み動作を迅速化することができる。ＴＬＢは、プロセッサ５０２の仮想アドレス変換を迅速化することができる。特定の実施形態では、プロセッサ５０２が、データ、命令、又はアドレスのための１又はそれ以上の内部レジスタを含むことができる。本開示は、プロセッサ５０２が、必要に応じてあらゆる好適な数のあらゆる好適な内部レジスタを含むことを考慮する。必要に応じて、プロセッサ５０２は、１又はそれ以上の演算論理ユニット（ＡＬＵ）を含むことができ、マルチコアプロセッサであってもよく、或いは１又はそれ以上のプロセッサ５０２を含むこともできる。本開示では、特定のプロセッサを説明及び例示しているが、本開示は、あらゆる好適なプロセッサを考慮する。
【０１０５】
特定の実施形態では、メモリ５０４が、プロセッサ５０２が実行する命令又はプロセッサ５０２が作用するデータを記憶するためのメインメモリを含む。限定ではなく一例として、コンピュータシステム５００は、記憶装置５０６又は（例えば、別のコンピュータシステム５００などの）別のソースからメモリ５０４に命令をロードすることができる。次に、プロセッサ５０２は、メモリ５０４からの命令を内部レジスタ又は内部キャッシュにロードすることができる。プロセッサ５０２は、これらの命令を実行するために、内部レジスタ又は内部キャッシュから命令を検索してこれを復号することができる。プロセッサ５０２は、命令の実行中又は実行後に、（中間結果であっても又は最終結果であってもよい）１又はそれ以上の結果を内部レジスタ又は内部キャッシュに書き込むことができる。その後、プロセッサ５０２は、これらの結果の１又はそれ以上をメモリ５０４に書き込むことができる。特定の実施形態では、プロセッサ５０２が、（記憶装置５０６又はその他の場所とは対照的に）１又はそれ以上の内部レジスタ又は内部キャッシュ、或いはメモリ５０４内の命令のみを実行し、（記憶装置５０６又はその他の場所とは対照的に）１又はそれ以上の内部レジスタ又は内部キャッシュ、或いはメモリ５０４内のデータのみに作用する。（各々がアドレスバス及びデータバスを含むことができる）１又はそれ以上のメモリバスが、プロセッサ５０２をメモリ５０４に接続することができる。バス５１２は、以下で説明するような１又はそれ以上のメモリバスを含むことができる。特定の実施形態では、プロセッサ５０２とメモリ５０４の間に１又はそれ以上のメモリ管理ユニット（ＭＭＵ）が存在して、プロセッサ５０２が要求するメモリ５０４へのアクセスを容易にする。特定の実施形態では、メモリ５０４が、ランダムアクセスメモリ（ＲＡＭ）を含む。必要に応じて、このＲＡＭを不揮発性メモリとすることができる。必要に応じて、このＲＡＭを動的ＲＡＭ（ＤＲＡＭ）又は静的ＲＡＭ（ＳＲＡＭ）とすることもできる。さらに、必要に応じて、このＲＡＭを単一ポート又はマルチポートＲＡＭとすることもできる。本開示は、あらゆる好適なＲＡＭを考慮する。必要に応じて、メモリ５０４は、１又はそれ以上のメモリ５０４を含むことができる。本開示では、特定のメモリを説明及び例示しているが、本開示はあらゆる好適なメモリを考慮する。
【０１０６】
特定の実施形態では、記憶装置５０６が、データ又は命令のための大容量記憶装置を含む。限定ではなく一例として、記憶装置５０６は、ＨＤＤ、フロッピー（登録商標）ディスクドライブ、フラッシュメモリ、光学ディスク、磁気光学ディスク、磁気テープ、又はユニバーサルシリアルバス（ＵＳＢ）ドライブ、或いはこれらの２又はそれ以上の組み合わせを含むことができる。必要に応じて、記憶装置５０６は、取り外し可能又は取り外し不能（すなわち固定）媒体を含むことができる。必要に応じて、記憶装置５０６は、コンピュータシステム５００の内部又は外部に存在することができる。特定の実施形態では、記憶装置５０６が不揮発性固体メモリである。特定の実施形態では、記憶装置５０６が読出し専用メモリ（ＲＯＭ）を含む。必要に応じて、このＲＯＭを、マスクプログラム化ＲＯＭ、プログラム可能ＲＯＭ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、電気的消去可能ＰＲＯＭ（ＥＥＰＲＯＭ）、電気的変更可能ＲＯＭ(ＥＡＲＯＭ)、又はフラッシュメモリ、或いはこれらの２又はそれ以上の組み合わせとすることができる。本開示は、大容量記憶装置５０６があらゆる好適な物理的形式をとることを考慮する。必要に応じて、記憶装置５０６は、プロセッサ５０２と記憶装置５０６の間の通信を容易にする１又はそれ以上の記憶制御ユニットを含むことができる。必要に応じて、記憶装置５０６は、１又はそれ以上の記憶装置５０６を含むことができる。本開示では、特定の記憶装置を説明及び例示しているが、本開示は、あらゆる好適な記憶装置を考慮する。
【０１０７】
特定の実施形態では、Ｉ／Ｏインターフェイス５０８が、コンピュータシステム５００と１又はそれ以上のＩ／Ｏ装置の間の通信のための１又はそれ以上のインターフェイスを提供するハードウェア、ソフトウェア、又はこれらの両方を含む。必要に応じて、コンピュータシステム５００は、これらのＩ／Ｏ装置の１又はそれ以上を含むことができる。これらのＩ／Ｏ装置の１又はそれ以上は、人とコンピュータシステム５００の間の通信を可能にすることができる。限定ではなく一例として、Ｉ／Ｏ装置は、キーボード、キーパッド、マイク、モニタ、マウス、プリンタ、スキャナ、スピーカ、静止カメラ、スタイラス、タブレット、タッチスクリーン、トラックボール、ビデオカメラ、別の好適なＩ／Ｏ装置、或いはこれらの２又はそれ以上の組み合わせを含むことができる。Ｉ／Ｏ装置は、１又はそれ以上のセンサを含むことができる。本開示は、あらゆる好適なＩ／Ｏ装置、及びこれらの装置のためのあらゆる好適なＩ／Ｏインターフェイス５０８を考慮する。必要に応じて、Ｉ／Ｏインターフェイス５０８は、プロセッサ５０２がこれらのＩ／Ｏ装置の１又はそれ以上を駆動できるようにする１又はそれ以上の装置又はソフトウェアドライバを含むことができる。必要に応じて、Ｉ／Ｏインターフェイス５０８は、１又はそれ以上のＩ／Ｏインターフェイス５０８を含むことができる。本開示では、特定のＩ／Ｏインターフェイスを説明及び例示しているが、本開示はあらゆる好適なＩ／Ｏインターフェイスを考慮する。
【０１０８】
特定の実施形態では、通信インターフェイス５１０が、コンピュータシステム５００と１又はそれ以上の他のコンピュータシステム５００、或いは１又はそれ以上のネットワークとの間の通信（例えば、パケットベースの通信など）のための１又はそれ以上のインターフェイスを提供するハードウェア、ソフトウェア、又はこれらの両方を含む。限定ではなく一例として、通信インターフェイス５１０は、イーサネット（登録商標）又は他の配線に基づくネットワークと通信するためのネットワークインターフェイスコントローラ（ＮＩＣ）又はネットワークアダプタ、或いはＷＩ−ＦＩネットワークなどの無線ネットワークと通信するための無線ＮＩＣ（ＷＮＩＣ）又は無線アダプタを含むことができる。本開示は、あらゆる好適なネットワーク、及びこのネットワークのためのあらゆる好適な通信インターフェイス５１０を考慮する。限定ではなく一例として、コンピュータシステム５００は、アドホックネットワーク、パーソナルエリアネットワーク（ＰＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、又はインターネットの１又はそれ以上の部分、或いはこれらの２又はそれ以上の組み合わせと通信することができる。これらのネットワークの１又はそれ以上の１又はそれ以上の部分は、有線であっても又は無線であってもよい。一例として、コンピュータシステム５００は、（例えば、ＢＬＵＥＴＯＯＴＨ  ＷＰＡＮなどの）無線ＰＡＮ（ＷＰＡＮ）、ＷＩ−ＦＩネットワーク、ＷＩ−ＭＡＸネットワーク、（例えば、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ（登録商標））ネットワークなどの）携帯電話ネットワーク、又はその他の好適な無線ネットワーク、或いはこれらの２又はそれ以上の組み合わせと通信することができる。必要に応じて、コンピュータシステム５００は、これらのネットワークのいずれかのためのあらゆる好適な通信インターフェイス５１０を含むことができる。必要に応じて、通信インターフェイス５１０は、１又はそれ以上の通信インターフェイス５１０を含むことができる。本開示では、特定の通信インターフェイスを説明及び例示しているが、本開示は、あらゆる好適な通信インターフェイスを考慮する。
【０１０９】
特定の実施形態では、バス５１２が、コンピュータシステム５００の構成要素を互いに接続するハードウェア、ソフトウェア、又はこれらの両方を含む。限定ではなく一例として、バス５１２は、アクセラレーティッド・グラフィクス・ポート（ＡＧＰ）又はその他のグラフィクスバス、拡張業界標準アーキテクチャ（ＥＩＳＡ）バス、フロント側バス（ＦＳＢ）、ハイパートランスポート（ＨＴ）相互接続、業界標準アーキテクチャ（ＩＳＡ）バス、ＩＮＦＩＮＩＢＡＮＤ相互接続、ローピンカウント（ＬＰＣ）バス、メモリバス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）バス、周辺構成要素相互接続（ＰＣＩ）バス、ＰＣＩエクスプレス（ＰＣＩ-Ｘ）バス、シリアル・アドバンスド・テクノロジ・アタッチメント（ＳＡＴＡ）バス、ビデオ電子機器標準アソシエーションローカル（ＶＬＢ）バス、又は別の好適なバス、或いはこれらの２又はそれ以上の組み合わせを含むことができる。必要に応じて、バス５１２は、１又はそれ以上のバス５１２を含むことができる。本開示では、特定のバスを説明及び例示しているが、本開示は、あらゆる好適なバス又は相互接続を考慮する。
【０１１０】
本明細書では、コンピュータ可読記憶媒体への言及が、１又はそれ以上の非一時的有形コンピュータ可読記憶媒体処理構造を含む。限定ではなく一例として、必要に応じて、コンピュータ可読記憶媒体は、（例えば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）又は特定用途向けＩＣ（ＡＳＩＣ）などの）半導体に基づく又はその他の集積回路（ＩＣ）、ハードディスク、ＨＤＤ、混合ハードドライブ（ＨＨＤ）、光学ディスク、光学ディスクドライブ（ＯＤＤ）、磁気光学ディスク、磁気光学ドライブ、フロッピー（登録商標）ディスク、フロッピー（登録商標）ディスクドライブ（ＦＤＤ）、磁気テープ、ホログラフィック記憶媒体、固体ドライブ（ＳＳＤ）、ＲＡＭドライブ、ＳＥＣＵＲＥ  ＤＩＧＩＴＡＬカード、ＳＥＣＵＲＥ  ＤＩＧＩＴＡＬドライブ、又は別の好適なコンピュータ可読記憶媒体、或いはこれらの２又はそれ以上の組み合わせを含むことができる。本明細書では、コンピュータ可読記憶媒体への言及は、米国特許法第１０１条における特許権保護の資格がないあらゆる媒体を除外する。本明細書では、コンピュータ可読記憶媒体への言及は、米国特許法第１０１条における特許権保護の資格がない限り、（伝搬電気又は電磁信号単独などの）一時的な信号送信の形を除外する。
【０１１１】
本開示は、あらゆる好適な記憶媒体を実装する１又はそれ以上のコンピュータ可読記憶媒体を考慮する。特定の実施形態では、必要に応じて、コンピュータ可読記憶媒体が、プロセッサ５０２の（例えば、１又はそれ以上の内部レジスタ又はキャッシュなどの）１又はそれ以上の部分、メモリ５０４の１又はそれ以上の部分、記憶装置５０６の１又はそれ以上の部分、或いはこれらの組み合わせを実装する。特定の実施形態では、コンピュータ可読記憶媒体はＲＡＭ又が、ＲＯＭを実装する。特定の実施形態では、コンピュータ可読記憶媒体が、揮発性又は永続メモリを実装する。特定の実施形態では、１又はそれ以上のコンピュータ可読記憶媒体が、ソフトウェアを具体化する。本明細書では、ソフトウェアへの言及が、必要に応じて、１又はそれ以上のアプリケーション、バイトコード、１又はそれ以上のコンピュータプログラム、１又はそれ以上の実行ファイル、１又はそれ以上の命令、論理、機械コード、１又はそれ以上のスクリプト、又はソースコードを含むことができ、逆もまた同様である。特定の実施形態では、ソフトウェアが、１又はそれ以上のアプリケーションプログラミングインターフェイス（ＡＰＩ）を含む。本開示は、あらゆる好適なプログラミング言語又はプログラミング言語の組み合わせで書かれた又は別様に表現されたあらゆる好適なソフトウェアを考慮する。特定の実施形態では、ソフトウェアが、ソースコード又はオブジェクトコードとして表現される。特定の実施形態では、ソフトウェアが、例えば、Ｃ、Ｐｅａｌ、又はこれらの適当な拡張などの高水準プログラミング言語で表現される。特定の実施形態では、ソフトウェアが、アセンブリ言語（又は機械コード）などの低水準プログラミング言語で表現される。特定の実施形態では、ソフトウェアがＪＡＶＡ（登録商標）で表現される。特定の実施形態では、ソフトウェアが、ハイパーテキストマークアップ言語（ＨＴＭＬ）、拡張可能マークアップ言語（ＸＭＬ）、又はその他の好適なマークアップ言語で表現される。
【０１１２】
本開示は、本明細書の実施形態例に対する、当業者が把握する全ての変更、置換、変形、改変、及び修正を含む。同様に、必要に応じて、添付の特許請求の範囲は、本明細書の実施形態例に対する、当業者が把握する全ての変更、置換、変形、改変、及び修正を含む。
【符号の説明】
【０１１３】
１１０  コンテンツ作成者からコンテンツフィードを介してコンテンツ消費者にコンテンツを配信するためのプッシュコスト及びプルコストを計算
１２０  コンテンツフィードのためのプッシュ方式又はプル方式のいずれかの配信コストが低い方を選択
【図１】
0005450841.tif 000019
【図２】
0005450841.tif 000020
【図３】
0005450841.tif 000021
【図４】
0005450841.tif 000022
【図５】
0005450841.tif 000023