gSketch: On Query Estimation in Graph Streams

Details gSketch: On Query Estimation in Graph Streams gSketch: On Query Estimation in Graph Streams

2011-11-30

arxiv.org/abs/1111.7167v1

Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 3, pp. 193-204 (2011)

Computer Science

Databases

VLDB2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

gSketch: On Query Estimation in Graph Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with gSketch: On Query Estimation in Graph Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and gSketch: On Query Estimation in Graph Streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8583