  Many dynamic applications are built upon large network infrastructures, such
as social networks, communication networks, biological networks and the Web.
Such applications create data that can be naturally modeled as graph streams,
in which edges of the underlying graph are received and updated sequentially in
a form of a stream. It is often necessary and important to summarize the
behavior of graph streams in order to enable effective query processing.
However, the sheer size and dynamic nature of graph streams present an enormous
challenge to existing graph management techniques. In this paper, we propose a
new graph sketch method, gSketch, which combines well studied synopses for
traditional data streams with a sketch partitioning technique, to estimate and
optimize the responses to basic queries on graph streams. We consider two
different scenarios for query estimation: (1) A graph stream sample is
available; (2) Both a graph stream sample and a query workload sample are
available. Algorithms for different scenarios are designed respectively by
partitioning a global sketch to a group of localized sketches in order to
optimize the query estimation accuracy. We perform extensive experimental
studies on both real and synthetic data sets and demonstrate the power and
robustness of gSketch in comparison with the state-of-the-art global sketch
method.
