Dimensionality reduction

• US 7,797,320 B2
• Filed: 03/15/2005
• Issued: 09/14/2010
• Est. Priority Date: 03/15/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Hyperion Solutions Corporation (Oracle Corporation)
• Inventors: Thomsen, Erik
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/081,121
• Publication Number:
  US 20090138428A1
• Time in Patent Office: 2,009 Days
• Field of Search: 707/101, 707/803
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A solution is provided wherein the apparent dimensionality of a data set is reduced by ranking combinations of dimensions and parts of dimensions in terms of their suitability for mapping to the axes of a grid display. A user may then be presented with dense lower dimensional views of the data that are much easier to understand than sparse high dimensional views. The user may then make further refinements, groupings, and analyses as needed.

Claims

1. A computer-implemented method for presenting a view of data in a multidimensional database the method comprising:

assigning aggregate measures of orthogonality to one or more combinations of two or more columns in the multidimensional database;

wherein each aggregate measure of orthogonality indicates a measure of interdependence between values in a first column and values in one or more other columns;

identifying a region of orthogonality in the multidimensional database,

wherein, for one or more rows of the multidimensional database, values for a first set of one or more columns are not fully orthogonal in relation to values for a second set of one or more columns;

wherein said region is a subset of rows, from the one or more rows, for which values of the first set of one or more columns are orthogonal to values of the second set of one or more columns;

determining a view of data based at least upon said aggregate measures of orthogonality and said region of orthogonality, said determining including determining an orthogonal basis for the view;

wherein said view is of a subset of data in the multidimensional database;

wherein said orthogonal basis is one or more columns of the multidimensional database selected based on the aggregate measures of orthogonality and said region of orthogonality; and

displaying said view of data.

2. The method of claim 1, wherein the step of assigning aggregate measures of orthogonality comprises scanning a sampling of data from a source table in the multidimensional database,

wherein said view comprises a certain value that is found in the set of all data in the source table but is not found in the sampling of data from the source table.

3. The method of claim 1, wherein said step of assigning includes calculating orthogonality indices for each column in the combinations of two or more columns.

4. The method of claim 3, wherein said calculating includes:

a) selecting a distinct value in the column;

b) selecting all the rows having said distinct value for the column;

c) selecting a sister column different from the column;

d) calculating a count ratio equal to a count of distinct values for said sister column in said rows, divided by a count of overall distinct values for said sister column;

e) repeating b), c), and d) for each additional distinct value in said column; and

f) averaging said count ratios.

5. The method of claim 4, wherein said calculating begins with a column forming a likely orthogonal complete basis and advances to a next column by selecting a column forming a likely fully orthogonal complete basis, if available.

6. The method of claim 1, wherein said step of assigning includes:

determining that the product of distinct counts in each column for a particular permutation of columns is equal to an overall count of rows for said columns; and

wherein said step of determining a view includes concluding that said particular permutation forms a likely fully orthogonal complete basis;

7. The method of claim 1, wherein a low mean of absolute values of differences between individual counts and mean counts, divided by mean count, is less than 10%.

13. The method of claim 1, wherein the orthogonal basis is a fully orthogonal complete basis, a fully orthogonal partial basis, or a semi-orthogonal partial basis.

14. The method of claim 1, wherein:

said step of assigning comprises determining that a count of distinct values in a first column multiplied by a count of distinct values in a second column is less than or equal to a count of all rows in a source table for said first column and second column; and

said step of determining a view comprises concluding that the first column and the second column do not, in combination, form an orthogonal basis.

15. The method of claim 1, wherein:

said step of assigning comprises the step of determining a first column having a count of distinct values equal to a count of rows in a source table for said first column;

said step of determining a view comprises concluding that the first column, by itself, is an orthogonal basis.

16. The method of claim 6, wherein said assigning further includes the steps of:

ranking columns by mean of absolute values of differences between individual counts and mean counts, divided by mean count;

