US6463180B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Spatial index compression through spatial subdivision encoding
Assignee: Autodesk Inc
•
Filing: 2000-05-10
•
Granted: 2002-10-08
•
Expires: 2020-05-10
Abstract
Abstract A technique for reducing the total storage used in representing data having spatial extents. The data is represented in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure. An encoded representation of the relation of a child node's extents with respect to its parent is stored in the node. A preorder traversal of the tree structure is performed to store it compactly in an output file.
Inventors
- 👤 Ravinder Patnam Krishnaswamy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 15:12
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/40
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
64 words
A computer-implemented method for representing and encoding data having spatial extents, comprising: (a) representing the data in a tree structure having a plurality of nodes; and (b) encoding a spatial identifier for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} th overlap, and degenerate axis Values.
Claim 2
Dependent Claim
64 words
A computer-implemented method for representing and encoding data having spatial extents, comprising: (a) representing the data in a tree structure having a plurality of nodes; and (b) encoding a spatial identifier for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} th overlap, and degenerate axis Values.
Claim 3
Dependent Claim
21 words
The method of claim 1 above, wherein the spatial identifier identifies the node's extents as a subdivision of the parent's extents.
Claim 4
Dependent Claim
13 words
The method of claim 2 above, wherein the subdivision comprises an octant subdivision.
Claim 5
Dependent Claim
27 words
The method of claim 2 above, wherein the subdivision comprises a {fraction (1/16)} th expanded version of an octant subdivision along coordinate planes that divide root extents.
Claim 6
Dependent Claim
22 words
The method of claim 2 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.
Claim 7
Dependent Claim
19 words
The method of claim 5 above, wherein the node classifies data that spans the extents along a coordinate axis.
Claim 8
Dependent Claim
18 words
The method of claim 5 above, wherein the node comprises a merger of nodes along two coordinate axes.
Claim 9
Dependent Claim
30 words
The method of claim 1 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.
Claim 10
Dependent Claim
67 words
A computer-implemented apparatus for representing and encoding data having spatial extents, comprising: (a) means for representing the data in a tree structure having a plurality of nodes; and (b) means for encoding a spatial identifier in each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} overlap, and degenerate axis values.
Claim 11
Dependent Claim
67 words
A computer-implemented apparatus for representing and encoding data having spatial extents, comprising: (a) means for representing the data in a tree structure having a plurality of nodes; and (b) means for encoding a spatial identifier in each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} overlap, and degenerate axis values.
Claim 12
Dependent Claim
21 words
The apparatus of claim 9 above, wherein the spatial identifier identifies the node's extents as a subdivision of the parent's extents.
Claim 13
Dependent Claim
13 words
The apparatus of claim 10 above, wherein the subdivision comprises an octant subdivision.
Claim 14
Dependent Claim
27 words
The apparatus of claim 10 above, wherein the subdivision comprises a {fraction (1/16)} th expanded version of an octant subdivision along coordinate planes that divide root extents.
Claim 15
Dependent Claim
22 words
The apparatus of claim 10 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.
Claim 16
Dependent Claim
19 words
The apparatus of claim 13 above, wherein the node classifies data that spans the extents along a coordinate axis.
Claim 17
Dependent Claim
18 words
The apparatus of claim 13 above, wherein the node comprises a merger of nodes along two coordinate axes.
Claim 18
Dependent Claim
30 words
The apparatus of claim 9 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.
Claim 19
Dependent Claim
66 words
An article of manufacture embodying logic for representing and encoding data having spatial extents, comprising: (a) representing the dam in a tree structure having a plurality of nodes; and (b) encoding a spatial identifier for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, ⅙ th overlap, and degenerate a values.
Claim 20
Dependent Claim
66 words
An article of manufacture embodying logic for representing and encoding data having spatial extents, comprising: (a) representing the dam in a tree structure having a plurality of nodes; and (b) encoding a spatial identifier for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, ⅙ th overlap, and degenerate a values.
Claim 21
Dependent Claim
23 words
The article of manufacture of claim 17 above, wherein the spatial identifier identifies the node's extents as a subdivision of the parent's extents.
Claim 22
Dependent Claim
15 words
The article of manufacture of claim 18 above, wherein the subdivision comprises an octant subdivision.
Claim 23
Dependent Claim
29 words
The article of manufacture of claim 18 above, wherein the subdivision comprises a {fraction (1/16)} th expanded version of an octant subdivision along coordinate planes that divide root extents.
Claim 24
Dependent Claim
24 words
The article of manufacture of claim 18 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.
Claim 25
Dependent Claim
21 words
The article of manufacture of claim 21 above, wherein the node classifies data that spans the extents along a coordinate axis.
Claim 26
Dependent Claim
20 words
The article of manufacture of claim 21 above, wherein the node comprises a merger of nodes along two coordinate axes.
Claim 27
Dependent Claim
32 words
The article of manufacture of claim 17 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.
Claim 28
Dependent Claim
68 words
A data structure stored in a data storage device for representing and encoding data having spatial extents, the data structure comprising a tree structure having a plurality of nodes, wherein a spatial identifier is encoded for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} th overlap, and degenerate axis values.
Claim 29
Dependent Claim
68 words
A data structure stored in a data storage device for representing and encoding data having spatial extents, the data structure comprising a tree structure having a plurality of nodes, wherein a spatial identifier is encoded for each node as a representation of the node's extents with respect to its parent's extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} th overlap, and degenerate axis values.
Claim 30
Dependent Claim
22 words
The data structure of claim 25 above, wherein the spatial identifier identifies the node's extents as a subdivision of the parent's extents.
Claim 31
Dependent Claim
14 words
The data structure of claim 26 above, wherein the subdivision comprises an octant subdivision.
Claim 32
Dependent Claim
28 words
The data structure of claim 26 above, wherein the subdivision comprises a {fraction (1/16)} th expanded version of an octant subdivision along coordinate planes that divide root extents.
Claim 33
Dependent Claim
23 words
The data structure of claim 26 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.
Claim 34
Dependent Claim
20 words
The data structure of claim 29 above, wherein the node classifies data that spans the extents along a coordinate axis.
Claim 35
Dependent Claim
19 words
The data structure of claim 29 above, wherein the node comprises a merger of nodes along two coordinate axes.
Claim 36
Dependent Claim
31 words
The data structure of claim 25 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.
References Cited (Backward Citations)
US5280547A
Cited
US5592667A
Cited
US5737732A
Cited
US5530957A
Cited
US5551027A
Cited
US5640551A
Cited
US5647058A
Cited
US5701467A
Cited
US5463389A
Cited
US5752243A
Cited
US5710916A
Cited
US5606669A
Cited
US5825936A
Cited
US5572221A
Cited
US6161105A
Cited
US5664174A
Cited
US5945982A
Cited
US5847761A
Cited
US5781906A
Cited
US5893104A
Cited
US6308177B1
Cited
US5953722A
Cited
US5968109A
Cited
US5799312A
Cited
US5883823A
Cited
US5963956A
Cited
US5977890A
Cited
US5884320A
Cited
US6092065A
Cited
US6081624A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-07 | 2006-04-08 | 2006-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-07 | 2010-04-08 | 2010-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-07 | 2014-04-08 | 2014-10-08 | $7700.00 | Window Closed / Lapsed |