US5978788A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for generating multi-representations of a data cube
Assignee: Google LLC
•
Filing: 1997-04-14
•
Granted: 1999-11-02
•
Expires: 2017-04-14
Abstract
Abstract An apparatus and method for approximating the data stored in a databases by generating multiple projections and representations from the database such that the OLAP queries for the original database (such as aggregation and histogram operations) may be applied to the approximated version of the database, which can be much smaller than the original databases. Other aspects optimize a mapping, via a mapping (or dimension) table, of non-numeric or numeric attributes to other numeric attributes such that the error incurred on applying queries to the approximated version of the database is minimized. Still further aspects define boundaries of approximations so that the boundaries are preserved when approximated versions of the databases are generated.
Inventors
- 👤 Vittorio Castelli
- 👤 Anant Deep Jhingran
- 👤 Chung-Sheng Li
- 👤 John Timothy Robinson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/28; G06F16/283; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
81 words
A computerized method of generating multi-representations of a data cube, comprising the steps of: splitting the data cube, which includes a plurality of lattice points, into a plurality of dimensions; generating representations selected from the group consisting of one or more of multi-resolutions and multi-projections, of one or more said dimensions of the data cube, in response to said splitting step; and reconstructing the data cube from said one or more of multi-resolutions and multi-projections, in response to said generating step.
Claim 2
Dependent Claim
81 words
A computerized method of generating multi-representations of a data cube, comprising the steps of: splitting the data cube, which includes a plurality of lattice points, into a plurality of dimensions; generating representations selected from the group consisting of one or more of multi-resolutions and multi-projections, of one or more said dimensions of the data cube, in response to said splitting step; and reconstructing the data cube from said one or more of multi-resolutions and multi-projections, in response to said generating step.
Claim 3
Dependent Claim
34 words
The method of claim 1, comprising the steps of: said generating step comprising generating said multi-projections of the data cube; storing a reconstructed data cube including said multi-projections, in response to said reconstructing step.
Claim 4
Dependent Claim
41 words
The method of claim 2, for online analytical processing (OLAP), comprising the steps of: receiving a query on a reconstructed data cube at a selected resolution; and synthesizing the reconstructed data cube at said selected resolution, in response to said query.
Claim 5
Dependent Claim
38 words
The method of claim 1 for online analytical processing (OLAP), comprising the steps of: said generating step comprising generating said multi-projections; and synthesizing multi-resolutions of a reconstructed data cube; and storing said multi-resolutions of said reconstructed data cube.
Claim 6
Dependent Claim
18 words
The method of claim 1, comprising the step of querying a reconstructed data cube at a selected resolution.
Claim 7
Dependent Claim
21 words
The method of claim 1, wherein said reconstructing step further comprises the step of compressing each projection of the data cube.
Claim 8
Dependent Claim
13 words
The method of claim 1, wherein the data cube is a multi-dimensional table.
Claim 9
Dependent Claim
77 words
The method of claim 1, further comprising the steps of: iteratively mapping non-numeric attributes or numeric attributes in a database to other numeric attributes; wherein each mapping includes the steps of: synthesizing the data cube at a selected resolution; querying the reconstructed data cube at the selected resolution; and computing and comparing an error between the selected resolution and a previous resolution, in response to said querying step; and selecting a mapping wherein the error is minimized.
Claim 10
Dependent Claim
47 words
The method of claim 8, further comprises the step of: computing a probability for the mapping as a function of a control parameter, if the error is increased in response to said computing and comparing step; and accepting the mapping as a random function of the probability.
Claim 11
Dependent Claim
23 words
The method of claim 1, wherein said generating step further comprises the step of preserving the relative spatial integrity of the lattice points.
Claim 12
Dependent Claim
44 words
The method of claim 10, wherein said generating step further comprises the steps of: said generating step comprising generating said multi-projections of the data cube; identifying boundaries of the data cube; and generating approximated versions of the data cube while preserving the boundaries thereof.
Claim 13
Dependent Claim
53 words
The method of claim 1, wherein said reconstructing step comprises the steps of: selecting lattice points in the data cube; applying one of histograms, aggregations, min, max, and wavelet operators to selected lattice points in the data cube to generate new values; and storing the new values, in response to said applying step.
Claim 14
Dependent Claim
42 words
The method of claim 1, wherein said generating step further comprises the steps of: generating said-multiple projections of the data cube by applying linear or nonlinear functions to the data cube; and storing the multiple projections in a memory for subsequent synthesis.
Claim 15
Dependent Claim
119 words
The method of claim 1, wherein the data cube is generated from a relational table or object-relational table in a relational database, further comprising the steps of: mapping non-numeric or numeric data in the database into another numeric representation; translating the relation table into a FACT table, in response to said mapping step; decomposing the FACT table into multiple FACT tables with a single dependent variable; generating multiple projections of each FACT table; synthesizing multiple representations of the FACT table from the multiple projections; applying one or more of histogram, aggregations, min, max, and wavelet operators to the multiple representations; and selecting one of the multiple representations for computing a specific query as a function of a user-specified tolerance.
Claim 16
Dependent Claim
21 words
A data structure, instantiated in a memory of a computer, said data structure generated according to the method of claim 1.
Claim 17
Dependent Claim
94 words
A computer program product tangibly embodying a program of instructions executable by a computer for generating, multi-representations of a data cube, said method comprising the steps of: splitting the data cube, which includes a plurality of lattice points, into a plurality of dimensions; generating representations selected from the group consisting of one or more of multi-resolutions and multi-projections, of one or more said dimensions of the data cube, in response to said splitting step; and reconstructing the data cube from said one or more of multi-resolutions and multi-projections, in response to said generating step.
Claim 18
Dependent Claim
94 words
A computer program product tangibly embodying a program of instructions executable by a computer for generating, multi-representations of a data cube, said method comprising the steps of: splitting the data cube, which includes a plurality of lattice points, into a plurality of dimensions; generating representations selected from the group consisting of one or more of multi-resolutions and multi-projections, of one or more said dimensions of the data cube, in response to said splitting step; and reconstructing the data cube from said one or more of multi-resolutions and multi-projections, in response to said generating step.
Claim 19
Dependent Claim
36 words
The computer program product of claim 16, comprising the steps of: said generating step comprising generating said multi-projections of the data cube; storing a reconstructed data cube including said multi-projections, in response to said reconstructing step.
Claim 20
Dependent Claim
43 words
The computer program product of claim 17 for online analytical processing (OLAP), comprising the steps of: receiving a query on the reconstructed data cube at a selected resolution; and synthesizing the reconstructed data cube at said selected resolution, in response to said query.
Claim 21
Dependent Claim
40 words
The computer program product of claim 16 for online analytical processing (OLAP), comprising the steps of: said generating step comprising generating said multi-projections; and synthesizing multi-resolutions of a reconstructed data cube; and storing said multi-resolutions of said reconstructed data cube.
Claim 22
Dependent Claim
20 words
The computer program product of claim 16, comprising the step of querying a reconstructed data cube at a selected resolution.
Claim 23
Dependent Claim
23 words
The computer program product of claim 16, wherein said reconstructing step further comprises the step of compressing each projection of the data cube.
Claim 24
Dependent Claim
15 words
The computer program product of claim 16, wherein the data cube is a multi-dimensional table.
Claim 25
Dependent Claim
79 words
The computer program product of claim 16, further comprising the steps of: iteratively mapping non-numeric attributes or numeric attributes in a database to other numeric attributes; wherein each mapping includes the steps of: synthesizing the data cube at a selected resolution; querying the reconstructed data cube at the selected resolution; and computing and comparing an error between the selected resolution and a previous resolution, in response to said querying step; and selecting a mapping wherein the error is minimized.
Claim 26
Dependent Claim
49 words
The computer program product of claim 23, further comprises the step of: computing a probability for the mapping as a function of a control parameter, if the error is increased in response to said computing and comparing step; and accepting the mapping as a random function of the probability.
Claim 27
Dependent Claim
25 words
The computer program product of claim 16, wherein said generating step further comprises the step of preserving the relative spatial integrity of the lattice points.
Claim 28
Dependent Claim
46 words
The computer program product of claim 25, wherein said generating step further comprises the steps of: said generating step comprising generating said multi-projections of the data cube; identifying boundaries of the data cube; and generating approximated versions of the data cube while preserving the boundaries thereof.
Claim 29
Dependent Claim
55 words
The computer program product of claim 16, wherein said reconstructing step comprises the steps of: selecting lattice points in the data cube; applying one of histograms, aggregations, min, max, and wavelet operators to selected lattice points in the data cube to generate new values; and storing the new values, in response to said applying step.
Claim 30
Dependent Claim
45 words
The computer program product of claim 16, wherein said generating step further comprises the steps of: generating said multiple projections of the data cube by applying linear or nonlinear functions to the data cube; and storing the multiple projections in a memory for subsequent synthesis.
Claim 31
Dependent Claim
121 words
The computer program product of claim 16, wherein the data cube is generated from a relational table or object-relational table in a relational database, further comprising the steps of: mapping non-numeric or numeric data in the database into another numeric representation; translating the relation table into a FACT table, in response to said mapping step; decomposing the FACT table into multiple FACT tables with a single dependent variable; generating multiple projections of each FACT table; synthesizing multiple representations of the FACT table from the multiple projections; applying one or more of histogram, aggregations, min, max, and wavelet operators to the multiple representations; and selecting one of the multiple representations for computing a specific query as a function of a user-specified tolerance.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |