In-memory time series database and processing in a distributed environment

• US 9,934,259 B2
• Filed: 08/15/2014
• Issued: 04/03/2018
• Est. Priority Date: 08/15/2013
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Leonard, Michael J., Blair, Ed
• Primary Examiner(s): Raab, Christopher J
• Application Number:
  US14/460,673
• Publication Number:
  US 20150052173A1
• Time in Patent Office: 1,327 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

This disclosure describes methods, systems, and computer-readable media for accessing information that describes a hierarchical schema for assembling multiple time series of data in a distributed manner. The hierarchical schema associates each of the time series with a particular level of the hierarchical schema and prescribes a structure of relationships between time series assigned to different levels of the hierarchical schema. Multiple time series associated with a lowest level of the hierarchical schema are assembled by inventorying a portion of a data set. Multiple time series associated with an intermediate level of the hierarchical schema are assembled by aggregating the time series associated with the lowest level based on the structure of nested relationships. Also, multiple additional time series that are associated with the intermediate level and which were assembled by other grid-computing devices are received. After the time series are assembled, they are made available for processing to facilitate parallelized forecasting.

Claims

1. A computer-program product tangibly embodied in a non-transitory, machine-readable storage medium having instructions stored thereon, the instructions being executable to cause a grid-computing device to perform the following operations:

accessing information while being operated in a grid-computing system that includes other grid-computing devices,

wherein the information describes a hierarchical schema for assembling multiple time series of data in a distributed manner that includes assembling multiple time series at the grid-computing device and other time series at the other grid-computing devices,

wherein the hierarchical schema associates each of the multiple time series with a particular level of the hierarchical schema and prescribes a structure of nested relationships between time series assigned to different levels of the hierarchical schema;

assembling multiple time series associated with a lowest level of the hierarchical schema by inventorying a portion of a data set;

assembling multiple time series associated with an intermediate level of the hierarchical schema by aggregating the time series associated with the lowest level based on the structure of nested relationships, wherein the intermediate level is above the lowest level, and wherein;

the data set is partitioned at the intermediate level of the hierarchical schema such that a first number (n) of partitions are defined, the n partitions including;

a partition that includes the inventoried portion;

and a second number (n−

1) of other partitions;

the other grid-computing devices consist of n−

1 grid-computing devices; and

each of the other partitions is assigned to one of the other grid-computing devices;

receiving multiple additional time series associated with the intermediate level and assembled by at least one of the other grid-computing devices;

assembling a time series associated with a level of the hierarchical schema above the intermediate level by aggregating the assembled time series associated with the intermediate level and the multiple additional time series based on the structure of nested relationships;

using volatile memory to store the time series associated with the level above the intermediate level;

accessing the stored time series in memory; and

generating a forecast by processing the accessed time series.

2. The computer-program product of claim 1, wherein:

no two of the other partitions are assigned to a same one of the other grid-computing devices.

3. The computer-program product of claim 2, wherein the operations further include:

providing each of the other grid-computing devices with each of the assembled time series associated with the intermediate level.

4. The computer-program product of claim 2, wherein:

the data set includes observations with respect to multiple variables; and

the data set is partitioned in accordance with a group-by data partitioning scheme in which at least one of the variables is specified as a group-by variable.

5. The computer-program product of claim 4, wherein the group-by data partitioning scheme prescribes:

identifying group-by groups of data entries formed on one or more group-by variables; and

partitioning the data set such that none of the group-by groups are segmented by the partitioning.

6. The computer-program product of claim 1, wherein one of the relationships relates a single time series associated with the intermediate level to multiple time series associated with the lowest level.

7. The computer-program product of claim 6, wherein the one of the relationships relates the single time series to the multiple time series through summation.

8. The computer-program product of claim 6, wherein the one of the relationships relates the single time series to the multiple nested time series through averaging.

9. A computer-implemented method comprising the following operations performed by a grid-computing device while operating in a grid-computing system that includes other grid-computing devices:

accessing information describing a hierarchical schema for assembling multiple time series of data in a distributed manner that includes assembling multiple time series at the grid-computing device and other time series at the other grid-computing devices,

wherein the hierarchical schema associates individual time series with a particular level of the hierarchical schema and prescribes a structure of nested relationships between time series assigned to different levels of the hierarchical schema;

assembling multiple time series associated with a lowest level of the hierarchical schema by inventorying a portion of a data set;

assembling multiple time series associated with an intermediate level of the hierarchical schema by aggregating the time series associated with the lowest level based on the structure of nested relationships, wherein the intermediate level is above the lowest level, and wherein;

the data set is partitioned at the intermediate level of the hierarchical schema such that a first number (n) of partitions are defined, the n partitions including;

a partition that includes the inventoried portion;

and a second number (n−

1) of other partitions;

the other grid-computing devices consist of n−

1 grid-computing devices; and

