Patent ID: 8768929

Claim:
A system for clustering vertices in a streaming graph, comprising: a structural sampler comprising a processor configured to receive a stream of graph updates including insertions and deletions of edges and vertices to the streaming graph, the structural sampler comprising: a reservoir manager configured to receive the stream of graph updates and create a structural reservoir and a support reservoir, wherein the creation of the structural reservoir and support reservoir comprises: assigning a random ranking to each received edge; discarding each received edge with the random ranking greater than a sampling rate; and adding each of the received edges with the random ranking less than a sampling rate to the structural reservoir; and a graph manager configured to receive the structural reservoir from the reservoir manager and to create a sampled graph from the structural reservoir, wherein the sampled graph includes one or more clusters that each include one or more connected vertices, wherein creating 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.