US6505205B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Relational database system for storing nodes of a hierarchical index of multi-dimensional data in a first module and metadata regarding the index in a second module
Assignee: Oracle International Corp
•
Filing: 2002-01-03
•
Granted: 2003-01-07
•
Expires: 2022-01-03
Abstract
Abstract A system and method for indexing and storing multi-dimensional or multi-attribute data. Data items are recursively sorted in a selected dimension (e.g., the dimension having the greatest variance) and divided until each subdivision fits into a leaf node having a specified fanout. Intermediate nodes and a root node are constructed to complete the index. Each node of the index is stored in a database as a separate object or record and may include a node identifier of the unique, an identifier of a parent and/or a sibling node and an entry for each child of the node, which may be data items or other nodes. Each record entry for a child includes an associated bounding area encompassing descendant data items. Another database table or module may store information about the index, such as the dimensionality of the data, the index fanout and an identifier of a root of the index.
Inventors
- 👤 Ravi Kothuri
- 👤 Siva Ravada
- 👤 Jayant Sharma
- 👤 Jayanta Banerjee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:01
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2264; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99937; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
233 words
A method of storing a hierarchical index of multi-dimensional data in a database on a computer system, comprising: constructing a first module in a first relational database; inserting a row in said first module for a hierarchical index of multi-dimensional data, wherein said row comprises: an identifier of a root node of said index; a node capacity of said index; and a measure of the dimensionality of said multi-dimensional data; constructing a second module in a second relational database; inserting a row in said second module for a first node of said index, wherein said row comprises one or more of: a first identifier of said first node; a location identifier configured to identify a storage location of said first node; a parent_node identifier of a parent node of said first node; a parent_location identifier configured to identify a storage location of said parent node; a sibling identifier of a sibling node of said first node; one or more entries, wherein each entry comprises: an identifier of a child of said first node, wherein said child is either a child data item or a child node; and a bounding area encompassing either said child data item or a set of data items accessible through said child node; and a count of the number of said one or more entries; and storing the multi-dimensional data in a third module in a third relational database.
Claim 2
Independent Claim
233 words
A method of storing a hierarchical index of multi-dimensional data in a database on a computer system, comprising: constructing a first module in a first relational database; inserting a row in said first module for a hierarchical index of multi-dimensional data, wherein said row comprises: an identifier of a root node of said index; a node capacity of said index; and a measure of the dimensionality of said multi-dimensional data; constructing a second module in a second relational database; inserting a row in said second module for a first node of said index, wherein said row comprises one or more of: a first identifier of said first node; a location identifier configured to identify a storage location of said first node; a parent_node identifier of a parent node of said first node; a parent_location identifier configured to identify a storage location of said parent node; a sibling identifier of a sibling node of said first node; one or more entries, wherein each entry comprises: an identifier of a child of said first node, wherein said child is either a child data item or a child node; and a bounding area encompassing either said child data item or a set of data items accessible through said child node; and a count of the number of said one or more entries; and storing the multi-dimensional data in a third module in a third relational database.
Claim 3
Dependent Claim
22 words
The method of claim 1 , wherein said first database comprises one or more of said second database and said third database.
Claim 4
Dependent Claim
23 words
The method of claim 1 , wherein said inserting a row in said second module is performed for every node in said index.
Claim 5
Dependent Claim
22 words
The method of claim 1 , wherein said parent node of said first node is the root node of said hierarchical index.
Claim 6
Dependent Claim
165 words
A computer-implemented method of constructing a hierarchical index from a set of multi-dimensional data, comprising: (a) calculating a number of members of a set of multi-dimensional data items; (b) determining whether said number of members exceeds a node capacity of a hierarchical index configured to index said data items; (c) determining a variance of values in one or more dimensions of said data items; (d) identifying a first dimension of said one or more multi dimensions in which to divide said set of multi-dimensional data items; (e) sorting said data items in said first dimension; (f) dividing said sorted data items in said first dimension into two or more subsets; (g) repeating (a)-(f) for each said subset in order to divide said set of data items into a plurality of data item clusters, wherein each cluster comprises a number of data items no greater than said node capacity; and (h) configuring a leaf node of said hierarchical index for data items in a first luster.
Claim 7
Dependent Claim
165 words
A computer-implemented method of constructing a hierarchical index from a set of multi-dimensional data, comprising: (a) calculating a number of members of a set of multi-dimensional data items; (b) determining whether said number of members exceeds a node capacity of a hierarchical index configured to index said data items; (c) determining a variance of values in one or more dimensions of said data items; (d) identifying a first dimension of said one or more multi dimensions in which to divide said set of multi-dimensional data items; (e) sorting said data items in said first dimension; (f) dividing said sorted data items in said first dimension into two or more subsets; (g) repeating (a)-(f) for each said subset in order to divide said set of data items into a plurality of data item clusters, wherein each cluster comprises a number of data items no greater than said node capacity; and (h) configuring a leaf node of said hierarchical index for data items in a first luster.
Claim 8
Dependent Claim
20 words
The method of claim 5 , wherein said multi-dimensional data items consist of data items having values for multiple attributes.
Claim 9
Dependent Claim
26 words
The method of claim 5 , in which said identifying comprises selecting a dimension, from said one or more dimensions, having the greatest variance of values.
Claim 10
Dependent Claim
32 words
The method of claim 5 , in which said dividing comprises: calculating an approximate median value in said first dimension; and selecting a first data item corresponding to said approximate median value.
Claim 11
Dependent Claim
69 words
The method of claim 5 , in which said configuring comprises: creating a first leaf node of the index; and inserting an entry in said first leaf node for each data item in a first subset of said set of multi-dimensional data items, wherein a first entry for a first data item comprises: an identifier of said first data item; and a bounding area encompassing said first data item.
Claim 12
Dependent Claim
16 words
The method of claim 5 , wherein the dimensions of said multi-dimensional data are inherently related.
Claim 13
Dependent Claim
16 words
The method of claim 5 , wherein the dimensions of the multi-dimensional data are independent attributes.
Claim 14
Dependent Claim
42 words
The method of claim 5 , further comprising identifying a query pattern for retrieving one or more data items from said set of data items, wherein said query pattern comprises a hierachy of two or more dimensions of said multi-dimensional data items.
Claim 15
Dependent Claim
22 words
The method of claim 12 , in which said identifying comprises selecting a dimension in said hierarchy of two or more dimensions.
Claim 16
Independent Claim
284 words
A method of updating an electronic index of multi-dimensional data items, comprising: receiving a new data item to be added to a set of hierarchically indexed multi-dimensional data items; inserting said new data item in a leaf node of said hierarchical index, wherein each node of said index comprises one or more of: a node identifier of said node; a row identifier of a storage location of said node in a database; a parent_node identifier of a parent of said node; a parent_row identifier of a storage location of said parent of said node in said database; a sibling identifier of a sibling of said node; and a set of child entries corresponding to children of said node; determining whether a first node in said index splits due to said inserting; if said first node splits due to said inserting: creating a second node; assigning said second node said node identifier of said first node; assigning a new node identifier to said first node; and transferring one or more child entries of said set of child entries of said first node to said second node; if said first node is a root node of said index: creating a new root node of said index; setting said parent_node identifier of one of said first node and said second node to said node identifier of said new root node; and setting said parent_row identifier of said one of said first node and said second node to said row identifier of said new root node; and updating metadata regarding said index, said metadata comprising: a dimensionality of said multi-dimensional data items; an identifier of said root node of said index; and a node capacity of said index.
Claim 17
Independent Claim
284 words
A method of updating an electronic index of multi-dimensional data items, comprising: receiving a new data item to be added to a set of hierarchically indexed multi-dimensional data items; inserting said new data item in a leaf node of said hierarchical index, wherein each node of said index comprises one or more of: a node identifier of said node; a row identifier of a storage location of said node in a database; a parent_node identifier of a parent of said node; a parent_row identifier of a storage location of said parent of said node in said database; a sibling identifier of a sibling of said node; and a set of child entries corresponding to children of said node; determining whether a first node in said index splits due to said inserting; if said first node splits due to said inserting: creating a second node; assigning said second node said node identifier of said first node; assigning a new node identifier to said first node; and transferring one or more child entries of said set of child entries of said first node to said second node; if said first node is a root node of said index: creating a new root node of said index; setting said parent_node identifier of one of said first node and said second node to said node identifier of said new root node; and setting said parent_row identifier of said one of said first node and said second node to said row identifier of said new root node; and updating metadata regarding said index, said metadata comprising: a dimensionality of said multi-dimensional data items; an identifier of said root node of said index; and a node capacity of said index.
Claim 18
Dependent Claim
74 words
The method of claim 14 , in which said inserting a new data item comprises: traversing one or more nodes of said index to locate a leaf node in which to insert said new data item; storing a node identifier of each of said one or more nodes during said traversing as a first node identifier in a data structure; and adding a child entry to said leaf node for said new data item.
Claim 19
Dependent Claim
62 words
The method of claim 15 , in which said determining comprises, after said adding: removing said first node identifiers of said one or more nodes from said data structure in reverse order of said storing; and determining whether said first node identifier of a node removed from said data structure is different from a node identifier of said node at said removing.
Claim 20
Dependent Claim
253 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of storing a hierarchical index of multi-dimensional data in a database on a computer system, the method comprising: constructing a first module in a first relational database; inserting a row in said first module for a hierarchical index of multi-dimensional data, wherein said row comprises: an identifier of a root node of said index; a node capacity of said index; and a measure of the dimensionality of said multi-dimensional data; constructing a second module in a second relational database; inserting a row in said second module for a first node of said index, wherein said row comprises one or more of: a first identifier of said first node; a location identifier configured to identify a storage location of said first node; a parent_node identifier of a parent node of said first node; a parent_location identifier configured to identify a storage location of said parent node; a sibling identifier of a sibling node of said first node; one or more entries, wherein each entry comprises: an identifier of a child of said first node, wherein said child is either a child data item or a child node; and a bounding area encompassing either said child data item or a set of data items accessible through said child node; and a count of the number of said one or more entries; and storing the multi-dimensional data in a third module in a third relational database.
Claim 21
Dependent Claim
253 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of storing a hierarchical index of multi-dimensional data in a database on a computer system, the method comprising: constructing a first module in a first relational database; inserting a row in said first module for a hierarchical index of multi-dimensional data, wherein said row comprises: an identifier of a root node of said index; a node capacity of said index; and a measure of the dimensionality of said multi-dimensional data; constructing a second module in a second relational database; inserting a row in said second module for a first node of said index, wherein said row comprises one or more of: a first identifier of said first node; a location identifier configured to identify a storage location of said first node; a parent_node identifier of a parent node of said first node; a parent_location identifier configured to identify a storage location of said parent node; a sibling identifier of a sibling node of said first node; one or more entries, wherein each entry comprises: an identifier of a child of said first node, wherein said child is either a child data item or a child node; and a bounding area encompassing either said child data item or a set of data items accessible through said child node; and a count of the number of said one or more entries; and storing the multi-dimensional data in a third module in a third relational database.
Claim 22
Dependent Claim
145 words
A computer readable storage medium containing a data structure configured for hierarchically indexing multi-dimensional data items, said data structure comprising: a first module configured to store a set of records, wherein each record consists of one or more of: an identifier of a node of a hierarchical index of multi-dimensional data items; an identifier of said record; an identifier of a parent node of said node; an identifier of a sibling node of said node; and one or more child entries, each said child entry comprising: an identifier of a child item of said node; and a bounding area encompassing one or more of said multi-dimensional data items; and a second module configured to store one or more of: a dimensionality of said multi-dimensional data items; an identifier of a root node of said index; and a measure of a node capacity of said index.
Claim 23
Dependent Claim
145 words
A computer readable storage medium containing a data structure configured for hierarchically indexing multi-dimensional data items, said data structure comprising: a first module configured to store a set of records, wherein each record consists of one or more of: an identifier of a node of a hierarchical index of multi-dimensional data items; an identifier of said record; an identifier of a parent node of said node; an identifier of a sibling node of said node; and one or more child entries, each said child entry comprising: an identifier of a child item of said node; and a bounding area encompassing one or more of said multi-dimensional data items; and a second module configured to store one or more of: a dimensionality of said multi-dimensional data items; an identifier of a root node of said index; and a measure of a node capacity of said index.
Claim 24
Dependent Claim
30 words
The computer readable storage medium of claim 18 , in which the data structure further comprises a third module configured to store one or more of said multi-dimensional data items.
Claim 25
Dependent Claim
72 words
The computer readable storage medium of claim 18 , wherein a child item of a first child entry comprises one of: a data item; and a child node; and said bounding area of said first child entry encompasses one of: if said child item is a data item, said data item; and if said child item is a child node, a subset of said multi-dimensional data items accessible through said child node.
Claim 26
Dependent Claim
20 words
The computer readable storage medium of claim 18 , wherein each of said multi-dimensional data items comprises a geographical position.
Claim 27
Dependent Claim
30 words
The computer readable storage medium of claim 21 , wherein said bounding area comprises a geographical region surrounding said geographic positions corresponding to said one or more multi-dimensional data items.
Claim 28
Dependent Claim
19 words
The computer readable storage medium of claim 18 , wherein said node capacity comprises a fanout of said index.
Claim 29
Independent Claim
196 words
An apparatus for indexing a set of multi-dimensional data items, comprising: a storage device configured to store a set of multi-dimensional data items; a processor configured to manipulate said set of multi-dimensional data items; and a database configured to store a hierarchical index of said set of multi-dimensional data items, wherein said index comprises one or more nodes, the database comprising: a first module configured to store one or more of: an identifier of a root node of said index; a node capacity of said index; and a dimensionality of said multi-dimensional data items; and a second module comprising a record for each of said one or more nodes, a first record for a first node comprising: an identifier of said first node; and an entry for each child of said first node, wherein a child is one of a data item and a child node and wherein a first entry comprises: an identifier of a first child of said first node; and a bounding region encompassing said first child if said first child is a data item or all data items of descendants of said first child if said first child is a child node.
Claim 30
Independent Claim
196 words
An apparatus for indexing a set of multi-dimensional data items, comprising: a storage device configured to store a set of multi-dimensional data items; a processor configured to manipulate said set of multi-dimensional data items; and a database configured to store a hierarchical index of said set of multi-dimensional data items, wherein said index comprises one or more nodes, the database comprising: a first module configured to store one or more of: an identifier of a root node of said index; a node capacity of said index; and a dimensionality of said multi-dimensional data items; and a second module comprising a record for each of said one or more nodes, a first record for a first node comprising: an identifier of said first node; and an entry for each child of said first node, wherein a child is one of a data item and a child node and wherein a first entry comprises: an identifier of a first child of said first node; and a bounding region encompassing said first child if said first child is a data item or all data items of descendants of said first child if said first child is a child node.
Claim 31
Dependent Claim
20 words
The apparatus of claim 24 , further comprising a generator for generating unique identifiers for each node of said index.
Claim 32
Dependent Claim
25 words
The apparatus of claim 24 , wherein said database further comprises: a third module configured to store one or more of said multi-dimensional data items.
Claim 33
Dependent Claim
184 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of constructing a hierarchical index from a set of multi-dimensional data, the method comprising: (a) calculating a number of members of a set of multi-dimensional data items; (b) determining whether said number of members exceeds a node capacity of a hierarchical index configured to index said data items; (c) determining a variance of values in one or more dimensions of said data items; (d) identifying a first dimension of said one or more multi dimensions in which to divide said set of multi-dimensional data items; (e) sorting said data items in said first dimension; (f) dividing said sorted data items in said first dimension into two or more subsets; (g) repeating (a)-(f) for each said subset in order to divide said set of data items into a plurality of data item clusters, wherein each cluster comprises a number of data items no greater than said node capacity; and (h) configuring a leaf node of said hierarchical index for data items in a first cluster.
Claim 34
Dependent Claim
184 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of constructing a hierarchical index from a set of multi-dimensional data, the method comprising: (a) calculating a number of members of a set of multi-dimensional data items; (b) determining whether said number of members exceeds a node capacity of a hierarchical index configured to index said data items; (c) determining a variance of values in one or more dimensions of said data items; (d) identifying a first dimension of said one or more multi dimensions in which to divide said set of multi-dimensional data items; (e) sorting said data items in said first dimension; (f) dividing said sorted data items in said first dimension into two or more subsets; (g) repeating (a)-(f) for each said subset in order to divide said set of data items into a plurality of data item clusters, wherein each cluster comprises a number of data items no greater than said node capacity; and (h) configuring a leaf node of said hierarchical index for data items in a first cluster.
Claim 35
Dependent Claim
273 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of updating an electronic index of multi-dimensional data items, the method comprising: receiving a new data item to be added to a set of hierarchically indexed multi-dimensional data items; inserting said new data item in a leaf node of said hierarchical index, wherein each node of said index comprises one or more of: a node identifier of said node; a row identifier of a storage location of said node in a database; a parent_node identifier of a parent of said node; a parent_row identifier of a storage location of said parent of said node in said database; a sibling identifier of a sibling of said node; and a set of child entries corresponding to children of said node; determining whether a first node in said index splits due to said inserting; if said first node splits due to said inserting: creating a second node; assigning said second node said node identifier of said first node; assigning a new node identifier to said first node; and transferring one or more child entries of said set of child entries of said first node to said second node; and if said first node is a root node of said index: creating a new root node of said index; setting said parent_node identifier of one of said first node and said second node to said node identifier of said new root node; and setting said parent_row identifier of said one of said first node and said second node to said row identifier of said new root node.
Claim 36
Dependent Claim
273 words
A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of updating an electronic index of multi-dimensional data items, the method comprising: receiving a new data item to be added to a set of hierarchically indexed multi-dimensional data items; inserting said new data item in a leaf node of said hierarchical index, wherein each node of said index comprises one or more of: a node identifier of said node; a row identifier of a storage location of said node in a database; a parent_node identifier of a parent of said node; a parent_row identifier of a storage location of said parent of said node in said database; a sibling identifier of a sibling of said node; and a set of child entries corresponding to children of said node; determining whether a first node in said index splits due to said inserting; if said first node splits due to said inserting: creating a second node; assigning said second node said node identifier of said first node; assigning a new node identifier to said first node; and transferring one or more child entries of said set of child entries of said first node to said second node; and if said first node is a root node of said index: creating a new root node of said index; setting said parent_node identifier of one of said first node and said second node to said node identifier of said new root node; and setting said parent_row identifier of said one of said first node and said second node to said row identifier of said new root node.
References Cited (Backward Citations)
US5404512A
Cited
US5647058A
Cited
US5701467A
Cited
US5752243A
Cited
US5706503A
Cited
US5724577A
Cited
US5781906A
Cited
US6182060B1
Cited
EP0887758A2
Cited
US5943668A
Cited
US5978796A
Cited
US5905985A
Cited
US5974407A
Cited
US5943677A
Cited
US6122628A
Cited
US6003036A
Cited
US6185552B1
Cited
US6070164A
Cited
US6223182B1
Cited
WO2001004795A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-01-06 | 2006-07-08 | 2007-01-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-01-06 | 2010-07-08 | 2011-01-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-01-06 | 2014-07-08 | 2015-01-07 | $7700.00 | Window Closed / Lapsed |