Apparatus and method for dynamically materializing a multi-dimensional data stream cube

1. A non-transitory computer readable storage medium, storing executable instructions to:

generate a stream cube to store data received from multiple data sources;

generate a plurality of multi-dimensional data streams to represent the received data;

repeatedly determine materialization strategies to implement for the stream cube during a duration of the stream cube, wherein at least two different materialization strategies are determined; and

materialize the stream cube according to determined materialization strategies to record the multi-dimensional data streams.

2. The computer readable storage medium of claim 1 , wherein the multi-dimensional data streams comprise a plurality of multi-dimensional data tuples, each data tuple associated with a timestamp.

3. The computer readable storage medium of claim 2 , wherein the stream cube comprises a plurality of sub-cubes associated with a plurality of time ranges each sub-cube aggregating multi-dimensional data for a given time range.

4. The computer readable storage medium of claim 3 , wherein each sub-cube comprises a plurality of cuboids, each cuboid representing a set of dimensions and measures.

5. The computer readable storage medium of claim 3 , wherein the plurality of sub-cubes are grouped by a set of time ranges.

6. The computer readable storage medium of claim 1 , wherein the executable instructions to repeatedly determine materialization strategies for the stream cube comprise executable instructions to repeatedly evaluate system conditions and users' requests and determine how to materialize the stream cube in response to the system conditions and users' requests.

7. The computer readable storage medium of claim 6 , wherein the materialization strategy comprises a materialization strategy selected from the group consisting of on-demand materialization, full materialization, and partial materialization.

8. The computer readable storage medium of claim 7 , wherein the executable instructions to repeatedly determine a materialization strategy for the stream cube comprise executable instructions to repeatedly determine which of at least two materialization paths to implement for the stream cube according to a predetermined criterion and a cost function.

9. The computer readable storage medium of claim 8 , wherein the executable instructions to materialize the stream cube comprise executable instructions to record the plurality of multi-dimensional data streams along the materialization path.

10. A non-transitory computer readable storage medium, storing executable instructions to:

generate a stream cube for representing multi-dimensional data streams;

repeatedly determine, during a duration of the stream cube, which of a plurality of materialization paths to implement for the stream cube based on a predetermined criterion and a cost function; and

record the multi-dimensional data streams into the stream cube according to the determined materialization paths.

11. The computer readable storage medium of claim 10 , wherein the multi-dimensional data streams comprise a plurality of multi-dimensional data tuples, each data tuple associated with a timestamp.

12. The computer readable storage medium of claim 11 , wherein the stream cube comprises a plurality of sub-cubes associated with a plurality of time ranges, each sub-cube aggregating multi-dimensional data for a given time range.

13. The computer readable storage medium of claim 12 , wherein each sub-cube comprises a plurality of cuboids, each cuboid representing a set of dimensions and measures.

14. The computer readable storage medium of claim 13 , wherein the executable instructions to repeatedly determine materialization paths comprise executable instructions to repeatedly evaluate the predetermined criterion to determine when to compute the determined materialization path.

15. The computer readable storage medium of claim 14 , wherein the predetermined criterion is selected from a group consisting of a query-based criterion, a threshold-based criterion, and a time-based criterion.

16. The computer readable storage medium of claim 14 , wherein the executable instructions to repeatedly determine materialization paths comprise executable instructions to compute the cost function for each cuboid.

17. The computer readable storage medium of claim 16 , wherein the cost function comprises a function of a set of parameters and a set of weights assigned to the cuboid parameters.

18. The computer readable storage medium of claim 17 , wherein the cuboid parameters are selected from a group consisting of cuboid materialization memory cost, cuboid popularity, and cuboid update potential.

19. The computer readable storage medium of claim 16 , further comprising executable instructions to determine a cost for each potential materialization path in the stream cube.

20. The computer readable storage medium of claim 19 , further comprising executable instructions to select the materialization path from all potential materialization paths that has the lowest cost.

21. The computer readable storage medium of claim 20 , wherein the executable instructions to select the materialization path comprise executable instructions to use an optimization technique selected from the group consisting of dynamic programming, integer programming and simulated annealing.

22. The computer readable storage medium of claim 13 , wherein the executable instructions to record the multi-dimensional data streams into the stream cube according to the materialization path comprise executable instructions to update measures for cuboids along the materialization path within each sub-cube in the plurality of sub-cubes.

23. A method for dynamically materializing a multi-dimensional stream cube having a plurality of cuboids, comprising:

repeatedly computing a cost for materializing each cuboid in the stream cube;

repeatedly computing a cost for each of two or more potential materialization paths in the stream cube; and

repeatedly selecting, during a duration of the stream cube, a materialization path from the potential materialization paths in the stream cube that has the lowest cost;

refreshing the stream cube according to the selected materialization paths.

24. The method of claim 23 , further comprising:

iterating through all cuboids in the stream cube from a first cuboid to a second cuboid to determine a predecessor cuboid for each cuboid, the predecessor cuboid associated with a cost value;

storing the predecessor cuboid and its associated cost value; and

backtracking from the second cuboid to the first cuboid to generate a materialization path for the stream cube.