Dynamically generating pre-aggregated datasets

• US 10,216,805 B1
• Filed: 08/11/2016
• Issued: 02/26/2019
• Est. Priority Date: 08/20/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Cai, Chao, Ewald, Eric W., Tangney, Cameron M., Nandy, Sagnik
• Primary Examiner(s): Vu, Bai D
• Application Number:
  US15/234,840
• Time in Patent Office: 929 Days
• Field of Search: None
• 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 that is calculated based on a proper subset of data in a data set;

creating a pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the first type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the first type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the first type of performance measure using the pre-aggregated data set;

splitting, into two or more subsets, the pre-aggregated data set when the change in the first amount of time meets a specified level, wherein each of the two or more subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the first type of performance measure using at least one of the two or more subsets of the pre-aggregated data set;

generating, by a graphical user interface generator, presentation data that represents a value of the first type of performance measure calculated using at least one of the two or more subsets of the pre-aggregated data set; and

providing, to a user device for display on a graphical user interface, the generated presentation data.

2. The method of claim 1, comprising:

determining that the change in the first amount of time does not meet the specified level; and

determining the first type of performance measure using the pre-aggregated data set.

3. The method of claim 1, wherein determining that the change in the first amount of time meets the specified level comprises determining that the change in the first amount of time is an increase in the first amount of time that meets the specified level.

4. The method of claim 1, comprising:

receiving, after storing the two or more subsets of the pre-aggregated data set, a different request for a different type of performance measure;

creating a second pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the different type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the different type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set; and

splitting, into two or more other subsets, the pre-aggregated data set different from the two or more subsets when the change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set meets a second specified level, wherein each of the two or more other subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more other subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the different type of performance measure using at least one of the two or more other subsets of the pre-aggregated data set.

5. The method of claim 1, comprising:

determining an amount of resources required for storing and maintaining the pre-aggregated data set based on resources used for storing more data in the pre-aggregated data set;

determining that the first amount of time required to determine the first type of performance measure using the pre-aggregated data set has increased; and

determining that the change in the first amount of time required to determine the first type of performance measure meets the specified level.

6. The method of claim 5, comprising:

determining that the change in the first amount of time required to determine the first type of performance measure meets a specified level; and

in response to determining that the change in the first amount of time meets a specified level, discarding the pre-aggregated data set.

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 that is calculated based on a proper subset of data in a data set;

creating a pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the first type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the first type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the first type of performance measure using the pre-aggregated data set;

splitting, into two or more subsets, of the pre-aggregated data set when the change in the first amount of time meets a specified level, wherein each of the two or more subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the first type of performance measure using at least one of the two or more subsets of the pre-aggregated data set;

generating, by a graphical user interface generator, presentation data that represents a value of the first type of performance measure calculated using at least one of the two or more subsets of the pre-aggregated data set; and

providing, to a user device for display on a graphical user interface, the generated presentation data.

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

determining that the change in the first amount of time does not meet the specified level; and

determining the first type of performance measure using the pre-aggregated data set.

10. The computer readable medium of claim 8, wherein determining that the change in the first amount of time meets the specified level comprises determining that the change in the first amount of time is an increase in the first amount of time that meets the specified level.

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 two or more subsets of the pre-aggregated data set, a different request for a different type of performance measure;

creating a second pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the different type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the different type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set; and

splitting, into two or more other subsets, the pre-aggregated data set different from the two or more subsets when the change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set meets a second specified level, wherein each of the two or more other subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more other subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the different type of performance measure using at least one of the two or more other subsets of the pre-aggregated data set.

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

determining an amount of resources required for storing and maintaining the pre-aggregated data set based on resources used for storing more data in the pre-aggregated data set;

determining that the first amount of time required to determine the first type of performance measure using the pre-aggregated data set has increased; and

determining that the change in the first amount of time required to determine the first type of performance measure meets the specified level.

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 change in the first amount of time required to determine the first type of performance measure meets a specified level; and

in response to determining that the change in the first amount of time meets a specified level, discarding the pre-aggregated data set.

14. The computer readable medium of claim 8, 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.

15. A system, comprising:

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

one or more data processing apparatus 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 that is calculated based on a proper subset of data in a data set;

creating a pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the first type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the first type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the first type of performance measure using the pre-aggregated data set;

splitting, into two or more subsets, the pre-aggregated data set when the change in the first amount of time meets a specified level, wherein each of the two or more subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the first type of performance measure using at least one of the two or more subsets of the pre-aggregated data set;

generating, by a graphical user interface generator, presentation data that represents a value of the first type of performance measure calculated using at least one of the two or more subsets of the pre-aggregated data set; and

providing, to a user device for display on a graphical user interface, the generated presentation data.

16. The system of claim 15, wherein determining that the change in the first amount of time meets the specified level comprises determining that the change in the first amount of time is an increase in the first amount of time that meets the specified level.

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

receiving, after storing the two or more subsets of the pre-aggregated data set, a different request for a different type of performance measure;

creating a second pre-aggregated data set that includes the proper subset of data from the data set based on a first amount of time required to determine the different type of performance measure using the pre-aggregated data set being less than a second amount of time required to determine the different type of performance measure using the data set;

storing, over a period of time, more data in the pre-aggregated data set;

monitoring, over the period of time, a change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set; and

splitting, into two or more other subsets, the pre-aggregated data set different from the two or more subsets when the change in the first amount of time required to determine the different type of performance measure using the pre-aggregated data set meets a second specified level, wherein each of the two or more other subsets of the pre-aggregate data set includes less data than the pre-aggregated data set, and wherein the combination of the two or more other subsets of the pre-aggregated data set includes the entirety of the proper subset of data from the data set;

determining the different type of performance measure using at least one of the two or more other subsets of the pre-aggregated data set.

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

determining an amount of resources required for storing and maintaining the pre-aggregated data set based on resources used for storing more data in the pre-aggregated data set;

determining that the first amount of time required to determine the first type of performance measure using the pre-aggregated data set has increased; and

determining that the change in the first amount of time required to determine the first type of performance measure meets the specified level.

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

determining that the change in the first amount of time required to determine the first type of performance measure meets a specified level; and

in response to determining that the change in the first amount of time meets a specified level, discarding the pre-aggregated data set.

20. The system of claim 15, 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.