QUERY RESULT ESTIMATION

• US 20130117257A1
• Filed: 11/03/2011
• Published: 05/09/2013
• Est. Priority Date: 11/03/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meijer, Henricus Johannes Maria, Isard, Michael, Stojanovic, Alexander Sasha, Carter-Schwendler, Carl, Toub, Stephen Harris
• Application Number:
  US13/288,947
• Publication Number:
  US 20130117257A1
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Techniques for efficiently performing queries are provided. A search component can receive a request for information based on data, and a management component can determine a degree of accuracy requested for the information. In turn, the search component can render the information based on the degree of accuracy requested. In an aspect, the search generates a query configured to determine the first information, and the management component instructs the search component to perform the query to a level of completion less than full completion when the degree of accuracy requested is below a predetermined threshold to cause the search component to render an estimation of the first information. In another aspect, a tracking component can track information associated with multiple query requests and an analysis determine and employ a related aspect of the tracked information to a new query request to determine an answer for a the new query request.

Claims

1. A method, comprising:

receiving, by a computing device, a request for information based on data;

generating a query configured to determine the information;

performing the query to a first level of completion less than a pre-defined full completion; and

determining a first estimation of the information based on the performing the first level of completion.

2. The method of claim 1, wherein the query comprises a computation based on N number of related functions, where N is an integer, and wherein the performing the query to the first level of completion comprises:

determining an estimated output of a first function; and

employing the estimated output of the first function in the computation.

3. The method of claim 2, wherein N is an integer greater than one, further comprising:

performing the query to a second level of completion less than the pre-defined full completion, including determining an estimated output of a second function and employing the estimated output of the second function and the first function in the computation; and

determining a second estimation of the information based on the performing the query to the second level of completion.

4. The method of claim 1, wherein the query comprises a computation based on N number of related functions, N is an integer, and the performing the query to the first level of completion comprises:

performing N−

M number of functions, wherein M is an integer and M<

N.

5. The method of claim 4, further comprising:

performing the query to a second level of completion, including performing N−

P number of functions, where P is an integer and M<

P<

N; and

determining a second estimation of the information based on the performing the query to the second level of completion.

6. The method of claim 1, wherein the query comprises a computation based on N number of related functions, where N is an integer, and wherein the performing the query to the first level of completion comprises:

determining a subset of the data; and

employing the subset of the data as input of at least one of the functions.

7. The method of claim 6, wherein the determining the subset of the data comprises determining an estimation of the subset of the data based on statistics associated with the data.

8. The method of claim 1, wherein the query comprises a computation based on N number of related functions, N is an integer greater than 1, and the performing the query to the first level of completion comprises:

performing the functions according to a priority order based on at least one of;

a time associated with the data, a cost associated with performing the function, a degree of accuracy associated with the first estimation of the information, or an efficiency associated with the determining the first estimation of the information.

9. The method of claim 1, wherein the performing the query to the first level of completion comprises:

receiving a control function; and

performing the query based on the control function.

10. The method of claim 9, wherein performing the query based on the control function includes performing the query based on at least one of:

a cost associated with performing the query, a resource constraint associated with performing the query, a duration of time associated with performing the query, a degree of accuracy associated with first estimation of the information, a confidence level associated with the first estimation of the information, or a speed associated with determining the first estimation of the information.

11. A system, comprising:

a memory having computer executable components stored thereon; and

a processor communicatively coupled to the memory, the processor configured to facilitate execution of the computer executable components, the computer executable components, comprising;

a search component configured to receive a request for first information based on data; and

a management component configured to determine a degree of accuracy requested for the first information, and wherein the search component is further configured to render the first information based on the degree of accuracy requested.

12. The system of claim 11, wherein the search component is further configured to generate a query configured to determine the first information, wherein the management component is configured to instruct the search component to perform the query to a level of completion less than a pre-defined full completion in response to the degree of accuracy requested being below a predetermined threshold, and wherein the search component is configured to render an estimation of the first information.

13. The system of claim 12, wherein the management component is configured to instruct the search component to perform the query to the level of completion less than the pre-defined full completion based on at least one of a duration of time associated with performing the query, a cost associated with performing the query, or a resource constraint associated with performing the query, and wherein the search component is configured to render an estimation of the first information.

14. The system of claim 12, wherein the query comprises a computation based on N number of related functions, N is an integer, and the management component is configured to instruct the search component to sample the data to determine an estimated input for at least one of the functions and to perform the query computation with the at least one estimated input.

15. The system of claim 12, where the management component is further configured to instruct the search component to perform the query to the pre-defined full completion in response to the degree of accuracy requested being above the predetermined threshold, and wherein the search component is configured to render the first information.

16. The system of claim 11, wherein the search component is further configured to receive multiple requests for additional information based on the data, and wherein the search component is configured to generate and perform queries to determine either the additional information or an estimation of the additional information, the system further comprising:

a tracking component configured to track query information associated with the queries.

17. The system of claim 16, further comprising

an analysis component configured to determine a correlation between the request for the first information and the query information, and wherein the search component is configured to employ the query information to determine the first information or an estimation of the first information based on the degree of accuracy requested for the first information.

18. A computer-readable storage medium comprising computer-readable instructions that, in response to execution, cause a computing system to perform operations, comprising:

receiving a request for information based on data;

generating a query configured to determine the information;

performing the query to a first level of completion less than the pre-defined full completion; and

determining a first estimation of the information based on the performing the query to the first level of completion.

19. The computer-readable storage medium of claim 18, wherein the query comprises a computation based on N number of related functions, N is an integer, and the performing the query to the first level of completion comprises:

determining an estimated output of a first function; and

employing the estimated output of the first function in the computation.

20. The computer-readable storage medium of claim, where N is an integer greater than one, further comprising operations for:

performing the query to a second level of completion, including determining an estimated output of a second function and employing the estimated output of the second function and the first function in the computation; and

determining a second estimation of the information based on the performing the query to the second level of completion.