USE OF DEPENDENCY GRAPHS TO DYNAMICALLY UPDATE N-DIMENSIONAL CUBES

• US 20150370882A1
• Filed: 09/23/2014
• Published: 12/24/2015
• Est. Priority Date: 06/20/2014
• Status: Abandoned Application

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Karnik, Mukul Vijay, Kalki, Santosh, Raghavan, Srinivasan Sundar, Rath, Timothy Andrew, Devgan, Amol, Sivasubramanian, Swaminathan
• Application Number:
  US14/494,513
• Publication Number:
  US 20150370882A1
• 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 structured using slice-based partitioning in which each slice comprises data points corresponding to a set of dimension values fixed across the slice and a set of dimension values allowed to vary. Slices may be partitioned and replicated across computing nodes. Views of the n-dimensional cube may be partially materialized by determining dependencies between slices. A central data dictionary may maintain information about slices and slice dependencies. Dimensions may be added by adding a new slice without requiring immediate recomputation of existing data points.

Claims

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

a plurality of computing nodes maintaining an n-dimensional cube comprising a plurality of dimensions; 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;

receive information indicative of adding an additional dimension to the n-dimensional cube;

form a data slice, the data slice comprising a plurality of data points corresponding to intersections of at least the additional dimension and at least one of the plurality of dimensions; and

partially materialize a hierarchy of the plurality of data points, wherein partially materializing the hierarchy comprises identifying a dependency between a first data point of the plurality of data points and a second data point of the plurality of data points, wherein less than all of the plurality of data points are computing during partial materialization.

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:

store information indicative of the dependency in a repository maintained on at least one of the plurality of computing nodes.

3. The system of claim 2, wherein the repository comprises information indicative of a second dependency between the data slice and an additional data slice of 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 a value associated the first data point of the hierarchy;

identify a path from the first data point to an additional data point of the hierarchy, the additional data point an ancestor of the first data point; and

record an indication that the additional data point is out of date with respect to the first data point.

5. The system of claim 1, wherein the information indicative of adding the additional dimension to the n-dimensional cube comprises data corresponding to the additional dimension.

6. 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:

defer computation of an additional data point of the hierarchy, based at least in part on a descendant of the additional data point being associated with an incomplete set of data.

7. A computer-implemented method of maintaining an n-dimensional cube on a plurality of computing nodes, the method comprising:

adding an additional dimension to the n-dimensional cube by at least forming a data slice on at least one of the plurality of computing nodes, the data slice comprising a plurality of data points corresponding to intersections of at least the additional dimension and at least one of a plurality of dimensions of the n-dimensional cube; and

partially forming a hierarchy of the plurality of data points, wherein partially forming the hierarchy comprises identifying a dependency between a first data point of the plurality of data points and a second data point of the plurality of data points.

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

identifying a second dependency between the data slice and another data slice maintained on a second at least one of the plurality of computing nodes; and

storing information indicative of the dependency in a repository maintained on a third at least one of the plurality of computing nodes.

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

calculating a value for the first data point of the hierarchy;

identifying a path from the first data point to an additional data point of the hierarchy, the additional data point an ancestor of the first data point; and

recording an indication that the additional data point is out of date with respect to the first data point.

10. The computer-implemented method of claim 7, further comprising:

receiving information indicative of adding the additional dimension to the n-dimensional cube, the information comprising data corresponding to the additional dimension.

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

deferring computation of an additional data point of the hierarchy, based at least in part on a descendant of the additional data point being associated with an incomplete set of data.

12. The computer-implemented method of claim 11, wherein the additional data point is associated with an aggregate value representative of a time period.

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

computing the additional data point based at least in part on a previous access pattern for data in the n-dimensional cube.

14. The computer-implemented method of claim 7, further comprising:

computing an additional data point of the hierarchy based at least in part on extrapolating a value associated with a descendent of the additional data point.

15. The computer-implemented method of claim 7, further comprising:

determining that the hierarchy is out of date with respect to a changed attribute value;

prioritizing computation of a first level of the hierarchy with respect to the changed attribute value;

deferring computation of a second level of the hierarchy, the second level dependent on the first level; and

prioritizing computation of the second level of the hierarchy in response to at least one of a drill-down, drill-up, or pivot event.

16. 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:

add an additional dimension to an n-dimensional cube by at least forming a data slice on at least one of the plurality of computing nodes, the data slice comprising a plurality of data points corresponding to intersections of at least the additional dimension and at least one of a plurality of dimensions of the n-dimensional cube; and

partially form a hierarchy of the plurality of data points, wherein partially forming the hierarchy comprises identifying a dependency between a first data point of the plurality of data points and a second data point of the plurality of data points.

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

identify a second dependency between the data slice and another data slice maintained on a second at least one of the plurality of computing nodes; and

store information indicative of the dependency in a repository maintained on a third at least one of the plurality of computing nodes.

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

calculate a value for the first data point of the hierarchy;

identify a path from the first data point to an additional data point of the hierarchy, the additional data point an ancestor of the first data point; and

record an indication that an additional value associated with the additional data point is out of date with respect to the first data point.

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

receive information indicative of adding the additional dimension to the n-dimensional cube, the information comprising data corresponding to the additional dimension.

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

defer computation of a value associated with an additional data point of the hierarchy, based at least in part on a descendant of the additional data point being associated with an incomplete set of data.

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

compute an aggregate value for an additional data point of the hierarchy based on an incomplete set of data, the incomplete set of data corresponding to a period of time that has not yet elapsed;

initially defer computation of a value associated with an ancestor of the additional data point; and

prioritize computation of the value associated with the ancestor of the additional data point in response to the time period elapsing.

22. The non-transitory computer-readable storage medium of claim 16, 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 hierarchy is out of date with respect to a changed attribute value;

prioritize computation of a first level of the hierarchy with respect to the changed attribute value; and

initially defer computation of a second level of the hierarchy, the second level dependent on the first level; and

prioritize computation of the second level of the hierarchy in response to at least one of a drill-down, drill-up, or pivot event.