Patent US5987467A successfully refreshed from Google Patents.
US5987467A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of calculating tuples for data cubes
Assignee: Columbia University
•
Filing: 1997-08-15
•
Granted: 1999-11-16
•
Expires: 2017-08-15
Abstract
Abstract A method and apparatus of calculating data cubes is shown in which a data set is partitioned into memory sized data fragments and cuboid tuples are calculated from the data fragments. A search lattice of the data cube is used as a basis for ordering calculations of lower dimensional cuboids in the data cube. Identification of a minimum number of paths through the lattice that is sufficient to traverse all nodes in the lattice is achieved by iteratively duplicating twice all paths in a lower dimensional space, distributing a new attribute to the first duplicate, moving end points from paths of the second duplicate to a corresponding path in the first duplicate and merging the first and second duplicates.
Inventors
- 👤 Kenneth A. Ross
- 👤 Divesh Srivastava
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:32
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; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
99 words
A method of constructing a data cube data structure from a data set, comprising the steps of: partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment, determining whether the size of the data fragment exceeds a predetermined threshold, and when the size of the data fragment does not exceed the predetermined threshold, computing cuboid tuples from the data fragment according to: sorting data of the data fragment by a first order of attributes, and calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.
Claim 2
Independent Claim
99 words
A method of constructing a data cube data structure from a data set, comprising the steps of: partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment, determining whether the size of the data fragment exceeds a predetermined threshold, and when the size of the data fragment does not exceed the predetermined threshold, computing cuboid tuples from the data fragment according to: sorting data of the data fragment by a first order of attributes, and calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.
Claim 3
Dependent Claim
68 words
The method of claim 1, further comprising steps of: when the size of the data fragment exceeds the predetermined threshold, partitioning the data fragment according to a second attribute into a plurality of sub-fragments, and for each sub-fragment, determining whether the size of the sub-fragment exceeds the predetermined threshold, and when the size of the sub-fragment does not exceed the predetermined threshold, computing cuboid tuples from the sub-fragment.
Claim 4
Dependent Claim
58 words
The method of claim 2, further comprising steps of: when the size of a sub-fragment exceeds the predetermined threshold, recursively partitioning the sub-fragment by additional attributes into other data fragments until a size of each other data fragment does not exceed the predetermined threshold, and for each other data fragment, computing cuboid tuples from the other data fragment.
Claim 5
Dependent Claim
68 words
The method of claim 1, wherein the computing step further comprises, in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively: resorting the data fragment by additional sort orders of attributes, and calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.
Claim 6
Dependent Claim
28 words
The method of claim 4, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.
Claim 7
Dependent Claim
108 words
The method of claim 5, wherein the minimum number of paths are selected according to a method comprising the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension, duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate.
Claim 8
Dependent Claim
37 words
The method of claim 6, further comprising a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.
Claim 9
Dependent Claim
22 words
The method of claim 4, wherein the order of paths is chosen to possess a common prefix with a previous sort order.
Claim 10
Dependent Claim
102 words
The method of claim 1, further comprising steps of: identifying a parent cuboid for a cuboid that remains to be calculated, determining whether a size of the parent cuboid exceeds the predetermined threshold, and in the event that the size of the parent cuboid exceeds the predetermined threshold, partitioning the parent cuboid into second data fragments according to a second attribute, for each second data fragment, determining whether the size of the second data fragment exceeds the predetermined threshold, and when the size of the second data fragment does not exceed the predetermined threshold, computing cuboid tuples from the second data fragment.
Claim 11
Dependent Claim
33 words
The method of claim 9, further comprising a step of in the event that the size of the parent cuboid does not exceed the predetermined threshold, calculating remaining cuboids from the parent cuboid.
Claim 12
Dependent Claim
67 words
The method of claim 10, wherein the step of calculating remaining cuboids comprises the steps of: sorting the parent cuboid according to a first sort order, computing uncalculated cuboids indexed by a prefix of the first sort order, and iteratively: resorting the parent cuboid according to additional sort orders, and computing uncalculated cuboids indexed by a prefix of the additional sort orders until all cuboids are calculated.
Claim 13
Dependent Claim
28 words
The method of claim 11, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.
Claim 14
Dependent Claim
22 words
The method of claim 11, wherein the additional sort orders are chosen to possess a common prefix with a previous sort order.
Claim 15
Independent Claim
138 words
A method of selecting a minimum number of paths necessary to traverse a search lattice of a data cube, comprising the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension, duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate; and after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.
Claim 16
Independent Claim
138 words
A method of selecting a minimum number of paths necessary to traverse a search lattice of a data cube, comprising the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension, duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate; and after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.
Claim 17
Dependent Claim
98 words
A data cube data structure constructed from a data set according to the method of: partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment, determining whether the size of the data fragment exceeds a predetermined threshold, and when the size of the data fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the sorted data fragment according to: sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.
Claim 18
Dependent Claim
98 words
A data cube data structure constructed from a data set according to the method of: partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment, determining whether the size of the data fragment exceeds a predetermined threshold, and when the size of the data fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the sorted data fragment according to: sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.
Claim 19
Dependent Claim
75 words
The data cube data structure of claim 15 wherein the method further comprises steps of: when the size of the data fragment exceeds the predetermined threshold, partitioning the data fragment according to a second attribute into a plurality of sub-fragments, and for each sub-fragment, determining whether the size of the sub-fragment exceeds the predetermined threshold, and when the size of the sub-fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the sub-fragment.
Claim 20
Dependent Claim
65 words
The data cube data structure of claim 16, wherein the method further comprises steps of: when the size of a sub-fragment exceeds the predetermined threshold, recursively partitioning the sub-fragment by additional attributes into other data fragments until a size of each other data fragment does not exceed the predetermined threshold, and for each other data fragment, computing cuboid fragment tuples from the other data fragment.
Claim 21
Dependent Claim
74 words
The data cube data structure of claim 15, wherein the computing step further comprises in the event that all cuboid fragments to be calculated from the data fragment are not calculated by the calculating step, recursively: resorting the data fragment by additional sort orders of attributes, and calculating tuples for all cuboid fragments indexed by prefixes of the additional sort orders until all cuboid fragments to be calculated from the data fragment are calculated.
Claim 22
Dependent Claim
34 words
The data cube data structure of claim 18, wherein the sorting and resorting steps of the method are performed to traverse a minimum number of paths through a search lattice of the data cube.
Claim 23
Dependent Claim
111 words
The data cube data structure of claim 19, wherein the minimum number of paths are selected according to a sub-method comprising the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension, duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate.
Claim 24
Dependent Claim
43 words
The data cube data structure of claim 20, wherein the sub-method further comprises a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.
Claim 25
Dependent Claim
36 words
The data cube data structure of claim 21, further comprising a step of in the event that the size of the parent cuboid does not exceed the predetermined threshold, calculating remaining cuboids from the parent cuboid.
Claim 26
Dependent Claim
25 words
The data cube data structure of claim 18, wherein the additional sort orders are chosen to possess a common prefix with a previous sort order.
Claim 27
Dependent Claim
69 words
The data cube structure of claim 23, wherein the step of calculating remaining cuboids comprises the steps of: sorting the parent cuboid according to a first sort order, computing uncalculated cuboids indexed by a prefix of the first sort order, recursively, resorting the parent cuboid according to additional sort orders, and computing uncalculated parent cuboids indexed by a prefix of the additional sort orders until all cuboids are calculated.
Claim 28
Dependent Claim
31 words
The data cube data structure of claim 24, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.
Claim 29
Dependent Claim
25 words
The data cube data structure of claim 24, wherein the additional sorts orders are chosen to possess a common prefix with a previous sort order.
Claim 30
Dependent Claim
103 words
The data cube data structure of claim 15 further comprising the steps of: identifying a parent cuboid for an uncalculated cuboid; determining whether a size of the parent cuboid exceeds the predetermined threshold, and in the event that the size of the parent cuboid exceeds the predetermined threshold, partitioning the parent cuboid into second data fragments according to a second attribute, for each second data fragment, determining whether the size of the second data fragment exceeds the predetermined threshold, and when the size of the second data fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the second data fragment.
Claim 31
Independent Claim
114 words
A method of calculating a data cube from a data set, comprising the steps of: identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and for each identified path, calculating the data cube from the data set indexed by each of the identified paths including, for each path: sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and calculating cuboids indexed by the sort order, wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.
Claim 32
Independent Claim
114 words
A method of calculating a data cube from a data set, comprising the steps of: identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and for each identified path, calculating the data cube from the data set indexed by each of the identified paths including, for each path: sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and calculating cuboids indexed by the sort order, wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.
Claim 33
Dependent Claim
104 words
A data cube data structure constructed from a data set according to the method of: identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and calculating cuboids indexed by each of the identified paths including, for each path: sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and calculating cuboids indexed by the sort order, wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.
Claim 34
Dependent Claim
104 words
A data cube data structure constructed from a data set according to the method of: identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and calculating cuboids indexed by each of the identified paths including, for each path: sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and calculating cuboids indexed by the sort order, wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.
Claim 35
Independent Claim
97 words
A method for performing a multiple attribute query on a data set in a memory, comprising the steps of: determining whether a size of the data set exceeds a predetermined threshold; when the size exceeds the predetermined threshold: partitioning the data set by a first attribute into a plurality of data fragments, and computing cuboid tuples from the data fragments according to; sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order, and identifying cuboid tuples responsive to the query.
Claim 36
Independent Claim
97 words
A method for performing a multiple attribute query on a data set in a memory, comprising the steps of: determining whether a size of the data set exceeds a predetermined threshold; when the size exceeds the predetermined threshold: partitioning the data set by a first attribute into a plurality of data fragments, and computing cuboid tuples from the data fragments according to; sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order, and identifying cuboid tuples responsive to the query.
Claim 37
Dependent Claim
16 words
The method of claim 30, wherein the attribute of partition is selected independently from the query.
Claim 38
Dependent Claim
68 words
The method of claim 30, wherein the computing step further, comprises in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively: resorting the data fragment by additional sort orders of attributes, and calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.
Claim 39
Dependent Claim
28 words
The method of claim 32, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.
Claim 40
Dependent Claim
108 words
The method of claim 33, wherein the minimum number of paths are selected according to a method comprising the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension: duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate.
Claim 41
Dependent Claim
37 words
The method of claim 34, further comprising a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.
Claim 42
Dependent Claim
22 words
The method of claim 34, wherein an order of paths is chosen to possess a common prefix with a previous sort order.
Claim 43
Dependent Claim
150 words
Apparatus for performing a multiple attribute query on a data set, comprising: a first memory for storing the data set, a second memory that implements data storage and retrieval faster than the first memory, and processor in communication with the first and second memories, wherein: the processor determines whether the data set fits within the second memory, when the data set does not fit within the second memory, the processor partitions the data set into a plurality of data fragments by a first attribute, for each data fragment, the processor loads the data fragment into the second memory, and the processor computes cuboid tuples from the loaded data fragment according to: sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order wherein certain of the computed cuboid tuples are responsive to the query.
Claim 44
Dependent Claim
150 words
Apparatus for performing a multiple attribute query on a data set, comprising: a first memory for storing the data set, a second memory that implements data storage and retrieval faster than the first memory, and processor in communication with the first and second memories, wherein: the processor determines whether the data set fits within the second memory, when the data set does not fit within the second memory, the processor partitions the data set into a plurality of data fragments by a first attribute, for each data fragment, the processor loads the data fragment into the second memory, and the processor computes cuboid tuples from the loaded data fragment according to: sorting data of the data fragment by a first order of attributes, calculating tuples for all cuboid fragments indexed by a prefix of the first sort order wherein certain of the computed cuboid tuples are responsive to the query.
Claim 45
Dependent Claim
19 words
Apparatus of claim 37, wherein the processor selects an attribute of partition independently from attributes defined in the query.
Claim 46
Dependent Claim
70 words
Apparatus of claim 37, wherein the processor further computes cuboid tuples according to, in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively: resorting the data fragment by additional sort orders of attributes, and calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.
Claim 47
Dependent Claim
28 words
Apparatus of claim 39, wherein the processor performs the sorting and resorting steps to traverse a minimum number of paths through a search lattice of the data cube.
Claim 48
Dependent Claim
105 words
Apparatus of claim 40, wherein the processor selects the minimum number of paths according to the steps of: counting out a number of dimensions equal to a number of dimensions of the data cube, and for each counted dimension: duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension, distributing an attribute associated with the counted dimension to the first duplicate, for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and merging the paths of the first and second duplicate.
References Cited (Backward Citations)
US5900880A
Cited
US5832475A
Cited
US5799300A
Cited
US5822751A
Cited
US5890150A
Cited
US5890151A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |