Cluster-based random walk processing
Implementations of the present specification disclose method, apparatus, and device for processing graph data using a random walk-based process. The process is applicable to either a cluster of machines, a stand-alone machine, or both. In one aspect, the method includes: obtaining, by a cluster, data describing a graph that has nodes and edges between the nodes, wherein the cluster comprises (i) a server cluster that includes a plurality of server machines and (ii) a working machine cluster that includes a plurality of working machines; generating a two-dimensional array based on the data, wherein generating the two-dimensional array comprises generating, for each node included in the graph, a row comprising respective identifiers of adjacent nodes of the node; and generating, based on the two-dimensional array, a random sequence that represents a random walk processing of the data by the cluster.
1. A method for performing cluster-based random walk, comprising:
obtaining, by each working machine in a working machine cluster, data describing a respective portion of a graph comprising nodes and comprising edges between the nodes, wherein each working machine in the working machine cluster comprises one or more processors;
synchronizing, by each working machine in the working machine cluster, the data describing the respective portion of the graph with a server cluster to provide synchronized data;
generating a full two-dimensional array based on the synchronized data, wherein generating the full two-dimensional array comprises
generating, by each working machine in the working machine cluster, a non-full two-dimensional array based on respective identifiers of (i) adjacent nodes whose identifiers are read by the working machine and (ii) a node connected to the adjacent nodes,
synchronizing, by the server cluster, the non-full two-dimensional arrays generated by the working machines of the working machine cluster, and
generating, by the server cluster, the full two-dimensional array based on all the non-full two-dimensional arrays;
synchronizing the full two-dimensional array across the working machine cluster to provide a synchronized two-dimensional array; and
generating, by each working machine in the working machine cluster, a random sequence, respectively, based on the synchronized two-dimensional array, wherein generating the random sequence comprises
generating a sorted two-dimensional array by sorting all rows of the full two-dimensional array based on a sequence of respective identifiers of the nodes, and
generating the random sequence based on the sorted two-dimensional array.
2. The method according to claim 1 , wherein obtaining the data describing the graph comprises:
reading, by the working machine cluster and from a database, respective identifiers of adjacent nodes of each node included in the graph, wherein each working machine reads respective identifiers of adjacent nodes of at least some of the nodes included in the graph.
3. The method according to claim 1 , wherein the generating the random sequence comprises:
determining, by the working machine, an identifier from respective identifiers of the nodes included in the graph as a target node identifier;
determining a corresponding row from the synchronized two-dimensional array based on the target node identifier, wherein the corresponding row comprises the target node identifier and respective adjacent node identifiers of adjacent nodes of a target node;
determining a quantity of adjacent node identifiers included in the corresponding row;
determining a non-negative integer K that is less than a value of the quantity of adjacent node identifiers in the corresponding row;
obtaining a Kth adjacent node identifier of a Kth adjacent node included in the corresponding row; and
generating the random sequence that includes the Kth adjacent node identifier.
4. The method according to claim 3 , wherein there are N nodes in total, an identifier of a mth node is m, 0≤m≤N−1, the target node is a ith node, and the corresponding row is an ith row of the full two-dimensional array.
5. The method according to claim 3 , wherein the corresponding row is a one-dimensional array, an identifier of a nth adjacent node of the target node is a nth element of the one-dimensional array, and n is counted from 0; and
the non-negative integer K is denoted as j, and the obtaining the Kth adjacent node identifier of the Kth adjacent node included in the corresponding row comprises:
obtaining an adjacent node identifier of a jth adjacent node of the target node by reading a jth element of the one-dimensional array.
6. The method according to claim 5 , wherein a total quantity of elements of the one-dimensional array is equal to a quantity of adjacent nodes of a node with the largest quantity of adjacent nodes among all the nodes.
7. The method according to claim 3 , wherein the generating the random sequence that includes the Kth adjacent node identifier comprises:
generating the random sequence that includes the Kth adjacent node identifier when a total quantity of target nodes reaches a predetermined quantity of random walk steps.
8. The method according to claim 1 , wherein the generating the random sequence comprises:
generating, by each working machine in the working machine cluster, a different random sequence until a total quantity of generated random sequences reaches a determined threshold.
9. The method according to claim 1 , wherein synchronizing the full two-dimensional array across the working machines in the working machine cluster comprises:
re-obtaining the full two-dimensional array from the server cluster when a local copy of the full two-dimensional array is lost.
10. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system comprising a working machine cluster to perform operations comprising:
obtaining, by each working machine in a working machine cluster, data describing a respective portion of a graph comprising nodes and comprising edges between the nodes, wherein each working machine in the working machine cluster comprises one or more processors;
synchronizing, by each working machine in the working machine cluster, the data describing the respective portion of the graph with a server cluster to provide synchronized data;
generating a full two-dimensional array based on the synchronized data, wherein generating the full two-dimensional array comprises;
generating, by each working machine in the working machine cluster, a non-full two-dimensional array based on respective identifiers of (i) adjacent nodes whose identifiers are read by the working machine and (ii) a node connected to the adjacent nodes,
synchronizing, by the server cluster, the non-full two-dimensional arrays generated by the working machines of the working machine cluster, and
generating, by the server cluster, the full two-dimensional array based on all the non-full two-dimensional arrays;
synchronizing the full two-dimensional array across the working machine cluster to provide a synchronized two-dimensional array; and
generating, by each working machine in the working machine cluster, a random sequence, respectively, based on the synchronized two-dimensional array, wherein generating the random sequence comprises
generating a sorted two-dimensional array by sorting all rows of the full two-dimensional array based on a sequence of respective identifiers of the nodes, and
generating the random sequence based on the sorted two-dimensional array.
11. The non-transitory, computer-readable medium according to claim 10 , wherein obtaining the data describing the graph comprises:
reading, by the working machine cluster and from a database, respective identifiers of adjacent nodes of each node included in the graph, wherein each working machine reads respective identifiers of adjacent nodes of at least some of the nodes included in the graph.
12. The non-transitory, computer-readable medium according to claim 10 , wherein the generating the random sequence comprises:
determining, by the working machine, an identifier from respective identifiers of the nodes included in the graph as a target node identifier;
determining a corresponding row from the synchronized two-dimensional array based on the target node identifier, wherein the corresponding row comprises the target node identifier and respective adjacent node identifiers of adjacent nodes of a target node;
determining a quantity of adjacent node identifiers included in the corresponding row;
determining a non-negative integer K that is less than a value of the quantity of adjacent node identifiers in the corresponding row;
obtaining a Kth adjacent node identifier of a Kth adjacent node included in the corresponding row; and
generating the random sequence that includes the Kth adjacent node identifier.
13. A computer-implemented system, comprising
a working machine cluster, wherein the working machine cluster comprises one or more computers and comprises one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising:
obtaining, by each working machine in a working machine cluster, data describing a respective portion of a graph comprising nodes and comprising edges between the nodes, wherein each working machine in the working machine cluster comprises one or more processors;
synchronizing, by each working machine in the working machine cluster, the data describing the respective portion of the graph with a server cluster to provide synchronized data;
generating a full two-dimensional array based on the synchronized data, wherein generating the full two-dimensional array comprises
generating, by each working machine in the working machine cluster, a non-full two-dimensional array based on respective identifiers of (i) adjacent nodes whose identifiers are read by the working machine and (ii) a node connected to the adjacent nodes,
synchronizing, by the server cluster, the non-full two-dimensional arrays generated by the working machines of the working machine cluster, and
generating, by the server cluster, the full two-dimensional array based on all the non-full two-dimensional arrays;
synchronizing the full two-dimensional array across the working machine cluster to provide a synchronized two-dimensional array; and
generating, by each working machine in the working machine cluster, a random sequence, respectively, based on the synchronized two-dimensional array, wherein generating the random sequence comprises
generating a sorted two-dimensional array by sorting all rows of the full two-dimensional array based on a sequence of respective identifiers of the nodes, and
generating the random sequence based on the sorted two-dimensional array.
14. The computer-implemented system according to claim 13 , wherein obtaining the data describing the graph comprises:
reading, by the working machine cluster and from a database, respective identifiers of adjacent nodes of each node included in the graph, wherein each working machine reads respective identifiers of adjacent nodes of at least some of the nodes included in the graph.
15. The computer-implemented system according to claim 13 , wherein the generating the random sequence comprises:
determining, by the working machine, an identifier from respective identifiers of the nodes included in the graph as a target node identifier;
determining a corresponding row from the synchronized two-dimensional array based on the target node identifier, wherein the corresponding row comprises the target node identifier and respective adjacent node identifiers of adjacent nodes of a target node;
determining a quantity of adjacent node identifiers included in the corresponding row;
determining a non-negative integer K that is less than a value of the quantity of adjacent node identifiers in the corresponding row;
obtaining a Kth adjacent node identifier of a Kth adjacent node included in the corresponding row; and
generating the random sequence that includes the Kth adjacent node identifier.