DATA INTEREST ESTIMATION FOR N-DIMENSIONAL CUBE COMPUTATIONS

• US 20150370883A1
• Filed: 09/23/2014
• Published: 12/24/2015
• Est. Priority Date: 06/20/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kalki, Santosh, Raghavan, Srinivasan Sundar, Rath, Timothy Andrew, Karnik, Mukul Vijay, Devgan, Amol, Sivasubramanian, Swaminathan
• Granted Patent: US 10,776,397 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 21/6236 between heterogeneous systems
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources

Abstract

An online analytical processing system may comprise an n-dimensional cube partitioned into slices, in which each slice may represent data points at the intersections of fixed and variable dimensions. Computation of data points within a slice may be deferred. A dependency graph may be initially constructed, in which the dependency graph is utilized in a subsequent computation. Calculation of data points may be prioritized based on information indicative of a chance that the data points will be accessed.

Claims

1. A system for performing online analytical processing on a data involving a real-time stream of data, the system comprising:

one or more computing nodes maintaining an n-dimensional cube comprising a plurality of dimensions and a plurality of data points corresponding to intersections of at least a subset of the plurality of dimensions, the plurality of data points comprising a first data point and a second data point; and

one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to;

identify a dependency between the first data point and the second data point, the dependency comprising calculation of the second data point based on the first data point;

determine a priority for calculating the second data point, the priority based at least in part on information indicative of a chance of receiving a request to access the second data point; and

schedule a calculation of the second data point based at least in part on the priority and on a change to the first data point.

2. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

calculate the chance of receiving the request to access the second data point based at least in part on receiving information indicative of interaction with a user interface.

3. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

calculate the chance of receiving the request to access the second data point based at least in part on access patterns implied by queries executed against at least one of the n-dimensional cube or a transactional data source related to the n-dimensional cube.

4. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

calculate the chance of receiving the request to access the second data point based at least in part on a request to perform at least one of a drill-down, drill-up, or pivot.

5. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

determine the priority for calculating the second value based at least in part on time elapsed while calculating the second data point.

6. A computer-implemented method for calculating values associated with data points of an n-dimensional cube, the method comprising:

identifying a dependency between a first data point and a second data point;

determining a priority for calculating the second data point, the priority based at least in part on information indicative of a chance of receiving a request to access the second data point; and

scheduling a calculation of the second data point based at least in part on the priority and on a change to the first data point.

7. The computer-implemented method of claim 6, wherein scheduling the calculation of the second data point comprises sorting the first and second data points based at least in part on the priority.

8. The computer-implemented method of claim 6, further comprising:

calculating the chance of receiving the request to access the second data point based at least in part on receiving information indicative of interaction with at least one of a drill-down, drill-up, or pivot control.

9. The computer-implemented method of claim 6, further comprising:

calculating the chance of receiving the request to access the second data point based at least in part on access patterns implied by queries executed against at least one of the n-dimensional cube or a transactional data source related to the n-dimensional cube.

10. The computer-implemented method of claim 9, wherein the access pattern comprises access to an aggregate value.

11. The computer-implemented method of claim 6, further comprising:

determining the priority for calculating the second data point based at least in part on a cost of computing the second data point.

12. The computer-implemented method of claim 6, further comprising:

calculating the second data point based at least in part on receiving the request to access the second data point.

13. The computer-implemented method of claim 6, further comprising:

determining that the chance of receiving the request to access the second value is increased, based at least in part on the first data point being transmitted to a computing device for display to a user.

14. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:

identify a dependency between a first data point and a second data point of an n-dimensional cube;

determine a priority for calculating the second data point, the priority based at least in part on information indicative of a chance of receiving a request to access the second data point; and

schedule a calculation of the second data point based at least in part on the priority and on a change to the first data point.

15. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

calculate the chance of receiving the request to access the second data point based at least in part on receiving information indicative of performing at least one of a drill-down, drill-up, or pivot operation.

16. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

calculate the chance of receiving the request to access the second data point based at least in part on access patterns implied by queries executed against at least one of the n-dimensional cube or a transactional data source related to the n-dimensional cube.

17. The non-transitory computer-readable storage medium of claim 16, wherein the access pattern includes a query processed by at least one of the n-dimensional cube or the transactional data source related to the n-dimensional cube, the query comprising an aggregation clause.

18. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine the priority for calculating the second data point based at least in part on a cost of computing the second data point.

19. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

calculate the second data point based at least in part on receiving the request to access the second data point.

20. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine that the chance of receiving the request to access the second data point is increased, based at least in part on the first value being transmitted to a computing device for display to a user.

21. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine to calculate the second data point based at least in part on the priority, the priority being relative to priorities for calculating other data points in the n-dimensional cube.

22. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine to calculate the second data point based at least in part on a security attribute associated with at least one of the second data point, a dimension, a hierarchy, or the n-dimensional cube.