CN104281664A - Data segmenting method and system of distributed graph calculating system - Google Patents

Abstract

The present invention provides a method and system for data segmentation in a distributed graph computing system. The method includes: determining the similarity measurement value between each data node in the data to be processed and its own first adjacent nodes; obtaining each first adjacent node The number of occurrences of the label of an adjacent node, and determine whether there are at least two labels with the same number of occurrences; The similarity measurement value between the second adjacent nodes determines the label of the data node; divides the data nodes with the same label into the same community, and stores the data nodes belonging to the same community in the same processing host. It fully considers the similarity characteristics between data nodes and realizes the community division of data nodes based on tags, which saves computing overhead, and closely related data nodes are assigned to the same processing host, reducing the communication overhead between different processing hosts .

Description

Distributed graph computing system data segmentation method and system

technical field

The invention belongs to the field of data processing, and in particular relates to a data segmentation method and system of a distributed graph computing system.

Background technique

In recent years, massive data generated in many fields represented by the Internet, high-energy physics, and computational biology have put forward higher requirements for data processing systems. Among these massive data, graph-structured data composed of nodes and edges is an important data structure that can effectively represent data relationships in many different fields. For example, social network data can be represented as a graph-structured data, where nodes represent Users, and edges represent the relationship between users. For example, if two users follow each other, it means that there is an edge between the two corresponding nodes. Similarly, the web page data of the Internet can also be represented as a graph structure data. Nodes represent web pages, and edges represent the relationship between web pages. For example, there is a hyperlink pointing to web page B on web page A, and the corresponding node A and node There is an edge between B.

With the increasing amount of data such as graph-structured data, limited by limited computing and storage capabilities, a single machine can no longer meet the efficient processing of large-scale graph-structured data. Therefore, as an effective tool for big data processing, distributed Data processing equipment provides a platform for processing massive graph-structured data. In order to realize distributed storage of data, distributed data processing devices generally adopt data segmentation. Data segmentation, in simple terms, refers to the distribution of data in massive data to multiple processing hosts through certain specific conditions, so as to achieve the effect of dispersing the load of a single processing host.

However, the current data storage mode of the graph data processing device is: for each data node in the graph data, create a primary node (itself) and at least one secondary node (backup node), and randomly store the primary node in a certain On the processing host, the adjacent data nodes of the primary node are stored on the processing host at the same time, wherein, if the primary node of the adjacent data node is on its processing host, the secondary nodes of the adjacent data node are stored.

In the above-mentioned graph-structured data processing method that divides data in units of data nodes, closely related data nodes are often stored on different processing hosts, and closely related data nodes are actually very likely to be processed simultaneously. Access, if these data nodes are not on the same processing host, it will take a lot of communication resources to obtain different closely related data nodes from different processing hosts. Moreover, the above-mentioned random allocation and redundant storage of data nodes will consume a lot of computing resources for some data nodes with a large degree (that is, the number of neighbor nodes), which will lead to large computing overhead and communication overhead, making data processing less efficient.

Contents of the invention

In view of the above existing problems, the present invention provides a data segmentation method and system of a distributed graph computing system, which is used to overcome the low data processing efficiency caused by the graph structure data processing method of data segmentation in units of data nodes in the prior art. low defect.

The invention provides a data segmentation method of a distributed graph computing system, including:

According to a preset algorithm, determine the similarity measure value between each data node in the data to be processed and its own first adjacent nodes;

Obtain the number of occurrences of each of the labels in each of the first adjacent nodes according to the labels of the first adjacent nodes, where the label includes a node identification ID;

According to the number of occurrences, determine whether there are at least two labels with the same number of occurrences among the labels of the first adjacent nodes;

If it exists, determine the second adjacent nodes corresponding to the at least two labels, and determine the data node's Label;

Divide the data nodes with the same label in the data to be processed into the same community, and store the data nodes belonging to the same community in the same processing host.

The present invention provides a distributed graph computing system data segmentation system, including:

The first determination module is used to determine the similarity measurement value between each data node in the data to be processed and its own first adjacent nodes according to a preset algorithm;

An acquisition module, configured to obtain the number of occurrences of each of the labels in each of the first adjacent nodes according to the labels of the first adjacent nodes, where the label includes a node identification ID;

