Patent ID: 8392398
Filing Date: 2013-03-05
Classification: G06F

Abstract:
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.