selecting said permutation of columns based on those ranked columns having a low mean of absolute values of differences between individual counts and mean counts, divided by mean count.

8. A computer-implemented method for presenting a view of data in a multidimensional database having one or more rows and one or more columns, the method comprising:

identifying a region of orthogonality in the multidimensional database,

wherein, for the one or more rows of the multidimensional database, values for a first set of one or more columns are not fully orthogonal in relation to values for a second set of one or more columns;

wherein said region is a subset of rows, from the one or more rows, for which values of the first set of one or more columns are orthogonal to values of the second set of one or more columns;

determining a view of the data based upon said region of orthogonality;

displaying said view.

9. The method of claim 8, wherein said identifying includes, for a first column and a second column, each of said columns having one or more distinct values:

a) creating a nested array whose outer elements are said distinct values for said first column and whose inner elements are said distinct values for said second column;

b) ranking values of said outer elements of said nested array by a count of entries in each of their associated inner elements;

c) creating a sister nested array whose outer elements are said distinct values for said second column and whose inner elements are said distinct values for said first column;

d) ranking values of said outer elements of said sister nested array by a count of entries in each of their associated inner elements;

e) selecting a row having the highest rank in said nested array;

f) determining which distinct values in said inner elements of said selected row of said nested array are high ranked values of said outer elements of said sister nested array;

g) unioning said distinct values of said outer elements of said selected row of said nested array with the cumulative union of all higher ranked rows, if any;

h) intersecting said distinct values of said inner elements of said selected row of said nested array that were determined to have high ranks in said outer elements of said sister nested array with the cumulative intersection of all higher ranked rows.

10. The method of claim 8, wherein said identifying is performed only with respect to columns that are not keys and that do not form part of a fully orthogonal basis.

11. The method of claim 8, wherein said identifying begins with a column pair having a highest orthogonality index as determined from a structure of orthogonality indices.

17. The method of claim 9, wherein said identifying includes:

creating an orthogonal view size for said selected row; and

initializing said orthogonal view size to a distinct count of said first column multiplied by a distinct count of said second column.

18. The method of claim 8, wherein said identifying includes unioning and intersecting local regions of orthogonality to discover orthogonal zones of three or higher dimensions.

19. The method of claim 8, wherein said identifying comprises identifying orthogonal tuples.

12. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for presenting a view of data in a multidimensional database, the method comprising:

assigning aggregate measures of orthogonality to one or more combinations of two or more columns in the multidimensional database;

wherein each aggregate measure of orthogonality indicates a measure of interdependence between values in a first column and values in one or more other columns;

identifying a region of orthogonality in the multidimensional database,

wherein, for one or more rows of the multidimensional database, values for a first set of one or more columns are not fully orthogonal in relation to values for a second set of one or more columns;

wherein said region is a subset of rows, from the one or more rows, for which values of the first set of one or more columns are orthogonal to values of the second set of one or more columns;

determining a view of data based at least upon said aggregate measures of orthogonality and said region of orthogonality, said determining including determining an orthogonal basis for the view;

wherein said view is of a subset of data in the multidimensional database;

wherein said orthogonal basis is one or more columns of the multidimensional database selected based on the aggregate measures of orthogonality and said region of orthogonality; and

displaying said view of data.

20. The program storage device of claim 12, wherein the step of assigning aggregate measures of orthogonality comprises scanning a sampling of data from a source table in the multidimensional database,

wherein said view comprises a certain value that is found in the set of all data in the source table but is not found in the sampling of data from the source table.

21. The program storage device of claim 12, wherein the method further comprises:

identifying a region of orthogonality in the multidimensional database,

wherein, for one or more rows of the multidimensional database, values for a first set of one or more columns are not fully orthogonal in relation to values for a second set of one or more columns;

wherein said region is a subset of rows, from the one or more rows, for which values of the first set of one or more columns are orthogonal to values of the second set of one or more columns; and

wherein said step of determining a view further includes determining a view of data based at least upon said region of orthogonality.

