Dynamically generating pre-aggregated datasets

• US 9,430,519 B1
• Filed: 07/26/2013
• Issued: 08/30/2016
• Est. Priority Date: 08/20/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cai, Chao, Ewald, Eric W., Tangney, Cameron M., Nandy, Sagnik
• Primary Examiner(s): Vu, Bai D.
• Application Number:
  US13/951,770
• Time in Patent Office: 1,131 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06Q 30/0242 Determining effectiveness of advertisements

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for dynamically generating and configuring pre-aggregated datasets optimized for responding to particular types of data requests made against a large sub-optimal multidimensional dataset are disclosed. A dynamic aggregator monitors the query types and response latencies associated with queries made against the large multidimensional dataset. The dynamic aggregator defines pre-aggregated datasets based on the types of queries received from users and calculates a respective benefit score for each pre-aggregated dataset. The benefit score of each pre-aggregated dataset can be based on the recorded latencies and query count for the pre-aggregated dataset. The dynamic aggregator can decide whether to generate and/or maintain particular pre-aggregated datasets based on the current values of the benefit scores associated with the particular pre-aggregated datasets.

Claims

1. A computer-implemented method performed by one or more data processing apparatus, comprising:

receiving one or more requests for a first type of performance measure;

identifying, based on the one or more requests and from a dataset, a proper subset of data used to determine a value for the first type of performance measure;

determining the value based on the proper subset of data;

determining a first latency specifying an amount of time that was required to determine the value using the dataset;

defining a pre-aggregated dataset that includes the proper subset of data from the dataset;

calculating a benefit score for the pre-aggregated dataset based on a difference between the first latency and a second latency specifying an amount of time required to respond to the request using the pre-aggregated dataset;

adjusting the benefit score as a rate of received queries for the first type of performance measure changes over time;

determining, at a given time, that the adjusted benefit score meets a threshold value; and

storing the pre-aggregated dataset in response to determining that the benefit score meets the threshold value.

2. The method of claim 1, comprising:

receiving a second request for a second type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the second type of performance measure lowers a latency for responding to the second request relative to a latency for responding to the second request using the dataset to determine the value for the second type of performance measure; and

increasing the benefit score for the pre-aggregated dataset in response to determining that using the pre-aggregated dataset to determine the value for the second type of performance measure lowers the latency for responding to the second request.

3. The method of claim 2, wherein determining that the benefit score meets the threshold value comprises determining that the increased benefit score meets the threshold value.

4. The method of claim 1, comprising:

receiving, after storing the pre-aggregated dataset, a different request for a different type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the different type of performance measure lowers a latency for responding to the different request relative to a latency for responding to the different request using the dataset;

determining, in response to the determination that using the pre-aggregated dataset lowers the latency relative to using the dataset, the value for the different type of performance measure using the pre-aggregated dataset; and

providing the value for the different type of performance measure in response to the different request.

5. The method of claim 1, comprising:

updating the pre-aggregated dataset using data newly added to the dataset;

determining an amount of resources required for storing and maintaining the pre-aggregated dataset based on resources used for updating the pre-aggregated dataset and storing the updated pre-aggregated dataset; and

decreasing the benefit score for the pre-aggregated dataset based on the amount of resources required for storing and maintaining the pre-aggregated dataset.

6. The method of claim 5, comprising:

determining that the decreased benefit score is below the threshold value; and

discarding the pre-aggregated dataset in response to determining that the decreased benefit score is below the threshold value.

7. The method of claim 1, wherein the first type of performance measure includes one of a measure of a specified type of user interaction or a financial value associated with a specified type of user interaction.

8. A non-transitory computer readable medium storing instructions that cause one or more data processing apparatus to perform operations comprising:

receiving one or more requests for a first type of performance measure;

identifying, based on the one or more requests and from a dataset, a proper subset of data used to determine a value for the first type of performance measure;

determining the value based on the proper subset of data;

determining a first latency specifying an amount of time that was required to determine the value using the dataset;

defining a pre-aggregated dataset that includes the proper subset of data from the dataset;

calculating a benefit score for the pre-aggregated dataset based on a difference between the first latency and a second latency specifying an amount of time required to respond to the request using the pre-aggregated dataset;

adjusting the benefit score as a rate of received queries for the first type of performance measure changes over time;

determining, at a given time, that the adjusted benefit score meets a threshold value; and

