Computer-implemented systems and methods for processing a multi-dimensional data structure

• US 8,676,801 B2
• Filed: 08/29/2011
• Issued: 03/18/2014
• Est. Priority Date: 08/29/2011
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Gong, Qing, Peressini, Kenneth John
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Liu, Hexing
• Application Number:
  US13/220,285
• Publication Number:
  US 20130054608A1
• Time in Patent Office: 932 Days
• Field of Search: 707/800, 707/801, 707/802, 707/811, 707/736, 707/791, 707/796
• US Class Current: 707/736
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Computer-implemented systems and methods are provided for processing a multi-dimensional data structure. For example, systems and methods are provided for processing the multi-dimensional data structure and allowing cell selection rules related to the multi-dimensional data structure to be resolved efficiently, so that computational cost associated with processing the multi-dimensional data structure can be saved.

Claims

1. A computer-implemented method, comprising:

receiving, in a computing system, data associated with a multi-dimensional cube, wherein the multi-dimensional cube includes multiple cells, and wherein each of the cells is referenced by an index number;

receiving a cell selection rule;

identifying one or more cells within the multi-dimensional cube, wherein identifying is based on the received cell selection rule and is performed on a computing device, wherein each cell is associated with multiple dimensions in the multi-dimensional cube, wherein each dimension includes a plurality of dimension members, and wherein each dimension member is associated with one or more offset values;

determining that the identified cells form a sub-cube within the multi-dimensional cube, wherein determining includes finding that two of the identified cells share same dimension members from all but one dimension of the multi-dimensional cube;

calculating, with one or more computer processors, the index number that references a start cell in the sub-cube, wherein calculating the index number that references the start cell includes using offset values associated with dimension members associated with the start cell;

calculating, with the one or more computing processors, the index numbers that reference each other cell in the sub-cube, wherein calculating the index numbers includes using the index number that references the start cell and involves;

calculating flatIndex2=flatIndex1+dimMultipliers[dim]×

(rank2−

rank1),

wherein;

flatIndex2 represents a cell index of a cell to be identified,

flatIndex1 represents a known cell index of a base cell,

rank1 represents an offset value of a dimension member of the base cell,

rank2 represents an offset value of a dimension member of the cell to be identified that is in a same dimension as the dimension member of the base cell,

dim represents the dimensions of the multi-dimensional cube; and

dimMultipliers[dim] represent multipliers of the dimensions of the multi-dimensional cube; and

outputting the cell index numbers for the sub-cube, wherein the outputted cell index numbers identify the cells in the sub-cube.

2. The method of claim 1, wherein the multi-dimensional cube is a multi-dimensional data structure.

3. The method of claim 1, wherein the cell indices in the sub-cube are ordered, and wherein the cells in the sub-cube are sequentially transversable using an order of the index numbers.

4. The method of claim 1, wherein an offset value represents a position of a dimension member in a dimension.

5. The method of claim 1, wherein calculating the index of each other cell in the sub-cube involves calculating flatIndex2.

6. The method of claim 5, wherein each dimension is associated with a multiplier, and wherein calculating flatIndex2 includes using the multiplier associated with one of the dimensions.

7. The method of claim 6, wherein each dimension is characterized by a cardinality that represents a quantity of dimension members included in the dimension.

8. The method of claim 7, further comprising:

for each dimension, determining the associated dimension multiplier based on the cardinality of the dimension.

9. The method of claim 8, wherein using the dependent cell index calculation algorithm further includes:

determining a rank difference between two of the cells of the sub-cube, wherein the rank difference is associated with a first one of the dimensions; and

obtaining a product by multiplying the rank difference by the dimension multiplier associated with the first one of the dimensions.

10. The method of claim 9, wherein using the dependent cell index calculation algorithm further includes:

adding the product to an index number previously computed with respect to one of the cells of the sub-cube.

11. The method of claim 1, wherein the outputted cell indices are used to perform one or more operations on data associated with the sub-cube within the multi-dimensional cube.

12. A system, comprising:

one or more processors;

a non-transitory computer-readable storage medium including instructions configured to cause the one or more processors to perform operations, including;

receiving data associated with a multi-dimensional cube, wherein the multi-dimensional cube includes multiple cells, and wherein each of the cells is referenced by an index number;

receiving a cell selection rule;

identifying one or more cells within the multi-dimensional cube, wherein identifying is based on the received cell selection rule, wherein each cell is associated with multiple dimensions in the multi-dimensional cube, wherein each dimension includes a plurality of dimension members, and wherein each dimension member is associated with one or more offset values;

determining that the identified cells form a sub-cube within the multi-dimensional cube, wherein determining includes finding that two of the identified cells share same dimension members from all but one dimension of the multi-dimensional cube;

calculating the index number that references a start cell in the sub-cube, wherein calculating the index number that references the start cell includes using offset values associated with dimension members associated with the start cell;

calculating the index numbers that reference each other cell in the sub-cube, wherein calculating the index numbers includes using the index number that references the start cell and involves;

calculating flatIndex2=flatIndex1+dimMultipliers[dim]×

(rank2−

rank1),

wherein;