A second determining module, configured to determine whether there are at least two labels with the same number of occurrences among the labels of the first adjacent nodes according to the number of occurrences;

The third determination module is configured to determine the second adjacent nodes respectively corresponding to the at least two labels, if there is one, and according to the similarity measure value between the data node and the second adjacent nodes , to determine the label of the data node;

The processing module is used to divide the data nodes with the same label in the data to be processed into the same community, and store the data nodes belonging to the same community in the same processing host.

The data segmentation method and system of the distributed graph computing system provided by the present invention, for the data to be processed with a large data scale, for each data node in the data to be processed, determine the similarity measurement value between itself and each adjacent node, Then, when it is determined that there are multiple labels with the same number of occurrences in the labels of its adjacent nodes, according to the similarity measurement value between the adjacent nodes with the same label, determine its own label, and then convert the data to be processed Data nodes with the same label are divided into the same community, and data nodes belonging to the same community are stored in the same processing host. By measuring the similarity between each data node and its adjacent nodes, the overall structural characteristics of the data to be processed are fully considered, and then each data node in the data to be processed is based on the similarity characteristics, combined with its adjacent nodes. Tags are used for cluster analysis to finally divide the data to be processed into multiple communities, and the data nodes in each community have the same label, and the data nodes in each community also have high similarity, so the community-based The unit performs split storage of data nodes on the processing host. Due to the full consideration of the similarity characteristics between data nodes and the realization of the community division of data nodes based on labels, the calculation cost is saved, and the closely related data nodes can be assigned to the same processing host, which greatly reduces the number of different processing hosts. Inter-communication overhead, thus improving the efficiency of data processing.

Description of drawings

FIG. 1 is a flow chart of Embodiment 1 of the data segmentation method of the distributed graph computing system of the present invention;

FIG. 2 is a flow chart of Embodiment 2 of the data segmentation method of the distributed graph computing system of the present invention;

3 is a schematic structural diagram of Embodiment 1 of the data segmentation system of the distributed graph computing system of the present invention;

FIG. 4 is a schematic structural diagram of Embodiment 2 of the data segmentation system of the distributed graph computing system of the present invention.

Detailed ways

Fig. 1 is a flowchart of Embodiment 1 of the data segmentation method of the distributed graph computing system of the present invention. As shown in Fig. 1, the method includes:

Step 101, according to a preset algorithm, determine the similarity measurement value between each data node in the data to be processed and its own first adjacent nodes;

The method provided in this embodiment is applicable to a scenario where a distributed data processing system is used for data segmentation and storage of large-scale graph-structured data, and multiple processing hosts are set in the distributed data processing system. It is worth noting that after the system receives a large amount of data to be processed, the existing distributed processing method can be used to distribute and store the data to be processed in multiple processing hosts in advance, and the method provided in this embodiment Processing can be performed on the data to be processed pre-stored in each processing host, and of course, processing can also be performed directly after receiving the data to be processed. The method provided in this embodiment may be executed by a processing system, such as a management platform of a distributed processing system.

In this embodiment, for graph-structured data, the data can be represented as an abstract graph of data nodes and edges, and the processing system calculates the similarity measure value of each data node in the data to be processed with its own adjacent nodes, Among them, the above-mentioned preset algorithm can be based on the weight of the connection edge between the data node and its adjacent nodes, or based on the degree of the data node (the total number of its adjacent nodes) and the degree of each adjacent node, or Based on the webpage ranking (PageRank, hereinafter referred to as PR) value of the data node and the like.

Step 102. According to the labels of the first adjacent nodes, the number of occurrences of each of the labels in the first adjacent nodes is obtained, and the labels include node identification IDs;

Step 103, according to the number of occurrences, determine whether there are at least two labels with the same number of occurrences among the labels of the first adjacent nodes, if so, perform step 104, otherwise, perform step 105;

Step 104: Determine the second adjacent nodes corresponding to the at least two labels, and determine the label of the data node according to the similarity measurement value between the data node and the second adjacent nodes ;

Step 105. Determine that the label of the data node is the same as the label with the most occurrences among the labels of the first adjacent nodes.

In this embodiment, a label may be pre-configured for each data node, and the label may be an identification ID preset for each node. It is worth noting that the label is the ID of the node, which does not mean that the label has a unique one-to-one correspondence with the data node. Simply put, the label has the meaning of classification, and each data node that meets certain conditions is marked with the same Label.

