Patent ID: 8635224

Claim:
A method for identifying one or more clusters in a streaming graph, the method comprising: receiving a stream of graph updates including insertions deletions of edges and vertices to the streaming graph; sampling, with a processor, the stream of graph updates to create a structural reservoir and support reservoir; creating a sampled graph from the structural reservoir; and identifying the one or more clusters in the sampled graph by grouping one or more connected vertices in the sampled graph, wherein the creating of the structural reservoir comprises: assigning a random ranking to each received graph update; discarding each received graph update with the random ranking greater than a sampling percentage; and adding each of the received graph update with the random ranking less than the sampling percentage to the structural reservoir, and wherein creating of the structural reservoir further comprises based on determining that adding a graph update to the structural reservoir caused the one or more clusters of the sampled graph have a size that exceeds the maximum cluster size, moving one or more graph updates from the structural reservoir to the support reservoir.