Multidimensional analysis tool for high dimensional data

• US 7,765,216 B2
• Filed: 06/15/2007
• Issued: 07/27/2010
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Yantao, Sun, Bing, Zhang, Haidong, Liu, Guowei, Wang, Min, Wang, Jian, Zhu, Wenli, Mahmud, Adnan Azfar
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US11/818,607
• Publication Number:
  US 20080313184A1
• Time in Patent Office: 1,138 Days
• Field of Search: 707/3, 707/5, 707/100, 707/705, 707/736, 707/741, 707/742, 709/203, 715/209, 714/38, 717/127
• US Class Current: 707/742
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Described is a technology by which high dimensional data may be efficiently analyzed, including by filtering, grouping, aggregating and/or sorting operations to provide an analysis result. For efficiency in the analysis, an inverted index may be built (e.g., as part of filtering), and/or a hash structure (e.g., as part of grouping). Analysis parameters specify dimensions, on which union and/or intersection operations are performed to provide a final dataset. The analysis tool provides a user interface for inputting analysis parameters and outputting information corresponding to an analysis result. The analysis tool may sort the information corresponding to the analysis result, e.g., to output the topmost or bottommost results.

Claims

1. A method performed by one or more computing devices, the method comprising:

accessing a master dataset, the master dataset comprising a plurality of dimensions and a plurality of rows, each dimension comprising a category or type of data, each row comprised of values corresponding to the dimensions, the rows forming columns of values that correspond to the dimensions, the master dataset further comprising a dimension table for a given dimension and an inverted index for the dimension table, the dimension table comprising rows, each row comprising a value or range of values corresponding to the category or type of data of the given dimension, the inverted index identifying, for each row of the dimension table, a corresponding row in the master dataset that contains a value of the dimension that matches the value or range of values of the row of the dimension table;

obtaining a final dataset from the master dataset based on analysis parameters, the analysis parameters including at least one parameter that identifies the given dimension and defines a set of values for the given dimension, wherein the final dataset is comprised of rows of master dataset;

finding the rows of the final dataset by using the inverted index to find rows of the master dataset that have values for the given dimension that match the set of values defined by the analysis parameters;

performing at least one of;

a grouping operation, an aggregating operation or a sorting operation, or any combination of a grouping operation, an aggregating operation or a sorting operation to configure a result set from the final dataset; and

outputting the result set.

2. The method of claim 1 wherein the analysis parameters define another dimension of the master dataset, and wherein obtaining the final dataset comprises performing a union operation on a set of rows in the other dimension and the rows in the final dataset.

3. The method of claim 1 wherein the analysis parameters define another dimension of the master dataset, and wherein obtaining the final dataset comprises performing an intersection operation on a set of rows in the other dimension and the rows in the final dataset.

4. The method of claim 1 wherein the analysis parameters define two other dimensions, the result dataset is obtained by performing a union operation on rows of the master dataset for the other dimensions to provide a merged set, and performing an intersection operation on the merged set and the final dataset.

5. The method of claim 1 wherein the grouping operation includes building a hash structure in which identifiers having identical dimension value or values correspond to the same group.

6. The method of claim 5 wherein the analysis parameters correspond to a plurality of sets of dimension values, and wherein building the hash structure comprises determining a hash value corresponding to each identifier based on a mathematical computation performed on each of the dimension values associated with that identifier.

7. The method of claim 1 wherein the aggregating operation includes accessing the inverted index and a hash structure to increment a counter for a group of dimension values.

8. The method of claim 1 wherein the sorting operation includes selecting only a top number or a bottom number of results for outputting in the result set.

9. At least one computer-readable storage medium having computer-executable instructions, which when executed by a computer perform steps, the steps comprising:

accessing a master dataset, the master dataset comprising a plurality of dimensions and a plurality of rows, each dimension comprising a dimension value identifying a category or type of data, each row comprised of values corresponding to the dimensions, the rows forming columns of values that correspond to the dimensions;

the master dataset further comprising a dimension table for a given dimension of the master dataset, comprised of rows, each row comprising a definition of a range of values corresponding to the category or type of data of the dimension table'"'"'s dimension;

an inverted index comprising, for each row of the dimension table, one or more identifiers of rows of the master dataset, wherein each such identified master dataset row has a value for the given dimension that falls within the range of values defined by a corresponding row of the dimension table;

receiving analysis parameters interactively inputted via a user interface;

performing a filtering operation on the master dataset by using the inverted index to find a set of identifiers of rows in the master dataset and a plurality of associated dimension values for each identifier;

grouping the dimension values via a hash operation into grouped dimension values, in which identifiers having identical dimension values correspond to the same dimension group, and

using the grouped dimension values to output a result set.

10. The computer-readable storage medium of claim 9 having further computer-executable instructions comprising, building an inverted index for each set of dimension values.

11. The computer-readable storage medium of claim 9 wherein the analysis parameters correspond to two sets of dimension values, and wherein filtering the data comprises performing a union operation on the two sets, or performing an intersection operation on the two sets.

12. The computer-readable storage medium of claim 9 wherein the analysis parameters correspond to a first, second and third set of dimension values, and wherein filtering the data comprises performing a union operation on the first and second sets to provide a merged set, and performing an intersection operation on the merged set and the third set.

13. The computer-readable storage medium of claim 9 wherein the analysis parameters correspond to a plurality of sets of dimensions, and wherein building the hash structure comprises determining a hash value corresponding to each identifier based on a mathematical computation performed on each of the dimension values associated with that identifier.

14. The computer-readable storage medium of claim 9 having further computer-executable instructions comprising, performing an aggregating operation using the grouped dimension values.

15. The computer-readable storage medium of claim 9 having further computer-executable instructions comprising, performing a sorting operation to select only a top number or a bottom number of results for outputting in the result set.

16. At least one computer-readable storage medium having computer-executable instructions, which when executed by a computer perform steps, the steps comprising:

accessing a master dataset, the master dataset comprising a plurality of dimensions and a plurality of rows, each dimension comprising a category or type of data, each row comprised of values corresponding to the dimensions, the rows forming columns of values that correspond to the dimensions, the master dataset further comprising a dimension table for a given dimension and an inverted index for the dimension table, the dimension table comprising rows, each row comprising a value or range of values corresponding to the category or type of data of the given dimension, the inverted index identifying, for each row of the dimension table, a corresponding row in the master dataset that contains a value of the dimension that matches the value or range of values of the row of the dimension table;

obtaining a final dataset from the master dataset based on analysis parameters, the analysis parameters including at least one parameter that identifies the given dimension and defines a set of values for the given dimension, wherein the final dataset is comprised of rows of master dataset;

finding the rows of the final dataset by using the inverted index to find rows of the master dataset that have values for the given dimension that match the set of values defined by the analysis parameters;

performing at least one of;

a grouping operation, an aggregating operation or a sorting operation, or any combination of a grouping operation, an aggregating operation or a sorting operation to configure a result set from the final dataset; and

outputting the result set.

17. At least one computer-readable storage medium according to claim 16, wherein the steps are performed by a data analysis tool, and the steps performed by the analysis tool further comprise:

displaying an interface by which the analysis parameters are inputted by a user, the interface including indicia of the dimensions, and displaying the outputted result set.