Spatial index compression through spatial subdivision encoding

Claim 2

A computer-implemented method for reducing storage requirements of data having spatial extents, comprising the steps of: (a) representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and (b) storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 3

The method of claim 1 above, further comprising the step of performing a preorder traversal of the tree structure to store it compactly in an output file.

Claim 4

The method of claim 2 above, further comprising the step of storing a pointer-less representation of the tree structure from the preorder traversal.

Claim 5

The method of claim 1 above, wherein the tree structure comprises a cell tree.

Claim 6

The method of claim 2 above, wherein the cell tree is an n-ary tree, wherein each root of a subtree in the cell tree contains extents of each node in the subtree.

Claim 7

The method of claim 1 above, wherein the nodes of type 3 classify data that spans the extents along a coordinate axis.

Claim 8

The method of claim 1 above, wherein the nodes of type 3 further comprise a merger of nodes along two coordinate axes.

Claim 9

The method of claim 1 above, wherein a node in the cell tree is in a realized state.

Claim 10

The method of claim 1 above, wherein a node in the cell tree is in an unrealized state.

Claim 11

The method of claim 9 above, wherein a node in the cell tree in the unrealized state indicates that a representation of its subtree is stored in a pre-order traversal format.

Claim 12

The method of claim 9 above, wherein a node in the cell tree in the unrealized state contains an offset into a buffer that has the start token of its subtree instead of pointing to the first child node in its subtree.

Claim 13

The method of claim 1 above, wherein a node is comprised of one or more fields selected from a group including a Buffer Pointer, State, Child Pointer, Data Offset, Spatial ID, Extents, Parent, and Sibling.

Claim 14

The method of claim 12 above, further comprising the step of adding entries to the tree structure.

Claim 15

The method of claim 13 above, wherein the adding step further comprises the steps of determining a first node that will fit the entity by traversing siblings of a first child node of a node, and identifying which node includes the extents that are specified by the Spatial ID.

Claim 16

The method of claim 12 above, wherein the Spatial ID is stored in an extension dictionary of a table record of a block table within a database of a datastream.

Claim 17

The method of claim 1 above, further comprising the step of computing the extents of each node from a traversal from a root node.

Claim 18

A computer-implemented apparatus for reducing storage requirements of data having spatial extents, comprising: (a) a computer having one or more electronic storage devices connected thereto, wherein the data is stored on one or more of the electronic storage devices; (b) means, performed by the computer, for representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and (c) means, performed by the computer, for storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 19

A computer-implemented apparatus for reducing storage requirements of data having spatial extents, comprising: (a) a computer having one or more electronic storage devices connected thereto, wherein the data is stored on one or more of the electronic storage devices; (b) means, performed by the computer, for representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and (c) means, performed by the computer, for storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 20

A program storage device, readable by a computer, tangibly embodying one or more instructions executable by the computer to perform method steps for reducing storage requirements of data having spatial extents, the method comprising the steps of: (a) representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and (b) storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 21

A program storage device, readable by a computer, tangibly embodying one or more instructions executable by the computer to perform method steps for reducing storage requirements of data having spatial extents, the method comprising the steps of: (a) representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and (b) storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 22

A data structure storing data having spatial extents, the data structure being stored in a data storage device for use by a computer program executed by a computer, the data structure comprising a tree structure having a plurality of nodes, each of the nodes having a parent and child relationship to one or more others of the nodes in the tree structure, and each of the nodes storing a Spatial ID that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 23

A data structure storing data having spatial extents, the data structure being stored in a data storage device for use by a computer program executed by a computer, the data structure comprising a tree structure having a plurality of nodes, each of the nodes having a parent and child relationship to one or more others of the nodes in the tree structure, and each of the nodes storing a Spatial ID that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.

Claim 24

The data structure of claim 19 above, wherein the data structure stores a preorder traversal of the tree structure.

Claim 25

The data structure of claim 20 above, wherein the data structure stores a pointer-less representation of the tree structure from the preorder traversal.

Claim 26

The data structure of claim 19 above, wherein the tree structure comprises a cell tree.

Claim 27

The data structure of claim 22 above, wherein the cell tree is an n-ary tree, wherein each root of a subtree in the cell tree contains extents of each node in the subtree.

Claim 28

The data structure of claim 19 above, wherein the nodes of type 3 classify data that spans the extents along a coordinate axis.

Claim 29

The data structure of claim 19 above, wherein the nodes of type 3 further comprise a merger of nodes along two coordinate axes.

Claim 30

The data structure of claim 19 above, wherein a node in the cell tree is in a realized state.

Claim 31

The data structure of claim 19 above, wherein a node in the cell tree is in an unrealized state.

Claim 32

The data structure of claim 27 above, wherein a node in the cell tree in the unrealized state indicates that a representation of its subtree is stored in a pre-order traversal format.

Claim 33

The data structure of claim 27 above, wherein a node in the cell tree in the unrealized state contains an offset into a buffer that has the start token of its subtree instead of pointing to the first child node in its subtree.

Claim 34

