Granted Patent B2

US 7,698,285 · App. 11/558,305 · Granted Apr 13, 2010

Abstract

Claims (71)

1. A method comprising:

determining, by a computing device, ordered sets of index values, wherein each of the index values identifies a position along one of a plurality of dimensions of a multidimensional dataset at which a data value exists in the multidimensional dataset, wherein each of the ordered sets of index values corresponds to a different one of the plurality of dimensions;

calculating, by the computing device, sets of respective offset values for the ordered sets of index values, wherein each of the offset values represents a difference between a current index value in one of the sets of index values and a preceding index value in the one of the sets of index values, wherein the preceding index value immediately precedes the current index value according to the order of the one of the sets of index values;

generating a data dictionary that maps unique numerical data identifiers to unique data values in the multidimensional dataset in a one-to-one mapping;

applying a compression algorithm to the sets of offset values and the data dictionary to generate a compressed version of the multidimensional dataset, wherein the compressed version of the multidimensional dataset includes a compressed data dictionary and compressed lists of offset values;

outputting the compressed version of the multidimensional dataset;

constructing a second multidimensional dataset as a result for a received query, wherein constructing the second multidimensional dataset comprises:

identifying a multidimensional subset comprising elements of the first multidimensional dataset that satisfy at least a portion of the query, wherein the multidimensional subset is defined by an intersection of the first multidimensional dataset and the second multidimensional dataset;

extracting the multidimensional subset from the compressed version of the first multidimensional dataset;

applying a decompression algorithm to the multidimensional subset extracted from the compressed version of the first multidimensional dataset;

extracting a remaining portion of the second multidimensional dataset from a database, wherein the remaining portion comprises elements of the query that were not satisfied by the multidimensional subset, wherein the remaining portion is defined by the difference between the second multidimensional dataset and the multidimensional subset; and

combining the multidimensional subset and the remaining portion to form the second multidimensional dataset; and

outputting the second multidimensional dataset.

2. The method of claim 1 ,

wherein the method further comprises:

obtaining a set of numerical data identifiers, wherein each numerical data identifier in the set of numerical data identifiers is a numerical data identifier of a data value in a multidimensional data element in the multidimensional dataset; and

calculating a set of offset values for the set of numerical data identifiers, wherein the set of offset values for the numerical data identifiers contains offset values for the set of numerical data identifiers; and

wherein applying a compression algorithm to the data dictionary comprises applying a lossless compression algorithm to the set of offset values that was calculated for the numerical data identifiers.

3. The method of claim 1 ,

wherein the method further comprises:

obtaining a set of multidimensional data element index values, wherein each multidimensional data element index value in the set of multidimensional data element index values is associated with a multidimensional data element in the multidimensional dataset that contains a data value; and

calculating a set of offset values for the multidimensional data element index values, wherein the set of offset values for the multidimensional data element index values contains offset values for the set of multidimensional data element index values; and

wherein applying a compression algorithm to the data dictionary comprises applying a lossless compression algorithm to the set of offset values for the multidimensional data element index values.

4. The method of claim 1 , wherein the compression algorithm comprises one of: Run-Length Encoding (RLE), Huffman encoding, Lempel-Ziv, DEFLATE, Lempel-Ziv-Welch and arithmetic coding.

5. The method of claim 1 , wherein outputting the compressed version comprises outputting the compressed version through a computer network.

6. The method of claim 1 , wherein the multidimensional dataset includes more than three dimensions.

7. The method of claim 1 , wherein the method further comprises:

receiving a query for the multidimensional dataset; and

extracting the multidimensional dataset from a superset of multidimensional data in response to the query.

8. The method of claim 7 , wherein receiving a query comprises receiving a query from enterprise planning software.

9. A method comprising:

receiving, by a computing device, a compressed version of a first multidimensional dataset comprising:

a compressed data dictionary, wherein the compressed data dictionary includes a data dictionary that maps unique numerical data identifiers to unique data values in the first multidimensional dataset in a one-to-one mapping; and

a set of compressed lists of offset values, wherein each of the set of compressed lists of offset values includes differences between an ordered set of index values, wherein each of the index values identifies a position along one of a plurality of dimensions of the first multidimensional dataset at which a data value exists in the first multidimensional dataset, wherein each of the ordered sets of index values corresponds to a different one of the plurality of dimensions, and wherein each of the offset values represents a difference between a current index value in one of the sets of index values and a preceding index value in the one of the sets of index values, wherein the preceding index value immediately precedes the current index value according to the order of the one of the sets of index values;

constructing a second multidimensional dataset as a result for a received query, wherein constructing the second multidimensional dataset comprises:

scanning the first multidimensional dataset to identify a multidimensional subset comprising elements of the first multidimensional dataset that satisfy at least a portion of the query, wherein the multidimensional subset is defined by an intersection of the first multidimensional dataset and the second multidimensional dataset;

extracting the multidimensional subset from the compressed version of the first multidimensional dataset;

applying a decompression algorithm to the multidimensional subset extracted from the compressed version of the first multidimensional dataset;

issuing a command that extracts a remaining portion of the second multidimensional dataset from a database, wherein the remaining portion comprises elements of the query that were not satisfied by the multidimensional subset, wherein the remaining portion is defined by the difference between the second multidimensional dataset and the multidimensional subset;

receiving the remaining portion in response to the command; and

combining the multidimensional subset and the remaining portion to form the second multidimensional dataset; and