It should be noted that the process of determining a label for each data node in this embodiment is a process of multiple iterations. At the beginning of the iteration, each data node can be configured with an identification ID used to distinguish it from other data nodes. In the first iteration, taking a certain data node i as an example, after calculating the data node i and its corresponding After the adjacent node, that is, the above-mentioned first adjacent node's similarity measure value, it is assumed that its similarity measure value with the adjacent node j is the largest, so that the label of data node i is determined to be the identification ID of data node j. That is to say, in the first iteration, the label of each adjacent node of data node i is the ID initially assigned to each adjacent node, and, since the label of each adjacent node at this time has a unique Therefore, the number of occurrences of each label is 1, that is, there are at least two labels with the same number of occurrences in the labels of the adjacent nodes of data node i, and at this time, each corresponding to the at least two labels respectively The second adjacent nodes are all adjacent nodes of data node i. Therefore, the label of data node i is determined according to the similarity measurement value between data node i and each adjacent data node in all adjacent nodes. For example, assuming that the similarity measure value between data node i and adjacent node j is the largest, so that the label of data node i is determined to be the identification ID of data node j, at this time, the label of data node i is no longer the initial assignment to it The identification ID becomes the identification ID of data node j.

Therefore, in the subsequent second or subsequent iteration process, due to the above-mentioned label change process, it is possible that the label of a certain adjacent node q of a certain data node k appears the most times in the subsequent iteration process, That is to say, the identification ID of the data node q is used as the label the most times among all adjacent nodes of the data node k. At this point, change the label of data node k to the identification ID of data node q.

Step 106: Divide the data nodes with the same label in the data to be processed into the same community, and store the data nodes belonging to the same community in the same processing host.

After each data node in the data to be processed has done the above-mentioned process of determining the label, many data nodes in the data to be processed will have the same label, and the data nodes with the same label will be divided into the same community, and will belong to The data nodes of the same community are stored in the same processing host, so as to complete the data segmentation processing of the data to be processed, that is, the data to be processed is divided into various communities, and the data nodes are stored in the community as a unit.

In this embodiment, for data to be processed with a large data scale, for each data node in the data to be processed, determine the similarity metric value between itself and each adjacent node, and then determine the label of each adjacent node When there are multiple labels with the same number of occurrences, determine its own label according to the similarity measurement value between adjacent nodes with the same label, and then divide the data nodes with the same label in the data to be processed into the same community, And store data nodes belonging to the same community in the same processing host. By measuring the similarity between each data node and its adjacent nodes, the overall structural characteristics of the data to be processed are fully considered, and then each data node in the data to be processed is based on the similarity characteristics, combined with its adjacent nodes. Tags are used for cluster analysis to finally divide the data to be processed into multiple communities, and the data nodes in each community have the same label, and the data nodes in each community also have high similarity, so the community-based The unit performs split storage of data nodes on the processing host. Due to the full consideration of the similarity between data nodes and the realization of the community division of data nodes based on labels, the calculation cost is saved, and the closely related data nodes can be assigned to the same processing host, which greatly reduces the number of different processing hosts. Inter-communication overhead, thus improving the efficiency of data processing.

Fig. 2 is a flowchart of Embodiment 2 of the data segmentation method of the distributed graph computing system of the present invention. As shown in Fig. 2, the method provided in this embodiment includes the following steps:

Step 201. Calculate the similarity measure value APS(u,v) between the data node u in the data to be processed and the adjacent node v of the data node u according to the formula (1);

