Spatial Sieve Tree

• US 20090182837A1
• Filed: 01/11/2008
• Published: 07/16/2009
• Est. Priority Date: 01/11/2008
• Status: Active Grant

• Current Assignee: SpaceCurve, Inc.
• Original Assignee: SpaceCurve, Inc.
• Inventors: Rogers, J. Andrew
• Granted Patent: US 7,734,714 B2
• Time in Patent Office: Days
• US Class Current: 709/215
• CPC Class Codes: G06F 16/9027 Trees

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.

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.

2. The machine readable medium of claim 1 wherein the data is multidimensional.

3. The machine readable medium of claim 1 wherein the total number of levels is limited to a predetermined number.

4. The machine readable medium of claim 1 wherein the total number of partitions of a node is limited to a predetermined number.

5. The machine readable medium of claim 1 wherein the nodes are partitioned uniformly.

6. The machine readable medium of claim 1 wherein the bounds of child nodes are equal in size at each level.

7. The machine readable medium of claim 1 wherein the nodes of the same level do not overlap.

8. The machine readable medium of claim 1 wherein the tree is based upon the structure of a Quad-free.

9. The machine readable medium of claim 1 wherein the tree is based upon the structure of a KD-Tree.

10. The machine readable medium of claim 1 wherein the tree is represented by a multimap.

11. The machine readable medium of claim 1 wherein a portion of the tree is represented by a multimap.

12. The machine readable medium of claim 11 further comprising:

determining, based upon a data object'"'"'s location in coordinate space and the smallest size node in which the data would wholly fit regardless of the data object'"'"'s location in coordinate space, the one or more lowest level parent nodes represented in the multimap that contain one or more child nodes that could contain the data object; and

recursively searching the tree from the determined parent nodes downward to access the one or more child nodes that could intersect with the data.

13. The machine readable medium of claim 1 further comprising:

receiving a query for a data object;

determining, based upon the data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, that multiple copies of the data have been inserted into a plurality of child nodes; and

masking duplicate copies of the data.

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;

15. The apparatus of claim 14, wherein a portion of the tree is represented by a multimap and the spatial sieve module;

determines, based upon a data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, the one or more lowest level parent nodes represented in the multimap that contain one or more child nodes that could contain the data; and

recursively searching the tree from the determined parent nodes downward to access the one or more child nodes that could intersect with the data.

16. The apparatus of claim 14, wherein the input and output module receives a query for a data object and the spatial sieve module determines, based upon the data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, that multiple copies of the data have been inserted into a plurality of child nodes further comprising;

an edge overlap masking module for masking duplicate copies of the data object.

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.

18. The apparatus of claim 17 wherein the memory further stores instructions to cause the processor to:

represent a portion of the tree with a multimap;

determine, based upon a data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, the one or more lowest level parent nodes represented in the multimap that contain one or more child nodes that could contain the data; and

recursively search the tree from the determined parent nodes downward to access the one or more child nodes that could intersect with the data.

19. The apparatus of claim 17 wherein the processor receives a query for a data object and the memory further stores instructions to cause the processor to:

determine, based upon the data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, that multiple copies of the data have been inserted into a plurality of child nodes; and

mask duplicate copies of the data object.

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.

21. The system of claim 20 wherein the memory further stores instructions to cause the processor to:

represent a portion of the tree with a multimap;

determine, based upon a data object'"'"'s location in coordinate space and smallest size node in which the data would wholly lit regardless of the data'"'"'s location in coordinate space, the one or more lowest level parent nodes represented in the multimap that contain one or more child nodes that could contain the data; and

recursively search the tree from the determined parent nodes downward to access the one or more child nodes that could intersect with the data.

22. The system of claim 20 wherein the processor receives a query for a data object and the memory further stores instructions to cause the processor to:

determine, based upon the data object'"'"'s location in coordinate space and smallest size node in which the data would wholly fit regardless of the data'"'"'s location in coordinate space, that multiple copies of the data have been inserted into a plurality of child nodes; and

mask duplicate copies of the data object.