outputting the second multidimensional dataset as the result for the query.

10. The method of claim 9 , wherein receiving the first multidimensional dataset comprises caching the first multidimensional dataset.

11. A computing device comprising:

a database to store a multidimensional dataset, wherein the multidimensional dataset comprises a plurality of dimensions;

a processor communicatively coupled to the database; and

a compression module executed by the processor to determine ordered sets of index values from the multidimensional dataset of the database, wherein each of the index values identifies a position along one of the plurality of dimensions of the multidimensional dataset at which a data value exists in the multidimensional dataset, wherein each of the ordered sets of index values corresponds to a different one of the plurality of dimensions, to calculate sets of respective offset values for the ordered sets of index values, wherein each of the offset values represents a difference between a current index value in one of the sets of index values and a preceding index value in the one of the sets of index values, wherein the preceding index value immediately precedes the current index value according to the order of the one of the sets of index values, to generate a data dictionary that maps unique numerical data identifiers to unique data values in the multidimensional dataset in a one-to-one mapping, to apply a compression algorithm to the sets of offset values and the data dictionary to generate a compressed version of the multidimensional dataset, wherein the compressed version of the multidimensional dataset includes a compressed data dictionary and compressed lists of offset values, to output the compressed version of the multidimensional dataset,

wherein the processor is configured to construct a second multidimensional dataset as a result for a received query, wherein to construct the second multidimensional dataset, the processor is configured to identify a multidimensional subset comprising elements of the first multidimensional dataset that satisfy at least a portion of the query, wherein the multidimensional subset is defined by an intersection of the first multidimensional dataset and the second multidimensional dataset, extract the multidimensional subset from the compressed version of the first multidimensional dataset, apply a decompression algorithm to the multidimensional subset extracted from the compressed version of the first multidimensional dataset, extract a remaining portion of the second multidimensional dataset from a database, wherein the remaining portion comprises elements of the query that were not satisfied by the multidimensional subset, wherein the remaining portion is defined by the difference between the second multidimensional dataset and the multidimensional subset, and combine the multidimensional subset and the remaining portion to form the second multidimensional dataset, and to output the second multidimensional dataset.

12. The device of claim 11 ,

wherein the compression module identifies a set of numerical data identifiers, wherein each numerical data identifier in the set of numerical data identifiers is a numerical data identifier of a data value in a multidimensional data element in the multidimensional dataset;

wherein the compression module calculates a set of offset values for the set of numerical data identifiers, wherein the set of offset values for the numerical data identifiers contains offset values for the set of numerical data identifiers; and

wherein, in outputting the compressed version of the multidimensional dataset, the compression module applies a lossless compression algorithm to the set of offset values that was calculated for the set of numerical identifiers.

13. The device of claim 11 ,

wherein the compression module identifies a set of multidimensional data element index values, wherein each multidimensional data element index value in the set of multidimensional data element index values is associated with a multidimensional data element in the multidimensional dataset that contains a data value;

wherein the compression module calculates a set of offset values for the multidimensional data element index values, wherein the set of offset values for the multidimensional data element index values contains offset values for the list of multidimensional data element index values; and

wherein, in outputting the compressed version of the multidimensional dataset, the compression module applies a lossless compression algorithm to the set of offset values for the multidimensional data element index values.

14. The device of claim 11 , wherein the network device further comprises a query engine to extract the multidimensional dataset from a superset of multidimensional data in the database in response to a query.

15. The device of claim 11 , wherein the network device further comprises a cache to store the compressed version of the multidimensional dataset.

16. A computer-readable storage medium comprising instructions for causing a programmable processor to:

determine ordered sets of index values, wherein each of the index values identifies a position along one of a plurality of dimensions of a multidimensional dataset at which a data value exists in the multidimensional dataset, wherein each of the ordered sets of index values corresponds to a different one of the plurality of dimensions;

calculate sets of respective offset values for the ordered sets of index values, wherein each of the offset values represents a difference between a current index value in one of the sets of index values and a preceding index value in the one of the sets of index values, wherein the preceding index value immediately precedes the current index value according to the order of the one of the sets of index values;

generate a data dictionary that maps unique numerical data identifiers to unique data values in the multidimensional dataset in a one-to-one mapping;

apply a compression algorithm to the sets of offset values and the data dictionary to generate a compressed version of the multidimensional dataset, wherein the compressed version of the multidimensional dataset includes a compressed data dictionary and compressed lists of offset values;

output the compressed version of the multidimensional dataset;

construct a second multidimensional dataset as a result for a received query, wherein the instructions to construct the second multidimensional dataset comprise instructions to:

identify a multidimensional subset comprising elements of the first multidimensional dataset that satisfy at least a portion of the query, wherein the multidimensional subset is defined by an intersection of the first multidimensional dataset and the second multidimensional dataset;

extract the multidimensional subset from the compressed version of the first multidimensional dataset;

apply a decompression algorithm to the multidimensional subset extracted from the compressed version of the first multidimensional dataset;

extract a remaining portion of the second multidimensional dataset from a database, wherein the remaining portion comprises elements of the query that were not satisfied by the multidimensional subset, wherein the remaining portion is defined by the difference between the second multidimensional dataset and the multidimensional subset; and

combine the multidimensional subset and the remaining portion to form the second multidimensional dataset; and

output the second multidimensional dataset.

Assignments (11)