flatIndex2 represents a cell index of a cell to be identified,

flatIndex1 represents a known cell index of a base cell,

rank1 represents an offset value of a dimension member of the base cell,

rank2 represents an offset value of a dimension member of the cell to be identified that is in a same dimension as the dimension member of the base cell,

dim represents the dimensions of the multi-dimensional cube; and

dimMultipliers[dim] represent multipliers of the dimensions of the multi-dimensional cube; and

outputting the cell index numbers for the sub-cube, wherein the outputted cell index numbers identify the cells in the sub-cube.

13. The system of claim 12, wherein the multi-dimensional cube is a multi-dimensional data structure.

14. The system of claim 12, wherein the cell indices in the sub-cube are ordered, and wherein the cells in the sub-cube are sequentially transversable using an order of the index numbers.

15. The system of claim 12, wherein an offset value represents a position of a dimension member in a dimension.

16. The system of claim 12, wherein calculating the index of each other cell in the sub-cube involves calculating flatIndex2.

17. The system of claim 13, wherein each dimension is associated with a multiplier, and wherein using the dependent cell index calculation algorithm includes calculating flatIndex2.

18. The system of claim 17, wherein each dimension is characterized by a cardinality that represents a quantity of dimension members included in the dimension.

19. The system of claim 18, wherein the operations further include:

for each dimension, determining the associated dimension multiplier based on the cardinality of the dimension.

20. The system of claim 19, wherein using the dependent cell index calculation algorithm further includes:

determining a rank difference between two of the cells of the sub-cube, wherein the rank difference is associated with a first one of the dimensions; and

obtaining a product by multiplying the rank difference by the dimension multiplier associated with the first one of the dimensions.

21. The system of claim 20, wherein using the dependent cell index calculation algorithm further includes:

adding the product to an index number previously computed with respect to one of the cells of the sub-cube.

22. The system of claim 12, wherein the outputted cell indices are used to perform one or more operations on data associated with the sub-cube within the multi-dimensional cube.

23. A computer-program product, tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a data processing apparatus to:

receive data associated with a multi-dimensional cube, wherein the multi-dimensional cube includes multiple cells, and wherein each of the cells is referenced by an index number;

receive a cell selection rule;

identify one or more cells within the multi-dimensional cube, wherein identifying is based on the received cell selection rule, wherein each cell is associated with multiple dimensions in the multi-dimensional cube, wherein each dimension includes a plurality of dimension members, and wherein each dimension member is associated with one or more offset values;

determine that the identified cells form a sub-cube within the multi-dimensional cube, wherein determining includes finding that two of the identified cells share same dimension members from all but one dimension of the multi-dimensional cube;

calculate the index number that references a start cell in the sub-cube, wherein calculating the index number that references the start cell includes using offset values associated with dimension members associated with the start cell;

calculate the index numbers that reference each other cell in the sub-cube, wherein calculating the index numbers includes using the index number that references the start cell and involves;

calculating flatIndex2=flatIndex1+dimMultipliers[dim]×

(rank2−

rank1),

wherein;

flatIndex2 represents a cell index of a cell to be identified,

flatIndex1 represents a known cell index of a base cell,

rank1 represents an offset value of a dimension member of the base cell,

rank2 represents an offset value of a dimension member of the cell to be identified that is in a same dimension as the dimension member of the base cell,

dim represents the dimensions of the multi-dimensional cube; and

dimMultipliers[dim] represent multipliers of the dimensions of the multi-dimensional cube; and

output the cell index numbers for the sub-cube, wherein the outputted cell index numbers identify the cells in the sub-cube.

24. The computer-program product of claim 23, wherein the multi-dimensional cube is a multi-dimensional data structure.

25. The computer-program product of claim 23, wherein the cell indices in the sub-cube are ordered, and wherein the cells in the sub-cube are sequentially transversable using an order of the index numbers.

26. The computer-program product of claim 23, wherein an offset value represents a position of a dimension member in a dimension.

27. The computer-program product of claim 23, wherein calculating the index of each other cell in the sub-cube involves calculating flatIndex2.

28. The computer-program product of claim 27, wherein each dimension is associated with a multiplier, and wherein calculating flatIndex2 includes using the multiplier associated with one of the dimensions.

29. The computer-program product of claim 28, wherein each dimension is characterized by a cardinality that represents a quantity of dimension members included in the dimension.

30. The computer-program product of claim 29, wherein the instructions are further configured to cause the data processing apparatus to:

determine, for each dimension, the associated dimension multiplier based on the cardinality of the dimension.

31. The computer-program product of claim 30, wherein using the dependent cell index calculation algorithm further includes:

determining a rank difference between two of the cells of the sub-cube, wherein the rank difference is associated with a first one of the dimensions; and

obtaining a product by multiplying the rank difference by the dimension multiplier associated with the first one of the dimensions.

32. The computer-program product of claim 31, wherein using the dependent cell index calculation algorithm further includes:

adding the product to an index number previously computed with respect to one of the cells of the sub-cube.

33. The computer-program product of claim 23, wherein the outputted cell indices are used to perform one or more operations on data associated with the sub-cube within the multi-dimensional cube.