Optimized data stream management system

• US 8,762,369 B2
• Filed: 05/10/2011
• Issued: 06/24/2014
• Est. Priority Date: 05/10/2011
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Macho, David Manzano, Pallares Lopez, Miguel Angel
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US14/113,555
• Publication Number:
  US 20140052729A1
• Time in Patent Office: 1,141 Days
• Field of Search: 707/706, 707/722, 707769-770
• US Class Current: 707/722
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/95 Retrieval from the web

Abstract

A continuous query result estimator for use in a data stream management system. The data stream management system configured to execute a continuous query against data items received via at least one input data stream to generate at least one output data stream. The continuous query result estimator comprises a classification module configured to classify a set of at least one data item received via the at least one input data stream into one of a plurality of input data groups. A data store configured to store a respective rule for estimating a result of executing the continuous query against a data item belonging to the input data group. The continuous query result estimator also includes a result estimation module configured to select a rule from the rules stored in the data store on the basis of the classification performed by the classification module.

Claims

1. A continuous query result estimator for use in a data stream management system to reduce data stream processing times, the data stream management system being configured to execute a continuous query against data items received via at least one input data stream to generate at least one output data stream, the continuous query result estimator comprising:

a classification module configured to classify a set of at least one data item received via the at least one input data stream into one of a plurality of input data groups;

a data store configured to store, in association with each of the input data groups, a respective rule for estimating a result of executing the continuous query against a data item belonging to the input data group; and

a result estimation module configured to;

select a rule from the rules stored in the data store on the basis of the classification performed by the classification module; and

apply the selected rule to the received set of data items to generate an estimate for a result of executing the continuous query against the received set of data items.

2. The continuous query result estimator according to claim 1, further comprising:

a control module configured to;

detect an absence of at least one expected data value in the received set of data items; and

upon detecting an absence of at least one expected data value in the received set of data items, trigger the classification of the received set of data items by the classification module.

3. The continuous query result estimator according to claim 1, further comprising:

a control module configured to execute a first detection of an absence of at least one expected data value in the received set of data items, and a second detection of the absence of at least one expected data value in the received set of data items after a prescribed time interval from the first detection and, if at least expected data values are determined in the second detection to be missing, trigger the classification of the received set of data items by the classification module.

4. The continuous query result estimator according to claim 2, wherein the control module is configured to trigger the classification of the received set of data items by the classification module when one of a number and a proportion of expected data values determined to be missing from the received set of data items is one of at and below a threshold value.

5. The continuous query result estimator according to claim 1, further comprising a learning module configured to:

generate the rules on a basis of received data items and results of executing the continuous query against the received data items; and

store the rules in the data store.

6. The continuous query result estimator according to claim 1, wherein the classification module is configured to:

classify the received set of data items by calculating for each of the input data groups a respective value of a similarity measure using the received set of data items, and

select an input data group on the basis of the calculated similarity measure values.

7. The continuous query result estimator according to claim 1, wherein each of the rules comprises a decision tree whose branches can be navigated to arrive at the estimate of the result of executing the continuous query based on values of the received set of data items.

18. The continuous query result estimator according to claim 3, wherein the control module is configured to trigger the classification of the received set of data items by the classification module when one of a number and a proportion of expected data values determined to be missing from the received set of data items is one of at and below a threshold value.

19. The continuous query result estimator according to claim 18, wherein the classification module is configured to:

classify the received set of data items by calculating for each of the input data groups a respective value of a similarity measure using the received set of data items, and

select an input data group on the basis of the calculated similarity measure values.

8. A data stream management system comprising:

a continuous query processor configured to execute a continuous query against data items received via at least one input data stream to produce at least one output data stream; and

a continuous query result estimator including;

a classification module configured to classify a set of at least one data item received via the at least one input data stream into one of a plurality of input data groups;

a data store configured to store, in association with each of the input data groups, a respective rule for estimating a result of executing the continuous query against a data item belonging to the input data group; and

a result estimation module configured to;

select a rule from the rules stored in the data store on the basis of the classification performed by the classification module; and

apply the selected rule to the received set of data items to generate an estimate for a result of executing the continuous query against the received set of data items;

the continuous query processor and the continuous query result estimator are configured such that the continuous query is executed against the received set of data items in the case where the classification module of the continuous query result estimator does not classify the received set of data items into one of the plurality of input data groups, the estimate of the continuous query execution result being generated in the case where the classification module classifies the received set of data items into one of the plurality of input data groups.

9. The data stream management system according to claim 8, wherein the continuous query result estimator further comprises:

a learning module; and

a missing data value calculator operable configured to generate an estimate of at least one missing data value when the control module detects an absence of at least one expected data value in the received set of data items,

wherein the continuous query processor is configured to;

execute the continuous query against received set of data items and estimates for the missing at least one data value generated by the missing data value calculator; and

feed the results of executing the continuous query back to the learning module; and

wherein the learning module is configured to;

generate the rules on the basis of received data items and the results fed back by the continuous query processor; and

store the rules in the data store.

10. A method of estimating a result of a continuous query in a data stream management system to reduce data stream processing times therein, the data stream management system being operable configured to execute the continuous query against data items received via at least one input data stream to produce at least one output data stream, the method comprising:

classifying a set of at least one data item received via the at least one input data stream into one of a plurality of input data groups;

storing in a data store, in association with each of the input data groups, a respective rule for estimating a result of executing the continuous query against a data item belonging to the input data group; and

selecting a rule from the rules stored in the data store on the basis of the classification; and

applying the selected rule to the received set of data items to generate an estimate for a result of executing the continuous query against the received set of data items.

11. The method according to claim 10, further comprising:

detecting an absence of at least one expected data value in the received set of data items; and

upon detecting an absence of at least one expected data values in the received set of data items, triggering the classification of the received set of data items.

12. The method according to claim 10, further comprising:

executing a first detection of an absence of at least one expected data value in the received set of data items, and a second detection of the absence of at least one expected data value in the received set of data items after a prescribed time interval from the first detection; and

if at least one expected data value are determined in the second detection to be missing, triggering the classification of the received set of data items.

13. The method according to claim 11, wherein the classification of the received set of data items is triggered when one of a number and a proportion of expected data values determined to be missing from the received set of data items is one of at and below a threshold value.

14. The method according to claim 10, further comprising:

generating the rules on the basis of received sets of one or more data items and results of executing the continuous query against the sets of data items, and storing the rules in the data store.

15. The method according to claim 10, wherein the set of received data items is classified by calculating for each of the input data groups a respective value of a similarity measure using the received data items, and selecting an input data group on the basis of the calculated similarity measure values.

16. The method according to claim 10, wherein each of the rules comprises a decision tree whose branches can be navigated to arrive at the estimate of the result of executing the continuous query based on values of the received set of data items.

20. The method according to claim 12, wherein the set of received data items is classified by calculating for each of the input data groups a respective value of a similarity measure using the received data items, and selecting an input data group on the basis of the calculated similarity measure values.

17. A computer-readable storage medium storing computer program instructions which, when executed by a processor, cause the processor to:

classify a set of at least one data item received via at least one input data stream into one of a plurality of input data groups;

cause storage of, in a data store and in association with each of the input data groups, a respective rule for estimating a result of executing a continuous query against a data item belonging to the input data group;

select a rule from the rules stored in the data store on the basis of the classification; and

apply the selected rule to the received set of data items to generate an estimate for a result of executing the continuous query against the received set of data items.