each of the other partitions is assigned to one of the other grid-computing devices;

receiving multiple additional time series associated with the intermediate level and assembled by at least one of the other grid-computing devices;

assembling a time series associated with a level of the hierarchical schema above the intermediate level by aggregating the assembled time series associated with the intermediate level and the multiple additional time series based on the structure of nested relationships;

using volatile memory to store the time series associated with the level above the intermediate level; and

accessing the stored time series in memory; and

generating a forecast by processing the accessed time series.

10. The method of claim 9, wherein:

no two of the other partitions are assigned to a same one of the other grid-computing devices.

11. The method of claim 10, further comprising:

providing each of the other grid-computing devices with each of the assembled time series associated with the intermediate level.

12. The method of claim 10, wherein each of the other grid-computing devices:

assembles at least one additional time series associated with the lowest level by inventorying the respectively assigned partition;

assembles at least one time series associated with the intermediate level by aggregating time series associated with the lowest level, based on the structure of relationships;

provides the grid-computing device and at least one of the other grid-computing devices with at least one time series associated with the intermediate level; and

receives at least one time series associated with the intermediate level from at least one of the other grid-computing devices.

13. The method of claim 10, wherein:

the data set includes observations with respect to multiple variables; and

the data set is partitioned in accordance with a group-by data partitioning scheme in which at least one of the variables is specified as a group-by variable.

14. The method of claim 13, wherein the group-by data partitioning scheme prescribes:

identifying group-by groups of data entries formed on one or more group-by variables; and

partitioning the data set such that none of the group-by groups are segmented by the partitioning.

15. The method of claim 9, wherein one of the relationships relates a single time series associated with the intermediate level to multiple time series associated with the lowest level.

16. The method of claim 15, wherein the one of the relationships relates the single time series to the multiple nested time series through summation.

17. The method of claim 15, wherein the one of the relationships relates the single time series to the multiple nested time series through averaging.

18. A grid-computing device comprising:

a hardware processor configured to perform operations while the grid-computing device operates in a grid-computing system that includes other grid-computing devices, the operations including;

accessing information describing a hierarchical schema for assembling multiple time series of data in a distributed manner that includes assembling multiple time series at the grid-computing device and other time series at the other grid-computing devices,

wherein the hierarchical schema associates individual time series with a particular level of the hierarchical schema and prescribes a structure of nested relationships between time series assigned to different levels of the hierarchical schema;

assembling multiple time series associated with a lowest level of the hierarchical schema by inventorying a portion of a data set;

assembling multiple time series associated with an intermediate level of the hierarchical schema by aggregating the time series associated with the lowest level based on the structure of nested relationships, wherein the intermediate level is above the lowest level, and wherein;

the data set is partitioned at the intermediate level of the hierarchical schema such that a first number (n) of partitions are defined, the n partitions including;

a partition that includes the inventoried portion;

and a second number (n−

1) of other partitions;

the other grid-computing devices consist of n−

1 grid-computing devices; and

each of the other partitions is assigned to one of the other grid-computing devices;

receiving multiple additional time series associated with the intermediate level and assembled by at least one of the other grid-computing devices;

assembling a time series associated with a level of the hierarchical schema above the intermediate level by aggregating the assembled time series associated with the intermediate level and the multiple additional time series based on the structure of nested relationships;

using volatile memory to store the time series associated with the level above the intermediate level;

accessing the stored time series in memory; and

generating a forecast by processing the accessed time series.

19. The grid-computing device of claim 18, wherein:

no two of the other partitions are assigned to a same one of the other grid-computing devices.

20. The grid-computing device of claim 19, wherein the operations further include:

providing each of the other grid-computing devices with each of the assembled time series associated with the intermediate level.

21. The grid-computing device of claim 19, wherein:

the data set includes observations with respect to multiple variables; and

the data set is partitioned in accordance with a group-by data partitioning scheme in which at least one of the variables is specified as a group-by variable.

22. The grid-computing device of claim 21, wherein the group-by data partitioning scheme prescribes:

identifying group-by groups of data entries formed on one or more group-by variables; and

partitioning the data set such that none of the group-by groups are segmented by the partitioning.

23. The grid-computing device of claim 18, wherein a particular one of the relationships relates a single time series associated with the intermediate level to multiple time series associated with the lowest level.

24. The grid-computing device of claim 23, wherein the particular relationship relates the single time series to the multiple time series through summation.

25. The grid-computing device of claim 23, wherein the particular nested relationship relates the single time series to the multiple nested time series through averaging.

26. The grid-computing device of claim 18, wherein accessing information describing a hierarchical schema includes receiving the information from a central control processing device configured to synchronize the grid-computing system.

27. The grid-computing device of claim 26, wherein generating a forecast includes:

receiving a command to generate the forecast from the central control processing device; and

communicating the forecast to the central control processing device.