SYSTEMS AND METHODS FOR DYNAMIC MAPPING FOR LOCALITY AND BALANCE

• US 20150095348A1
• Filed: 10/01/2013
• Published: 04/02/2015
• Est. Priority Date: 10/01/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: PRESTA, Alessandro, SHALITA, Alon Michael
• Granted Patent: US 9,934,323 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

To dynamically map nodes for locality and balance, computer implemented methods, systems, and computer readable media, in an embodiment, may compute histograms for nodes in a first partition. Histograms may be computed for nodes in a second partition. The second partition may be selected as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition. The first partition may be selected as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition. At least a portion of the set of nodes in the first partition may be mapped to the second partition and at least a portion of the set of nodes in the second partition may be mapped to the first partition based on load balancing.

Claims

1. A computer implemented method comprising:

computing, with a computer system, histograms for nodes in a first partition;

computing, with the computer system, histograms for nodes in a second partition;

selecting, with the computer system, the second partition as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition;

selecting, with the computer system, the first partition as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition; and

remapping, with the computer system, at least a portion of the set of nodes in the first partition to the second partition and at least a portion of the set of nodes in the second partition to the first partition based on load balancing.

2. The computer implemented method of claim 1, further comprising:

computing, with the computer system, histograms for nodes in a third partition;

selecting, with the computer system, the third partition as a candidate partition for another set of nodes in the first partition based on the histograms for the nodes in the first partition;

selecting, with the computer system, the first partition as a candidate partition for a set of nodes in the third based on the histograms for the nodes in the third partition; and

remapping, with the computer system, at least a portion of the other set of nodes in the first partition to the third partition and at least a portion of the set of nodes in the third partition to the first partition based on load balancing.

3. The computer implemented method of claim 1, further comprising:

sorting, with the computer system, the set of nodes in the first partition based on a gain in edge locality; and

sorting, with the computer system, the set of nodes in the second partition based on a gain in edge locality.

4. The computer implemented method of claim 3, wherein the second partition is selected as the candidate partition for the nodes in the first partition based on a probability relating to the gain in edge locality.

5. The computer implemented method of claim 1, wherein the histograms for the nodes in the first partition indicate a number of connected nodes in each of a plurality of partitions.

6. The computer implemented method of claim 1, wherein a difference between a number of nodes in the first partition remapped to the second partition and a number of nodes in the second partition remapped to the first partition is within a threshold.

7. The computer implemented method of claim 1, wherein a difference between a weight of nodes in the first partition remapped to the second partition and a weight of nodes in the second partition remapped to the first partition is within a threshold.

8. The computer implemented method of claim 1, further comprising:

computing, with the computer system, a first total node weight of the first partition before the remapping.

9. The computer implemented method of claim 8, further comprising:

computing, with the computer system, a second total node weight of the first partition after the remapping.

10. The computer implemented method of claim 1, wherein the computer system is a non-distributed system, the method further comprising:

loading, with the computer system, a node graph into memory, wherein the node graph comprises the nodes in the first partition and the nodes in the second partition.

11. The computer implemented method of claim 1, wherein the computer system is a distributed system, the method further comprising:

loading, with the computer system, different portions of a node graph across the distributed system, wherein the node graph comprises the nodes in the first partition and the nodes in the second partition.

12. The computer implemented method of claim 11, further comprising receiving current partition IDs of connected nodes associated with each of the nodes in the first partition.

13. The computer implemented method of claim 12, wherein the histograms for the nodes in the first partition are computed based on the current partition IDs.

14. The computer implemented method of claim 13, further comprising providing a current partition ID of each of the nodes in the first partition.

15. The computer implemented method of claim 14, wherein candidate partitions are selected based on a locality gain threshold.

16. The computer implemented method of claim 11, wherein the second partition is selected as the candidate partition for the nodes in the first partition based on a probability relating to a gain in edge locality.

17. The computer implemented method of claim 11, further comprising:

generating, with the computer system, a record of all partition pairs for a plurality of partitions that indicates nodes to be remapped.

18. The computer implemented method of claim 1, wherein the node graph is supported by a social networking system.

19. A system comprising:

at least one processor, and

a memory storing instructions configured to instruct the at least one processor to perform;

computing histograms for nodes in a first partition;

computing histograms for nodes in a second partition;

selecting the second partition as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition;

selecting the first partition as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition; and

remapping at least a portion of the set of nodes in the first partition to the second partition and at least a portion of the set of nodes in the second partition to the first partition based on load balancing.

20. A computer storage medium storing computer-executable instructions that, when executed, cause a computer system to perform computer-implemented method comprising:

computing histograms for nodes in a first partition;

computing histograms for nodes in a second partition;

selecting the second partition as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition;

selecting the first partition as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition; and

remapping at least a portion of the set of nodes in the first partition to the second partition and at least a portion of the set of nodes in the second partition to the first partition based on load balancing.