Learning-based method for estimating cost and statistics of complex operators in continuous queries

• US 20060100969A1
• Filed: 11/08/2004
• Published: 05/11/2006
• Est. Priority Date: 11/08/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Padmanabhan, Sriram K., Wang, Min, Gao, Like
• Application Number:
  US10/984,323
• Publication Number:
  US 20060100969A1
• Time in Patent Office: Days
• US Class Current: 705/400
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

A learning-based method for estimating costs or statistics of an operator in a continuous query includes a cost estimation model learning procedure and a model applying procedure. The model learning procedure builds a cost estimation model from training data, and the applying procedure uses the model to estimate the cost associated with a given query. The learning procedure uses a feature extractor and a cost estimator. The feature extractor collects relevant training data and obtains feature values. The extracted feature values are associated with costs and used to create the cost estimator. When applying the cost estimator to a continuous stream of data, the feature extractor extracts feature values from the data stream and uses the extracted feature values as inputs into the cost estimator to obtain the desired cost values.

Claims

1. A method for estimating costs for continuous queries over streaming data, the method comprising:

creating a query cost estimator capable of associating costs to features in a stream of data for a continuous query; and

applying the cost estimator to the features in one or more streams of data to estimate costs associated with conducting the continuous query over the streams of data.

2. The method of claim 1, wherein the step of creating the cost estimator comprises:

identifying a method for use in creating the cost estimator; and

providing training data in accordance with the identified method to be used in creating the cost estimator.

3. The method of claim 2, wherein the method for use in creating the cost estimator comprises a learning-based method and the step of providing training data comprises providing data from historical runs of the continuous query, the data comprising feature values and associated costs.

4. The method of claim 2, further comprising converting the training data into a form suitable for use in the identified method for creating the cost estimator.

5. The method of claim 4, wherein the step of converting the training data comprises using discrete Fourier transformation to generate approximations of the training data.

6. The method of claim 2, further comprising:

extracting relevant feature values from the training data;

associating costs with the relevant feature values; and

using the extracted feature values and associated costs to create the cost estimator.

7. The method of claim 1, wherein the step of applying the cost estimator comprises accessing a stream of data, extracting relevant feature values from the stream of data and inputting the extracted feature values into the cost estimator to derive the associated costs.

8. The method of claim 1, further comprising using the estimated cost in conducting the continuous query.

9. The method of claim 8, wherein the step of using the estimated cost comprises conducting the continuous query on features in the data stream inversely by estimated cost.

10. A computer readable medium containing a computer executable code that when read by a computer causes the computer to perform a method for estimating costs in continuous queries over streaming data, the method comprising:

creating a query cost estimator capable of associating costs to features in a stream of data for a continuous query; and

applying the cost estimator to the features in one or more streams of data to estimate costs associated with conducting the continuous query over the streams of data.

11. The computer readable medium of claim 10, wherein the step of creating the cost estimator comprises:

identifying a method for use in creating the cost estimator; and

providing training data in accordance with the identified method to be used in creating the cost estimator.

12. The computer readable medium of claim 11, wherein the method for use in creating the cost estimator comprises a learning-based method and the step of providing training data comprises providing data from historical runs of the continuous query, the data comprising feature values and associated costs.

13. The computer readable medium of claim 11, further comprising converting the training data into a form suitable for use in the identified method for creating the cost estimator.

14. The computer readable medium of claim 13, wherein the step of converting the training data comprises using discrete Fourier transformation to generate approximations of the training data.

15. The computer readable medium of claim 11, further comprising:

extracting relevant feature values from the training data;

associating costs with the relevant feature values; and

using the extracted feature values and associated costs to create the cost estimator.

16. The computer readable medium of claim 10, wherein the step of applying the cost estimator comprises accessing a stream of data, extracting relevant feature values from the stream of data and inputting the extracted feature values into the cost estimator to derive the associated costs.

17. The computer readable medium of claim 10, further comprising using the estimated cost in conducting the continuous query.

18. The computer readable medium of claim 17, wherein the step of using the estimated cost comprises conducting the continuous query on features in the data stream inversely by estimated cost.