$\mathrm{<span\; class="notranslate">\; APS</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; PG</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; PG</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&cap;</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Wherein, v is any one of the first adjacent nodes of the data node u, δ(v) is each of the first adjacent nodes of the data node v, and V is all data nodes in the data to be processed , δ(u) is each first adjacent node of the data node u, and n is the number of nodes that belong to each first adjacent node of data node v and each first adjacent node of data node u at the same time PG(v _j ,u) is the PR value of the page ranking transmitted from data node v _j to data node u, determined according to PG(v _j ,u)=PR(u), PG(v _j ,v) is data node The PR value of web page ranking propagated by v _j to data node v is determined according to PG(v _j ,v)=PR(v), where PR(u) and PR(v) are determined according to formula (2):

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; in</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span>}\frac{\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}{<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; out</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

Wherein, γ is a weighting coefficient, in(w) is the set of adjacent nodes corresponding to the incoming edge of the data node w, out (w) is the set of adjacent nodes corresponding to the outgoing edge of the data node w, |out( w)| is the number of nodes contained in the adjacent node set corresponding to the outgoing edge.

In this embodiment, the degree of similarity between a certain data node and its adjacent nodes can be calculated according to the PageRank value of the data node. PageRank is a proprietary algorithm of Google, which is used to measure the importance of a specific webpage relative to other webpages in the search engine index. The data is the degree of importance in the data to be processed. Each data node calculates its similarity measure with all adjacent nodes through the above calculation method, so that each data node can save a structure, which stores the identification IDs of all its adjacent nodes and the data node The similarity measure value of , so as to be used in the subsequent determination process of the label of the data node.

Step 202. According to the labels of the first adjacent nodes, the number of occurrences of each of the labels in the first adjacent nodes is obtained;

Step 203, according to the number of occurrences, determine whether there are at least two labels with the same number of occurrences among the labels of the first adjacent nodes, if yes, perform step 204, otherwise, perform step 205;

Step 204: Determine the second adjacent nodes respectively corresponding to the at least two labels, determine the third adjacent node from the second adjacent nodes, determine the label of the data node and the first The labels of the three adjacent nodes are the same, and the similarity metric value between the third adjacent node and the data node is greater than that of other second phases of the second adjacent nodes except the third adjacent node. The similarity measure value of the adjacent node and the data node;

Step 205. Determine that the label of the data node is the same as the label with the most occurrences among the labels of the first adjacent nodes.

The foregoing steps 202-205 are consistent with those in the embodiment shown in FIG. 1 , and will not be repeated here.

Step 206: Divide the data nodes with the same label in the data to be processed into the same community, sort each community in the data to be processed in descending order of community size, and the community size is the The number of data nodes contained in the community;

Step 207: According to the preset storage order of each processing host and the order of each community, respectively determine the processing hosts that each community should store in, the storage order refers to the storage order of each community stored by each processing host sequence.

In this embodiment, when the data to be processed has been pre-stored in each processing host, in order to make each community after the data to be processed is divided into communities, and the pre-stored data in the processing host that stores the data nodes in the community The data nodes have better matching, thereby further reducing the processing overhead and optimizing the processing effect. In this embodiment, after the data nodes with the same label in the data to be processed are divided into the same community, the following processing is also performed:

Sort each community in order of community size from large to small, where the community size is the number of data nodes contained in the community; according to the preset storage order of each processing host and the order of each community, respectively Determine the processing hosts in which the communities should be stored, and the storage sequence refers to the order in which the processing hosts store the communities.

It should be noted that in this embodiment, sorting the communities according to the size of the communities in descending order is only an optional manner, and it can also be sorted in descending order. Moreover, the preset storage order of the above-mentioned processing hosts is simply equivalent to sequentially numbering each processing host. Therefore, according to the preset storage order of each processing host and the sorting of each community, the processing hosts that should be stored in each community are respectively determined, specifically: each processing host is stored in one community at a time, according to The order in which communities are sorted and the order in which each processing host stores each community determines the processing host where each community should be stored.

For example, assuming that there are N1 communities in the data to be processed, they are arranged in order of community size from large to small: community 1, community 2, ..., community N1, and there are N2 processing hosts, according to the preset storage order The order is: processing host 1, processing host 2, ..., processing host N2. If N1 is less than or equal to N2, then the corresponding relationship between each community and each processing host is: community 1 (that is, all data nodes contained in community 1) is stored in processing host 1, community 2 is stored in processing host 2, and so on , the community N1 is stored in the processing host N1; if N1 is greater than N2, it means that the number of communities to be stored is more than the number of processing hosts. At this time, the corresponding relationship between each community and each processing host is: Community 1 is stored in the processing host In 1, community 2 is stored in processing host 2, and so on, community N2 is stored in processing host N2, and subsequent communities are stored in a cycle from the beginning, that is, community N2+1 is stored in processing host 1, community N2+2 is stored in into processing host 2, and so on.

Therefore, after the processing hosts that each community should be stored in are determined, optionally, each community can be stored in corresponding processing hosts in turn. However, in another optional way, in order to enable each community to be stored in a processing host with a good matching degree between the pre-stored data nodes and the data nodes contained in the community, in this embodiment, the following steps will be performed:

Step 208: Using each of the communities as the community to be processed, determine the relationship between the data nodes contained in the community to be processed and the data nodes pre-saved in each of the processing hosts. degree of matching;

Specifically, the determining the degree of matching between the data nodes contained in the community to be processed and the data nodes pre-saved in each of the processing hosts respectively includes:

Each matching degree is determined as the number of identical data nodes contained between the data nodes contained in the community to be processed and the corresponding data nodes pre-saved in each processing host.

To put it simply, for each community, the data nodes contained in it are compared with the data nodes pre-saved in each processing host in turn to determine the degree of matching with the data nodes pre-saved in each processing host. That is, the number of repeated data nodes.

Step 209, determining a target processing host corresponding to the community to be processed from the processing hosts, where the pre-saved data nodes in the target processing host have the highest matching degree with the data nodes contained in the community to be processed;

For each community, after determining the degree of matching with the pre-saved data nodes in each processing host, that is, the number of repeated data nodes, select the processing host with the largest number of repeated data nodes as the final community. The target processing host to be logged.

Step 210: Determine whether the target processing host is the same as the processing host that should be stored in the community to be processed determined according to the preset storage order of the processing hosts and the ranking of the communities, and if they are the same, execute the step 211, otherwise, execute step 212;

Step 211, storing the community to be processed in the processing host that should be stored.

Step 212, storing the community to be processed in the target processing host.

If the determined target processing host is the same as the processing host determined according to the community sorting and processing host sorting, then it is sufficient to store the community into the processing host; otherwise, storing the community into the target processing host is equivalent to removing the community from The initially determined processing host was migrated to the target processing host.

In this embodiment, by measuring the similarity between each data node and its adjacent nodes, the overall structural characteristics of the data to be processed are fully considered, and then each data node in the data to be processed is based on the similarity characteristics, combined with The labels of its adjacent nodes are clustered to finally divide the data to be processed into multiple communities, and the data nodes in each community have the same label, and the data nodes in each community also have high similarity , so that the data nodes are segmented and stored on the processing host in units of communities. Due to the full consideration of the similarity between data nodes and the realization of the community division of data nodes based on labels, the calculation cost is saved, and the closely related data nodes can be assigned to the same processing host, which greatly reduces the number of different processing hosts. Inter-communication overhead, thus improving the efficiency of data processing. In addition, in the process of storing the community into the processing host, the processing host to be stored in each community is finally determined according to the matching degree between the data nodes contained in the community and the data nodes pre-stored in the processing host, which reduces the number of unprocessed data. The change of the storage location of the data nodes further reduces the processing overhead and improves the processing efficiency.

Fig. 3 is a schematic structural diagram of Embodiment 1 of the data segmentation system of the distributed graph computing system of the present invention. As shown in Fig. 3, the system includes:

The first determination module 11 is configured to determine the similarity measure value between each data node in the data to be processed and its own first adjacent nodes according to a preset algorithm;

An acquisition module 12, configured to obtain the number of occurrences of each of the labels in each of the first adjacent nodes according to the labels of the first adjacent nodes, where the label includes a node identification ID;

The second determination module 13 is configured to determine whether there are at least two labels with the same number of occurrences among the labels of the first adjacent nodes according to the number of occurrences;

The third determination module 14 is configured to determine the second adjacent nodes respectively corresponding to the at least two labels if the second determination module 13 determines that there are at least two labels with the same number of occurrences, and according to the The similarity measurement value between the data node and the second adjacent nodes determines the label of the data node;

The processing module 15 is configured to divide the data nodes with the same label in the data to be processed into the same community, and store the data nodes belonging to the same community in the same processing host.

The third determination module 14 is also used for:

If the second determination module 13 determines that there are no at least two labels with the same number of occurrences, it is determined that the label of the data node is the same as the label with the largest number of occurrences among the labels of the first adjacent nodes.

The system of this embodiment can be used to execute the technical solution of the method embodiment shown in FIG. 1 , and its implementation principle and technical effect are similar, and will not be repeated here.

Fig. 4 is a schematic structural diagram of Embodiment 2 of the data segmentation system of the distributed graph computing system of the present invention. As shown in Fig. 4, the system provided in this embodiment is based on the embodiment shown in Fig. 3, and the first Determine module 11, specifically for:

Calculate the similarity measure value APS(u, v) between the data node u in the data to be processed and the adjacent node v of the data node u according to formula (1):

$\mathrm{<span\; class="notranslate">\; APS</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; PG</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; PG</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&cap;</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Wherein, v is any one of the first adjacent nodes of the data node u, δ(v) is each of the first adjacent nodes of the data node v, and V is all data nodes in the data to be processed , δ(u) is each first adjacent node of the data node u, and n is the number of nodes that belong to each first adjacent node of data node v and each first adjacent node of data node u at the same time PG(v _j ,u) is the PR value of the page ranking transmitted from data node v _j to data node u, determined according to PG(v _j ,u)=PR(u), PG(v _j ,v) is data node The PR value of web page ranking propagated by v _j to data node v is determined according to PG(v _j ,v)=PR(v), where PR(u) and PR(v) are determined according to formula (2):

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&gamma;</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; in</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span>}\frac{\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}{<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; out</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

Wherein, γ is a weighting coefficient, in(w) is the set of adjacent nodes corresponding to the incoming edge of the data node w, out (w) is the set of adjacent nodes corresponding to the outgoing edge of the data node w, |out( w)| is the number of nodes contained in the adjacent node set corresponding to the outgoing edge;

The third determination module 14 is specifically used for:

A third adjacent node is determined from the second adjacent nodes, and the similarity metric value between the third adjacent node and the data node is greater than that of the second adjacent nodes except the third adjacent node. The similarity measure value between other second neighboring nodes and the data node except neighboring nodes;

determining that the label of the data node is the same as the label of the third adjacent node;

The processing module 15 is also used for:

Sort each community in the data to be processed in descending order of community size, where the community size is the number of data nodes contained in the community;

According to the preset storage order of each processing host and the sorting of each community, respectively determine the processing host that each community should be stored in, and the storage order refers to the order in which each processing host stores the various communities;

Store each community in the corresponding processing hosts in sequence;

The system also includes a fourth determining module 21, configured to:

Using each community in each of the communities as the community to be processed, determine the matching degree between the data nodes contained in the community to be processed and the data nodes pre-saved in each of the processing hosts respectively ;

Determining a target processing host corresponding to the community to be processed from the processing hosts, where the pre-saved data nodes in the target processing host have the highest matching degree with the data nodes contained in the community to be processed;

determining whether the target processing host is the same as the processing host that should be stored in the communities to be processed determined according to the preset storage order of the processing hosts and the ranking of the communities;

The processing module 15 is also used for:

If the fourth determining module 21 determines that the target processing host is the same as the processing host that should be stored in the community to be processed determined according to the preset storage order of the processing hosts and the ranking of the communities, then the The community to be processed is stored in the processing host that should be stored;

If the fourth determination module 21 determines that the target processing host is different from the processing host that should be stored in the community to be processed determined according to the preset storage order of the processing hosts and the ranking of the communities, then The community to be processed is stored in the target processing host.

The system of this embodiment can be used to implement the technical solution of the method embodiment shown in FIG. 2 , and its implementation principle and technical effect are similar, and will not be repeated here.

Those of ordinary skill in the art can understand that all or part of the steps for realizing the above-mentioned method embodiments can be completed by hardware related to program instructions, and the aforementioned program can be stored in a computer-readable storage medium. When the program is executed, the It includes the steps of the above-mentioned method embodiments; and the aforementioned storage medium includes: ROM, RAM, magnetic disk or optical disk and other various media that can store program codes.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than limiting them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the present invention. scope.

Claims (10)

1. a distributed figure computing system data segmentation method, is characterized in that, comprising:

According to preset algorithm, determine each back end in pending data and the similarity measure values between each first-phase neighbors of self;

According to the label of described each first-phase neighbors, obtain the occurrence number of each described label in described each first-phase neighbors, described label comprises node identification ID;

According to described occurrence number, determine whether there are at least two identical labels of occurrence number in the label of described each first-phase neighbors;

If exist, then determine each second-phase neighbors corresponding respectively with described at least two labels, and according to the similarity measure values between described back end and described each second-phase neighbors, determine the label of described back end;

The back end in described pending data with same label is divided into same community, and the back end belonging to same community is stored in same processing host.

2. method according to claim 1, is characterized in that, described according to preset algorithm, determines each back end in pending data and the similarity measure values between each first-phase neighbors of self, comprising:

Similarity measure values APS (u, v) between the adjacent node v calculating back end u in described pending data and described back end u according to formula (1):

$\mathrm{APS}(u,v)={\mathrm{\&Sigma;}}_{j=1}^n\min (\mathrm{PG}(v_j,u),\mathrm{PG}(v_j,v)),u,v\&Element;V,v_j\&Element;(\mathrm{\&delta;}\left(v\right)\&cap;\mathrm{\&delta;}\left(u\right))---\left(1\right)$

Wherein, v is any one back end in each first-phase neighbors of described back end u, each first-phase neighbors that δ (v) is back end v, V is the set of all back end in described pending data, each first-phase neighbors that δ (u) is described back end u, n is the number of the node simultaneously belonging to each first-phase neighbors of back end v and each first-phase neighbors of back end u, PG (v _j, u) be back end v _jpropagate into the page rank PR value of back end u, according to PG (v _j, u)=PR (u) determines, PG (v _j, v) be back end v _jpropagate into the page rank PR value of back end v, according to PG (v _j, v)=PR (v) determines, wherein, PR (u) and PR (v) determines according to formula (2):

$\mathrm{PR}\left(w\right)=(1-\mathrm{\&gamma;})+\mathrm{\&gamma;}{\mathrm{\&Sigma;}}_{v_i\&Element;\mathrm{in}\left(w\right)}\frac{\mathrm{PR}\left(v_i\right)}{\left|\mathrm{out}\left(w\right)\right|},w\&Element;V---\left(2\right)$

Wherein, γ is weighting coefficient, in (w) for described back end w enter adjacent node set corresponding to limit, out (w) for back end w go out adjacent node set corresponding to limit, | out (w) | be the described node number going out to comprise in adjacent node set corresponding to limit.

3. method according to claim 2, is characterized in that, described according to the similarity measure values between described back end and described each second-phase neighbors, determines the label of described back end, comprising:

From described each second-phase neighbors, determine third phase neighbors, the similarity measure values of described third phase neighbors and described back end is greater than the similarity measure values of other second-phase neighbors in described each second-phase neighbors except described third phase neighbors and described back end;

Determine that the label of described back end is identical with the label of described third phase neighbors.

4. method according to claim 1, is characterized in that, described according to described occurrence number, after determining whether there are at least two identical labels of occurrence number in the described label of described each first-phase neighbors, also comprises:

If do not exist, then determine that the label that the label of described back end is maximum with occurrence number in the label of described each first-phase neighbors is identical.

5. method according to any one of claim 1 to 4, is characterized in that, described the back end in described pending data with same label is divided into same community after, also comprise:

Sorted according to community's scale order from big to small each community in described pending data, described community scale is the number of the back end comprised in described community;

Described the back end belonging to same community to be stored in same processing host, to comprise:

According to the default storage order of each processing host and the sequence of each community described, determine respectively each community described should stored in processing host, described storage order refers to the sequencing of each community described in described each process host stores;

By each community described successively stored in each processing host of correspondence.

6. method according to claim 5, is characterized in that, described according to the default storage order of each processing host and the sequence of each community described, determine respectively each community described should stored in processing host after, also comprise:

Respectively using each community in each community described as pending community, determine the matching degree between the back end preserved in advance in the back end that comprises in the described pending community each processing host respectively and in described each processing host;

From described each processing host, determine the target processing host corresponding with described pending community, the matching degree of the back end comprised in the back end preserved in advance in described target processing host and described pending community is the highest;

Determine described target processing host and the described pending community determined according to the default storage order of described each processing host and the sequence of each community described should stored in processing host whether identical;

If identical, then by described pending community stored in described should stored in processing host in.

7. method according to claim 6, it is characterized in that, described determine described target processing host and the described pending community determined according to the default storage order of described each processing host and the sequence of each community described should stored in processing host whether identical after, also comprise:

If not identical, then by described pending community stored in described target processing host.

8. the method according to claim 6 or 7, is characterized in that, the matching degree between the back end preserved in advance in each processing host of the described back end determining to comprise in described pending community respectively and in described each processing host, comprising:

Determine that each described matching degree is the number of back end and the identical data node comprised between the back end preserved in advance in corresponding each processing host comprised in described pending community.

9. a distributed figure computing system data cutting system, is characterized in that, comprising:

First determination module, for according to preset algorithm, determines each back end in pending data and the similarity measure values between each first-phase neighbors of self;

Acquisition module, for the label according to described each first-phase neighbors, obtain the occurrence number of each described label in described each first-phase neighbors, described label comprises node identification ID;

Second determination module, for according to described occurrence number, determines whether there are at least two identical labels of occurrence number in the label of described each first-phase neighbors;

3rd determination module, if for existing, then determines each second-phase neighbors corresponding respectively with described at least two labels, and according to the similarity measure values between described back end and described each second-phase neighbors, determines the label of described back end;

Processing module, for the back end in described pending data with same label is divided into same community, and is stored in the back end belonging to same community in same processing host.

10. system according to claim 9, is characterized in that, described first determination module, specifically for:

Similarity measure values APS (u, v) between the adjacent node v calculating back end u in described pending data and described back end u according to formula (1):

$\mathrm{APS}(u,v)={\mathrm{\&Sigma;}}_{j=1}^n\min (\mathrm{PG}(v_j,u),\mathrm{PG}(v_j,v)),u,v\&Element;V,v_j\&Element;(\mathrm{\&delta;}\left(v\right)\&cap;\mathrm{\&delta;}\left(u\right))---\left(1\right)$

Wherein, v is any one back end in each first-phase neighbors of described back end u, each first-phase neighbors that δ (v) is back end v, V is the set of all back end in described pending data, each first-phase neighbors that δ (u) is described back end u, n is the number of the node simultaneously belonging to each first-phase neighbors of back end v and each first-phase neighbors of back end u, PG (v _j, u) be back end v _jpropagate into the page rank PR value of back end u, according to PG (v _j, u)=PR (u) determines, PG (v _j, v) be back end v _jpropagate into the page rank PR value of back end v, according to PG (v _j, v)=PR (v) determines, wherein, PR (u) and PR (v) determines according to formula (2):

$\mathrm{PR}\left(w\right)=(1-\mathrm{\&gamma;})+\mathrm{\&gamma;}{\mathrm{\&Sigma;}}_{v_i\&Element;\mathrm{in}\left(w\right)}\frac{\mathrm{PR}\left(v_i\right)}{\left|\mathrm{out}\left(w\right)\right|},w\&Element;V---\left(2\right)$

Wherein, γ is weighting coefficient, in (w) for described back end w enter adjacent node set corresponding to limit, out (w) for back end w go out adjacent node set corresponding to limit, | out (w) | be the described node number going out to comprise in adjacent node set corresponding to limit;

Described 3rd determination module, specifically for:

From described each second-phase neighbors, determine third phase neighbors, the similarity measure values of described third phase neighbors and described back end is greater than the similarity measure values of other second-phase neighbors in described each second-phase neighbors except described third phase neighbors and described back end;

Determine that the label of described back end is identical with the label of described third phase neighbors;

Described 3rd determination module, also for:

If do not exist, then determine that the label that the label of described back end is maximum with occurrence number in the label of described each first-phase neighbors is identical;

Described processing module, also for:

Sorted according to community's scale order from big to small each community in described pending data, described community scale is the number of the back end comprised in described community;

According to the default storage order of each processing host and the sequence of each community described, determine respectively each community described should stored in processing host, described storage order refers to the sequencing of each community described in described each process host stores;

By each community described successively stored in each processing host of correspondence;

Described system also comprises the 4th determination module, for:

Respectively using each community in each community described as pending community, determine the matching degree between the back end preserved in advance in the back end that comprises in the described pending community each processing host respectively and in described each processing host;

From described each processing host, determine the target processing host corresponding with described pending community, the matching degree of the back end comprised in the back end preserved in advance in described target processing host and described pending community is the highest;

Determine described target processing host and the described pending community determined according to the default storage order of described each processing host and the sequence of each community described should stored in processing host whether identical;

Described processing module, also for:

If identical, then by described pending community stored in described should stored in processing host in;

If not identical, then by described pending community stored in described target processing host.