Nova Patents
JP6272467B2

Systems and methods for dynamic mapping for locality and balance

Abstract

This record has no abstract on file.

JP6272467B2, drawing sheet 1
Sheet 1 of 7

Term

Projected expiry 20 November 2033.

  1. Priority and filed
  2. Granted
  3. Today
  4. Projected expiry

17 claims: 6 independent, 11 dependent

  1. 1
    コンピュータ実装方法であって、 コンピュータ・システムが、第1のパーティションのノードのヒストグラムを演算するステップと、 前記コンピュータ・システムが、第2のパーティションのノードのヒストグラムを演算するステップと、 前記コンピュータ・システムが、前記第1のパーティションのノードのヒストグラムに基づいて、前記第1のパーティションの一組のノードの候補パーティションとして前記第2のパーティションを選択するステップと、 前記コンピュータ・システムが、前記第2のパーティションのノードのヒストグラムに基づいて、前記第2のパーティションの一組のノードの候補パーティションとして前記第1のパーティションを選択するステップと、 前記コンピュータ・システムが、負荷平衡に基づいて、前記第1のパーティションの一組のノードの少なくとも一部を前記第2のパーティションに再マッピングし、前記第2のパーティションの一組のノードの少なくとも一部を前記第1のパーティションに再マッピングするステップと、を備える、コンピュータ実装方法。
  2. 2
    前記コンピュータ・システムが、第3のパーティションのノードのヒストグラムを演算するステップと、 前記コンピュータ・システムが、前記第1のパーティションのノードのヒストグラムに基づいて、前記第1のパーティションの別の一組のノードの候補パーティションとして前記第3のパーティションを選択するステップと、 前記コンピュータ・システムが、前記第3のパーティションのノードのヒストグラムに基づいて、前記第3のパーティションの一組のノードの候補パーティションとして前記第1のパーティションを選択するステップと、 前記コンピュータ・システムが、負荷平衡に基づいて、前記第1のパーティションの他の一組のノードの少なくとも一部を前記第3のパーティションに再マッピングするとともに、前記第3のパーティションの一組のノードの少なくとも一部を前記第1のパーティションに再マッピングするステップと、をさらに備える、請求項1に記載のコンピュータ実装方法。
  3. 3
    前記コンピュータ・システムが、エッジ局所性のゲインに基づいて、前記第1のパーティションの一組のノードをソートするステップと、 前記コンピュータ・システムが、エッジ局所性のゲインに基づいて、前記第2のパーティションの一組のノードをソートするステップと、をさらに備え、 前記第2のパーティションが、エッジ局所性のゲインに関する確率に基づいて、前記第1のパーティションのノードの候補パーティションとして選択される、請求項1または2に記載のコンピュータ実装方法。
  4. 4
    前記第1のパーティションのノードのヒストグラムが、複数のパーティションのそれぞれにおける接続ノードの数を示す、請求項1~3のいずれか一項に記載のコンピュータ実装方法。
  5. 5
    前記第2のパーティションに再マッピングされた前記第1のパーティションのノードの数と前記第1のパーティションに再マッピングされた前記第2のパーティションのノードの数との差が、しきい値の範囲内であること、および、 前記第2のパーティションに再マッピングされた前記第1のパーティションのノードの重みと前記第1のパーティションに再マッピングされた前記第2のパーティションのノードの重みとの差が、しきい値の範囲内であることのうちの少なくとも一方を含む、請求項1~4のいずれか一項に記載のコンピュータ実装方法。
  6. 6
    前記コンピュータ・システムが、前記再マッピングの前に、前記第1のパーティションの第1の総ノード重みを演算するステップをさらに備え、 好ましくは、前記コンピュータ・システムが、前記再マッピングの後に、前記第1のパーティションの第2の総ノード重みを演算するステップをさらに備える、請求項1~5のいずれか一項に記載のコンピュータ実装方法。
  7. 7
    前記コンピュータ・システムが、非分散システムであり、 該コンピュータ実装方法が、 前記コンピュータ・システムが、ノードグラフをメモリにロードするステップをさらに備え、 前記ノードグラフが、前記第1のパーティションのノードおよび前記第2のパーティションのノードを含む、請求項1~6のいずれか一項に記載のコンピュータ実装方法。
  8. 8
    前記コンピュータ・システムが、分散システムであり、 該コンピュータ実装方法が、 前記コンピュータ・システムが、ノードグラフの異なる部分を前記分散システム全体にロードするステップをさらに備え、 前記ノードグラフが、前記第1のパーティションのノードおよび前記第2のパーティションのノードを含む、請求項1~6のいずれか一項に記載のコンピュータ実装方法。
  9. 9
    前記第1のパーティションの複数のノードのそれぞれと関連付けられた接続ノードの現行パーティションIDを受信するステップをさらに備え、 好ましくは、前記第1のパーティションのノードのヒストグラムが、前記現行パーティションIDに基づいて演算され、 好ましくは、前記第1のパーティションの複数のノードのそれぞれの現行パーティションIDを提供するステップをさらに備える、請求項1~8のいずれか一項に記載のコンピュータ実装方法。
  10. 10
    候補パーティションが、局所性ゲインしきい値に基づいて選択される、請求項1~9のいずれか一項に記載のコンピュータ実装方法。
  11. 11
    前記第2のパーティションが、エッジ局所性のゲインに関する確率に基づいて、前記第1のパーティションのノードの候補パーティションとして選択される、請求項1~10のいずれか一項に記載のコンピュータ実装方法。
  12. 12
    前記コンピュータ・システムが、再マッピングされるノードを示す複数のパーティションのすべてのパーティション対の記録を生成するステップをさらに備える、請求項1~11のいずれか一項に記載のコンピュータ実装方法。
  13. 13
    前記ノードグラフが、ソーシャルネットワーキング・システムによりサポートされている、請求項1~12のいずれか一項に記載のコンピュータ実装方法。
  14. 14
    少なくとも1つのプロセッサと、 前記少なくとも1つのプロセッサに指示して、請求項1~13のいずれか一項に記載の方法を実行するように構成された命令を格納したメモリと、 を備えた、システム。
  15. 15
    実行された場合に、請求項1~13のいずれか一項に記載のコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納した、コンピュータ記憶媒体。
  16. 16
    システムであって、 少なくとも1つのプロセッサと、 メモリと、を備え、 前記メモリは、 前記少なくとも1つのプロセッサに指示して、 第1のパーティションのノードのヒストグラムを演算すること、 第2のパーティションのノードのヒストグラムを演算すること、 前記第1のパーティションのノードのヒストグラムに基づいて、前記第1のパーティションの一組のノードの候補パーティションとして前記第2のパーティションを選択すること、 前記第2のパーティションのノードのヒストグラムに基づいて、前記第2のパーティションの一組のノードの候補パーティションとして前記第1のパーティションを選択すること、 負荷平衡に基づいて、前記第1のパーティションの前記一組のノードの少なくとも一部を前記第2のパーティションに再マッピングするとともに、前記第2のパーティションの前記一組のノードの少なくとも一部を前記第1のパーティションに再マッピングすることと、を実行するように構成された命令を格納する、システム。
  17. 17
    コンピュータ記憶媒体であって、 実行された場合に、 第1のパーティションのノードのヒストグラムを演算するステップと、 第2のパーティションのノードのヒストグラムを演算するステップと、 前記第1のパーティションのノードのヒストグラムに基づいて、前記第1のパーティションの一組のノードの候補パーティションとして前記第2のパーティションを選択するステップと、 前記第2のパーティションのノードのヒストグラムに基づいて、前記第2のパーティションの一組のノードの候補パーティションとして前記第1のパーティションを選択するステップと、 負荷平衡に基づいて、前記第1のパーティションの一組のノードの少なくとも一部を前記第2のパーティションに再マッピングするとともに、前記第2のパーティションの一組のノードの少なくとも一部を前記第1のパーティションに再マッピングするステップと、 を含むコンピュータ実装方法をコンピュータ・システムに実行させるコンピュータ実行可能命令を格納した、コンピュータ記憶媒体。
Independent claims17