# US 8,788,481 B2 · Method for processing stream data and system thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,481 B2
- Document ID: US8788481B2
- Status: Granted
- Kind: B2
- Application number: 13/778,255
- Filed: 2013-02-27
- Published: 2013-07-04
- Granted: 2014-07-22
- Earliest claimed: 2008-10-29
- Assignees: Hitachi, Ltd.
- Applicants: Hitachi, Ltd.
- Inventors: Tsuneyuki Imaki; Itaru Nishizawa; Toshihiko Kashiyama
- Web page: https://patentgrep.com/patent/US8788481B2

## CPC

- G06F 16/24542: {Plan optimisation}
- G06F 16/2453: Query optimisation
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A network interface receives stream data and a processor processes the stream data. The processor: constructs an operator graph comprising information regarding a plurality of operators for processing the stream data based on a query; assigns an operator execution order to the plurality of operators based on an inter-operator input and output relation, with respect to all of the operators on the operator graph; extracts a set of the operators that maintains the stream data assigned with a time stamp, a time of which is earlier than or equal to a reference time, in an input queue; and executes processing of the stream data assigned with the time stamp, having the earliest time, in the operator assigned a minimum operator graph execution order among the operators and maintaining the stream data assigned with the time stamp having the earliest time, among the extracted set of the operators.

## Claims

### Claim 1

A system for processing stream data based on a query, the system comprising:
a network interface that receives the stream data and a processor that processes the stream data,
wherein the processor:
constructs an operator graph comprising information regarding a plurality of operators for processing the stream data based on the query;
assigns an operator execution order to the plurality of operators based on an inter-operator input and output relation, with respect to all of the operators on the operator graph;
extracts a set of the operators that maintains the stream data assigned with a time stamp, a time of which is earlier than or equal to a reference time, in an input queue; and
executes processing of the stream data assigned with the time stamp, having the earliest time, in the operator assigned a minimum operator graph execution order among the operators and maintaining the stream data assigned with the time stamp having the earliest time, among the extracted set of the operators.

### Claim 2 (depends on 1)

The system for processing stream data according to claim 1,
wherein the processor, when the operator execution order is determined, simulates the operator graph to a directed graph having a directed side from an input side operator to an output side operator based on the inter-operator input and output relation, decomposes the directed graph into a set of strongly connected components, and determines whether the operator execution order assigned to all of the operators configuring an output side component is larger than the operator execution order assigned to any operator configuring an input side component, based on the inter-component input and output relation belonging to the set of the strongly connected components.

### Claim 3

A method for processing stream data based on a query, the method comprising the step of:
receiving stream data;
constructing an operator graph comprising information regarding a plurality of operators for processing the stream data based on the query;
assigning an operator execution order to the plurality of operators based on an inter-operator input and output relation, with respect to all of the operators on the operator graph;
extracting a set of the operators that maintains the stream data assigned with a time stamp, a time of which is earlier than or equal to a reference time, in a input queue; and
executing processing of the stream data assigned with the time stamp, having the earliest time, in the operator assigned a minimum operator graph execution order among the operators and maintaining the stream data assigned with the time stamp having the earliest time, among the extracted set of the operators.

### Claim 4 (depends on 3)

The method for processing stream data according to claim 3, further comprising the steps of:
when the operator execution order is determined, simulating the operator graph to a directed graph having a directed side from an input side operator to an output side operator based on the inter-operator input and output relation;
decomposing the directed graph into a set of strongly connected components; and
determining whether the operator execution order assigned to all of the operators configuring an output side component is larger than the operator execution order assigned to any operator configuring an input side component, based on the inter-component input and output relation belonging to the set of the strongly connected components.