Spatial Sieve Tree
First Claim
1. A machine readable medium having executable instructions to cause a machine to perform a method comprising:
- creating a multi-level, multidimensional tree, including a root node with defined bounds;
partitioning the bounds of the root node of the tree;
creating, at a level in the tree below the level of the root node, a plurality of child nodes, wherein each child node has defined bounds associated with a partitioned portion of the root node and which may he further partitioned into additional levels of child nodes, and each level of the tree below the root node level containing successively smaller nodes;
determining which level of the tree has the smallest size node in which a data object could wholly fit regardless of the data object'"'"'s location in coordinate space; and
storing the data object in one or more nodes of the determined level that at least partially contain the data object based on the bounds of the one or more nodes.
2 Assignments
0 Petitions
Accused Products
Abstract
A method, apparatus, and system is described for creating a spatial sieve tree which stores, manages, and manipulates multidimensional data by partitioning the bounds of the nodes of the tree, creating child nodes which each have defined bounds associated with a partitioned portion of their parent node(s) and may be further partitioned into additional levels of child nodes, and determining which level of the tree has the smallest size node in which a data object could wholly fit regardless of the data object'"'"'s location in coordinate space and the one or more nodes of that determined level that could at least partially contain the data object based on the bounds of the one or more nodes and the data object'"'"'s location in coordinate space.
218 Citations
22 Claims
-
1. A machine readable medium having executable instructions to cause a machine to perform a method comprising:
-
creating a multi-level, multidimensional tree, including a root node with defined bounds; partitioning the bounds of the root node of the tree; creating, at a level in the tree below the level of the root node, a plurality of child nodes, wherein each child node has defined bounds associated with a partitioned portion of the root node and which may he further partitioned into additional levels of child nodes, and each level of the tree below the root node level containing successively smaller nodes; determining which level of the tree has the smallest size node in which a data object could wholly fit regardless of the data object'"'"'s location in coordinate space; and storing the data object in one or more nodes of the determined level that at least partially contain the data object based on the bounds of the one or more nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. An apparatus comprising;
-
an input and output module for receiving and sending one or more data objects and data object instructions; a node creation module for creating a multi-level, multidimensional tree to store the one or more data objects, including a root node with defined bounds, wherein the node creation module partitions the bounds of the root node of the tree and creates, at a level in the tree below the level of the root node, a plurality of child nodes, wherein each child node has defined bounds associated with a partitioned portion of the root node and which may be further partitioned into additional levels of child nodes, and each level of the tree below the root node level containing successively smaller nodes; a spatial sieve module for determining which level of the tree has the smallest size node in which the data object could wholly fit regardless of the data object'"'"'s location in coordinate space; a data insertion module for instructing a storage device to store the data object in one or more nodes of the determined level that at least partially contain the data object based on the bounds of the one or more nodes; - View Dependent Claims (15, 16)
-
-
17. An apparatus comprising:
-
a processor; and a memory coupled to the processor to store instructions to cause the processor to; create a multi-level, multidimensional tree, including a root node with defined bounds; partition the bounds of the root node of the tree; create, at a level so the tree below the level of the root node, a plurality of child nodes, wherein each child node has defined bounds associated with a partitioned portion of the root node and which may be further partitioned into additional levels of child nodes, and each level of the tree below the root node level containing successively smaller nodes; determine which level of the tree has the smallest size node in which a data object could wholly fit regardless of the data object'"'"'s location in coordinate space; and store the data object in one or more nodes of the determined level that at least partially contain the data object based on the bounds of the one or more nodes. - View Dependent Claims (18, 19)
-
-
20. A system comprising:
-
a processor; a storage device to store a multidimensional, multi-level tree; a network coupled between the processor and the storage device; and a memory coupled to the processor to store instructions to cause the processor to create a multi-level, multidimensional tree, including a root node with defined bounds; partition the bounds of the root node of the tree; create, at a level in the tree below the level of the root node, a plurality of child nodes, wherein each child node has defined bounds associated with a partitioned portion of the root node and which may be further partitioned into additional levels of child nodes, and each level of the tree below the root node level containing successively smaller nodes; determine which level of the tree has the smallest size node in which a data object could wholly fit regardless of the data object'"'"'s location in coordinate space; and store the data object in one or more nodes of the determined level that at least partially contain the data object based on the bounds of the one or more nodes. - View Dependent Claims (21, 22)
-
Specification