Patent US6003036A successfully refreshed from Google Patents.
US6003036A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interval-partitioning method for multidimensional data
Assignee: Individual
•
Filing: 1998-02-12
•
Granted: 1999-12-14
•
Expires: 2018-02-12
Abstract
Abstract A data structure that uses one or more keys which are members of a multidimensional composite key to partition sparse data (FIG. 2A, FIG. 2B) into a hypercube like structure (FIG. 1). Only the data structure produced by the method in this invention is actually better than a hypercube since all involved keys can have true symmetric access as opposed to just the keys that have the highest sort order significance. Equivalent query efficiency could only be otherwise obtained through storing multiple copies of the sparse data sorted on different permutations of the member keys of the multidimensional composite key (FIG. 2C). The data structure has two major components: the partitioned data with or without the boundary keys and the non-dense index necessarily containing the boundary keys (FIG. 3). This data structure and partitioning method can be used to partition multidimensional data across physical hardware storage devices and parallel computer architectures (FIG. 4) to produce variable grained data partitions that can be queried, loaded, or updated in parallel and simultaneous multidimensional index selectivity. And finally, as noted above, this same partitioning method can be used in a nested fashion or in combination with other data structures to provide good performance for the batch maintenance of volatile data and special performance advantages for true time-series data.
Inventors
- 👤 Michael W. Martin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 17:28
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
324 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity produced by any combination of said keys or said groups of one or more keys can be precisely controlled comprising the steps of: a) determining the number of records from said data to be packed into each unit partition b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity of combinations of said keys can be precisely controlled by said selectivity for each said key or group of one or more said keys as determined in step b).
Claim 2
Independent Claim
324 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity produced by any combination of said keys or said groups of one or more keys can be precisely controlled comprising the steps of: a) determining the number of records from said data to be packed into each unit partition b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity of combinations of said keys can be precisely controlled by said selectivity for each said key or group of one or more said keys as determined in step b).
Claim 3
Independent Claim
350 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet the degree of packing of records from said data into unit partitions can be precisely controlled comprising the steps of: a) determining the number of records from said data to be packed into each unit partition b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by step b) and whose packing of said records into said unit partitions can be precisely controlled by step a).
Claim 4
Independent Claim
350 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet the degree of packing of records from said data into unit partitions can be precisely controlled comprising the steps of: a) determining the number of records from said data to be packed into each unit partition b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by step b) and whose packing of said records into said unit partitions can be precisely controlled by step a).
Claim 5
Dependent Claim
29 words
The method of claim 2, wherein all said unit partitions, file pages, or I/O sectors are fully packed to hold the maximum number of said records per unit partition.
Claim 6
Dependent Claim
40 words
The method of claim 3, wherein said records within each said unit partition are further subpartitioned by the method of claim 3 in a nested fashion such that additional said computer memory or said computer storage media are not required.
Claim 7
Dependent Claim
54 words
The method of claim 4 combined with other data structures or partitioning methods such that said data can be partitioned across hardware devices or entire computers with conventional methods and subpartitioned by the method of claim 3 in a nested fashion such that additional said computer memory or said computer storage are not required.
Claim 8
Independent Claim
410 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet a non-dense index which requires no addition computer memory or computer storage media space can be built comprising the steps of: a) determining the number of records from said data to be packed into each unit partition taking into account the extra available space in said unit partitions due to the removal of one or more said component records from one said record in said unit partitions b) determining selectivity of each said key or said group of one or more records chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) and removing one or more said component keys from one said record out of each said unit partition corresponding to each entry in said non-dense index f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by st b) and on which a corresponding non-dense index requiring no additional computer memory or computer storage media space can be built.
Claim 9
Independent Claim
410 words
A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet a non-dense index which requires no addition computer memory or computer storage media space can be built comprising the steps of: a) determining the number of records from said data to be packed into each unit partition taking into account the extra available space in said unit partitions due to the removal of one or more said component records from one said record in said unit partitions b) determining selectivity of each said key or said group of one or more records chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) and removing one or more said component keys from one said record out of each said unit partition corresponding to each entry in said non-dense index f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by st b) and on which a corresponding non-dense index requiring no additional computer memory or computer storage media space can be built.
References Cited (Backward Citations)
US5226109A
Cited
US5551027A
Cited
US5701467A
Cited
US5495539A
Cited
US5497486A
Cited
US5870768A
Cited
US5546499A
Cited
US5710915A
Cited
US5787422A
Cited
US5878424A
Cited
US5864857A
Cited
US5886700A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-13 | 2003-06-14 | 2003-12-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-13 | 2007-06-14 | 2007-12-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-13 | 2011-06-14 | 2011-12-14 | $7700.00 | Window Closed / Lapsed |