US5963956A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method of optimizing database queries in two or more dimensions
Assignee: Telcontar Inc
•
Filing: 1997-02-27
•
Granted: 1999-10-05
•
Expires: 2017-02-27
Abstract
Abstract A method and system for storing and retrieving spatial data objects from a spatial database is discussed. The system stores multi-dimensional objects within the database by determining their position in a multi-tiered coordinate system. One each object has been assigned to a particular coordinate, the object is further assigned to one of many overlapping sections within the coordinate system. Each object is assigned to a particular section of the coordinate system depending on its overall size and position.
Inventors
- 👤 Brian E. Smartt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 20:01
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2264; G06F16/29; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
62 words
A method of organizing spatial data objects in a map database, comprising: referencing data objects as location points in a region to a coordinate system; separating said region into multiple sub-regions; and assigning said data objects whose location point falls within a sub-region to said sub-region so long as no part of said object extends outside said sub-region by a predetermined amount.
Claim 2
Independent Claim
62 words
A method of organizing spatial data objects in a map database, comprising: referencing data objects as location points in a region to a coordinate system; separating said region into multiple sub-regions; and assigning said data objects whose location point falls within a sub-region to said sub-region so long as no part of said object extends outside said sub-region by a predetermined amount.
Claim 3
Dependent Claim
13 words
The method of claim 1 wherein said data objects are spatial data objects.
Claim 4
Dependent Claim
25 words
The method of claim 1 wherein said location point of said data object is calculated by determining the minimum bounding rectangle for said data object.
Claim 5
Dependent Claim
14 words
The method of claim 1 wherein multiple sub-regions further comprise multiple tiers of sub-regions.
Claim 6
Dependent Claim
15 words
The method of claim 1 wherein each of said sub-regions is assigned a unique code.
Claim 7
Dependent Claim
18 words
The method of claim 1 wherein said predetermined amount is equal to one-half the size of said quadrant.
Claim 8
Independent Claim
18 words
The method of claim I wherein said predetermined amount is equal to one-fourth the size of said quadrant.
Claim 9
Dependent Claim
17 words
The method of claim 1 wherein said predetermined amount is equal to the size of said quadrant.
Claim 10
Dependent Claim
20 words
The method of claim 1 wherein said data objects are selected from the group comprising: lines, circles, squares and polygons.
Claim 11
Dependent Claim
14 words
The method of claim 1 wherein said region is separated into multiple square sub-regions.
Claim 12
Dependent Claim
14 words
The method of claim 1 wherein said region is separated into multiple rectangular sub-regions.
Claim 13
Dependent Claim
14 words
The method of claim 1 wherein said region is separated into multiple round sub-regions.
Claim 14
Dependent Claim
14 words
The method of claim 1 wherein said region is separated into multiple hexagonal sub-regions.
Claim 15
Independent Claim
122 words
A method of storing spatial data objects to a computer memory, comprising the steps of: determining the size of each data object within a coordinate system; assigning each spatial data object to a location point in said coordinate system; calculating the boundaries of a first tier of overlapping sub-regions of said coordinate system so that each point in said coordinate system is assigned to at least one sub-region; referencing each spatial data object that is smaller than the size of said sub-regions in said first tier to a specific sub-region of said coordinate system based on the location point of each spatial data object; and storing said spatial data objects along with its reference to a specific sub-region to said computer memory.
Claim 16
Independent Claim
122 words
A method of storing spatial data objects to a computer memory, comprising the steps of: determining the size of each data object within a coordinate system; assigning each spatial data object to a location point in said coordinate system; calculating the boundaries of a first tier of overlapping sub-regions of said coordinate system so that each point in said coordinate system is assigned to at least one sub-region; referencing each spatial data object that is smaller than the size of said sub-regions in said first tier to a specific sub-region of said coordinate system based on the location point of each spatial data object; and storing said spatial data objects along with its reference to a specific sub-region to said computer memory.
Claim 17
Dependent Claim
16 words
The method of claim 14 wherein said spatial data objects are part of a map database.
Claim 18
Dependent Claim
21 words
The method of claim 14 wherein said spatial data objects are selected from the group comprising: lines, circles, squares and polygons.
Claim 19
Dependent Claim
14 words
The method of claim 14 wherein said computer memory is a computer hard disk.
Claim 20
Dependent Claim
18 words
The method of claim 14 wherein said referencing step comprises the Peano-Hilbert method of ordering spatial data quadrants.
Claim 21
Dependent Claim
17 words
The method of claim 14 wherein said sub-regions are shingles and said reference is a shingle code.
Claim 22
Dependent Claim
21 words
The method of claim 14 wherein the size of said overlap between sub-regions is equal to the size of said sub-region.
Claim 23
Dependent Claim
22 words
The method of claim 14 wherein the size of said overlap between sub-regions is equal to one-half the size of said sub-region.
Claim 24
Dependent Claim
22 words
The method of claim 14 wherein the size of said overlap between sub-regions is equal to one-fourth the size of said sub-region.
Claim 25
Dependent Claim
21 words
The method of claim 14 wherein said determining step further comprises calculating a minimum bounding rectangle for said spatial data object.
Claim 26
Dependent Claim
37 words
The method of claim 23, wherein said assigning step comprises determining the coordinate position of the lower left corner of the minimum bounding rectangle of said spatial data object and storing said location point to said position.
Claim 27
Dependent Claim
29 words
The method of claim 14 wherein said spatial data objects are selected from the group comprising: engineering and architectural drawings, animation and virtual reality databases and raster bit maps.
Claim 28
Dependent Claim
76 words
The method of claim 14 further comprising the steps of: calculating the boundaries of a second tier of overlapping sub-regions of said coordinate system so that each point in said coordinate system is assigned to at least one sub-region; and referencing each spatial data object that is larger than the size of said sub-regions in said first tier to a specific sub-region in said second tier based on the location point of each spatial data object.
Claim 29
Dependent Claim
20 words
The method of claim 14 wherein said data objects are selected from the group comprising: lines, circles, squares and polygons.
Claim 30
Dependent Claim
14 words
The method of claim 14 wherein said region is separated into multiple square sub-regions.
Claim 31
Dependent Claim
14 words
The method of claim 14 wherein said region is separated into multiple rectangular sub-regions.
Claim 32
Dependent Claim
14 words
The method of claim 14 wherein said region is separated into multiple round sub-regions.
Claim 33
Dependent Claim
14 words
The method of claim 14 wherein said region is separated into multiple hexagonal sub-regions.
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-10-04 | 2003-04-05 | 2003-10-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-04 | 2007-04-05 | 2007-10-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-04 | 2011-04-05 | 2011-10-05 | $7700.00 | Window Closed / Lapsed |