Query optimization over graph data streams

1. A method for executing a query on a graph data stream, the method comprising the steps of:

accessing a graph data stream, the graph data stream comprising data representing edges that connect vertices of a graph;

constructing a plurality of synopsis data structures based on at least a subset of the graph data stream, wherein each vertex connected to an edge represented within the subset of the graph data stream is assigned to a synopsis data structure such that each synopsis data structure represents a corresponding section of the graph data stream;

mapping each received edge represented within the graph data stream onto the synopsis data structure which corresponds to the section of the graph data stream which includes that edge; and

using the plurality of synopsis data structures to execute a frequency query on the graph data stream, wherein executing a frequency query comprises estimating a frequency of one or more edges in the data stream graph using the synopsis data structures, wherein estimating comprises determining an aggregate frequency of edges in one or more synopsis data structures;

wherein the constructing, mapping and using steps are executed on a computing system comprising a processor and a memory, wherein one or more software modules for implementing the constructing, mapping and using steps are loaded from the memory and executed by the processor.

2. The method of claim 1 , wherein the plurality of synopsis data structures comprise sketch tables.

3. The method of claim 1 , wherein the plurality of synopsis data structures comprise hash-based sketch data structures.

4. The method of claim 1 , wherein each edge represented within the graph data stream but not within the subset of the graph data stream is mapped onto a given one of the plurality of synopsis data structures.

5. The method of claim 1 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures based at least in part on an aggregate frequency of the edges connected to each of the one or more vertices.

6. The method of claim 5 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures so as to minimize an objective error function.

7. The method of claim 1 , wherein constructing the plurality of synopsis data structures comprises constructing a partition decision tree.

8. The method of claim 7 , wherein each leaf of the partition decision tree corresponds to a given one of the plurality of synopsis data structures.

9. The method of claim 7 , wherein an objective error function is minimized at each level of the partition decision tree.

10. The method of claim 1 , wherein constructing the plurality of synopsis data structures comprises assigning a relative weight to a given vertex based on a relative frequency of at least one edge connected to the given vertex being used in a given query.

11. The method of claim 1 , wherein mapping the received edge onto the corresponding synopsis data structure comprises storing data representative of the received edge within the corresponding synopsis data structure.

12. The method of claim 1 , wherein mapping the received edge onto the corresponding synopsis data structure comprises incrementing one or more values stored within the corresponding synopsis data structure.

13. An apparatus for executing a query on a graph data stream, the apparatus comprising:

a memory; and

a processor operative to perform the steps of:

accessing a graph data stream, the graph data stream comprising data representing edges that connect vertices of a graph;

constructing a plurality of synopsis data structures based on at least a subset of the graph data stream, wherein each vertex connected to an edge represented within the subset of the graph data stream is assigned to a synopsis data structure such that each synopsis data structure represents a corresponding section of the graph data stream;

mapping each received edge represented within the graph data stream onto the synopsis data structure which corresponds to the section of the graph data stream which includes that edge; and

using the plurality of synopsis data structures to execute a frequency query on the graph data stream, wherein executing a frequency query comprises estimating a frequency of one or more edges in the data stream graph using the synopsis data structures, wherein estimating comprises determining an aggregate frequency of edges in one or more synopsis data structures.

14. The apparatus of claim 13 , wherein the plurality of synopsis data structures comprise sketch tables.

15. The apparatus of claim 13 , wherein each edge represented within the graph data stream but not within the subset of the graph data stream is mapped onto a given one of the plurality of synopsis data structures.

16. The apparatus of claim 13 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures based at least in part on an aggregate frequency of the edges connected to each of the one or more vertices.

17. The apparatus of claim 13 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures so as to minimize an objective error function.

18. The apparatus of claim 13 , wherein constructing the plurality of synopsis data structures comprises constructing a partition decision tree.

19. A computer program product comprising a tangible, non-signal, computer readable recordable storage medium including computer usable program code for executing a query on a graph data stream, the computer program product comprising:

computer usable program code for accessing a graph data stream, the graph data stream comprising data representing edges that connect vertices of a graph;

computer usable program code for constructing a plurality of synopsis data structures based on at least a subset of the graph data stream, wherein each vertex connected to an edge represented within the subset of the graph data stream is assigned to a synopsis data structure such that each synopsis data structure represents a corresponding section of the graph data stream;

computer usable program code for mapping each received edge represented within the graph data stream onto the synopsis data structure which corresponds to the section of the graph data stream which includes that edge; and

computer usable program code for using the plurality of synopsis data structures to execute a frequency query on the graph data stream, wherein executing a frequency query comprises estimating a frequency of one or more edges in the data stream graph using the synopsis data structures, wherein estimating comprises determining an aggregate frequency of edges in one or more synopsis data structures.

20. The computer program product of claim 19 , wherein the plurality of synopsis data structures comprise sketch tables.

21. The computer program product of claim 19 , wherein each edge represented within the graph data stream but not within the subset of the graph data stream is mapped onto a given one of the plurality of synopsis data structures.

22. The computer program product of claim 19 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures based at least in part on an aggregate frequency of the edges connected to each of the one or more vertices.

23. The computer program product of claim 19 , wherein the one or more vertices are assigned to a given one of the plurality of synopsis data structures so as to minimize an objective error function.

24. The computer program product of claim 19 , wherein constructing the plurality of synopsis data structures comprises constructing a partition decision tree.