storing the pre-aggregated dataset in response to determining that the benefit score meets the threshold value.

9. The computer readable medium of claim 8, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

receiving a second request for a second type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the second type of performance measure lowers a latency for responding to the second request relative to a latency for responding to the second request using the dataset to determine the value for the second type of performance measure; and

increasing the benefit score for the pre-aggregated dataset in response to determining that using the pre-aggregated dataset to determine the value for the second type of performance measure lowers the latency for responding to the second request.

10. The computer readable medium of claim 9, wherein determining that the benefit score meets the threshold value comprises determining that the increased benefit score meets the threshold value.

11. The computer readable medium of claim 8, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

receiving, after storing the pre-aggregated dataset, a different request for a different type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the different type of performance measure lowers a latency for responding to the different request relative to a latency for responding to the different request using the dataset;

determining, in response to the determination that using the pre-aggregated dataset lowers the latency relative to using the dataset, the value for the different type of performance measure using the pre-aggregated dataset; and

providing the value for the different type of performance measure in response to the different request.

12. The computer readable medium of claim 8, wherein the one or more data processing apparatus to perform operations comprising:

updating the pre-aggregated dataset using data newly added to the dataset;

determining an amount of resources required for storing and maintaining the pre-aggregated dataset based on resources used for updating the pre-aggregated dataset and storing the updated pre-aggregated dataset; and

decreasing the benefit score for the pre-aggregated dataset based on the amount of resources required for storing and maintaining the pre-aggregated dataset.

13. The computer readable medium of claim 12, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

determining that the decreased benefit score is below the threshold value; and

discarding the pre-aggregated dataset in response to determining that the decreased benefit score is below the threshold value.

14. A system, comprising:

a data store storing a dataset associated with one or more types of performance measures; and

one or more processors that interact with the data store and execute instructions that cause the one or more data processing apparatus to perform operations comprising;

receiving one or more requests for a first type of performance measure;

identifying, based on the one or more requests and from a dataset, a proper subset of data used to determine a value for the first type of performance measure;

determining the value based on the proper subset of data;

determining a first latency specifying an amount of time that was required to determine the value using the dataset;

defining a pre-aggregated dataset that includes the proper subset of data from the dataset;

calculating a benefit score for the pre-aggregated dataset based on a difference between the first latency and a second latency specifying an amount of time required to respond to the request using the pre-aggregated dataset;

adjusting the benefit score as a rate of received queries for the first type of performance measure changes over time;

determining, at a given time, that the adjusted benefit score meets a threshold value; and

storing the pre-aggregated dataset in response to determining that the benefit score meets the threshold value.

15. The system of claim 14, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

receiving a second request for a second type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the second type of performance measure lowers a latency for responding to the second request relative to a latency for responding to the second request using the dataset to determine the value for the second type of performance measure; and

increasing the benefit score for the pre-aggregated dataset in response to determining that using the pre-aggregated dataset to determine the value for the second type of performance measure lowers the latency for responding to the second request.

16. The system of claim 15, wherein determining that the benefit score meets the threshold value comprises determining that the increased benefit score meets the threshold value.

17. The system of claim 14, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

receiving, after storing the pre-aggregated dataset, a different request for a different type of performance measure;

determining that using the pre-aggregated dataset to determine a value for the different type of performance measure lowers a latency for responding to the different request relative to a latency for responding to the different request using the dataset;

determining, in response to the determination that using the pre-aggregated dataset lowers the latency relative to using the dataset, the value for the different type of performance measure using the pre-aggregated dataset; and

providing the value for the different type of performance measure in response to the different request.

18. The system of claim 14, wherein the one or more data processing apparatus to perform operations comprising:

updating the pre-aggregated dataset using data newly added to the dataset;

determining an amount of resources required for storing and maintaining the pre-aggregated dataset based on resources used for updating the pre-aggregated dataset and storing the updated pre-aggregated dataset; and

decreasing the benefit score for the pre-aggregated dataset based on the amount of resources required for storing and maintaining the pre-aggregated dataset.

19. The system of claim 18, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

determining that the decreased benefit score is below the threshold value; and

discarding the pre-aggregated dataset in response to determining that the decreased benefit score is below the threshold value.

20. The system of claim 14, wherein the first type of performance measure includes one of a measure of a specified type of user interaction or a financial value associated with a specified type of user interaction.