US6094651A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Discovery-driven exploration of OLAP data cubes
Assignee: International Business Machines Corp
•
Filing: 1997-08-22
•
Granted: 2000-07-25
•
Expires: 2017-08-22
Abstract
Abstract A method for locating data anomalies in a k dimensional data cube that includes the steps of associating a surprise value with each cell of a data cube, and indicating a data anomaly when the surprise value associated with a cell exceeds a predetermined exception threshold. According to one aspect of the invention, the surprise value associated with each cell is a composite value that is based on at least one of a Self-Exp value for the cell, an In-Exp value for the cell and a Path-Exp value for the cell. Preferably, the step of associating the surprise value with each cell includes the steps of determining a Self-Exp value for the cell, determining an In-Exp value for the cell, determining a Path-Exp value for the cell, and then generating the surprise value for the cell based on the Self-Exp value, the In-Exp value and the Path-value.
Inventors
- 👤 Rakesh Agrawal
- 👤 Sunita Sarawagi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 21:59
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
73 words
A method for locating data anomalies in a k-dimensional data cube, the method comprising the steps of: associating a surprise value with each cell of a data cube, the surprise value associated with a cell representing a degree of anomaly of a content of the cell with respect to other cells of the data cube; and indicating a data anomaly when the surprise value associated with a cell exceeds a predetermined exception threshold.
Claim 2
Independent Claim
73 words
A method for locating data anomalies in a k-dimensional data cube, the method comprising the steps of: associating a surprise value with each cell of a data cube, the surprise value associated with a cell representing a degree of anomaly of a content of the cell with respect to other cells of the data cube; and indicating a data anomaly when the surprise value associated with a cell exceeds a predetermined exception threshold.
Claim 3
Dependent Claim
45 words
The method according to claim 1, wherein the surprise value associated with each cell is a composite value that is based on at least one of a Self-Exp value for the cell, an In-Exp value for the cell and a Path-Exp value for the cell.
Claim 4
Dependent Claim
61 words
The method according to claim 1, wherein the step of associating the surprise value with each cell includes the steps of: determining a Self-Exp value for the cell; determining an In-Exp value for the cell; determining a Path-Exp value for the cell; and generating the surprise value for the cell based on the Self-Exp value, the In-Exp value and the Path-value.
Claim 5
Dependent Claim
36 words
The method according to claim 3, wherein the Self-Exp value for the cell represents a degree of anomaly of the cell with respect to other cells at a same level of aggregation in the data cube.
Claim 6
Dependent Claim
25 words
The method according to claim 3, wherein the In-Exp value for the cell represents a degree of anomaly underneath the cell in the data cube.
Claim 7
Dependent Claim
29 words
The method according to claim 5, wherein the In-Exp value for the cell is a maximum surprise value associated with all cells in the data cube underneath the cell.
Claim 8
Dependent Claim
30 words
The method according to claim 5, wherein the In-Exp value for the cell is a sum of surprise values associated with all cells in the data cube underneath the cell.
Claim 9
Dependent Claim
30 words
The method according to claim 3, wherein the Path-Exp value for the cell represents a degree of surprise for each respective drill-down path in the data cube from the cell.
Claim 10
Dependent Claim
35 words
The method according to claim 8, wherein the Path-Exp value for the cell is based on a drill-down path having a fewest number of high value In-Exp cells in the data cube underneath the cell.
Claim 11
Dependent Claim
33 words
The method according to claim 3, wherein the step of indicating the data anomaly includes the step of displaying the cell having a background intensity corresponding to the surprise value of the cell.
Claim 12
Dependent Claim
17 words
The method according to claim 10, wherein the background intensity corresponds to the Self-Exp for the cell.
Claim 13
Dependent Claim
33 words
The method according to claim 3, wherein the step of indicating the data anomaly includes the step of displaying the cell having a border intensity corresponding to the surprise value of the cell.
Claim 14
Dependent Claim
17 words
The method according to claim 12, wherein the border intensity corresponds to the In-Exp for the cell.
Claim 15
Dependent Claim
31 words
The method according to claim 1, wherein the surprise value of the cell is a residual difference between an expected value for the cell and an actual value for the cell.
Claim 16
Dependent Claim
33 words
The method according to claim 14, further comprising the step of summing coefficients corresponding to each of 2k-1 levels of aggregation of the data cube for obtaining the expected value of the cell.
Claim 17
Dependent Claim
33 words
The method according to claim 15, further comprising the step of multiplying coefficients corresponding to each of 2k-1 levels of group-bys of the data cube for obtaining the expected value of the cell.
Claim 18
Dependent Claim
47 words
The method according to claim 15, further comprising the step of determining a coefficient for each group-by by recursively subtracting all coefficients from group-bys that are at a smaller level of detail than a level of detail of the group-by from an average value at the group-by.
Claim 19
Dependent Claim
47 words
The method according to claim 15, further comprising the step of determining a coefficient for each group-by by recursively subtracting all coefficients from group-bys that are at a smaller level of detail than a level of detail of the group-by from an median value at the group-by.
Claim 20
Dependent Claim
47 words
The method according to claim 14, wherein the residual difference is determined using the steps of: recursively averaging all values of the data cube along each dimension of the data cube; and recursively subtracting the average value from each value along each dimension of the data cube.
Claim 21
Dependent Claim
52 words
The method according to claim 1, further comprising the steps of: determining aggregate values for each group-by of the data cube based on a selected aggregation function; determining residuals for the cell at each group-by of the data cube; and summarizing exceptional values of the data cube based on the determined residuals.
Claim 22
Dependent Claim
50 words
The method according to claim 20, wherein the step of determining residuals at each group-by includes the steps of: determining an average value for each cell at each level of aggregation; and recursively subtracting from each average value residuals that are at a lower level of detail than the cell.
Claim 23
Dependent Claim
94 words
A program storage device comprising: a storage area; and information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps comprising: associating a surprise value with each cell of a data cube, the surprise value associated with a cell representing a degree of anomaly of a content of the cell with respect to other cells of the data cube; and indicating a data anomaly when the surprise value associated with a cell exceeds a predetermined exception threshold.
Claim 24
Dependent Claim
94 words
A program storage device comprising: a storage area; and information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps comprising: associating a surprise value with each cell of a data cube, the surprise value associated with a cell representing a degree of anomaly of a content of the cell with respect to other cells of the data cube; and indicating a data anomaly when the surprise value associated with a cell exceeds a predetermined exception threshold.
Claim 25
Dependent Claim
47 words
The program storage device according to claim 22, wherein the surprise value associated with each cell is a composite value that is based on at least one of a Self-Exp value for the cell, an In-Exp value for the cell and a Path-Exp value for the cell.
Claim 26
Dependent Claim
65 words
The program storage device according to claim 22, wherein method includes the step of associating the surprise value with each cell includes the steps of: determining a Self-Exp value for the cell; determining an In-Exp value for the cell; determining a Path-Exp value for the cell; and generating the surprise value for the cell based on the Self-Exp value, the In-Exp value and the Path-value.
Claim 27
Dependent Claim
38 words
The program storage device according to claim 24, wherein the Self-Exp value for the cell represents a degree of anomaly of the cell with respect to other cells at a same level of aggregation in the data cube.
Claim 28
Dependent Claim
27 words
The program storage device according to claim 24, wherein the In-Exp value for the cell represents a degree of anomaly underneath the cell in the data cube.
Claim 29
Dependent Claim
31 words
The program storage device according to claim 26, wherein the In-Exp value for the cell is a maximum surprise value associated with all cells in the data cube underneath the cell.
Claim 30
Dependent Claim
32 words
The program storage device according to claim 26, wherein the In-Exp value for the cell is a sum of surprise values associated with all cells in the data cube underneath the cell.
Claim 31
Dependent Claim
32 words
The program storage device according to claim 24, wherein the Path-Exp value for the cell represents a degree of surprise for each respective drill-down path in the data cube from the cell.
Claim 32
Dependent Claim
37 words
The program storage device according to claim 29, wherein the Path-Exp value for the cell is based on a drill-down path having a fewest number of high value In-Exp cells in the data cube underneath the cell.
Claim 33
Dependent Claim
37 words
The program storage device according to claim 24, wherein method includes the step of indicating the data anomaly includes the step of displaying the cell having a background intensity corresponding to the surprise value of the cell.
Claim 34
Dependent Claim
19 words
The program storage device according to claim 31, wherein the background intensity corresponds to the Self-Exp for the cell.
Claim 35
Dependent Claim
35 words
The program storage device according to claim 24, wherein the step of indicating the data anomaly includes the step of displaying the cell having a border intensity corresponding to the surprise value of the cell.
Claim 36
Dependent Claim
19 words
The program storage device according to claim 33, wherein the border intensity corresponds to the In-Exp for the cell.
Claim 37
Dependent Claim
33 words
The program storage device according to claim 22, wherein the surprise value of the cell is a residual difference between an expected value for the cell and an actual value for the cell.
Claim 38
Dependent Claim
38 words
The program storage device according to claim 35, wherein the method further comprises the step of summing coefficients corresponding to each of 2k-1 levels of aggregation of the data cube for obtaining the expected value of the cell.
Claim 39
Dependent Claim
52 words
The program storage device according to claim 36, wherein the method further comprises the step of determining a coefficient for each group-by by recursively subtracting all coefficients from group-bys that are at a smaller level of detail than a level of detail of the group-by from an average value at the group-by.
Claim 40
Dependent Claim
52 words
The program storage device according to claim 36, wherein the method further comprises the step of determining a coefficient for each group-by by recursively subtracting all coefficients from group-bys that are at a smaller level of detail than a level of detail of the group-by from an median value at the group-by.
Claim 41
Dependent Claim
38 words
The program storage device according to claim 35, wherein the method further comprises the step of multiplying coefficients corresponding to each of 2k-1 levels of group-bys of the data cube for obtaining the expected value of the cell.
Claim 42
Dependent Claim
50 words
The program storage device according to claim 35, wherein the residual difference is determined using the method steps of: recursively averaging all values of the data cube along each dimension of the data cube; and recursively subtracting the average value from each value along each dimension of the data cube.
Claim 43
Dependent Claim
57 words
The program storage device according to claim 22, wherein the method further comprises the steps of: determining aggregate values for each group-by of the data cube based on a selected aggregation function; determining residuals for the cell at each group-by of the data cube; and summarizing exceptional values of the data cube based on the determined residuals.
Claim 44
Dependent Claim
52 words
The program storage device according to claim 41, wherein the step of determining residuals at each group-by includes the steps of: determining an average value for each cell at each level of aggregation; and recursively subtracting from each average value residuals that are at a lower level of detail than the cell.
Claim 45
Dependent Claim
18 words
The program storage device according to claim 22, wherein the program storage device includes a magnetically recordable medium.
Claim 46
Dependent Claim
18 words
The program storage device according to claim 22, wherein the program storage device includes an optically recordable medium.
References Cited (Backward Citations)
US4719571A
Cited
US5031206A
Cited
US5168565A
Cited
US4956774A
Cited
US5321612A
Cited
US5263120A
Cited
US5359724A
Cited
US5418951A
Cited
US5446908A
Cited
US5655137A
Cited
US5713020A
Cited
US5742283A
Cited
US5598559A
Cited
US5511190A
Cited
US5669006A
Cited
US5808966A
Cited
US5825482A
Cited
US5784540A
Cited
US5832475A
Cited
US5799311A
Cited
US5890191A
Cited
US5799300A
Cited
US5822751A
Cited
US5926820A
Cited
US5890151A
Cited
US5884320A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-25 | 2004-01-24 | 2004-07-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-25 | 2008-01-24 | 2008-07-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-25 | 2012-01-24 | 2012-07-25 | $7700.00 | Window Closed / Lapsed |