ADAPTIVE SAMPLING SCHEMES FOR CLUSTERING STREAMING GRAPHS

• US 20150261886A1
• Filed: 03/13/2014
• Published: 09/17/2015
• Est. Priority Date: 03/13/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: WU, KUN-LUNG, XIA, YINGLONG
• Granted Patent: US 9,886,521 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method for clustering vertices of streaming graphs includes: maintaining one or more clusters, assigning a random number to an incoming edge, computing a sampling threshold based on the current clusters, and adjusting the current clusters based on the random number and the sampling threshold.

Claims

1. A method for clustering a streaming graph, the method comprising:

maintaining one or more clusters;

assigning a random number to an incoming edge;

computing a sampling threshold based on the current clusters; and

adjusting the current clusters based on the random number and the sampling threshold.

2. The method of claim 1, wherein the maintaining of the one or more clusters comprises:

maintaining an intra-cluster graph structure for each cluster; and

maintaining inter-cluster edges for each pair of clusters.

3. The method of claim 2, wherein the maintaining of the intra-cluster graph structure comprises:

maintaining a spanning tree for a corresponding cluster that corresponds to part of the vertices of the cluster; and

maintaining the remaining vertices of the corresponding cluster not included in the tree.

4. The method of claim 1, wherein the adjusting is based on a fixed upper bound on the number of vertices allowed in each cluster.

5. The method of claim 4, wherein the computing the sampling threshold comprises setting the sampling threshold to a value based on a size of the current clusters and the upper bound.

6. The method of claim 5, wherein the computing the sampling threshold comprises:

decreasing the value when the sizes of most of the clusters is between a threshold and the upper bound, where the threshold is less than the upper bound; and

increasing the value when the sizes of most of the clusters is below the threshold.

7. The method of claim 1, wherein adjusting the clusters comprises:

inserting the incoming edge into the current clusters if the random number is less than the sampling threshold; and

discarding the incoming edge if the random number is not less than the sampling threshold.

8. The method of claim 7, wherein the inserting of the incoming edge comprises:

identifying cluster identifiers (IDs) of clusters corresponding to two vertices of the incoming edge; and

merging two clusters corresponding to the IDs when the cluster IDs are different and a number of inter-cluster edges between the clusters exceeds a threshold.

9. The method of claim 1, further comprises:

computing a new random number when a given edge of the existing clusters was previously sampled using a previous sampling threshold greater than the computed sampling threshold; and

performing one of removing or retaining of the given edge based on the random number.

10. The method of claim 9, wherein the performing comprises:

determining a value by dividing the computed sampling threshold by the previous sampling threshold;

retaining the given edge when the new random number is less than the value; and

deleting the given edge when the new random number is not less than the value.

11. The method of claim 1, wherein the incoming edge represents a computer message exchanged between a first user and a second user.

12. A system to manage clustering a streaming graph, the system comprising:

a memory comprising a computer program and a data structure storing one or more clusters; and

a processor configured to execute the program to adjust the clusters in response to an incoming edge by assigning a random number to the edge, computing a sampling threshold based on the current clusters, and adjusting the current clusters based on the random number and the sampling threshold.

13. The system of claim 12, wherein the data structure maintains an intra-cluster graph structure for each cluster and inter-cluster edges for each pair of clusters.

14. The system of claim 13, wherein the data structure further maintains a spanning tree for a corresponding cluster that corresponds to part of the vertices of the cluster and the remaining vertices of the corresponding cluster not included in the tree.

15. The system of claim 12, wherein the program adjusts the clusters based on a fixed upper bound on the number of vertices allowed in each cluster.

16. The system of claim 15, wherein the program computes the sampling threshold setting the sampling threshold to a value based on a size of the current clusters and the upper bound.

17. The system of claim 16, wherein the program computes the sampling threshold by decreasing the value when the sizes of most of the clusters is between a threshold less than the upper bound and the upper bound and increasing the value when the sizes of most of the clusters is below the threshold.

18. The system of claim 12, wherein the program adjusts the clusters by inserting the incoming edge into the current clusters if the random number is less than the sampling threshold and discarding the incoming edge if the random number is not less than the sampling threshold.

19. The system of claim 18, wherein the program inserts the incoming edge by identifying cluster identifiers (IDs) of clusters corresponding to two vertices of the incoming edge and merging two clusters corresponding to the IDs when the cluster IDs are different and a number of inter-cluster edges between the clusters exceeds a threshold.

20. The system of claim 12, wherein the program computes a new random number when a given edge of the existing clusters was previously sampled using a previous sampling threshold greater than the computed sampling threshold and performs one of removing or retaining of the given edge based on the random number.

22. The system of claim 12, wherein the incoming edge represents a computer message exchanged between a first user and a second user.

21. The system of claim 21, wherein the program determines a value by dividing the computed sampling threshold by the previous sampling threshold, retains the given edge when the new random number is less than the value, and deletes the given edge when the new random number is not less than the value.

23. A method for clustering vertices of a streaming graph, the method comprising:

assigning a random number to an incoming edge;

computing a sampling threshold based on existing clusters of the graph;

inserting the incoming edge into the existing clusters if the random number is less than the sampling threshold; and

discarding the incoming edge if the random number is not less than the sampling threshold.

24. The method of claim 23, further comprises:

computing a new random number when a given edge of the existing clusters was previously sampled using a previous sampling threshold greater than the computed sampling threshold; and

performing one of removing or retaining of the given edge based on the random number.

25. The method of claim 23, wherein the inserting of the incoming edge comprises:

identifying cluster identifiers (IDs) of clusters corresponding to two vertices of the incoming edge; and

merging two clusters corresponding to the IDs when the cluster IDs are different and a number of inter-cluster edges between the clusters exceeds a threshold.