Spatial Sieve Tree

• US 7,734,714 B2
• Filed: 01/11/2008
• Issued: 06/08/2010
• Est. Priority Date: 01/11/2008
• Status: Expired due to Fees

• Current Assignee: SpaceCurve, Inc.
• Original Assignee: SpaceCurve, Inc.
• Inventors: Rogers, J. Andrew
• Primary Examiner(s): Tran; Philip B
• Application Number:
  US12/013,385
• Publication Number:
  US 20090182837A1
• Time in Patent Office: 879 Days
• Field of Search: 709/215, 709/220, 709/223, 709/200, 709/224, 707/103.X, 707/101, 707/3
• 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 be 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, wherein the data object is not wholly contained by one node of the determined level but would be wholly contained by one node if the data object was translated in coordinate space; and

storing the data object in two or more nodes of the determined level that at least partially contain the data object based on the bounds of the two 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-Tree.

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 wherein determining which level of the tree has the smallest size node in which a data object could wholly fit comprises:

treating the root node as a current node;

determining that the data object would wholly fit within a child node of the current node;

determining which one or more child nodes of the current node at least partially contain the data object; and

recursively treating each of the one or more child nodes that at least partially contain the data object as the current node until reaching a level for which the data object will not wholly fit within a child node even if translated in coordinate space.

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 if the data object was translated 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 a data object could wholly fit, wherein the data object is not wholly contained by one node of the determined level but would be wholly contained by one node if the data object was translated in coordinate space; and

a data insertion module for instructing a storage device to store the data object in two or more nodes of the determined level that at least partially contain the data object based on the bounds of the two or more nodes.

15. The apparatus of claim 14, wherein a portion of the tree is represented by a multimap and wherein determining which level of the tree has the smallest size node in which a data object could wholly fit comprises:

treating the root node as a current node;

determining that the data object would wholly fit within a child node of the current node; and

determining which one or more child nodes of the current node at least partially contain the data object; and

recursively treating each of the one or more child nodes that at least partially contain the data object as the current node until reaching a level for which the data object will not wholly fit within a child node even if translated in coordinate space.

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 if the data object was translated 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 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, wherein the data object is not wholly contained by one node of the determined level but would be wholly contained by one node if the data object was translated in coordinate space; and

store the data object in two or more nodes of the determined level that at least partially contain the data object based on the bounds of the two 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 and wherein determining which level of the tree has the smallest size node in which a data object could wholly fit comprises

treating the root node as a current node;

determining that the data object would wholly fit within a child node of the current node; and

determining which one or more child nodes of the current node at least partially contain the data object; and

recursively treating each of the one or more child nodes that at least partially contain the data object as the current node until reaching a level for which the data object will not wholly fit within a child node even if translated in coordinate space.

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 if the data object was translated 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, wherein the data object is not wholly contained by one node of the determined level but would be wholly contained by one node if the data object was translated in coordinate space; and

store the data object in two or more nodes of the determined level that at least partially contain the data object based on the bounds of the two 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 and wherein determining which level of the tree has the smallest size node in which a data object could wholly fit comprises

treating the root node as a current node;

determining that the data object would wholly fit within a child node of the current node; and

determining which one or more child nodes of the current node at least partially contain the data object; and

recursively treating each of the one or more child nodes that at least partially contain the data object as the current node until reaching a level for which the data object will not wholly fit within a child node even if translated in coordinate space.

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 if the data object was translated 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.