Patent US6161105A successfully refreshed from Google Patents.
US6161105A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for multidimensional database using binary hyperspatial code
Assignee: Oracle International Corp
•
Filing: 1996-10-02
•
Granted: 2000-12-12
•
Expires: 2016-10-02
Abstract
Abstract An improved database data structure and datatype is disclosed for storing, manipulating and accessing multidimensional spatial data in a database. Binary helical hyperspatial code (HH CODE) is used to represent data of N dimensions. The binary HH CODE data structure maintains the dimensional organization of multidimensional data within the data itself. Spatial data is stored using BH code which is modeled as a N-tree structure derived using recursive decomposition. A high water mark is set as the upper limit for data volume which may be stored in any one partition. As data stored in a partition exceeds the high water mark, the data is decomposed into child partitions such that no partition data stores exceed the high water mark. If the high water mark is exceeded, additional child partitions are automatically created and the parent table is not retained. A data structure is defined which represents the partitioned tables and BH code values. Appropriate attributes are associated with each of the BH code values which may represent non-spatial data such as temperature, salinity, or cosmic ray flux. Methods and apparatus are also provided to apply teachings of binary HH CODE to line segments and topology.
Inventors
- 👤 Edric Keighan
- 👤 Panagiotis A. Vretanos
- 👤 Michael Galluchon
- 👤 Herman P. Varma
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 04:05
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5854; G06F16/20; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 79
Claim 1
Independent Claim
102 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; determining a hyperspatial code for said data points by recursively defining spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; generating hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.
Claim 2
Independent Claim
102 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; determining a hyperspatial code for said data points by recursively defining spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; generating hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.
Claim 3
Dependent Claim
26 words
The method for storing dimensional data as defined by claim 1, wherein each of said data partitions stored in said data dictionary is a database object.
Claim 4
Independent Claim
89 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; and determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code.
Claim 5
Independent Claim
89 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; and determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code.
Claim 6
Dependent Claim
27 words
The method for storing dimensional data as defined by claim 3, wherein said meta data includes dimension bits to identify a number of dimensions in hyperspatial key.
Claim 7
Dependent Claim
32 words
The method for storing dimensional data as defined by claim 3, wherein said meta data includes a type bit to identify the type of a geometric object associated with the hyperspatial key.
Claim 8
Dependent Claim
31 words
The method for storing dimensional data as defined by claim 3, wherein said meta data includes a topology bit to identify whether hyperspatial key represents the interior or boundary of topology.
Claim 9
Dependent Claim
40 words
The method for storing dimensional data as defined by claim 3, wherein said meta data includes level bits to identify the number of levels of precision which are encoded in hyperspatial key for each dimension identified by said dimension bits.
Claim 10
Independent Claim
79 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; determining a hyperspatial code for said data points by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; and generating a data dictionary, wherein said data dictionary includes a list of all tables stored in said database that are multidimensional.
Claim 11
Independent Claim
79 words
A method for storing dimensional data in a database, comprising the computer-implemented steps of: receiving dimensional data points; determining a hyperspatial code for said data points by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; and generating a data dictionary, wherein said data dictionary includes a list of all tables stored in said database that are multidimensional.
Claim 12
Dependent Claim
26 words
The method for storing dimensional data as defined by claim 8, wherein said database stores a list of said dimensional data, including both spatial and non-spatial.
Claim 13
Dependent Claim
41 words
The method for storing dimensional data as defined by claim 8 wherein said data dictionary includes partitioned tables and non-partitioned tables, said non-partitioned tables comprising relational database tables that include at least one column having attributes with spatial hyperspatial code columns.
Claim 14
Dependent Claim
37 words
The method for storing dimensional data as defined by claim 10, wherein said partitioned tables comprise multidimensional tables that include at least one spatial column and are partitioned on said at least one of said spatial columns.
Claim 15
Independent Claim
127 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; an element for partitioning and storing said hyperspatial code in said database, said element for partitioning generates hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and an element for generating a data dictionary, said data dictionary including a partition table having respective entries for each of said generated data partitions.
Claim 16
Independent Claim
127 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; an element for partitioning and storing said hyperspatial code in said database, said element for partitioning generates hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and an element for generating a data dictionary, said data dictionary including a partition table having respective entries for each of said generated data partitions.
Claim 17
Dependent Claim
22 words
The apparatus as defined by claim 12, wherein each of said data partitions stored in said data dictionary is a database object.
Claim 18
Independent Claim
105 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code; and an element for partitioning and storing said BH codes in said database.
Claim 19
Independent Claim
105 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code; and an element for partitioning and storing said BH codes in said database.
Claim 20
Dependent Claim
24 words
The apparatus as defined by claim 14, wherein said meta data includes dimension bits to identify a number of dimensions in the hyperspatial key.
Claim 21
Dependent Claim
28 words
The apparatus as defined by claim 14, wherein said meta data includes a type bit to identify the type of a geometric object associated with the hyperspatial key.
Claim 22
Dependent Claim
27 words
The apparatus as defined by claim 14, wherein said meta data includes a topology bit to identify whether hyperspatial key represents the interior or boundary of topology.
Claim 23
Dependent Claim
36 words
The apparatus as defined by claim 14, wherein said meta data includes level bits to identify the number of levels of precision which are encoded in hyperspatial key for each dimension identified by said dimension bits.
Claim 24
Independent Claim
103 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; an element for partitioning and storing said hyperspatial code in said database; and an element for generating a data dictionary, wherein said data dictionary includes a multidimension table which contains a list of all tables stored in said database that are multidimensional.
Claim 25
Independent Claim
103 words
An apparatus for storing dimensional data points in a database coupled to a computer, comprising: an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; an element for partitioning and storing said hyperspatial code in said database; and an element for generating a data dictionary, wherein said data dictionary includes a multidimension table which contains a list of all tables stored in said database that are multidimensional.
Claim 26
Dependent Claim
22 words
The apparatus as defined by claim 19, wherein said database stores a list of said dimensional data, including both spatial and non-spatial.
Claim 27
Dependent Claim
37 words
The apparatus as defined by claim 19, wherein said data dictionary includes partitioned tables and non-partitioned tables, said non-partitioned tables comprising relational database tables that include at least one column having attributes with spatial hyperspatial code columns.
Claim 28
Dependent Claim
33 words
The apparatus as defined by claim 21, wherein said partitioned tables comprise multidimensional tables that include at least one spatial column and are partitioned on said at least one of said spatial columns.
Claim 29
Independent Claim
93 words
A method for storing a line segment in a database, comprising the computer-implemented steps of: receiving data points representing a first (x 1 ,y 1 ) and a second (x 2 , y 2 ) end point of said line segment; and determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.
Claim 30
Independent Claim
93 words
A method for storing a line segment in a database, comprising the computer-implemented steps of: receiving data points representing a first (x 1 ,y 1 ) and a second (x 2 , y 2 ) end point of said line segment; and determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.
Claim 31
Dependent Claim
22 words
The method as defined by claim 23, wherein said hyperspatial code determined for said line segment is a four dimension hyperspatial code.
Claim 32
Dependent Claim
60 words
The method as defined by claim 24, wherein: a first dimension of the four dimension hyperspatial code represents x 1 , a second dimension of the four dimension hyperspatial code represents y 1 , a third dimension of the four dimension hyperspatial code represents x 2 and a fourth dimension of the four dimension hyperspatial code represents y 2 .
Claim 33
Dependent Claim
29 words
The method as defined by claim 23, wherein a plurality of line segments are stored in said database, each of said line segments being represented by a hyperspatial code.
Claim 34
Dependent Claim
38 words
The method as defined by claim 23, further providing an element for performing the steps of generating hyperspatial code data partitions based upon a predefined number of hyperspatial code entries which may be disposed in any one partition.
Claim 35
Dependent Claim
41 words
The method as defined by claim 27, wherein if during said generation of hyperspatial code data partitions said predefined number of hyperspatial code entries is exceeded, additional child data partitions are generated and said original parent data partition is not retained.
Claim 36
Dependent Claim
32 words
The method as defined by claim 28, wherein for each of said parent data partitions in which said predefined number of hyperspatial code entries are exceeded, sixteen child data partitions are created.
Claim 37
Dependent Claim
29 words
The method as defined by claim 29, wherein of said sixteen data partitions only those partitions in which a hyperspatial code is actually stored are maintained in said database.
Claim 38
Dependent Claim
32 words
The method as defined by claim 27, wherein attribute data is associated with said hyperspatial codes representing said dimensional data, said attribute data further being associated with said BH code data partitions.
Claim 39
Dependent Claim
36 words
The method as defined by claim 27, further including an element for performing the steps of generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.
Claim 40
Dependent Claim
22 words
The method as defined by claim 32, wherein each of said data partitions stored in said data dictionary is a database objects.
Claim 41
Dependent Claim
41 words
The method as defined by claim 26, wherein each said hyperspatial code is a binary hyperspatial code (BH code) including a data structure having hyperspatial code data representing a hyperspatial key and meta data representing an attribute of the BH code.
Claim 42
Dependent Claim
28 words
The method as defined by claim 34, wherein said meta data includes a type bit to identify the type of said hyperspatial code data as a geometric object.
Claim 43
Dependent Claim
24 words
The method as defined by claim 32, wherein said data dictionary includes a list of all tables stored in said database that are multidimensional.
Claim 44
Dependent Claim
93 words
The method as defined by claim 32, further including a method for accessing said stored line segments, comprising the steps of: receiving input from a user defining a region of interest; identifying which of said data partitions define line segments which are at least partially disposed within said region of interest; compiling a list of said identified data partitions; determining if each of said hyperspatial code entries in said identified partitions are disposed within said region of interest, and reporting those hyperspatial code entries which are disposed within said region to said user.
Claim 45
Dependent Claim
78 words
The method as defined by claim 37, wherein said step of identifying which of said data partitions define line segments which are at least partially disposed within said region of interest includes the steps of: defining sixteen potential partition shapes for said stored line segments, said sixteen partition shapes representing said data partitions in said data dictionary; and examining each of said hyperspatial code entries in said partitions stored in said data dictionary and decoding said hyperspatial code.
Claim 46
Independent Claim
97 words
An apparatus for storing a line segment in a database coupled to a computer, comprising: an element for receiving data points representing a first (x 1 ,y 1 ) and a second (x 2 ,y 2 ) end point of said line segment; an element for determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.
Claim 47
Independent Claim
97 words
An apparatus for storing a line segment in a database coupled to a computer, comprising: an element for receiving data points representing a first (x 1 ,y 1 ) and a second (x 2 ,y 2 ) end point of said line segment; an element for determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.
Claim 48
Dependent Claim
22 words
The apparatus as defined by claim 39, wherein said hyperspatial code determined for said line segment is a four dimension hyperspatial code.
Claim 49
Dependent Claim
60 words
The apparatus as defined by claim 40, wherein: a first dimension of the four dimension hyperspatial code represents x 1 , a second dimension of the four dimension hyperspatial code represents y 1 , a third dimension of the four dimension hyperspatial code represents x 2 and a fourth dimension of the four dimension hyperspatial code represents y 2 .
Claim 50
Dependent Claim
29 words
The apparatus as defined by claim 39, wherein a plurality of line segments are stored in said database, each of said line segments being represented by a hyperspatial code.
Claim 51
Dependent Claim
34 words
The apparatus as defined by claim 39, further providing an element for generating hyperspatial code data partitions based upon a predefined number of hyperspatial code entries which may be disposed in any one partition.
Claim 52
Dependent Claim
41 words
The apparatus as defined by claim 43, wherein if during said generation of hyperspatial code data partitions said predefined number of hyperspatial code entries is exceeded, additional child data partitions are generated and said original parent data partition is not retained.
Claim 53
Dependent Claim
32 words
The apparatus as defined by claim 44, wherein for each of said parent data partitions in which said predefined number of hyperspatial code entries are exceeded, sixteen child data partitions are treated.
Claim 54
Dependent Claim
28 words
The apparatus as defined by claim 45, wherein of said sixteen data partitions only those partitions in which hyperspatial code is actually stored are maintained in said database.
Claim 55
Dependent Claim
32 words
The apparatus as defined by claim 43, wherein attribute data is associated with said hyperspatial codes representing said dimensional data, said attribute data further being associated with said hyperspatial code data partitions.
Claim 56
Dependent Claim
32 words
The apparatus as defined by claim 43, further including an element for generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.
Claim 57
Dependent Claim
22 words
The apparatus as defined by claim 48, wherein each of said data partitions stored in said data dictionary is a database object.
Claim 58
Dependent Claim
41 words
The apparatus as defined by claim 42, wherein each said hyperspatial code is a binary hyperspatial code (BH code) including a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code.
Claim 59
Dependent Claim
26 words
The apparatus as defined by claim 50, wherein said meta data includes a type bit to identify the type of hyperspatial key as a geometric object.
Claim 60
Dependent Claim
26 words
The apparatus as defined by claim 48, wherein said data dictionary includes a list of all tables stored in a corresponding relational database which are multidimensional.
Claim 61
Dependent Claim
103 words
The apparatus as defined by claim 43, further including an apparatus for accessing said stored line segments, comprising: an element for receiving input from a user to define a region of interest; an element for identifying which of said data partitions define line segments which are at least partially disposed within said region of interest; an element for compiling a list of said identified data partitions; an element for determining if each of said hyperspatial code entries in said identified partitions are disposed within said region of interest, and reporting those hyperspatial code entries which are disposed within said region to said user.
Claim 62
Independent Claim
73 words
A method for storing a topologic representation of a first object in a database, comprising the computer-implemented steps of: defining an interior I 1 and a boundary B 1 for said first object; recursively decomposing said first object into first object tile regions defined by BH codes; and wherein said BH codes identify whether each of said first tile regions forms part of said interior I 1 or said boundary B 1 .
Claim 63
Independent Claim
73 words
A method for storing a topologic representation of a first object in a database, comprising the computer-implemented steps of: defining an interior I 1 and a boundary B 1 for said first object; recursively decomposing said first object into first object tile regions defined by BH codes; and wherein said BH codes identify whether each of said first tile regions forms part of said interior I 1 or said boundary B 1 .
Claim 64
Dependent Claim
25 words
The method as defined by claim 54, further comprising the step of creating an object partitioned table for said first object containing said BH codes.
Claim 65
Dependent Claim
77 words
The method as defined by claim 55, further including the steps of: providing a second object; defining an interior I 2 , and a boundary B 2 for said second object; recursively decomposing said second object into second object tile regions defined by BH codes; wherein each of said BH codes for said second object identifies whether each of said second object tile regions forms part of said interior I 2 or said boundary B 2 .
Claim 66
Dependent Claim
29 words
The method as defined by claim 56, further comprising the step of creating an object partitioned table for said second object containing said BH codes for said second object.
Claim 67
Dependent Claim
41 words
The method as defined by claim 57, further including the step of applying an intersection methodology to said BH codes in said first and second object partitioned tables to determine the relationship of said first and second objects to one another.
Claim 68
Dependent Claim
18 words
The method as defined by claim 58, wherein said intersection methodology comprises an Egenhofer Four Point Intersection methodology.
Claim 69
Independent Claim
80 words
An apparatus for storing a topologic representation of a first object in a database, comprising: an element for defining an interior I 1 and a boundary B 1 for said first object; and an element for recursively decomposing said first object into first object tile regions defined by binary hyperspatial codes (BH code); wherein each of said BH codes identifies whether each of said first tile regions forms part of said interior I 1 or said boundary B 1 .
Claim 70
Independent Claim
80 words
An apparatus for storing a topologic representation of a first object in a database, comprising: an element for defining an interior I 1 and a boundary B 1 for said first object; and an element for recursively decomposing said first object into first object tile regions defined by binary hyperspatial codes (BH code); wherein each of said BH codes identifies whether each of said first tile regions forms part of said interior I 1 or said boundary B 1 .
Claim 71
Dependent Claim
25 words
The apparatus as defined by claim 60 further including an element for creating an object partitioned table for said first object containing said BH codes.
Claim 72
Dependent Claim
74 words
The apparatus as defined by claim 61 further including: a second object; an element for defining an interior I 2 and a boundary B 2 for said second object; and an element for recursively decomposing said second object into second object tile regions defined by BH codes; wherein each of said BH codes identifies whether each of said second tile regions forms part of said interior I 2 or said boundary B 2 .
Claim 73
Dependent Claim
29 words
The apparatus as defined by claim 62, further including an element for creating an object partitioned table for said second object containing said BH codes for said second object.
Claim 74
Dependent Claim
41 words
The apparatus as defined by claim 63, further including an element for applying an intersection methodology to said BH codes in said first and second object partitioned tables to determine the relationship of said first and second objects to one another.
Claim 75
Dependent Claim
18 words
The apparatus as defined by claim 64, wherein said intersection methodology comprises an Egenhofer Four Point Intersection methodology.
Claim 76
Dependent Claim
34 words
The method as defined by claim 1, wherein each of said respective entries for each of said generated data partitions includes a hyperspatial code value representing an extent of a corresponding generated data partition.
Claim 77
Dependent Claim
34 words
The apparatus as defined by claim 12, wherein each of said respective entries for each of said generated data partitions includes a hyperspatial code value representing an extent of a corresponding generated data partition.
Claim 78
Dependent Claim
43 words
The method as defined by claim 56, wherein each of BH codes includes a data structure having code data and meta data, said meta data including a topology bit to identify whether said BH code data represents the interior or boundary of topology.
Claim 79
Dependent Claim
43 words
The apparatus as defined by claim 62, wherein each of BH codes includes a data structure having code data and meta data, said meta data including a topology bit to identify whether said BH code data represents the interior or boundary of topology.
References Cited (Backward Citations)
US4555771A
Cited
US4794461A
Cited
US4788538A
Cited
US5261032A
Cited
US5257365A
Cited
US5359724A
Cited
US5414780A
Cited
US5647058A
Cited
US5701467A
Cited
US5446806A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-12 | 2004-06-12 | 2004-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-12 | 2008-06-12 | 2008-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-12 | 2012-06-12 | 2012-12-12 | $7700.00 | Window Closed / Lapsed |