(57)【特許請求の範囲】
【請求項１】
コンピュータ実装方法であって、
コンピュータ・システムが、第１のパーティションのノードのヒストグラムを演算するステップと、
前記コンピュータ・システムが、第２のパーティションのノードのヒストグラムを演算するステップと、
前記コンピュータ・システムが、前記第１のパーティションのノードのヒストグラムに基づいて、前記第１のパーティションの一組のノードの候補パーティションとして前記第２のパーティションを選択するステップと、
前記コンピュータ・システムが、前記第２のパーティションのノードのヒストグラムに基づいて、前記第２のパーティションの一組のノードの候補パーティションとして前記第１のパーティションを選択するステップと、
前記コンピュータ・システムが、負荷平衡に基づいて、前記第１のパーティションの一組のノードの少なくとも一部を前記第２のパーティションに再マッピングし、前記第２のパーティションの一組のノードの少なくとも一部を前記第１のパーティションに再マッピングするステップと、を備える、コンピュータ実装方法。
【請求項２】
前記コンピュータ・システムが、第３のパーティションのノードのヒストグラムを演算するステップと、
前記コンピュータ・システムが、前記第１のパーティションのノードのヒストグラムに基づいて、前記第１のパーティションの別の一組のノードの候補パーティションとして前記第３のパーティションを選択するステップと、
前記コンピュータ・システムが、前記第３のパーティションのノードのヒストグラムに基づいて、前記第３のパーティションの一組のノードの候補パーティションとして前記第１のパーティションを選択するステップと、
前記コンピュータ・システムが、負荷平衡に基づいて、前記第１のパーティションの他の一組のノードの少なくとも一部を前記第３のパーティションに再マッピングするとともに、前記第３のパーティションの一組のノードの少なくとも一部を前記第１のパーティションに再マッピングするステップと、をさらに備える、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記コンピュータ・システムが、エッジ局所性のゲインに基づいて、前記第１のパーティションの一組のノードをソートするステップと、
前記コンピュータ・システムが、エッジ局所性のゲインに基づいて、前記第２のパーティションの一組のノードをソートするステップと、をさらに備え、
前記第２のパーティションが、エッジ局所性のゲインに関する確率に基づいて、前記第１のパーティションのノードの候補パーティションとして選択される、請求項１または２に記載のコンピュータ実装方法。
【請求項４】
前記第１のパーティションのノードのヒストグラムが、複数のパーティションのそれぞれにおける接続ノードの数を示す、請求項１〜３のいずれか一項に記載のコンピュータ実装方法。
【請求項５】
前記第２のパーティションに再マッピングされた前記第１のパーティションのノードの数と前記第１のパーティションに再マッピングされた前記第２のパーティションのノードの数との差が、しきい値の範囲内であること、および、
前記第２のパーティションに再マッピングされた前記第１のパーティションのノードの重みと前記第１のパーティションに再マッピングされた前記第２のパーティションのノードの重みとの差が、しきい値の範囲内であることのうちの少なくとも一方を含む、請求項１〜４のいずれか一項に記載のコンピュータ実装方法。
【請求項６】
前記コンピュータ・システムが、前記再マッピングの前に、前記第１のパーティションの第１の総ノード重みを演算するステップをさらに備え、
好ましくは、前記コンピュータ・システムが、前記再マッピングの後に、前記第１のパーティションの第２の総ノード重みを演算するステップをさらに備える、請求項１〜５のいずれか一項に記載のコンピュータ実装方法。
【請求項７】
前記コンピュータ・システムが、非分散システムであり、
該コンピュータ実装方法が、
前記コンピュータ・システムが、ノードグラフをメモリにロードするステップをさらに備え、
前記ノードグラフが、前記第１のパーティションのノードおよび前記第２のパーティションのノードを含む、請求項１〜６のいずれか一項に記載のコンピュータ実装方法。
【請求項８】
前記コンピュータ・システムが、分散システムであり、
該コンピュータ実装方法が、
前記コンピュータ・システムが、ノードグラフの異なる部分を前記分散システム全体にロードするステップをさらに備え、
前記ノードグラフが、前記第１のパーティションのノードおよび前記第２のパーティションのノードを含む、請求項１〜６のいずれか一項に記載のコンピュータ実装方法。
【請求項９】
前記第１のパーティションの複数のノードのそれぞれと関連付けられた接続ノードの現行パーティションＩＤを受信するステップをさらに備え、
好ましくは、前記第１のパーティションのノードのヒストグラムが、前記現行パーティションＩＤに基づいて演算され、
好ましくは、前記第１のパーティションの複数のノードのそれぞれの現行パーティションＩＤを提供するステップをさらに備える、請求項１〜８のいずれか一項に記載のコンピュータ実装方法。
【請求項１０】
候補パーティションが、局所性ゲインしきい値に基づいて選択される、請求項１〜９のいずれか一項に記載のコンピュータ実装方法。
【請求項１１】
前記第２のパーティションが、エッジ局所性のゲインに関する確率に基づいて、前記第１のパーティションのノードの候補パーティションとして選択される、請求項１〜１０のいずれか一項に記載のコンピュータ実装方法。
【請求項１２】
前記コンピュータ・システムが、再マッピングされるノードを示す複数のパーティションのすべてのパーティション対の記録を生成するステップをさらに備える、請求項１〜１１のいずれか一項に記載のコンピュータ実装方法。
【請求項１３】
前記ノードグラフが、ソーシャルネットワーキング・システムによりサポートされている、請求項１〜１２のいずれか一項に記載のコンピュータ実装方法。
【請求項１４】
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに指示して、請求項１〜１３のいずれか一項に記載の方法を実行するように構成された命令を格納したメモリと、
を備えた、システム。
【請求項１５】
実行された場合に、請求項１〜１３のいずれか一項に記載のコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納した、コンピュータ記憶媒体。
【請求項１６】
システムであって、
少なくとも１つのプロセッサと、
メモリと、を備え、
前記メモリは、
前記少なくとも１つのプロセッサに指示して、
第１のパーティションのノードのヒストグラムを演算すること、
第２のパーティションのノードのヒストグラムを演算すること、
前記第１のパーティションのノードのヒストグラムに基づいて、前記第１のパーティションの一組のノードの候補パーティションとして前記第２のパーティションを選択すること、
前記第２のパーティションのノードのヒストグラムに基づいて、前記第２のパーティションの一組のノードの候補パーティションとして前記第１のパーティションを選択すること、
負荷平衡に基づいて、前記第１のパーティションの前記一組のノードの少なくとも一部を前記第２のパーティションに再マッピングするとともに、前記第２のパーティションの前記一組のノードの少なくとも一部を前記第１のパーティションに再マッピングすることと、を実行するように構成された命令を格納する、システム。
【請求項１７】
コンピュータ記憶媒体であって、
実行された場合に、
第１のパーティションのノードのヒストグラムを演算するステップと、
第２のパーティションのノードのヒストグラムを演算するステップと、
前記第１のパーティションのノードのヒストグラムに基づいて、前記第１のパーティションの一組のノードの候補パーティションとして前記第２のパーティションを選択するステップと、
前記第２のパーティションのノードのヒストグラムに基づいて、前記第２のパーティションの一組のノードの候補パーティションとして前記第１のパーティションを選択するステップと、
負荷平衡に基づいて、前記第１のパーティションの一組のノードの少なくとも一部を前記第２のパーティションに再マッピングするとともに、前記第２のパーティションの一組のノードの少なくとも一部を前記第１のパーティションに再マッピングするステップと、
を含むコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納した、コンピュータ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードグラフの分野、特に、コンピュータ実装方法およびシステムならびに記憶媒体に関する。より詳細には、本発明は、ノードをパーティションにマッピングする技術を提供する。
【背景技術】
【０００２】
ソーシャルネットワーキング・ウェブサイトは、メンバーが他のメンバーとつながってコミュニケーションできる動的な環境を提供する。これらのウェブサイトは一般的に、メンバーが既存のソーシャル・ネットワークにおいて相互作用するとともに新たなソーシャル・ネットワークを作成することを可能にするオンライン・メカニズムを提供していてもよい。メンバーには、組織または企業等、任意の個人またはエンティティを含んでいてもよい。数ある属性の中で、ソーシャルネットワーキング・ウェブサイトは、メンバーがそれぞれのソーシャル・ネットワークに関連情報を効果的かつ効率的に伝達できるようにする。
【０００３】
ソーシャル・ネットワークのメンバーは、メンバー専用またはその他の形でコンテンツに使用可能なウェブサイトの領域に対して、情報、ニュース記事、リレーションアクティビティ、音楽、映像、およびその他任意の関心コンテンツを強調または共有することができる。ソーシャル・ネットワークの他のメンバーは、メンバー・プロフィールの閲覧または専用サーチの実行によって、共有コンテンツにアクセスすることができる。コンテンツに対するアクセスおよび評価に際して、他のメンバーは、コンテンツに関するフィードバックまたは意見の提供等、１つまたは複数の応答アクションによって反応することができる。メンバーがこのように相互作用できることにより、メンバー間でのコミュニケーションが促進されるとともに、ソーシャルネットワーキング・ウェブサイトの目標を実現するのに役立つ。
【０００４】
ソーシャル・ネットワークは、ソーシャルグラフとしてモデル化されていてもよい。ソーシャルグラフ等のノードグラフは、膨大な数のノードおよびノードをつなげるエッジを含む場合がある。ソーシャルネットワーキング・システムの場合、ユーザは、ノードグラフに反映された膨大な情報に対するアクセスおよび共有が可能である。たとえば、ノード数は、数億または数十億の場合がある。このような膨大なデータの保守および提供には、多くの課題が伴う。
【発明の概要】
【課題を解決するための手段】
【０００５】
局所性および平衡を目的としてノードを動的にマッピングするため、コンピュータ実装方法、システム、およびコンピュータ可読媒体は、一実施形態において、第１のパーティションのノードのヒストグラムを演算するようにしてもよい。また、第２のパーティションのノードのヒストグラムが演算されるようになっていてもよい。第２のパーティションは、第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの一組のノードの候補パーティションとして選択されるようになっていてもよい。第１のパーティションは、第２のパーティションのノードのヒストグラムに基づいて、第２のパーティションの一組のノードの候補パーティションとして選択されるようになっていてもよい。負荷平衡に基づいて、第１のパーティションの一組のノードの少なくとも一部が第２のパーティションにマッピングされるとともに、第２のパーティションの一組のノードの少なくとも一部が第１のパーティションにマッピングされるようになっていてもよい。
【０００６】
一実施形態においては、第３のパーティションのノードのヒストグラムが演算されるようになっていてもよい。第３のパーティションは、第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの別の一組のノードの候補パーティションとして選択されるようになっていてもよい。第１のパーティションは、第３のパーティションのノードのヒストグラムに基づいて、第３のパーティションの一組のノードの候補パーティションとして選択されるようになっていてもよい。負荷平衡に基づいて、第１のパーティションの上記他の一組のノードの少なくとも一部が第３のパーティションにマッピングされるとともに、第３のパーティションの一組のノードの少なくとも一部が第１のパーティションにマッピングされるようになっていてもよい。
【０００７】
一実施形態において、第１のパーティションの一組のノードは、エッジ局所性のゲインに基づいてソートされるようになっていてもよい。第２のパーティションの一組のノードは、エッジ局所性のゲインに基づいてソートされるようになっていてもよい。
【０００８】
一実施形態において、第２のパーティションは、エッジ局所性のゲインに関する確率に基づいて、第１のパーティションのノードの候補パーティションとして選択されるようになっていてもよい。
【０００９】
一実施形態において、第１のパーティションのノードのヒストグラムは、複数のパーティションそれぞれにおける接続ノードの数を示していてもよい。
一実施形態において、第２のパーティションに再マッピングされた第１のパーティションのノードの数と第１のパーティションに再マッピングされた第２のパーティションのノードの数との差は、しきい値の範囲内であってもよい。
【００１０】
一実施形態において、第２のパーティションに再マッピングされた第１のパーティションのノードの重みと第１のパーティションに再マッピングされた第２のパーティションのノードの重みとの差は、しきい値の範囲内であってもよい。
【００１１】
一実施形態においては、再マッピングの前に、第１のパーティションの第１の総ノード重みが演算されるようになっていてもよい。
一実施形態においては、再マッピングの後に、第１のパーティションの第２の総ノード重みが演算されるようになっていてもよい。
【００１２】
一実施形態において、コンピュータ・システムは、非分散システムであってもよい。また、ノードグラフがメモリにロードされるようになっていてもよい。ノードグラフは、第１のパーティションのノードおよび第２のパーティションのノードを含んでいてもよい。
【００１３】
一実施形態において、コンピュータ・システムは、分散システムであってもよい。また、ノードグラフの異なる部分が分散システム全体にロードされるようになっていてもよい。ノードグラフは、第１のパーティションのノードおよび第２のパーティションのノードを含んでいてもよい。
【００１４】
一実施形態においては、第１のパーティションのノードそれぞれと関連付けられた接続ノードの現行パーティションＩＤが受信されるようになっていてもよい。
一実施形態において、第１のパーティションのノードのヒストグラムは、現行パーティションＩＤに基づいて演算される。
【００１５】
一実施形態においては、第１のパーティションのノードそれぞれの現行パーティションＩＤが提供されるようになっていてもよい。
一実施形態においては、局所性ゲインしきい値に基づいて候補パーティションが選択されるようになっていてもよい。
【００１６】
一実施形態において、第２のパーティションは、エッジ局所性のゲインに関する確率に基づいて、第１のパーティションのノードの候補パーティションとして選択されるようになっていてもよい。
【００１７】
一実施形態においては、再マッピングされるノードを示す複数のパーティションのすべてのパーティション対の記録が生成されるようになっていてもよい。
一実施形態において、ノードグラフは、ソーシャルネットワーキング・システムによりサポートされていてもよい。
【００１８】
添付の図面および以下の詳細な説明から、本発明のその他多くの特徴および実施形態が明らかとなろう。
本発明に係る実施形態は、方法、システム、および媒体に関する添付の特許請求の範囲において特に開示しており、ある請求カテゴリ（たとえば、方法）に記載の如何なる特徴も、別の請求カテゴリ（たとえば、システム）において同様に請求可能である。
【００１９】
本発明に係る一実施形態において、コンピュータ実装方法は、
コンピュータ・システムにより、第１のパーティションのノードのヒストグラムを演算するステップと、
コンピュータ・システムにより、第２のパーティションのノードのヒストグラムを演算するステップと、
コンピュータ・システムにより、第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの一組のノードの候補パーティションとして第２のパーティションを選択するステップと、
コンピュータ・システムにより、第２のパーティションのノードのヒストグラムに基づいて、第２のパーティションの一組のノードの候補パーティションとして第１のパーティションを選択するステップと、
コンピュータ・システムにより、負荷平衡に基づいて、第１のパーティションの一組のノードの少なくとも一部を第２のパーティションに再マッピングするとともに、第２のパーティションの一組のノードの少なくとも一部を第１のパーティションに再マッピングするステップと、
を含む。
【００２０】
このコンピュータ実装方法は、
コンピュータ・システムにより、第３のパーティションのノードのヒストグラムを演算するステップと、
コンピュータ・システムにより、第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの別の一組のノードの候補パーティションとして第３のパーティションを選択するステップと、
コンピュータ・システムにより、第３のパーティションのノードのヒストグラムに基づいて、第３のパーティションの一組のノードの候補パーティションとして第１のパーティションを選択するステップと、
コンピュータ・システムにより、負荷平衡に基づいて、第１のパーティションの上記他の一組のノードの少なくとも一部を第３のパーティションに再マッピングするとともに、第３のパーティションの一組のノードの少なくとも一部を第１のパーティションに再マッピングするステップと、
をさらに含むのが好ましい。
【００２１】
また、このコンピュータ実装方法は、
コンピュータ・システムにより、エッジ局所性のゲインに基づいて、第１のパーティションの一組のノードをソートするステップと、
コンピュータ・システムにより、エッジ局所性のゲインに基づいて、第２のパーティションの一組のノードをソートするステップと、
を含んでいてもよい。
【００２２】
上記において、第２のパーティションは、エッジ局所性のゲインに関する確率に基づいて、第１のパーティションのノードの候補パーティションとして選択されるのが好ましい。
【００２３】
別の実施形態において、第１のパーティションのノードのヒストグラムは、複数のパーティションそれぞれにおける接続ノードの数を示し、および／または、
第２のパーティションに再マッピングされた第１のパーティションのノードの数と第１のパーティションに再マッピングされた第２のパーティションのノードの数との差は、しきい値の範囲内であり、および／または、
第２のパーティションに再マッピングされた第１のパーティションのノードの重みと第１のパーティションに再マッピングされた第２のパーティションのノードの重みとの差は、しきい値の範囲内である。
【００２４】
別の実施形態において、この方法は、
再マッピングの前に、第１のパーティションの第１の総ノード重みを演算するステップ、および、
再マッピングの後に、第１のパーティションの第２の総ノード重みを演算するステップ、の両方または一方を含む。
【００２５】
また、このコンピュータ実装方法は、コンピュータ・システムが非分散システムであり、
コンピュータ・システムにより、ノードグラフをメモリにロードするステップであって、ノードグラフが、第１のパーティションのノードおよび第２のパーティションのノードを含む、ステップをさらに含んでいてもよい。
【００２６】
また、このコンピュータ実装方法は、コンピュータ・システムが分散システムであり、
コンピュータ・システムにより、ノードグラフの異なる部分を分散システム全体にロードするステップであって、ノードグラフが、第１のパーティションのノードおよび第２のパーティションのノードを含む、ステップをさらに含んでいてもよく、および／または、
第１のパーティションのノードそれぞれと関連付けられた接続ノードの現行パーティションＩＤを受信するステップをさらに含み、および／または、
第１のパーティションのノードのヒストグラムが、現行パーティションＩＤに基づいて演算され、および／または、
第１のパーティションのノードそれぞれの現行パーティションＩＤを提供するステップをさらに含み、および／または、
候補パーティションが、局所性ゲインしきい値に基づいて選択され、および／または、
第２のパーティションが、エッジ局所性のゲインに関する確率に基づいて、第１のパーティションのノードの候補パーティションとして選択され、および／または、
コンピュータ・システムにより、再マッピングされるノードを示す複数のパーティションのすべてのパーティション対の記録を生成するステップをさらに含む。
【００２７】
また、このコンピュータ実装方法は、ソーシャルネットワーキング・システムによりサポートされたノードグラフを含んでいてもよい。
本発明に係るシステムは、
少なくとも１つのプロセッサと、
上記少なくとも１つのプロセッサに指示して、上述の実施形態のいずれかまたはすべてに係る方法を実行するように構成された命令を格納したメモリと、
を備えるのが好ましい。
【００２８】
実行された場合に、上述の実施形態のいずれかまたはすべてに係るコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納したコンピュータ記憶媒体。
【００２９】
本発明に係るシステムは、
少なくとも１つのプロセッサと、
上記少なくとも１つのプロセッサに指示して、
第１のパーティションのノードのヒストグラムを演算することと、
第２のパーティションのノードのヒストグラムを演算することと、
第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの一組のノードの候補パーティションとして第２のパーティションを選択することと、
第２のパーティションのノードのヒストグラムに基づいて、第２のパーティションの一組のノードの候補パーティションとして第１のパーティションを選択することと、
負荷平衡に基づいて、第１のパーティションの一組のノードの少なくとも一部を第２のパーティションに再マッピングするとともに、第２のパーティションの一組のノードの少なくとも一部を第１のパーティションに再マッピングすることと、
を実行するように構成された命令を格納したメモリと、
を備えるのが好ましい。
【００３０】
実行された場合に、
第１のパーティションのノードのヒストグラムを演算するステップと、
第２のパーティションのノードのヒストグラムを演算するステップと、
第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの一組のノードの候補パーティションとして第２のパーティションを選択するステップと、
第２のパーティションのノードのヒストグラムに基づいて、第２のパーティションの一組のノードの候補パーティションとして第１のパーティションを選択するステップと、
負荷平衡に基づいて、第１のパーティションの一組のノードの少なくとも一部を第２のパーティションに再マッピングするとともに、第２のパーティションの一組のノードの少なくとも一部を第１のパーティションに再マッピングするステップと、
を好ましくは含むコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納したコンピュータ記憶媒体。
【図面の簡単な説明】
【００３１】
【図１】一実施形態に係る、例示的な最適化モジュール１００を示した図である。
【図２】一実施形態に係る、例示的な局所性制御モジュール１０２を示した図である。
【図３】一実施形態に係る、例示的な分散システムを示した図である。
【図４】一実施形態に係る、例示的な平衡再マッピング・モジュール１０３を示した図である。
【図５】一実施形態に係る、ノードを再マッピングする例示的な最適化プロセスを示した図である。
【図６】一実施形態に係る、ソーシャルネットワーキング・システム内でノードのマッピングを最適化するシステムの例示的なネットワーク図である。
【図７】一実施形態に係る、本明細書に記載の実施形態のうちの１つまたは複数の実装に使用できる例示的なコンピュータ・システムを示した図である。
【発明を実施するための形態】
【００３２】
上記図面は、説明のみを目的として本発明の種々実施形態を示しており、同様の要素の識別には、同様の符号を使用している。以下の記述から、当業者には、本明細書に記載の本発明の原理から逸脱することなく、図面に示す構造および方法の別の実施形態を採用可能であることが容易に認識されよう。
【００３３】
ノードグラフは、分散システムの複数のコンピュータにわたって分配されていてもよい。ノードがパーティション（partition）に対してどのようにマッピングされているかが性能に影響を及ぼす場合がある。たとえば、ソーシャル・ネットワークにおいて、友達（たとえば、「友達関係」に基づいてエッジによりつなげられたノード）を同じパーティションにマッピングすると、友達に関するクエリが開始された場合の他のパーティションに対するファンアウト・クエリの量の最小化によって、性能が向上する場合がある。パーティションには、たとえばサーバまたはデータセンタを含んでいてもよい。さらに、友達は、重複した情報を問い合わせる傾向にあり、この場合、重複した情報がクエリに対してすでに読み出され、キャッシュ等の高速メモリに格納されている可能性が高いため、ネットワーク性能が向上する可能性がある。したがって、エッジ局所性を高めることが有益となる場合がある。
【００３４】
さらには、パーティションの負荷もネットワーク性能に影響を及ぼす場合がある。「負荷」の種類は、アプリケーションに基づいて変化する可能性がある。たとえば、アプリケーションによっては、負荷がパーティション内のノード（たとえば、ユーザ）の数に基づいていてもよい。他のアプリケーションにおいて、負荷は、パーティションに格納されたデータの量に基づいていてもよい。さらに他のアプリケーションにおいて、負荷は、アクティビティレベルに基づいていてもよい。アクティビティレベルは、パーティションにおけるユーザのアクティビティに関連していてもよい。アクティビティは、ユーザが１つまたは複数のアクティビティを行う回数、ユーザがアップロード、ダウンロード、または両者を行うデータの量等に関連していてもよい。負荷の種類は、アプリケーションが異なれば変化する可能性があるものの、一般的には、パーティション間の平衡負荷を維持する性能に有益である。
【００３５】
場合によっては、低エッジ局所性（low edge locality）となる可能性が高い大略ランダムな様態で、ノードがパーティションにマッピングされるようになっていてもよい。たとえば、ソーシャル・ネットワークのユーザは、それぞれのネットワークへの参加時間およびその時点で利用可能なパーティションに基づいて、該パーティションにマッピングされるようになっていてもよい。このような場合、ソーシャル・ネットワークのユーザは、それぞれの友達がマッピングされている場所を一切考慮することなく、パーティションにマッピングされるようになっていてもよい。
【００３６】
場合によっては、パーティション間の負荷を平衡させつつ高いエッジ局所性（higher edge locality）を提供しようとする際に、ノードグラフの初期マッピングが生成されるようになっていてもよい。例示的な初期マッピングは、たとえばパーティション間の負荷を平衡させつつ高いエッジ局所性を生成しようとする地理的ロケーションに基づいていてもよい。ただし、ソーシャルグラフ等のノードグラフは、動的かつ頻繁に変化するため、エッジ局所性または平衡に悪影響を及ぼす可能性がある。たとえば、ソーシャル・ネットワークのユーザは、友達を得る場合または失う場合があり、異なる地理的ロケーションに移動する場合があり、新たな組織、会社、学校等に参加する場合がある。さらに、新たなユーザがネットワークに参加して既存のユーザと新たな友達関係を形成する場合があり、これも、エッジ局所性または平衡に悪影響を及ぼす可能性がある。さらに、ユーザがそれぞれの振る舞いまたは習慣を変更する場合があり、ユーザがマッピングされているパーティションに与える負荷の量が変化する可能性がある。いくつかの初期マッピング法は、作成時点で有益な場合があるものの、静的であるため、変化するノードグラフに対応していない可能性がある。
【００３７】
本明細書に記載のシステムおよび方法の実施形態は、ノードグラフのノードのマッピングを最適化して、パーティションにおける負荷平衡を維持しつつエッジ局所性（または、接続局所性）を改善することに関する。最適化プロセスには、負荷平衡を依然として維持しつつパーティションにおけるエッジ局所性を絶えず改善する一連の反復を含んでいてもよい。たとえば、特定の実施形態において、最適化プロセスでは、異なるパーティションに再マッピングされた場合にエッジ局所性の利益となるノードを決定するようにしてもよい。候補パーティションへの再マッピングの利益を享受する各ノードに対して、該候補パーティションが選択されるようになっていてもよい。そして、最適化プロセスでは、負荷平衡を維持する様態で、ノードを候補パーティションに対して選択的に移動させるようにしてもよい。その後、最適化プロセスでは、該最適化プロセスが安定するまで、後続の一連の反復を実行するようにしてもよい。
【００３８】
さらに、最適化プロセスは、将来的に繰り返して実行することにより、マッピングを最適化して、経時的に発生したノードグラフの任意の変化に対応するようにしてもよい。一実施形態において、最適化プロセスは、１週間後、１カ月後、６カ月後、またはその他任意の期間後等、所定の期間後に再実行されるようになっていてもよい。
【００３９】
ノードグラフが経時的に変化する場合は、これらの変化がエッジ局所性または平衡に有害となる可能性があるため、安定したマッピングに対する不一致（または、撹乱効果）が生じる場合がある。マッピングのその他の安定した部分はすでに安定状態であるため、最適化プロセスでは主として、これらの不一致に焦点を当てる。こうすることにより、最適化プロセスでは、全く新しいマッピングを毎回ゼロから生成する必要なく、現在のマッピングを絶えず最適化するようにしてもよい。たとえば、新たなユーザは、友達関係のつながりを持たない傾向にあるため、最初は、エッジ局所性を最小限に考慮するか、または一切考慮せずに、ランダムなパーティションにマッピングされるようになっていてもよい。将来的な最適化プロセスでは、安定したマッピングに対する変化の特定の理由に焦点を当てるようにしてもよい。
【００４０】
図１は、一実施形態に係る、例示的な最適化モジュール１００を示している。最適化モジュール１００は、パーティションにわたって負荷平衡を維持しつつエッジ局所性（または、接続局所性）を改善するように、該パーティションに対するノードグラフのノードのマッピングを最適化する。一実施形態において、本明細書に記載のノードおよびエッジは、ソーシャルネットワーキング・システムのユーザおよびそれぞれの友達関係に関していてもよい。また、基礎となる考え方および原理は、他の種類のノードおよびエッジに適用可能であってもよい。一実施形態において、ノードは、具体的であれ抽象的であれ、ノードとして表し得る人間、人間以外、組織、コンテンツ（たとえば、画像、映像、音声等）、イベント、ウェブページ、通信、オブジェクト、コンセプト、もしくはその他任意の事物、観念、または構成概念等と関連付けられていてもよい。ノードには、ソーシャルネットワーキング・システム等のネットワーキング・システムのユーザを含んでいてもよい。ユーザは、必ずしも人間に限定されず、その他人間以外のエンティティを含んでいてもよい。エッジ局所性は、２つのパーティション間のエッジとは対照的に、パーティション内のエッジの数または割合に関していてもよい。所与のパーティションに関して、エッジ局所性は、異なるパーティションにつながるエッジの数に対して、該所与のパーティションに含まれるエッジの数に関していてもよい。所与のノードに関して、エッジ局所性は、該所与のノードを異なるパーティションにつながるエッジの数に対して、該所与のノードにつなげられた該所与のノードのパーティション内のエッジの数に関していてもよい。最適化モジュール１００は、初期化モジュール（initialization module）１０１、局所性制御モジュール（locality control module）１０２、および平衡再マッピング・モジュール（balanced remapping module）１０３を具備していてもよい。この図面および本明細書のすべての図面に示す構成要素は、例示に過ぎず、他の実施態様では、追加の構成要素、より少ない構成要素、または異なる構成要素を具備していてもよい。関連する細部が分かり難くならないように、図示していない構成要素もある。
【００４１】
初期化モジュール１０１は、パーティションに対するノードグラフのノードの現在のマッピング（たとえば、初期マッピング）を取得するようにしてもよい。初期化モジュール１０１は、ノードグラフをメモリにロードするようにしてもよい。また、初期化モジュール１０１は、ノード重みまたはエッジ重みをメモリにロードするようにしてもよい。ノード重みは、ユーザがパーティションに掛けた負荷の量に関していてもよい。たとえば、ソーシャルネットワーキング・システムにおけるユーザのノード重みは、ユーザのログイン、写真のアップロード等の回数に関していてもよい。エッジ重みは、２つのユーザ間のエッジに適用された負荷の量等、異なるパーティションに２つのノードを有する「コスト」に関していてもよい。たとえば、互いに大量のデータを共有する２つのユーザは、高いエッジ重みを有するものと判定されるようになっていてもよい。エッジの係数は、２つのノードの近接性または近縁性に関していてもよい。たとえば、２つのユーザは、家族であることにより、一般的な知人よりも高い係数を有していてもよい。場合によっては、係数がエッジ重みとして機能するようになっていてもよい。
【００４２】
また、初期化モジュール１０１は、ノードの初期マッピングをパーティションにロードするようにしてもよい。たとえば、初期マッピングには、ノードの地理的関連性に基づいたパーティションに対するノードの初期マッピングを含んでいてもよい。そして、本明細書に記載の通り、初期マッピングの最適化によって、負荷平衡を維持しつつ局所性を改善するようにしてもよい。
【００４３】
一実施形態においては、非分散システムがマッピングを最適化する。たとえば、ノードグラフは、パーティションに対するノードの最適化マッピングを演算可能な単一またはローカルのマシン（または、他の非分散システム）のメモリ（たとえば、ランダム・アクセス・メモリ（ＲＡＭ））にロードされるようになっていてもよい。
【００４４】
別の実施形態においては、複数のコンピュータを具備した分散システムがマッピングを最適化するようになっていてもよい。たとえば、ノードグラフが複数のコンピュータ（または、マシン）全体にロードされて、各コンピュータが一意のノードグラフ部分集合をロードするようにしてもよい。ノードグラフは、たとえばＨａｄｏｏｐ分散ファイル・システム（ＨＤＦＳ：Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）等の分散ファイル・システムによるテーブルに含まれていてもよい。また、ノード重み、エッジ重み、および初期マッピングは、分散ファイル・システムによる別のテーブルに含まれていてもよい。
【００４５】
局所性制御モジュール１０２は、本明細書においてより詳しく説明する通り、パーティションにおけるエッジ局所性の改善に関する演算および解析を行う。平衡再マッピング・モジュール１０３は、本明細書においてより詳しく説明する通り、パーティション全体で負荷平衡を維持する様態での異なるパーティションに対するノードの再マッピングに関する演算および解析を行う。
【００４６】
図２は、一実施形態に係る、例示的な局所性制御モジュール１０２を示している。局所性制御モジュール１０２は、ヒストグラム生成モジュール（histogram generation module）２０１、ゲイン演算モジュール（gain computation module）２０２、候補パーティション選択モジュール（candidate partition selection module）２０３、およびマトリクス生成モジュール（matrix generation module）２０４を具備していてもよい。
【００４７】
ヒストグラム生成モジュール２０１は、１つまたは複数のパーティションのノードのヒストグラム（histogram）を演算するようにしてもよい。エッジによって所与のノードにつなげられたノード（または、所与のノードとのつながりを有するノード）の数は、本明細書において「接続ノード」と称する場合がある。エッジ重みを考慮しない一実施形態において、所与のノードのヒストグラムは、多数のパーティションにわたって、各パーティション内の接続ノードの数を識別可能であってもよい。エッジ重みを考慮する一実施形態において、所与のノードのヒストグラムは、多数のパーティションにわたって、各パーティションにつなげられたエッジの総重みを識別可能であってもよい。
【００４８】
非分散システムがマッピングを最適化する一実施形態において、各ノードのヒストグラムは、該非分散システム（たとえば、単一のコンピュータ）により演算されるようになっていてもよい。たとえば、単一のコンピュータは、各ノードの現在のパーティションのほか、各ノードの接続ノードを識別するデータを含んでいてもよい。このように、コンピュータがデータにアクセスして、各ノードのヒストグラムを生成するようにしてもよい。
【００４９】
分散システムがマッピングを最適化する一実施形態においては、複数のコンピュータの使用により、コンピュータ間で情報（または、メッセージ）をやり取りすることによって、ノードグラフのノードのヒストグラムを生成するようにしてもよい。たとえば、各ノードは、その現在のパーティションを（たとえば、現行パーティションＩＤを介して）その接続ノードそれぞれに伝達するようにしてもよい。そして、各ノードは、各接続ノードがマッピングされたパーティションを識別した後、それ自体のヒストグラムを生成するようにしてもよい。ノード重みを考慮する一実施形態においては、ノード重みもノード間でやり取りされるようになっていてもよい。本明細書においてより詳しく説明する通り、現在のパーティションおよびノード重みの全体としてのテーブルへの集約により、各パーティション内のノードまたはエッジの総重みを識別するようにしてもよい。
【００５０】
ゲイン演算モジュール２０２は、現在のパーティションから異なるパーティションへのノードの再マッピングと関連付けられた「ゲイン」値を演算するようにしてもよい。所与のノードの「ゲイン」は、異なるパーティションにマッピングされた接続ノードの数と所与のノードの現在のパーティションにマッピングされた接続ノードの数との差によって演算されるようになっていてもよい。たとえば、所与のノードがパーティション＃１に割り当てられており、５個の接続ノードがパーティション＃１にマッピングされ、７個の接続ノードがパーティション＃２にマッピングされている場合、該所与のノードは、パーティション＃２に再マッピングされた場合に、ゲイン「２」（すなわち、７−５）を有するようになっていてもよい。異なるパーティションへの再マッピングと関連付けられたゲインは、正であってもよく、所与のノードと同じパーティション内の接続ノードの数の増加を反映して、所与のノードのエッジ局所性を増大させる。異なるパーティションへの再マッピングと関連付けられたゲインは、負であってもよく、所与のノードと同じパーティション内の接続ノードの数の減少を反映して、所与のノードのエッジ局所性を低下させる。場合により、ゲインは０であってもよく、所与のノードと同じパーティション内の接続ノードの数が変わらないことを反映する。
【００５１】
エッジ重みを考慮する一実施形態において、異なるパーティションへの再マッピングと関連付けられた所与のノードのゲインは、異なるパーティションにマッピングされた接続ノードの総エッジ重み（total edge weights）と所与のノードの現在のパーティションにマッピングされた接続ノードの総エッジ重みとの差によって演算されるようになっていてもよい。
【００５２】
候補パーティション選択モジュール２０３は、ノードが再マッピングされる候補パーティションを選択するようにしてもよい。所与のノードの候補パーティションの選択は、該所与のノードのエッジ局所性の改善に基づいて選択されるようになっていてもよい。また、場合によっては、所与のノードに対して、同じエッジ局所性を維持する（すなわち、ゲインが０となる）候補パーティションが選択されるようになっていてもよい。
【００５３】
一実施形態において、所与のノードの候補パーティションは、該所与のノードのエッジ局所性のゲインに関する確率に基づいて選択されるようになっていてもよい。たとえば、所与のノードの候補パーティションは、エッジ局所性がより大きく増大するパーティションに対するバイアスを有する確率アルゴリズムに基づいて選択されるようになっていてもよい。このように、所与のノードのゲインが大きくなるパーティションは、該所与のノードの候補パーティションとして選択される確率がより高くなるが、必ずしも確実ではない。たとえば、ノードＣがパーティション＃３にマッピングされ、パーティション＃３に５個の接続ノード、パーティション＃６に１０個の接続ノード、パーティション＃１２に８個の接続ノードを有し、他のパーティションには、接続ノードを有していなくてもよい。一実施形態において、確率アルゴリズムは、パーティション内の接続ノードの数のほか、ゲインが得られるパーティション内の接続ノードの総数に基づいて規定されていてもよい。たとえば、候補パーティションとして選択されるパーティション＃３の確率は、５／２３となるが、「５」はパーティション＃３内の接続ノードの数であり、「２３」は接続ノードの総数（パーティション＃３から５つ、パーティション＃６から１０個、およびパーティション＃１２から８つ）である。候補パーティションとして選択されるパーティション＃６の確率は、１０／２３となる。また、候補パーティションとして選択されるパーティション＃１２の確率は、８／２３となる。一実施形態においては、ゲインが０となるパーティションについても、候補パーティションと考えることができる。たとえば、このように、確率アルゴリズムは、パーティション内の接続ノードの数のほか、ゲインが正または０となるパーティション内の接続ノードの総数に基づいて規定されていてもよい。
【００５４】
別の実施形態においては、エッジ局所性が最大限に増大するパーティションが候補パーティションとして選択されるようになっていてもよい。
一実施形態においては、パーティションが候補パーティションとして適格となるようにしきい値を満たすかまたは超過するゲインとなる必要がある局所性ゲインしきい値が実装されるようになっていてもよい。たとえば、局所性ゲインしきい値が３である場合、所与のノードの再マッピングがゲイン１または２となるパーティションは、候補パーティションとしての選択に適格とはならない。ただし、所与のノードの再マッピングがゲイン３以上となるパーティションは、候補パーティションとしての選択に適格となる。たとえば、局所性ゲインしきい値の実装によって、最小ゲインのパーティション間の再マッピングを抑制または排除するようにしてもよい。
【００５５】
一実施形態において、局所性ゲインしきい値は、最適化の反復ごとに変化してもよい。たとえば、局所性ゲインしきい値は、高い値から始まり、反復を通して低下するようになっていてもよい。また、しきい値の値に関して、他の変化パターンが実装されるようになっていてもよい。場合によっては、長期または短期にわたるノードの再マッピングの停止または減速のため、高い局所性ゲインしきい値が設定されるようになっていてもよい。分散システムがマッピングを最適化する一実施形態において、局所性ゲインしきい値は、高い値から始まり、反復を通して低下するようになっていてもよい。このように、ノードのより有用な再マッピングが最初に生じた後、分配の改善および安定化に伴って徐々に低下することにより、よりきめ細かな再マッピングが提供されるようになっていてもよい。
【００５６】
マトリクス生成モジュール２０４は、あらゆるパーティション対（Ｘ，Ｙ）のノードに基づいて、ノードリストのマトリクスを生成する。非分散システムがマッピングを最適化する一実施形態において、パーティション対（Ｘ，Ｙ）のリストは、パーティションＹを候補パーティションとするパーティションＸ内のノードを一覧化する。たとえば、パーティション対（１，２）の場合は、パーティション＃２を候補パーティションとするパーティション＃１内のすべてのノードが一覧化されるようになっていてもよい。パーティション対（１，３）の場合は、パーティション＃３を候補パーティションとするパーティション＃１内のすべてのノードが一覧化されるようになっていてもよい。パーティション対（３，１）の場合は、パーティション＃１を候補パーティションとするパーティション＃３内のすべてのノードが一覧化されるようになっていてもよい。そして、あらゆるパーティション対（Ｘ，Ｙ）のリストは、このデータに基づいて生成されるようになっていてもよい。また、一実施形態においては、候補パーティションに再マッピングされるノードと関連付けられたゲインをリストが示していてもよい。ノード重みを考慮する一実施形態において、パーティション対（Ｘ，Ｙ）のリストには、パーティションＹを候補パーティションとするパーティションＸ内のノードの総重みを含んでいてもよい。
【００５７】
分散システムがマッピングを最適化する一実施形態において、マトリクス中のリストには、パーティションＹを候補パーティションとするパーティションＸのノード数を表す値を含んでいてもよい。ノード重みを考慮する場合、リストには、パーティションＹを候補パーティションとするパーティションＸのノードの総ノード重みを含んでいてもよい。一実施形態において、各ノードと関連付けられたマシンは、その現在のパーティションおよびノード重みを、他のパーティションの他のノードと関連付けられたマシンに伝達するようにしてもよい。このように、ノード重みの全体としての集約により、各パーティションの総ノード重みを反映するようにしてもよい。また、パーティションの総ノード重みは、テーブルに反映されていてもよい。
【００５８】
そして、マトリクス生成モジュール２０４により生成されたリストは、平衡再マッピング・モジュール１０３への提供により、ノードを異なるパーティションに再マッピングするようにしてもよい。本明細書においてより詳しく説明する通り、再マッピングは、パーティションの負荷平衡を維持しつつエッジ局所性を増大させるように実行されてもよい。
【００５９】
非分散システムの構造は、分散システムの構造と異なっていてもよい。たとえば、非分散システムがマッピングを最適化する一実施形態において、ヒストグラム生成モジュール２０１、ゲイン演算モジュール２０２、候補パーティション選択モジュール２０３、およびマトリクス生成モジュール２０４は、単一のコンピュータ・システムに実装されていてもよく、最適化プロセスと関連付けられたデータは、コンピュータ・システムの単一または共有メモリ（たとえば、ＲＡＭ）に保持されていてもよい。分散システムにおいて、ゲイン演算モジュール２０２、候補パーティション選択モジュール２０３、およびマトリクス生成モジュール２０４はそれぞれ、該分散システムの１つまたは複数のコンピュータ・システム全体に実装されていてもよい。
【００６０】
図３は、一実施形態に係る、例示的な分散システムを示している。分散システム３００は、コンピュータ・システム３０１〜３０３、集約モジュール３０４〜３１２、およびマスター・コンピュータ・システム３１３を具備していてもよい。
【００６１】
ノードグラフは、コンピュータ・システム３０１〜３０３それぞれが一意（または、非一意）のノードグラフ部分集合を含むように、コンピュータ・システム３０１〜３０３全体にロードされていてもよい。一例として、３つのコンピュータ・システムを使用しているが、当然のことながら、他の実施形態においては、その他任意数のコンピュータ・システムが実装されていてもよい。
【００６２】
また、コンピュータ・システム３０１〜３０３はそれぞれ、集約モジュール３０４〜３１２の部分集合を含んでいてもよい。集約モジュール３０４〜３１２はそれぞれ、ノードリストおよびパーティション対（Ｘ，Ｙ）のマトリクスの生成に利用可能な１つまたは複数のパーティション対（Ｘ，Ｙ）のノードリストを生成するようにしてもよい。一実施形態において、集約モジュール３０４〜３１２はそれぞれ、パーティション対（Ｘ，Ｙ）のうちの１つのリストを生成するようにしてもよい。また、集約モジュール３０４〜３１２はそれぞれ、たとえばヒストグラム生成モジュール２０１、ゲイン演算モジュール２０２、および候補パーティション選択モジュール２０３を具備していてもよい。一例として、９つの集約モジュール３０４〜３１２を使用しているが、当然のことながら、他の実施形態においては、実装される集約モジュールの数がこれ以外であってもよい。また、当然のことながら、コンピュータ・システム当たりの集約モジュールの数が異なっていてもよい。
【００６３】
各コンピュータ・システム３０１〜３０３は、それぞれの集約モジュール３０４〜３１２の部分集合からノードリストを受信するようにしてもよい。そして、コンピュータ・システム３０１〜３０３はそれぞれ、各リストを相互およびマスター・コンピュータ・システム３１３に伝達するようにしてもよい。たとえば、コンピュータ・システム３０１は、集約モジュール３０４〜３０６で生成されたリストをコンピュータ・システム３０２および３０３ならびにマスター・コンピュータ・システム３１３に伝達するようにしてもよい。そして、コンピュータ・システム３０１〜３０３およびマスター・コンピュータ・システム３１３は、すべてのパーティション対（Ｘ，Ｙ）のマトリクス全体を生成するようにしてもよい。このように、マトリクス生成モジュール２０４は、たとえば集約モジュール３０４〜３１２、コンピュータ・システム３０１〜３０３、およびマスター・コンピュータ・システム３１３により実装されていてもよい。集約モジュール３０４〜３１２がそれぞれ、特定のパーティション対（Ｘ，Ｙ）のリストを生成する一方、コンピュータ・システム３０１〜３０３およびマスター・コンピュータ・システム３１３がパーティション対（Ｘ，Ｙ）のマトリクス全体を生成するようになっていてもよい。一実施形態において、マスター・コンピュータ・システム３１３は、ノードグラフの如何なる部分集合も含む必要はないものの、ノードリストおよびパーティション対（Ｘ，Ｙ）のマトリクスを生成する。
【００６４】
図４は、一実施形態に係る、例示的な平衡再マッピング・モジュール１０３を示している。平衡再マッピング・モジュール１０３は、ノード選択モジュール４０１、ノード再マッピング・モジュール４０２、および終端モジュール４０３を具備していてもよい。
【００６５】
ノード選択モジュール４０１は、任意所与の２つのパーティションに関して、パーティション全体で負荷平衡を維持しつつエッジ局所性を増大させるため、第１のパーティションのどのノードを第２のパーティションに再マッピング可能であるかを決定するようにしてもよい。ノード再マッピング・モジュール４０２は、ノード選択モジュール４０１により決定された任意所与の２つのパーティション間で、ノードの再マッピングを行う。
【００６６】
ノード重みを考慮しない一実施形態において、第１のパーティションから第２のパーティションに再マッピングされるノードの総数は、第２のパーティションから第１のパーティションに再マッピングされるノードの総数と同じであってもよい。別の実施形態において、第１のパーティションから第２のパーティションに再マッピングされるノードの総数は、第２のパーティションから第１のパーティションに再マッピングされるノードの総数と同じではないが、パーティション全体で負荷平衡を維持するための許容範囲内であってもよい。ノード重みを考慮する一実施形態において、第１のパーティションから第２のパーティションに再マッピングされるノードの総重みは、第２のパーティションから第１のパーティションに再マッピングされるノードの総重みと同じであってもよい。別の実施形態において、第１のパーティションから第２のパーティションに再マッピングされるノードの総重みは、第２のパーティションから第１のパーティションに再マッピングされるノードの総重みと同じではないが、負荷平衡と考えられる許容範囲内であってもよい。
【００６７】
ノード選択モジュール４０１は、パーティション対（Ｘ，Ｙ）の生成リストに基づいて、再マッピングを決定するようにしてもよい。一実施形態において、平衡を維持するため、パーティションＸからパーティションＹへの移動が選択されるノードの数は、パーティションＹからパーティションＸへの移動が選択されるノードの数と同じであってもよい。２つのパーティション対（たとえば、パーティション対（１，２）およびパーティション対（２，１））のリストが異なるノード数を有する場合、一実施形態において、各パーティションからの再マッピングが選択されるノードの数は、ノードの数が少ない方のパーティション対のリスト内のノードの数と同じであってもよい。たとえば、パーティション＃２を候補パーティションとするパーティション＃１の５つのノードをパーティション対（１，２）のリストが含み、パーティション＃１を候補パーティションとするパーティション＃２の１０個のノードをパーティション対（２，１）のリストが含む場合、各パーティションからの再マッピングには、５つのノードが選択されるようになっていてもよい。たとえば、パーティション対（１，２）のリスト中の全５つのノードがパーティション＃２に再マッピングされ、パーティション対（２，１）のリストのうちゲインが最大の５つのノードがパーティション＃１に再マッピングされるようになっていてもよい。
【００６８】
非分散システムがマッピングを最適化する一実施形態において、ノード選択モジュール４０１は、ゲインによってパーティション対（Ｘ，Ｙ）のリストをソートするソート・モジュールを具備していてもよい。たとえば、パーティションＹを候補パーティションとするパーティションＸのノードは、各ノードが候補パーティションに再マッピングされた場合に有することになるゲインに基づいてランク付けされる。このように、ゲインが最も高いノードがまず、再マッピング対象として選択される。
【００６９】
ノード重みを考慮する一実施形態においては、パーティション対の任意の２つのリスト内のノードの総重みの演算により、これら２つのパーティション間でノードを再マッピング可能であるか否かを判定するようにしてもよい。たとえば、パーティション＃３のノードの演算総重みがパーティション＃４のノードの総重みよりも大きく、パーティション対（３，４）のリスト中にノードが存在する場合、該パーティション対（３，４）のリスト中のノードは、パーティション＃４に再マッピングされるようになっていてもよい。２つのパーティション内のノードの総重みは、パーティション＃３および＃４のノード間の更新された再マッピングに基づいて再演算され、解析が繰り返されるようになっていてもよい。パーティション＃３のノードの演算総重みがパーティション＃４のノードの総重み以下であり、パーティション対（４，３）のリスト中にノードが存在する場合、該パーティション対（４，３）のリスト中のノードは、パーティション＃３に再マッピングされるようになっていてもよい。２つのパーティション内のノードの総重みは、更新された再マッピングに基づいて再演算され、解析が繰り返されるようになっていてもよい。ノード重みが等しくない場合のパーティションおよび関連する再マッピングに関する総ノード重みの比較は、任意適当な反復回数にわたって繰り返されるようになっていてもよい。パーティション対の各リストの総ノード重みが等しいか、またはそれぞれの差が選択しきい値の範囲内である場合は、解析を終了して、該パーティションが負荷平衡であるものと考えるようにしてもよい。一実施形態において、パーティション内のノードの総重みは、パーティション＃３および＃４のノード間の更新された再マッピングのみならず、他のパーティションとパーティション＃３および＃４の一方または両方との間のノードのその他任意の更新された再マッピングにも基づいて再演算されるようになっていてもよい。一般的に、ノードの再マッピングによる負荷平衡に関する本明細書に記載の原理は、ノードグラフのノードと関連付けられたすべてのパーティションのあらゆる組み合わせに適用可能である。
【００７０】
分散システムがマッピングを最適化する一実施形態において、マスター・コンピュータ・システム３１３は、ノードリストおよびパーティション対（Ｘ，Ｙ）のマトリクスを生成して、異なるパーティションに再マッピングすべきノードの数を決定するようにしてもよい。たとえば、マスター・コンピュータ・システム３１３は、集約器３０４〜３１２から、すべてのパーティション対（Ｘ，Ｙ）のリストを受信するようにしてもよい。これらのリストでは、パーティションＹを候補パーティションとするパーティションＸのノードの総数を識別していてもよい。ノード重みを考慮する場合、リストでは、パーティションＹを候補パーティションとするパーティションＸのノードの総重みを識別していてもよい。
【００７１】
そして、マスター・コンピュータ・システム３１３は、異なるパーティションに再マッピングすべきノードの数を決定することにより、平衡を維持するようにしてもよい。その後、マスター・コンピュータ・システム３１３は、再マッピングされるノードの数をコンピュータ・システム３０１〜３０３に伝達するようにしてもよい。一実施形態においては、平衡を維持するため、２つのパーティション対（たとえば、パーティション対（１，２）およびパーティション対（２，１））のリストが異なるノード数を有する場合、各パーティションからの再マッピングが選択されるノードの数は、ノードの数が少ない方のパーティション対のリスト内のノードの数と等しくなる。
【００７２】
一実施形態において、異なるパーティションに再マッピングされるノードの数は、確率に基づいて、マスター・コンピュータ・システム３１３からコンピュータ・システム３０１〜３０３に伝達される。たとえば、パーティション対（Ｘ，Ｙ）のリスト中のノードの再マッピングの確率ＰＸＹは、以下の式に基づいて決定されるようになっていてもよい。
ＰＸＹ＝ＺＸＹ／ｍＸＹ
ここで、ＺＸＹは、パーティションＸからパーティションＹに再マッピングされるノードの数を表しており、
ｍＸＹは、パーティションＹを候補パーティションとするパーティションＸのノードの総数を表している。
【００７３】
パーティションＹを候補パーティションとするパーティションＸの各ノードは、パーティションＹへの再マッピングの確率がＰＸＹである。
終端モジュール４０３は、演算または解析によって、最適化プロセスを停止すべきタイミングを決定するようにしてもよい。一実施形態において、終端モジュール４０３は、最適化が安定した後に最適化プロセスを停止するようにしてもよい。分散システムがマッピングを最適化する一実施形態において、終端モジュール４０３は、マスター・コンピュータ・システム３１３により実装されていてもよい。また、終端モジュール４０３は、収束検出技術を実行することによって、最適化プロセスが収束して停止可能であるか否かを判定するようにしてもよい。一実施形態において、終端モジュール４０３は、所定回数の反復の後に最適化プロセスを停止するようにしてもよい。
【００７４】
一実施形態において、終端モジュール４０３は、ノードグラフのエッジの総数に対する局所エッジ（または、パーティション全体に対するあるパーティション内のエッジ）の総数または総重みを識別可能な「局所性割合（locality percentage）」に基づいて、最適化プロセスを停止するようにしてもよい。エッジの総数は、たとえば最適化プロセスの最初に演算されるようになっていてもよい。終端モジュール４０３は、集約器３０４〜３１２からノードグラフに関する全体統計およびノードグラフの最適化を受信することにより、局所性割合を決定するようにしてもよい。パーティションの各ノードは、そのエッジが（該ノードと同じパーティションにおいて）局所的であるか否かに基づいて、局所性割合の決定に寄与するようにしてもよい。局所エッジの重みが集約器３０１〜３０３により集約されることによって、局所的な総エッジ重みが決定されるようになっていてもよい。
【００７５】
局所性割合は、他の考慮事項に基づいていてもよい。また、局所性割合は、エッジの総数とは対照的に、エッジの総重みに適用可能であってもよい。終端モジュール４０３は、ノードグラフのノードの総重みに対するパーティションの局所的な総重みの比を局所性割合の根拠としていてもよい。一実施形態において、局所性割合の決定には、パーティションの局所エッジの総数およびパーティションのエッジの総重みの両者を考慮するようにしてもよい。
【００７６】
所定回数の反復で局所性割合が安定となったら、最適化プロセスは、収束したと考えられてもよく、停止可能であってもよい。一実施形態において、このような安定は、選択された反復回数での選択しきい値の範囲内となる局所性割合の値の変化に反映されていてもよい。
【００７７】
図５は、一実施形態に係る、ノードを再マッピングする例示的な最適化方法５００を示している。当然のことながら、図１〜図４に関する上記説明は、図５の方法にも適用可能である。ここでは、簡略化および明瞭化のため、図５に適用可能な如何なる特徴および機能も繰り返さない。
【００７８】
方法５００のブロック５０２においては、第１のパーティションのノードのヒストグラムを演算するようにしてもよい。ブロック５０４においては、第２のパーティションのノードのヒストグラムを演算するようにしてもよい。一実施形態において、ブロック５０２および５０４は、図２のヒストグラム生成モジュール２０１により実行されるようになっていてもよい。分散システムがマッピングを最適化する一実施形態においては、接続ノードと関連付けられたマシンから伝達された情報に基づいて、各ノードがヒストグラムを生成する。
【００７９】
ブロック５０６において、第２のパーティションは、第１のパーティションのノードのヒストグラムに基づいて、第１のパーティションの一組のノードの候補パーティションとして選択されるようになっていてもよい。ブロック５０８において、第１のパーティションは、第２のパーティションのノードのヒストグラムに基づいて、第２のパーティションの一組のノードの候補パーティションとして選択されるようになっていてもよい。一実施形態において、ブロック５０６および５０８は、図２の候補パーティション選択モジュール２０３により実行されるようになっていてもよい。候補パーティションは、エッジ局所性の改善に基づいて選択されるようになっていてもよい。一実施形態において、候補パーティションは、エッジ局所性のゲインに関する確率に基づいて選択されるようになっていてもよい。たとえば、候補パーティションは、エッジ局所性がより大きく増大するパーティションに対するバイアスを有する確率アルゴリズムに基づいて選択されるようになっていてもよい。一実施形態においては、パーティションが候補パーティションとして適格となるようにしきい値を満たすかまたは超過するゲインとなる必要がある局所性ゲインしきい値が実装されるようになっていてもよい。パーティションのノードの候補パーティションの選択には、ノードグラフのノードと関連付けられた１つ、多数、またはすべてのパーティションが関与していてもよい。
【００８０】
ブロック５１０においては、パーティションの負荷平衡に基づいて、第１のパーティションの一組のノードの少なくとも一部が第２のパーティションに再マッピングされるとともに、第２のパーティションの一組のノードの少なくとも一部が第１のパーティションに再マッピングされるようになっていてもよい。さらに、ノードの再マッピングによる負荷平衡は、ノードグラフのノードと関連付けられたすべてのパーティションの一部または全部の組み合わせに適用可能である。一実施形態において、ブロック５１０は、図４の平衡再マッピング・モジュール１０２により実行されるようになっていてもよい。ノード重みを考慮しない一実施形態において、一方のパーティションから再マッピングされるノードの総数は、他方のパーティションから再マッピングされるノードの総数と同じであってもよい。ノード重みを考慮する一実施形態において、一方のパーティションから再マッピングされるノードの総重みは、他方のパーティションから再マッピングされるノードの総重みと同じであってもよい。非分散システムがマッピングを最適化する一実施形態においては、最も高いゲインと関連付けられたノードがまず、再マッピング対象として選択されるように、ノードがゲインに基づいて再マッピングされるようになっていてもよい。一実施形態において、ノードの再マッピングは、ノードの重みに基づいていてもよい。分散システムがマッピングを最適化する一実施形態においては、平衡を維持するために各パーティションに再マッピングすべきノードの数をマスター・コンピュータ・システムが決定した後、該パーティションが存在して再マッピングを実行するコンピュータ・システムにその数を伝達するようにしてもよい。
【００８１】
ソーシャルネットワーキング・システム例示的な実施態様
図６は、本発明の一実施形態に係る、ソーシャル・ネットワーク内のビデオリンクの代わりとなる例示的なシステム６００のネットワーク図である。システム６００は、１つまたは複数のユーザ機器６１０、１つまたは複数の外部システム６２０、ソーシャルネットワーキング・システム６３０、およびネットワーク６５０を具備する。一実施形態において、上述の実施形態と関連して説明したソーシャルネットワーキング・システムは、ソーシャルネットワーキング・システム６３０として実装されていてもよい。説明の便宜上、図６に示すシステム６００の実施形態には、単一の外部システム６２０および単一のユーザ機器６１０を含む。ただし、他の実施形態において、システム６００は、より多くのユーザ機器６１０およびより多くの外部システム６２０の両方または一方を具備していてもよい。特定の実施形態においては、ソーシャルネットワーキング・システム６３０がソーシャル・ネットワーク・プロバイダにより運用されるのに対して、外部システム６２０は、異なるエンティティにより運用可能である点において、ソーシャルネットワーキング・システム６３０から分離されている。ただし、種々実施形態において、ソーシャルネットワーキング・システム６３０および外部システム６２０は、協調して動作することにより、ソーシャルネットワーキング・システム６３０のユーザ（メンバー）にソーシャルネットワーキングサービスを提供する。この意味において、ソーシャルネットワーキング・システム６３０は、プラットフォームまたはバックボーンを提供し、これを外部システム６２０等の他のシステムが利用して、インターネット全体でユーザにソーシャルネットワーキングサービスおよび機能を提供するようにしてもよい。
【００８２】
ユーザ機器６１０は、ユーザからの入力を受け付けるとともにネットワーク６５０を介してデータを送受信可能な１つまたは複数のコンピュータ機器を備える。一実施形態において、ユーザ機器６１０は、たとえばＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ互換オペレーティング・システム（ＯＳ）、Ａｐｐｌｅ  ＯＳ  Ｘ、および／またはＬｉｎｕｘディストリビューションを実行する従来のコンピュータ・システムである。別の実施形態において、ユーザ機器６１０としては、スマートフォン、タブレット、携帯情報端末（ＰＤＡ：Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、携帯電話等、コンピュータ機能を有する機器が可能である。ユーザ機器６１０は、ネットワーク６５０を介して通信を行うように構成されている。また、ユーザ機器６１０は、該ユーザ機器６１０のユーザによるソーシャルネットワーキング・システム６３０との相互作用を可能にするブラウザ・アプリケーション等のアプリケーションを実行可能である。別の実施形態において、ユーザ機器６１０は、ｉＯＳおよびＡＮＤＲＯＩＤ等、ユーザ機器６１０のネイティブオペレーティング・システムが提供するアプリケーション・プログラミング・インタフェース（ＡＰＩ）を通して、ソーシャルネットワーキング・システム６３０と相互作用する。ユーザ機器６１０は、有線通信システムおよび無線通信システムの両方または一方を用いることにより、ローカル・エリア・ネットワークおよびワイド・エリア・ネットワークの両方または一方の任意の組み合わせを含み得るネットワーク６５０を介して、外部システム６２０およびソーシャルネットワーキング・システム６３０と通信するように構成されている。
【００８３】
一実施形態において、ネットワーク６５０は、標準的な通信技術およびプロトコルを使用する。このため、ネットワーク６５０には、イーサネット、８０２．１１、ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）、３Ｇ、４Ｇ、ＣＤＭＡ（Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）、ＧＳＭ（Ｇｌｏｂａｌ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）、ＬＴＥ（Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）、デジタル・サブスクライバ・ライン（ＤＳＬ）等の技術を用いたリンクを含み得る。同様に、ネットワーク６５０で用いられるネットワーキング・プロトコルとしては、マルチ・プロトコル・ラベル・スイッチング（ＭＰＬＳ）、伝送制御プロトコル／インターネット・プロトコル（ＴＣＰ／ＩＰ：Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）、ユーザ・データグラム・プロトコル（ＵＤＰ）、ハイパー・テキスト転送プロトコル（ＨＴＴＰ：Ｈｙｐｅｒｔｅｘｔ  Ｔｒａｎｓｐｏｒｔ  Ｐｒｏｔｏｃｏｌ）、簡易メール転送プロトコル（ＳＭＴＰ：Ｓｉｍｐｌｅ  Ｍａｉｌ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）、ファイル転送プロトコル（ＦＴＰ：Ｆｉｌｅ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）等が挙げられる。ネットワーク６５０上で交換されるデータは、ハイパー・テキスト・マークアップ言語（ＨＴＭＬ：Ｈｙｐｅｒｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）および拡張マークアップ言語（ＸＭＬ：Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）を含む技術およびフォーマットまたは技術もしくはフォーマットを用いて表すことができる。また、全部または一部のリンクは、セキュアソケットレイヤ（ＳＳＬ：Ｓｅｃｕｒｅ  Ｓｏｃｋｅｔｓ  Ｌａｙｅｒ）、トランスポートレイヤセキュリティ（ＴＬＳ：Ｔｒａｎｓｐｏｒｔ  Ｌａｙｅｒ  Ｓｅｃｕｒｉｔｙ）、およびインターネット・プロトコル・セキュリティ（Ｉｐｓｅｃ：Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｓｅｃｕｒｉｔｙ）等の従来の暗号化技術を用いて暗号化可能である。
【００８４】
一実施形態において、ユーザ機器６１０は、外部システム６２０およびソーシャルネットワーキング・システム６３０から受信したマークアップ言語ドキュメント（markup language document）６１４をブラウザ・アプリケーション６１２で処理することにより、外部システム６２０およびソーシャルネットワーキング・システム６３０または外部システム６２０もしくはソーシャルネットワーキング・システム６３０からのコンテンツを表示するようにしてもよい。マークアップ言語ドキュメント６１４は、コンテンツおよび該コンテンツの書式設定または体裁を記述した１つまたは複数の命令を識別する。マークアップ言語ドキュメント６１４に含まれる命令を実行することにより、ブラウザ・アプリケーション６１２は、マークアップ言語ドキュメント６１４により記述されたフォーマットまたは体裁で識別コンテンツを表示する。たとえば、マークアップ言語ドキュメント６１４には、外部システム６２０およびソーシャルネットワーキング・システム６３０から読み出されたテキストおよび画像データまたはテキストもしくは画像データを含む複数のフレームを有するウェブページを生成および表示する命令を含む。種々実施形態において、マークアップ言語ドキュメント６１４は、拡張マークアップ言語（ＸＭＬ）データ、拡張ハイパー・テキスト・マークアップ言語（ＸＨＴＭＬ：Ｅｘｔｅｎｓｉｂｌｅ  Ｈｙｐｅｒｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）データ等のマークアップ言語データを含むデータ・ファイルを備える。また、マークアップ言語ドキュメント６１４は、ＪＳＯＮ（ＪａｖａＳｃｒｉｐｔ  Ｏｂｊｅｃｔ  Ｎｏｔａｔｉｏｎ）データ、ＪＳＯＮＰ（ＪＳＯＮ  ｗｉｔｈ  ｐａｄｄｉｎｇ）、およびＪａｖａＳｃｒｉｐｔデータを含むことにより、外部システム６２０とユーザ機器６１０との間のデータ交換を容易化するようにしてもよい。ユーザ機器６１０上のブラウザ・アプリケーション６１２は、ＪａｖａＳｃｒｉｐｔコンパイラを用いて、マークアップ言語ドキュメント６１４を復号化するようにしてもよい。
【００８５】
また、マークアップ言語ドキュメント６１４は、ＦＬＡＳＨ（商標）またはＵｎｉｔｙ（商標）アプリケーション、ＳｉｌｖｅｒＬｉｇｈｔ（商標）アプリケーション・フレームワーク等のアプリケーションまたはアプリケーション・フレームワークを含んでいてもよいし、これらとリンクしていてもよい。
【００８６】
また、一実施形態において、ユーザ機器６１０は、該ユーザ機器６１０のユーザがソーシャルネットワーキング・システム６３０にログインしたか否かを示すデータを含む１つまたは複数のクッキー６１６を含むことにより、ソーシャルネットワーキング・システム６３０からユーザ機器６１０に伝達されたデータの変更ができるようになっていてもよい。
【００８７】
外部システム６２０は、ネットワーク６５０を用いてユーザ機器６１０に伝達される１つまたは複数のウェブページ６２２ａ、６２２ｂを含む１つまたは複数のウェブ・サーバを具備する。また、外部システム６２０は、ソーシャルネットワーキング・システム６３０から分離されている。たとえば、外部システム６２０が第１のドメインと関連付けられる一方、ソーシャルネットワーキング・システム６３０は、別個のソーシャルネットワーキングドメインと関連付けられている。外部システム６２０に含まれるウェブページ６２２ａ、６２２ｂは、コンテンツを識別するとともに該識別コンテンツの書式設定または体裁を指定する命令を含むマークアップ言語ドキュメント６１４を含む。
【００８８】
ソーシャルネットワーキング・システム６３０は、複数のユーザを含み、ソーシャル・ネットワークのユーザに対して該ソーシャル・ネットワークの他のユーザと通信および相互作用する能力を提供する、該ソーシャル・ネットワーク用の１つまたは複数のコンピュータ機器を具備する。場合によっては、グラフ、すなわちエッジおよびノードを含むデータ構造により、ソーシャル・ネットワークを表すことができる。ソーシャル・ネットワークは、データベース、オブジェクト、クラス、メタ要素、ファイル、またはその他任意のデータ構造等、他のデータ構造を用いて表すこともできるが、これらに限定されない。ソーシャルネットワーキング・システム６３０は、オペレータにより運営、管理、または制御されるようになっていてもよい。ソーシャルネットワーキング・システム６３０のオペレータは、人間、自動化アプリケーション、またはコンテンツの管理、ポリシーの調整、ソーシャルネットワーキング・システム６３０内の利用状況総計値の収集を行う一連のアプリケーションであってもよい。オペレータは、任意の種類が用いられるようになっていてもよい。
【００８９】
ユーザは、ソーシャルネットワーキング・システム６３０に参加した後、ソーシャルネットワーキング・システム６３０のつながりたい任意数の他ユーザとのつながりを追加するようにしてもよい。本明細書において、用語「友達」は、ユーザがソーシャルネットワーキング・システム６３０を介して、つながり、関連性、または関係を形成した、ソーシャルネットワーキング・システム６３０のその他任意のユーザを表す。たとえば、一実施形態において、ソーシャルネットワーキング・システム６３０のユーザがソーシャルグラフのノードとして表される場合、用語「友達」は、２つのユーザ・ノード間に形成され、これら２つのユーザ・ノードを直接つなげるエッジを表し得る。
【００９０】
つながりは、ユーザ（たとえば、同じ教育機関の同窓生であるユーザ）の共通特性に基づいて、ユーザが明示的に追加してもよいし、ソーシャルネットワーキング・システム６３０が自動的に作成するようにしてもよい。たとえば、第１のユーザは、友達となる特定の他ユーザを具体的に選択する。ソーシャルネットワーキング・システム６３０におけるつながりは通例、両方向であるが、これは必須ではないため、用語「ユーザ」および「友達」は、枠組みによって決まる。ソーシャルネットワーキング・システム６３０のユーザ間のつながりは通例、双方向（「２方向」）すなわち「相互」であるが、単方向すなわち「１方向」であってもよい。たとえば、ボブ（Ｂｏｂ）およびジョー（Ｊｏｅ）がともにソーシャルネットワーキング・システム６３０のユーザであり、互いにつながっている場合、ボブおよびジョーは、互いのつながりである。一方、ボブがジョーとつながって、ジョーによりソーシャルネットワーキング・システム６３０に伝達されたデータを見たいものの、ジョーが相互のつながりを形成したくない場合は、単方向のつながりが確立されるようになっていてもよい。ユーザ間のつながりは、直接的なつながりであってもよい。ただし、ソーシャルネットワーキング・システム６３０のいくつかの実施形態によれば、つながりは、１つまたは複数のつながりレベルまたは分離度によって、間接的にすることができる。
【００９１】
ユーザ間のつながりの確立および維持ならびにユーザ間の相互作用の許可に加えて、ソーシャルネットワーキング・システム６３０は、該ソーシャルネットワーキング・システム６３０によりサポートされたさまざまな種類の項目に対するアクションをユーザが起こせるようにする。これらの項目には、ソーシャルネットワーキング・システム６３０のユーザが属し得るグループまたはネットワーク（すなわち、人々、エンティティ、およびコンセプトのソーシャル・ネットワーク）、ユーザが関心を示す可能性があるイベントまたはカレンダ・エントリ、ユーザがソーシャルネットワーキング・システム６３０を介して使用可能なコンピュータ・ベースのアプリケーション、ソーシャルネットワーキング・システム６３０が提供するサービスまたはソーシャルネットワーキング・システム６３０を通してユーザがアイテムの売買を行えるトランザクション、およびユーザがソーシャルネットワーキング・システム６３０上またはソーシャルネットワーキング・システム６３０外で実行可能な広告との相互作用、を含んでいてもよい。これらは、ユーザがソーシャルネットワーキング・システム６３０上で行うことができる項目のわずかな例に過ぎず、その他多くが可能である。ユーザは、ソーシャルネットワーキング・システム６３０もしくは外部システム６２０にて表し得るあらゆるもの、ソーシャルネットワーキング・システム６３０とは別個のあらゆるもの、またはネットワーク６５０を介してソーシャルネットワーキング・システム６３０に結合されたあらゆるものと相互作用可能である。
【００９２】
また、ソーシャルネットワーキング・システム６３０は、多様なエンティティをリンク可能である。たとえば、ソーシャルネットワーキング・システム６３０は、ＡＰＩ、ウェブサービス、または他の通信チャンネルを通して、ユーザの互いの相互作用および外部システム６２０または他のエンティティとの相互作用を可能にする。ソーシャルネットワーキング・システム６３０は、複数のエッジにより相互につなげられた複数のノードを含む「ソーシャルグラフ」を生成して保持する。ソーシャルグラフの各ノードは、別のノードに作用可能なエンティティおよび別のノードが作用し得るエンティティの両方または一方を表していてもよい。ソーシャルグラフは、さまざまな種類のノードを含んでいてもよい。ノードの種類の例としては、ユーザ、人間以外のエンティティ、コンテンツ項目、ウェブページ、グループ、アクティビティ、メッセージ、コンセプト、およびソーシャルネットワーキング・システム６３０のオブジェクトにより表し得るその他任意の事物が挙げられる。ソーシャルグラフの２つのノード間のエッジは、ノード関係または一方のノードが他方のノードに対して行ったアクションに由来し得る２つのノード間の特定種類のつながりすなわち関連性を表していてもよい。場合により、ノード間のエッジは、重み付け可能である。エッジの重みは、ノード間のつながりすなわち関連性の強度等、エッジと関連付けられた属性を表し得る。エッジの種類が異なれば、異なる重みが可能である。たとえば、あるユーザが別のユーザに「いいね！」をした場合に作成されるエッジにある重みが与えられる一方、ユーザが別のユーザと友達になった場合に作成されるエッジには、異なる重みが与えられるようになっていてもよい。
【００９３】
一例として、第１のユーザが第２のユーザを友達として識別した場合は、第１のユーザを表すノードと第２のユーザを表す第２のノードとをつなげるソーシャルグラフのエッジが生成される。さまざまなノードが互いに関連または相互作用すると、ソーシャルネットワーキング・システム６３０は、該さまざまなノードをつなげるエッジを修正して、上記関係および相互作用を反映する。
【００９４】
また、ソーシャルネットワーキング・システム６３０は、該ソーシャルネットワーキング・システム６３０とのユーザの相互作用を増進させるユーザ生成コンテンツを含む。ユーザ生成コンテンツには、ユーザがソーシャルネットワーキング・システム６３０に追加、アップロード、送信、または「投稿」可能なあらゆるものを含み得る。たとえば、ユーザは、ユーザ機器６１０からソーシャルネットワーキング・システム６３０に投稿を伝達する。投稿には、近況等の文字情報、ロケーション情報、写真等の画像、映像、リンク、音楽、またはその他類似のデータおよび媒体またはデータもしくは媒体等のデータを含んでいてもよい。また、コンテンツは、第三者によってソーシャルネットワーキング・システム６３０に追加されるようになっていてもよい。コンテンツ「項目」は、ソーシャルネットワーキング・システム６３０のオブジェクトとして表される。このように、ソーシャルネットワーキング・システム６３０のユーザは、さまざまな通信チャンネルを通して、さまざまな種類の媒体の文字およびコンテンツ項目を投稿することにより、互いの通信が促される。このようなコミュニケーションでは、ユーザの互いの相互作用が増大するとともに、ユーザがソーシャルネットワーキング・システム６３０と相互作用する頻度が高くなる。
【００９５】
ソーシャルネットワーキング・システム６３０は、ウェブ・サーバ６３２、ＡＰＩ要求サーバ６３４、ユーザプロフィール・ストア６３６、つながりストア６３８、アクション・ロガー６４０、アクティビティ・ログ６４２、承認サーバ６４４、および最適化モジュール６４６を具備する。本発明の一実施形態において、ソーシャルネットワーキング・システム６３０は、さまざまなアプリケーションを対象として、追加の構成要素、より少ない構成要素、または異なる構成要素を具備していてもよい。ネットワーク・インタフェース、セキュリティ・メカニズム、ロード・バランサ、フェイルオーバ・サーバ、管理・ネットワーク運用コンソール等の他の構成要素については、システムの細部が分かり難くならないように、図示していない。
【００９６】
ユーザプロフィール・ストア６３６は、略歴、人口統計学的情報、およびユーザによる申告またはソーシャルネットワーキング・システム６３０による推察が行われた職歴、学歴、趣味または好み、ロケーション等の他の種類の記述的情報等、ユーザアカウントに関する情報を保持する。この情報は、各ユーザが一意に識別されるように、ユーザプロフィール・ストア６３６に格納される。また、ソーシャルネットワーキング・システム６３０は、異なるユーザ間の１つまたは複数のつながりを記述したデータをつながりストア６３８に格納する。つながり情報は、職歴、グループ・メンバーシップ、趣味、または学歴が類似または共通するユーザを示していてもよい。また、ソーシャルネットワーキング・システム６３０には、ユーザによる他ユーザとの関係の指定を可能にする異なるユーザ間のユーザ定義のつながりを含む。たとえば、ユーザ定義のつながりによれば、ユーザは、友達、同僚、パートナー等、ユーザの実生活の関係と似た他ユーザとの関係を生成可能である。ユーザは、所定の種類のつながりから選択を行うようにしてもよいし、必要に応じて、自身のつながりの種類を規定するようにしてもよい。人間以外のエンティティ、バケット、クラスタセンタ、画像、関心、ページ、外部システム、コンセプト等、ソーシャルネットワーキング・システム６３０の他のノードとのつながりについても、つながりストア６３８に格納される。
【００９７】
ソーシャルネットワーキング・システム６３０は、ユーザが相互作用可能なオブジェクトに関するデータを保持する。このデータを保持するため、ユーザプロフィール・ストア６３６およびつながりストア６３８は、ソーシャルネットワーキング・システム６３０により保持された対応する種類のオブジェクトのインスタンスを格納する。各オブジェクト種類は、オブジェクトの種類に相応しい情報を格納するのに適した情報フィールドを有する。たとえば、ユーザプロフィール・ストア６３６は、ユーザのアカウントおよびユーザのアカウントに関する情報の記述に適したフィールドを備えたデータ構造を含む。特定種類の新たなオブジェクトが作成された場合、ソーシャルネットワーキング・システム６３０は、対応する種類の新たなデータ構造を初期化し、一意のオブジェクト識別子を割り当てるとともに、必要に応じて、オブジェクトへのデータの追加を開始する。これは、たとえばユーザがソーシャルネットワーキング・システム６３０のユーザとなり、ソーシャルネットワーキング・システム６３０がユーザプロフィール・ストア６３６のユーザ・プロフィールの新たなインスタンスを生成し、一意の識別子をユーザアカウントに割り当て、ユーザが提供する情報のユーザアカウントのフィールドへの入力を開始した場合に起こる可能性がある。
【００９８】
つながりストア６３８には、ユーザの他ユーザとのつながり、外部システム６２０とのつながり、または他のエンティティとのつながりを記述するのに適したデータ構造を含む。また、つながりストア６３８は、ユーザに関する情報へのアクセスを調整するユーザのプライバシー設定と併せて使用可能なユーザのつながりに対して、つながりの種類を関連付けるようにしてもよい。本発明の一実施形態において、ユーザプロフィール・ストア６３６およびつながりストア６３８は、連合データベースとして実装されていてもよい。
【００９９】
つながりストア６３８、ユーザプロフィール・ストア６３６、およびアクティビティ・ログ６４２に格納されたデータによれば、ソーシャルネットワーキング・システム６３０は、ノードを用いてさまざまなオブジェクトを識別するとともに、ノードをつなげるエッジを用いて異なるオブジェクト間の関係を識別するソーシャルグラフを生成することができる。たとえば、ソーシャルネットワーキング・システム６３０において、第１のユーザが第２のユーザとのつながりを確立した場合は、ユーザプロフィール・ストア６３６からの第１のユーザおよび第２のユーザのユーザアカウントがソーシャルグラフのノードとして作用するようになっていてもよい。つながりストア６３８が格納する第１のユーザと第２のユーザとの間のつながりは、第１のユーザおよび第２のユーザと関連付けられたノード間のエッジである。この例を続けて、第２のユーザは、ソーシャルネットワーキング・システム６３０において、第１のユーザにメッセージを送信するようにしてもよい。格納可能なメッセージを送信するアクションは、第１のユーザおよび第２のユーザを表すソーシャルグラフの２つのノード間の別のエッジである。また、メッセージ自体は、第１のユーザおよび第２のユーザを表すノードとつながった別のノードとして、ソーシャルグラフにおいて識別されるとともに含まれていてもよい。
【０１００】
別の例において、第１のユーザは、ソーシャルネットワーキング・システム６３０により保持された画像（または、ソーシャルネットワーキング・システム６３０の外部の別のシステムにより保持された画像）において、第２のユーザにタグを付けるようにしてもよい。画像自体は、ソーシャルネットワーキング・システム６３０のノードとして表されていてもよい。このタグ付けアクションによって、第１のユーザと第２のユーザとの間にエッジを作成するとともに、ユーザそれぞれと画像（これもソーシャルグラフのノードである）との間にエッジを作成するようにしてもよい。さらに別の例において、ユーザがイベントへの出席を確認した場合は、ユーザおよびイベントは、ユーザプロフィール・ストア６３６から得られるノードであり、イベントへの出席は、アクティビティ・ログ６４２から読み出し可能なノード間のエッジである。ソーシャルグラフを生成して保持することにより、ソーシャルネットワーキング・システム６３０は、さまざまな種類のオブジェクトならびにこれらオブジェクト間の相互作用およびつながりを記述したデータを含み、社会的な関連情報の宝庫（rich source）となる。
【０１０１】
ウェブ・サーバ６３２は、ネットワーク６５０を介して、ソーシャルネットワーキング・システム６３０を１つもしくは複数のユーザ機器６１０および１つもしくは複数の外部システム６２０の両方または一方にリンクさせる。また、ウェブ・サーバ６３２は、ウェブページのほか、Ｊａｖａ、ＪａｖａＳｃｒｉｐｔ、Ｆｌａｓｈ、ＸＭＬ等の他のウェブ関連コンテンツを提供する。ウェブ・サーバ６３２は、ソーシャルネットワーキング・システム６３０と１つまたは複数のユーザ機器６１０との間でメッセージの受信およびルーティングを行うメール・サーバ等のメッセージング機能を含んでいてもよい。メッセージとしては、インスタントメッセージ、待ち行列型メッセージ（たとえば、電子メール）、テキストおよびＳＭＳメッセージ、またはその他任意の適当なメッセージングフォーマットが可能である。
【０１０２】
ＡＰＩ要求サーバ６３４によれば、１つまたは複数の外部システム６２０およびユーザ機器６１０は、１つまたは複数のＡＰＩ機能を呼び出すことによって、ソーシャルネットワーキング・システム６３０からのアクセス情報を呼び出すことができる。また、ＡＰＩ要求サーバ６３４によれば、外部システム６２０は、ＡＰＩを呼び出すことによって、ソーシャルネットワーキング・システム６３０に情報を送ることができる。一実施形態において、外部システム６２０は、ネットワーク６５０を介して、ＡＰＩ要求をソーシャルネットワーキング・システム６３０に送信し、ＡＰＩ要求サーバ６３４は、このＡＰＩ要求を受信する。ＡＰＩ要求サーバ６３４は、このＡＰＩ要求と関連付けられたＡＰＩを呼び出して要求を処理することにより、適当な応答を生成し、これをＡＰＩ要求サーバ６３４が、ネットワーク６５０を介して外部システム６２０に伝達する。たとえば、ＡＰＩ要求に応答して、ＡＰＩ要求サーバ６３４は、外部システム６２０にログインしたユーザのつながり等、ユーザと関連付けられたデータを収集し、この収集データを外部システム６２０に伝達する。別の実施形態において、ユーザ機器６１０は、外部システム６２０と同じ様態で、ＡＰＩを介してソーシャルネットワーキング・システム６３０と通信する。
【０１０３】
アクション・ロガー６４０は、ソーシャルネットワーキング・システム６３０上およびソーシャルネットワーキング・システム６３０外でのユーザ・アクションまたはソーシャルネットワーキング・システム６３０上もしくはソーシャルネットワーキング・システム６３０外でのユーザ・アクションに関するウェブ・サーバ６３２からの通信を受信可能である。また、アクション・ロガー６４０は、ユーザ・アクションに関する情報をアクティビティ・ログ６４２に入力することによって、ソーシャルネットワーキング・システム６３０のユーザが該ソーシャルネットワーキング・システム６３０内外で起こしたさまざまなアクションを該ソーシャルネットワーキング・システム６３０が発見できるようにする。ソーシャルネットワーキング・システム６３０上の別のノードに関して特定のユーザが起こした如何なるアクションも、アクティビティ・ログ６４２または類似のデータベース等のデータ・リポジトリ（data repository）に保持された情報によって、各ユーザのアカウントと関連付け可能である。ソーシャルネットワーキング・システム６３０においてユーザが起こす識別および格納対象のアクションの例としては、たとえば別のユーザへのつながりの追加、別のユーザへのメッセージの送信、別のユーザからのメッセージを読むこと、別のユーザと関連付けられたコンテンツの閲覧、別のユーザが投稿したイベントへの出席、画像の投稿、画像の投稿の試行、または別のユーザもしくは別のオブジェクトと相互作用するその他のアクションが挙げられる。ユーザがソーシャルネットワーキング・システム６３０においてアクションを起こすと、該アクションがアクティビティ・ログ６４２に記録される。一実施形態において、ソーシャルネットワーキング・システム６３０は、エントリのデータベースとしてアクティビティ・ログ６４２を維持する。ソーシャルネットワーキング・システム６３０においてアクションが起こされると、該アクションのエントリがアクティビティ・ログ６４２に追加される。アクティビティ・ログ６４２は、アクション・ログと称する場合もある。
【０１０４】
また、ユーザ・アクションは、ソーシャルネットワーキング・システム６３０とは別個の外部システム６２０等、ソーシャルネットワーキング・システム６３０の外部のエンティティ内で起こるコンセプトおよびアクションと関連付けられていてもよい。たとえば、アクション・ロガー６４０は、外部システム６２０とのユーザの相互作用を記述したデータをウェブ・サーバ６３２から受信するようにしてもよい。この例において、外部システム６２０は、ソーシャルグラフの構造化されたアクションおよびオブジェクトに従って、ユーザの相互作用を報告する。
【０１０５】
ユーザが外部システム６２０と相互作用するアクションの他の例としては、外部システム６２０または別のエンティティに対する関心をユーザが示すこと、外部システム６２０または外部システム６２０内のウェブページ６２２ａに関するコメントをユーザがソーシャルネットワーキング・システム６３０に投稿すること、ユニフォーム・リソース・ロケータ（ＵＲＬ）または外部システム６２０と関連付けられた他の識別子をユーザがソーシャルネットワーキング・システム６３０に投稿すること、外部システム６２０と関連付けられたイベントにユーザが出席すること、または外部システム６２０に関するユーザによるその他任意のアクションが挙げられる。このように、アクティビティ・ログ６４２には、ソーシャルネットワーキング・システム６３０のユーザとソーシャルネットワーキング・システム６３０とは別個の外部システム６２０との間の相互作用を記述したアクションを含んでいてもよい。
【０１０６】
承認サーバ６４４は、ソーシャルネットワーキング・システム６３０のユーザの１つまたは複数のプライバシー設定を実施する。ユーザのプライバシー設定は、ユーザと関連付けられた特定の情報がどのように共有可能であるかを決定する。プライバシー設定には、ユーザと関連付けられた特定の情報の仕様、および情報を共有可能な１つまたは複数のエンティティの仕様を含む。情報を共有可能なエンティティの例としては、他のユーザ、アプリケーション、外部システム６２０、または潜在的に情報にアクセス可能な任意のエンティティが挙げられる。ユーザが共有可能な情報には、プロフィール写真、ユーザと関連付けられた電話番号、ユーザのつながり、つながりの追加やユーザ・プロフィール情報の変更等、ユーザが起こしたアクション等のユーザアカウント情報を含む。
【０１０７】
プライバシー設定の仕様は、さまざまな粒度レベル（different levels of granularity）で提供されていてもよい。たとえば、プライバシー設定は、他のユーザと共有される特定の情報を識別していてもよく、勤務先の電話番号またはプロフィール写真、自宅の電話番号、およびステータスを含む個人情報等の特定の関連情報集合を識別する。または、プライバシー設定は、ユーザと関連付けられたすべての情報に適用可能である。特定の情報にアクセス可能なエンティティ集合の仕様についても、さまざまな粒度レベルで指定可能である。情報を共有できるさまざまなエンティティ集合としては、たとえばユーザのすべての友達、友達のすべての友達、すべてのアプリケーション、またはすべての外部システム６２０が挙げられる。一実施形態によれば、エンティティ集合の仕様には、エンティティ一覧を含むことができる。たとえば、ユーザは、特定の情報へのアクセスが許可された外部システム６２０の一覧を提供するようにしてもよい。別の実施形態によれば、仕様には、情報へのアクセスが許可されていない例外と併せてエンティティ集合を含むことができる。たとえば、ユーザは、その勤務先情報にすべての外部システム６２０がアクセスすることを許可するが、該勤務先情報へのアクセスが許可されていない外部システム６２０の一覧を指定するようにしてもよい。特定の実施形態では、特定の情報へのアクセスが許可されていない例外の一覧を「ブロックリスト（block list）」と称する。ユーザが指定するブロックリストに属する外部システム６２０は、プライバシー設定に指定された情報へのアクセスがブロックされる。情報の仕様の粒度および情報が共有されるエンティティの仕様の粒度は、さまざまな組み合わせが可能である。たとえば、すべての個人情報が友達と共有される一方、すべての勤務先情報が友達の友達と共有されるようになっていてもよい。
【０１０８】
承認サーバ６４４は、ユーザと関連付けられた特定の情報にユーザの友達、外部システム６２０、ならびに／または他のアプリケーションおよびエンティティがアクセス可能であるか否かを判定するロジックを含む。外部システム６２０は、ユーザの勤務先の電話番号等、ユーザのより私的かつ繊細な情報にアクセスするため、承認サーバ６４４の承認が必要となる場合がある。ユーザのプライバシー設定に基づいて、承認サーバ６４４は、ユーザが起こすアクションに関する情報等、ユーザと関連付けられた情報に対して、別のユーザ、外部システム６２０、アプリケーション、または別のエンティティがアクセス可能であるか否かを判定する。
【０１０９】
最適化モジュール６４６は、ソーシャルネットワーキング・システム６３０に関するソーシャルグラフのノードの現在のマッピングを最適化するようにしてもよい。また、最適化モジュール６４６は、負荷平衡を維持しつつエッジ局所性を改善するように、現在のマッピングを最適化するようにしてもよい。一実施形態において、最適化モジュール６４６は、図１の最適化モジュール１００として実装されていてもよい。
ハードウェアの実施態様
上記プロセスおよび特徴は、多種多様なネットワークおよびコンピュータ環境において、多種多様なマシンおよびコンピュータ・システムアーキテクチャにより実装可能である。図７は、本発明の一実施形態に係る、本明細書に記載の実施形態のうちの１つまたは複数の実装に使用可能なコンピュータ・システム７００の一例を示している。コンピュータ・システム７００には、本明細書に記載のプロセスおよび特徴を該コンピュータ・システム７００に実行させる命令セットを含む。また、コンピュータ・システム７００は、他のマシンにつなげられていてもよい（たとえば、ネットワーク化されていてもよい）。ネットワーク配置において、コンピュータ・システム７００は、クライアント／サーバ・ネットワーク環境におけるサーバ・マシンもしくはクライアント・マシンまたはピア・ツー・ピア（または、分散）ネットワーク環境におけるピアマシン（peer machine）として動作するようになっていてもよい。本発明の一実施形態において、コンピュータ・システム７００は、本明細書に記載のソーシャルネットワーキング・システムの構成要素であってもよい。本発明の一実施形態において、コンピュータ・システム７００は、ソーシャルネットワーキング・システム６３０の全部または一部を構成する多くのサーバのうちの１つであってもよい。
【０１１０】
コンピュータ・システム７００は、プロセッサ７０２、キャッシュ７０４、ならびにコンピュータ可読媒体に格納され、本明細書に記載のプロセスおよび特徴を対象とした１つまたは複数の実行可能なモジュールおよびドライバを具備する。また、コンピュータ・システム７００は、高性能入出力（Ｉ／Ｏ）バス７０６および標準Ｉ／Ｏバス７０８を具備する。ホスト・ブリッジ７１０がプロセッサ７０２を高性能Ｉ／Ｏバス７０６に結合させる一方、Ｉ／Ｏバス・ブリッジ７１２が２つのバス７０６および７０８を互いに結合させる。高性能Ｉ／Ｏバス７０６には、システム・メモリ７１４および１つまたは複数のネットワーク・インタフェース７１６が結合されている。コンピュータ・システム７００は、ビデオメモリおよび該ビデオメモリに結合された表示装置をさらに具備していてもよい（図示せず）。標準Ｉ／Ｏバス７０８には、マス・ストレージ７１８およびＩ／Ｏポート７２０が結合されている。コンピュータ・システム７００は、任意選択として、標準Ｉ／Ｏバス７０８に結合されたキーボードおよびポインティング・デバイス、表示装置等の入出力装置（図示せず）を具備していてもよい。これらの要素は総じて、カリフォルニア州サンタクララのインテル・コーポレーション社（Ｉｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎ）が製造するｘ８６互換プロセッサ、カリフォルニア州サニーベールのアドバンスト・マイクロ・デバイセズ（ＡＭＤ）社（Ａｄｖａｎｃｅｄ  Ｍｉｃｒｏ  Ｄｅｖｉｃｅｓ  （ＡＭＤ），Ｉｎｃ．）が製造するｘ８６互換プロセッサ、およびその他任意の適当なプロセッサに基づくコンピュータ・システム等、広範囲のコンピュータ・ハードウェア・システムを表すことを意図しているが、これらに限定されない。
【０１１１】
ソフトウェア・アプリケーション（図示せず）に対するデータの入出力等、コンピュータ・システム７００の動作は、オペレーティング・システムが管理および制御する。オペレーティング・システムは、システム上で実行されるソフトウェア・アプリケーションとシステムのハードウェア構成要素との間のインタフェースを提供する。ＬＩＮＵＸオペレーティング・システム、カリフォルニア州クパチーノのアップル・コンピュータ・インコーポレイテッド社（Ａｐｐｌｅ  Ｃｏｍｐｕｔｅｒ  Ｉｎｃ．）から入手可能なＡｐｐｌｅ  Ｍａｃｉｎｔｏｓｈオペレーティング・システム、ＵＮＩＸオペレーティング・システム、Ｍｉｃｒｏｓｏｆｔ（登録商標）  Ｗｉｎｄｏｗｓ（登録商標）オペレーティング・システム、ＢＳＤオペレーティング・システム等、任意適当なオペレーティング・システムを使用可能である。また、他の実施態様も可能である。
【０１１２】
以下、コンピュータ・システム７００の要素について、より詳しく説明する。特に、ネットワーク・インタフェース７１６は、コンピュータ・システム７００とイーサネット（たとえば、ＩＥＥＥ  ８０２．３）ネットワーク、バックプレーン等の広範なネットワークのいずれかとの間の通信を提供する。マス・ストレージ７１８は、上記識別された各演算システムにより実装される上記プロセスおよび特徴を実行するデータおよびプログラミング命令の格納を提供する。一方、システム・メモリ７１４（たとえば、ＤＲＡＭ）は、プロセッサ７０２により実行される場合のデータおよびプログラミング命令の一時的な格納を提供する。Ｉ／Ｏポート７２０は、コンピュータ・システム７００に結合し得る付加的な周辺機器間の通信を提供する１つもしくは複数のシリアル通信ポートおよびパラレル通信ポートまたは１つもしくは複数のシリアル通信ポートもしくはパラレル通信ポートであってもよい。
【０１１３】
コンピュータ・システム７００は、多様なシステム・アーキテクチャを含んでいてもよく、コンピュータ・システム７００のさまざまな構成要素が再配置されるようになっていてもよい。たとえば、キャッシュ７０４は、プロセッサ７０２とともにオンチップであってもよい。または、キャッシュ７０４およびプロセッサ７０２は、一体的に「プロセッサ・モジュール」としてパッケージングされていてもよく、プロセッサ７０２は「プロセッサ・コア」と称する。さらに、本発明の特定の実施形態においては、上記構成要素がすべて不要であってもよいし、すべて具備していなくてもよい。たとえば、高性能Ｉ／Ｏバス７０６には、標準Ｉ／Ｏバス７０８に結合された周辺機器が結合されていてもよい。また、いくつかの実施形態においては、バスが１つだけ存在し、コンピュータ・システム７００の構成要素がこの単一バスに結合されていてもよい。さらに、コンピュータ・システム７００は、付加的なプロセッサ、記憶装置、またはメモリ等、付加的な構成要素を具備していてもよい。
【０１１４】
一般的に、本明細書に記載のプロセスおよび特徴は、オペレーティング・システムまたは特定のアプリケーション、コンポーネント、プログラム、オブジェクト、モジュール、もしくは「プログラム」と称する一連の命令の一部として実装されていてもよい。たとえば、本明細書に記載の特定のプロセスは、１つまたは複数のプログラムを用いて実行してもよい。プログラムは通常、１つまたは複数のプロセッサにより読み出されて実行された場合に、本明細書に記載のプロセスおよび特徴を実行する演算をコンピュータ・システム７００に行わせる１つまたは複数の命令をコンピュータ・システム７００のさまざまなメモリおよび記憶装置に含む。本明細書に記載のプロセスおよび特徴は、ソフトウェア、ファームウェア、ハードウェア（たとえば、特定用途向け集積回路）、またはこれらの任意の組み合わせに実装されていてもよい。
【０１１５】
一実施態様において、本明細書に記載のプロセスおよび特徴は、分散コンピュータ環境において個別または一括に、コンピュータ・システム７００が動作させる一連の実行可能モジュールとして実装されていてもよい。上記モジュールは、ハードウェア、コンピュータ可読媒体（または、機械可読媒体）に格納された実行可能モジュール、または両者の組み合わせによって実現されるようになっていてもよい。たとえば、これらのモジュールは、プロセッサ７０２等、ハードウェア・システムのプロセッサにより実行される複数の命令または一連の命令を含んでいてもよい。最初は、マス・ストレージ７１８等の記憶装置に一連の命令が格納されていてもよい。ただし、一連の命令は、任意適当なコンピュータ可読記憶媒体に格納可能である。さらに、一連の命令は、ローカルに格納する必要はなく、ネットワーク・インタフェース７１６を介して、ネットワーク上のサーバ等のリモート記憶装置から受信することも可能である。命令は、マス・ストレージ７１８等の記憶装置からシステム・メモリ７１４へのコピーの後、プロセッサ７０２がアクセスして実行する。種々実施態様においては、並列処理環境における複数のサーバ等、１つまたは複数のロケーションの１つまたは複数のプロセッサによって、１つまたは複数のモジュールを実行可能である。
【０１１６】
コンピュータ可読媒体の例としては、揮発性および不揮発性メモリ・デバイス等の記録可能な種類の媒体、ソリッド・ステート・メモリ、フロッピー等のリムーバブルディスク、ハードディスクドライブ、磁気媒体、光ディスク（たとえば、コンパクトディスクリードオンリーメモリ（ＣＤ  ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ））、その他類似する非一時的（または、一時的）の有形（または、無形）記憶媒体、またはコンピュータ・システム７００による実行によって、本明細書に記載のプロセスおよび特徴のうちのいずれか１つもしくは複数を実行する一連の命令の格納、符号化、または伝達に適した任意の種類の媒体が挙げられるが、これらに限定されない。
【０１１７】
説明の便宜上、本明細書の十分な理解が得られるように、多くの具体的詳細を示した。ただし、当業者には、これらの具体的詳細がなくても、本開示の実施形態を実現可能であることが明らかとなろう。場合により、モジュール、構造、プロセス、特徴、および機器をブロック図の形態で示すことによって、説明が分かり難くならないようにしている。他の例では、機能ブロック図およびフロー図を示すことにより、データおよび論理の流れを表している。ブロック図およびフロー図の構成要素（たとえば、モジュール、ブロック、構造、機器、特徴等）は、本明細書における明示的な説明および図示以外の様態でのさまざまな組み合わせ、分離、除去、並び替え、および置き換えがなされていてもよい。
【０１１８】
本明細書における「一実施形態」、「他の実施形態」、「一連の実施形態」、「いくつかの実施形態」、「種々実施形態」等の言及は、該実施形態に関連して説明した特定の特徴、設計、構造、または特性が本開示の少なくとも１つの実施形態に含まれることを意味する。本明細書のさまざまな箇所における表現「一実施形態において」等の出現は、必ずしもすべてが同じ実施形態を表してはおらず、相互に他の実施形態を除外する別個または別の実施形態でもない。さらには、「実施形態」等の明示的な言及の有無に関わらず、いくつかの実施形態においてはさまざまに組み合わせて包含可能であり、他の実施形態においてはさまざまに省略も可能である種々特徴を記載している。同様に、いくつかの実施形態では選好または要件となり得るが、他の実施形態ではなり得ない種々特徴を記載している。
【０１１９】
本明細書において使用する表現は、主として読み易さおよび教示の便宜上から選択しており、本発明に係る主題を描写または限定するようには選択していない場合がある。したがって、本発明の範囲は、この詳細な説明ではなく、これに基づく用途に由来する任意の請求項によって限定されるものとする。以上から、本発明の実施形態に関する開示は、以下の特許請求の範囲に示す本発明の範囲の例示であり、何ら限定的なものではない。
【図１】
0006272467.tif 000002
【図２】
0006272467.tif 000003
【図３】
0006272467.tif 000004
【図４】
0006272467.tif 000005
【図５】
0006272467.tif 000006
【図６】
0006272467.tif 000007
【図７】
0006272467.tif 000008