The data structure of claim 19 above, wherein a node is comprised of one or more fields selected from a group including a Buffer Pointer, State, Child Pointer, Data Offset, Spatial D, Extents, Parent, and Sibling.

Claim 35

The data structure of claim 30 above, wherein an entity is added to the data structure by determining a first node that will fit the entity by traversing siblings of a first child node of a node, and identifying which node includes the extents that are specified by the Spatial ID.

Claim 36

The data structure of claim 19 above, wherein the extents of each node are computed from a traversal from a root node.

Claim 37

The data structure of claim 19 above, wherein the Spatial ID is stored in an extension dictionary of a table record of a block table within the data structure. TABLE 1 ______________________________________ Total # #Objects Average % of Total # Objects #Cells visited # Cells Sample Cells in in the visited during Objects expanded Drawing the Cell Cell during the per by type tree tree query query Cell query ______________________________________ AEC 512 5743 94 553 11 18 GIS 472 5001 133 995 11 28 Electrical 295 2353 41 266 8 14 100 × 100 697 10000 49 185 14 7 Rect. Array of 10000 lines (synthetic case). ______________________________________

Claim 38

The apparatus of claim 17 above, further comprising the step of performing a preorder traversal of the tree structure to store it compactly in an output file.

Claim 39

The apparatus of claim 34 above, further comprising the step of storing a pointer-less representation of the tree structure from the preorder traversal.

Claim 40

The apparatus of claim 17 above, wherein the tree structure comprises a cell tree.

Claim 41

The apparatus of claim 34 above, wherein the cell tree is an n-ary tree, wherein each root of a subtree in the cell tree contains extents of each node in the subtree.

Claim 42

The apparatus of claim 17 above, wherein the nodes of type 3 classify data that spans the extents along a coordinate axis.

Claim 43

The apparatus of claim 17 above, wherein the nodes of type 3 further comprise a merger of nodes along two coordinate axes.

Claim 44

The apparatus of claim 17 above, wherein a node in the cell tree is in a realized state.

Claim 45

The apparatus of claim 17 above, wherein a node in the cell tree is in an unrealized state.

Claim 46

The method of claim 41 above, wherein a node in the cell tree in the unrealized state indicates that a representation of its subtree is stored in a pre-order traversal format.

Claim 47

The method of claim 41 above, wherein a node in the cell tree in the unrealized state contains an offset into a buffer that has the start token of its subtree instead of pointing to the first child node in its subtree.

Claim 48

The apparatus of claim 17 above, wherein a node is comprised of one or more fields selected from a group including a Buffer Pointer, State, Child Pointer, Data Offset, Spatial ID, Extents, Parent, and Sibling.

Claim 49

The method of claim 44 above, farther comprising the step of adding entries to the tree structure.

Claim 50

The method of claim 45 above, wherein the adding step further comprises the steps of determining a first node that will fit the entity by traversing siblings of a first child node of a node, and identifying which node includes the extents that are specified by the Spatial ID.

Claim 51

The method of claim 44 above, wherein the Spatial ID is stored in an extension dictionary of a table record of a block table within a database of a datastream.

Claim 52

The apparatus of claim 17 above, further comprising the step of computing the extents of each node from a traversal from a root node.

Claim 53

The method of claim 18 above, further comprising the step of performing a preorder traversal of the tree structure to store it compactly in an output file.

Claim 54

The method of claim 49 above, further comprising the step of storing a pointer-less representation of the tree structure from the preorder traversal.

Claim 55

The method of claim 18 above, wherein the tree structure comprises a cell tree.

Claim 56

The method of claim 49 above, wherein the cell tree is an n-ary tree, wherein each root of a subtree in the cell tree contains extents of each node in the subtree.

Claim 57

The method of claim 18 above, wherein the nodes of type 3 classify data that spans the extents along a coordinate axis.

Claim 58

The method of claim 18 above, wherein the nodes of type 3 further comprise a merger of nodes along two coordinate axes.

Claim 59

The method of claim 18 above, wherein a node in the cell tree is in a realized state.

Claim 60

The method of claim 18 above, wherein a node in the cell tree is in an unrealized state.

Claim 61

The method of claim 56 above, wherein a node in the cell tree in the unrealized state indicates that a representation of its subtree is stored in a pre-order traversal format.

Claim 62

The method of claim 56 above, wherein a node in the cell tree in the unrealized state contains an offset into a buffer that has the start token of its subtree instead of pointing to the first child node in its subtree.

Claim 63

The method of claim 18 above, wherein a node is comprised of one or more fields selected from a group including a Buffer Pointer, State, Child Pointer, Data Offset, Spatial ID, Extents, Parent, and Sibling.

Claim 64

The method of claim 59 above, further comprising the step of adding entries to the tree structure.

Claim 65

The method of claim 60 above, wherein the adding step further comprises the steps of determining a first node that will fit the entity by traversing siblings of a first child node of a node, and identifying which node includes the extents that are specified by the Spatial ID.

Claim 66

The method of claim 59 above, wherein the Spatial ID is stored in an extension dictionary of a table record of a block table within a database of a datastream.

Claim 67

The method of claim 18 above, further comprising the step of computing the extents of each node from a traversal from a root node.