Agglomerative algorithm for graph clustering
Disclosed herein are system, method, and computer program product embodiments for determining clusters of operations in a data processing pipeline. By clustering the operations according to the operations' programming languages using the algorithm disclosed herein, performance efficiency gains can be achieved. The algorithm is iterative, traversing all operations in a data processing pipeline with subsequent iterations addressing the clustering regime determined by prior iterations.
1. A computer implemented method, comprising:
receiving a data processing pipeline comprising operations and connections between the operations,
wherein the operations are programmed in an operation-associated set of programming languages, and
wherein the operations perform a transformational function on a set of data received by the data processing pipeline;
grouping the operations into clusters,
wherein the clusters are each assigned a cluster-associated set of programming languages based on the operation-associated set of programming languages for the operations in the clusters; and
executing the operations in the clusters in a programming language contained in the cluster-associated set of programming languages,
wherein at least one of the receiving, grouping, and executing are performed by one or more computers.
2. The method of claim 1 , the grouping the operations into clusters further comprising:
initializing the clusters so that each cluster encompasses one operation, wherein the cluster-associated set of programming languages matches the operation-associated set of programming languages for the encompassed operation;
iterating through the operations, and for each operation:
(1) setting a max gain to zero;
(2) setting a best cluster to null;
(3) determining a set of neighboring clusters for the operation, wherein the set of neighboring clusters are the clusters sharing a connection with the operation;
(4) iterating through the set of neighboring clusters, and for each neighboring cluster:
(a) determining a label intersection;
(b) determining a gain of moving;
(c) setting the max gain to the gain of moving and setting the best cluster to the neighboring cluster if the gain of moving is greater than the max gain and the label intersection is not null; and
(5) moving the operation to the best cluster if the max gain is greater than zero; and
repeating the initializing and iterating against an updated data processing pipeline derived from the prior iteration until an iteration occurs without modifying the clusters.
3. The method of claim 2 , the determining a label intersection further comprising:
calculating an intersection between the operation-associated set of programming languages associated for the operation and the cluster-associated set of programming languages for the neighboring cluster.
4. The method of claim 2 , the determining a gain of moving further comprising:
counting a number of internal connections added to the neighboring cluster if the operation moves to the neighboring cluster;
counting a number of internal connections lost if the operation moves to the neighboring cluster; and
calculating the gain of moving by subtracting the number of internal connections lost from the number of internal connections added.
5. The method of claim 2 , the moving the operation to the best cluster further comprising:
updating the cluster-associated set of programming languages for the best cluster by calculating an intersection of the operation-associated set of programming languages for the operation and the cluster-associated set of programming languages for the best cluster; and
updating the cluster-associated set of programming languages for the operation's prior cluster by calculating an intersection of the sets of programming languages for all operations remaining in the operation's prior cluster.
6. The method of claim 2 , wherein the updated data processing pipeline comprises operations set to the clusters determined during the previous iteration, connections between the operations set to the connections between the clusters determined during the previous iteration, and the operation-associated set of programming languages set to the cluster-associated set of programming languages determined during the previous iteration.
7. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
receive a data processing pipeline comprising operations and connections between the operations, wherein the operations are programmed in an operation-associated set of programming languages, and wherein the operations perform a transformational function on a set of data received by the data processing pipeline;
group the operations into clusters, wherein the clusters are each assigned a cluster-associated set of programming languages based on the operation-associated set of programming languages for the operations in the clusters; and
execute the operations in the clusters in a programming language contained in the cluster-associated set of programming languages.
8. The system of claim 7 , wherein to group the operations into clusters, the at least one processor is configured to:
initialize the clusters so that each cluster encompasses exactly one operation, wherein the cluster-associated set of programming languages matches the operation-associated set of programming languages for the encompassed operation;
iterate through the operations, and for each operation:
(1) set a max gain to zero;
(2) set a best cluster to null;
(3) determine a set of neighboring clusters for the operation, wherein the set of neighboring clusters are the clusters sharing a connection with the operation;
(4) iterate through the set of neighboring clusters, and for each neighboring cluster:
(a) determine a label intersection;
(b) determine a gain of moving;
(c) set the max gain to the gain of moving and set the best cluster to the neighboring cluster if the gain of moving is greater than the max gain and the label intersection is not null; and
(5) move the operation to the best cluster if the max gain is greater than zero; and
repeat the initialize and iterate steps against an updated data processing pipeline derived from the prior iteration until an iteration occurs without modifying the clusters.
9. The system of claim 8 , wherein to determine a label intersection, the at least one processor is configured to:
calculate an intersection between the operation-associated set of programming languages associated for the operation and the cluster-associated set of programming languages for the neighboring cluster.
10. The system of claim 8 , wherein to determine a gain of moving, the at least one processor is configured to:
count a number of internal connections added to the neighboring cluster if the operation moves to the neighboring cluster;
count a number of internal connections lost if the operation moves to the neighboring cluster; and
calculate the gain of moving by subtracting the number of internal connections lost from the number of internal connections added.
11. The system of claim 8 , wherein to move the operation, the at least one processor is configured to:
update the cluster-associated set of programming languages for the best cluster by calculating an intersection of the operation-associated set of programming languages for the operation and the cluster-associated set of programming languages for the best cluster; and
update the cluster-associated set of programming languages for the operation's prior cluster by calculating an intersection of the sets of programming languages for all operations remaining in the operation's prior cluster.
12. The system of claim 8 , wherein the updated data processing pipeline comprises operations set to the clusters determined during the previous iteration, connections between the operations set to the connections between the clusters determined during the previous iteration, and the operation-associated set of programming languages set to the cluster-associated set of programming languages determined during the previous iteration.
13. A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
receiving a data processing pipeline comprising operations and connections between the operations, wherein the operations are programmed in an operation-associated set of programming languages, and wherein the operations perform a transformational function on a set of data received by the data processing pipeline;
grouping the operations into clusters, wherein the clusters are each assigned a cluster-associated set of programming languages based on the operation-associated set of programming languages for the operations in the clusters; and
executing the operations in the clusters in a programming language contained in the cluster-associated set of programming languages.
14. The non-transitory computer-readable device of claim 13 , the grouping further comprising:
initializing the clusters so that each cluster encompasses exactly one operation, wherein the cluster-associated set of programming languages matches the operation-associated set of programming languages for the encompassed operation;
iterating through the operations, and for each operation:
(1) setting a max gain to zero;
(2) setting a best cluster to null;
(3) determining a set of neighboring clusters for the operation, wherein the set of neighboring clusters are the clusters sharing a connection with the operation;
(4) iterating through the set of neighboring clusters, and for each neighboring cluster:
(a) determining a label intersection;
(b) determining a gain of moving;
(c) setting the max gain to the gain of moving and setting the best cluster to the neighboring cluster if the gain of moving is greater than the max gain and the label intersection is not null; and
(5) moving the operation to the best cluster if the max gain is greater than zero; and
repeating the initializing and iterating against an updated data processing pipeline derived from the prior iteration until an iteration occurs without modifying the clusters.
15. The non-transitory computer-readable device of claim 14 , the determining a label intersection further comprising:
calculating an intersection between the operation-associated set of programming languages associated for the operation and the cluster-associated set of programming languages for the neighboring cluster.
16. The non-transitory computer-readable device of claim 14 , the determining a gain of moving further comprising:
counting a number of internal connections added to the neighboring cluster if the operation moves to the neighboring cluster;
counting a number of internal connections lost if the operation moves to the neighboring cluster; and
calculating the gain of moving by subtracting the number of internal connections lost from the number of internal connections added.
17. The non-transitory computer-readable device of claim 14 , the moving the operation to the best cluster further comprising:
updating the cluster-associated set of programming languages for the best cluster by calculating an intersection of the operation-associated set of programming languages for the operation and the cluster-associated set of programming languages for the best cluster; and
updating the cluster-associated set of programming languages for the operation's prior cluster by calculating an intersection of the sets of programming languages for all operations remaining in the operation's prior cluster.
18. The non-transitory computer-readable device of claim 14 , wherein the updated data processing pipeline comprises operations set to the clusters determined during the previous iteration, connections between the operations set to the connections between the clusters determined during the previous iteration, and the operation-associated set of programming languages set to the cluster-associated set of programming languages determined during the previous iteration.
19. The method of claim 1 , further comprising:
providing a data configuration tool that displays a visualization of the data processing pipeline comprising the operations used in the processing pipeline, the connections between the operations, and the operation-associated programming languages associated with the operations.
20. The system of claim 7 , wherein the at least one processor is configured to:
provide a data configuration tool that displays a visualization of the data processing pipeline comprising the operations used in the processing pipeline, the connections between the operations, and the operation-associated programming languages associated with the operations.