Patent US6154746A successfully refreshed from Google Patents.
US6154746A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High-dimensional index structure
Assignee: AT&T Inc
•
Filing: 1998-04-22
•
Granted: 2000-11-28
•
Expires: 2018-04-22
Abstract
Abstract A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure is disclosed. The data space is divided into a first plurality of pyramids each having a center point of the data space as a top and a (d-1) dimensional surface of the data space as a base, wherein the first plurality of pyramids is equal to twice the number of dimensions of the data space. Each pyramid is then divided into a second plurality of partitions. A Pyramid-value for each partition is then computed. Finally, each partition is stored in the index structure using the Pyramid-value as an index key.
Inventors
- 👤 Stefan Berchtold
- 👤 Christian Boehm
- 👤 Hans-Peter Kriegel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 13:52
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/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
119 words
A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure, comprising the steps of: splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1 dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space; dividing each pyramid into a second plurality of partitions; computing a Pyramid-value for each partition; and storing each partition in said index structure using said Pyramid-value as an index key.
Claim 2
Independent Claim
119 words
A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure, comprising the steps of: splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1 dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space; dividing each pyramid into a second plurality of partitions; computing a Pyramid-value for each partition; and storing each partition in said index structure using said Pyramid-value as an index key.
Claim 3
Dependent Claim
19 words
A method according to claim 1, wherein said 1-dimensional index structure is created using an order-preserving 1-dimensional access method.
Claim 4
Dependent Claim
22 words
A method according to claim 2, wherein each partition and associated index key are stored in leaf nodes of the index structure.
Claim 5
Dependent Claim
18 words
A method according to claim 2, wherein each partition corresponds to one data page of the index structure.
Claim 6
Dependent Claim
14 words
A method according to claim 2, wherein said 1-dimensional index structure is a B+-tree.
Claim 7
Dependent Claim
25 words
A method according to claim 1, wherein each pyramid is divided parallel to the base of the pyramid to form said second plurality of partitions.
Claim 8
Independent Claim
141 words
A method for storing and querying multidimensional data points, comprising the steps of: splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space; dividing each pyramid into a second plurality of partitions; computing a Pyramid-value for each partition; storing each partition in a 1-dimensional index structure using said Pyramid-value as an index key; computing the range of Pyramid-values affected by the query; querying the index using said range to produce a candidate set of partitions; outputting all candidate partitions that are inside the query range.
Claim 9
Independent Claim
141 words
A method for storing and querying multidimensional data points, comprising the steps of: splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space; dividing each pyramid into a second plurality of partitions; computing a Pyramid-value for each partition; storing each partition in a 1-dimensional index structure using said Pyramid-value as an index key; computing the range of Pyramid-values affected by the query; querying the index using said range to produce a candidate set of partitions; outputting all candidate partitions that are inside the query range.
Claim 10
Dependent Claim
19 words
A method according to claim 7, wherein said 1-dimensional index structure is created using an order-preserving 1-dimensional access method.
Claim 11
Dependent Claim
22 words
A method according to claim 8, wherein each partition and associated index key are stored in leaf nodes of the index structure.
Claim 12
Dependent Claim
18 words
A method according to claim 8, wherein each partition corresponds to one data page of the index structure.
Claim 13
Dependent Claim
14 words
A method according to claim 8, wherein said 1-dimensional index structure is a B+-tree.
Claim 14
Dependent Claim
25 words
A method according to claim 7, wherein each pyramid is divided parallel to the base of the pyramid to form said second plurality of partitions.
References Cited (Backward Citations)
US5701467A
Cited
US5778354A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-28 | 2004-05-29 | 2004-11-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-28 | 2008-05-29 | 2008-11-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-28 | 2012-05-29 | 2012-11-28 | $7700.00 | Window Closed / Lapsed |