22. The program storage device of claim 12, wherein said step of assigning includes calculating orthogonality indices for each column in the combinations of two or more columns.

23. The program storage device of claim 22, wherein said calculating includes:

a) selecting a distinct value in a column;

b) selecting all rows having said distinct value for the column;

c) selecting a sister column different from the column;

d) calculating a count ratio equal to a count of distinct values for said sister column in said rows, divided by a count of overall distinct values for said sister column;

e) repeating b), c), and d) for each additional distinct value in said column; and

f) averaging said count ratios.

24. The program storage device of claim 23, wherein said calculating begins with a column forming a likely orthogonal complete basis and advances to a next column by selecting a column forming a likely fully orthogonal complete basis, if available.

25. The program storage device of claim 12, wherein said step of assigning includes:

determining that the product of distinct counts in each column for a particular permutation of columns is equal to an overall count of rows for said columns; and

wherein said step of determining a view includes concluding that said particular permutation forms a likely fully orthogonal complete basis;

26. The program storage device of claim 25, wherein said assigning further includes the steps of:

ranking columns by mean of absolute values of differences between individual counts and mean counts, divided by mean count;

selecting said permutation of columns based on those ranked columns having a low mean of absolute values of differences between individual counts and mean counts, divided by mean count.

27. The program storage device of claim 26, wherein a low mean of absolute values of differences between individual counts and mean counts, divided by mean count, is less than 10%.

28. The program storage device of claim 12, wherein the orthogonal basis is a fully orthogonal complete basis, a fully orthogonal partial basis, or a semi-orthogonal partial basis.

29. The program storage device of claim 12, wherein:

said step of assigning comprises determining that a count of distinct values in a first column multiplied by a count of distinct values in a second column is less than or equal to a count of all rows in a source table for said first column and second column; and

said step of determining a view comprises concluding that the first column and the second column do not, in combination, form an orthogonal basis.

30. The program storage device of claim 12, wherein:

said step of assigning comprises the step of determining a first column having a count of distinct values equal to a count of rows in a source table for said first column;

said step of determining a view comprises concluding that the first column is an orthogonal basis.

31. The program storage device of claim 12, wherein said identifying includes, for a first column and a second column, each of said columns having one or more distinct values:

a) creating a nested array whose outer elements are said distinct values for said first column and whose inner elements are said distinct values for said second column;

b) ranking values of said outer elements of said nested array by a count of entries in each of said outer elements of said nested array'"'"'s associated inner elements;

c) creating a sister nested array whose outer elements are said distinct values for said second column and whose inner elements are said distinct values for said first column;

d) ranking values of said outer elements of said sister nested array by a count of entries in each of said outer elements of said sister nested array'"'"'s associated inner elements;

e) selecting a row having the highest rank in said nested array;

f) determining which distinct values in said inner elements of said selected row of said nested array are high ranked values of said outer elements of said sister nested array;

g) unioning said distinct values of said outer elements of said selected row of said nested array with the cumulative union of all higher ranked rows, if any;

h) intersecting said distinct values of said inner elements of said selected row of said nested array that were determined to have high ranks in said outer elements of said sister nested array with the cumulative intersection of all higher ranked rows.

32. The program storage device of claim 31, wherein said identifying includes:

creating an orthogonal view size for said selected row; and

initializing said orthogonal view size to a distinct count of said first column multiplied by a distinct count of said second column.

33. The program storage device of claim 12, wherein said identifying is performed only with respect to columns that are not keys and that do not form part of a fully orthogonal basis.

34. The program storage device of claim 12, wherein said identifying begins with a column pair having a highest orthogonality index as determined from a structure of orthogonality indices.

35. The program storage device of claim 12, wherein said identifying includes unioning and intersecting local regions of orthogonality to discover orthogonal zones of three or higher dimensions.

36. The program storage device of claim 12, wherein said identifying comprises identifying orthogonal topics.