Method and/or system for transforming between trees and arrays

• US 10,394,785 B2
• Filed: 03/09/2015
• Issued: 08/27/2019
• Est. Priority Date: 03/31/2005
• Status: Expired due to Fees

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. And, Virginia T. Jenkins
• Inventors: LeTourneau, Jack J.
• Primary Examiner(s): Allen, Brittany N
• Application Number:
  US14/641,735
• Publication Number:
  US 20150310048A1
• Time in Patent Office: 1,632 Days
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments of articles, apparatuses, devices and/or systems for manipulating hierarchical sets of data are disclosed.

Claims

1. A method, comprising:

accessing instructions from one or more physical memory devices for execution by one or more processors;

executing instructions accessed from the one or more physical memory devices by the one or more processors;

storing, in at least one of the physical memory devices, signal values resulting from having executed the instructions on the one or more processors;

wherein the accessed instructions to transform between a tree and an array of numerical signal values; and

wherein executing the transformation instructions further comprising;

transforming the tree to the array of numerical signal values, based at least in part on a unique mapping between tree structures and numerical signal values, the array of numerical signal values comprising one or more rows and columns of numerical signal values and an associated index for the one or more rows and columns of numerical signal values;

performing manipulation of the tree, wherein the performing manipulation of the tree comprises processing the array of numerical signal values to yield an updated array of numerical signal values, the updated array of numerical signal values utilizing less storage space in the one or more physical memory devices than the array of numerical signal values;

storing the updated array of numerical signal values in the one or more physical memory devices; and

generating a resulting tree, wherein the generating the resulting tree comprises transforming the updated array of numerical signal values to an updated tree, based at least in part on the unique mapping between the tree structures and numerical signal values.

2. The method of claim 1, wherein the updated array of numerical signal values comprises a condensed array of numerical signal values representing the tree in a compressed format.

3. The method of claim 1, wherein executing the accessed transformation instructions further comprises:

associating numerical label values with at least some nodes and/or edges in the tree; and

associating label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerical signal values derived, at least in part, from label values associated with the child nodes.

4. The method of claim 3, wherein executing the accessed transformation instructions further comprises pruning the child nodes.

5. The method of claim 3, wherein a numerical label value associated with at least one of the parent nodes is based, at least in part, on a combination of non-composite numerical signal values derived, at least in part, from label values associated with the child nodes.

6. The method of claim 3, wherein executing the accessed transformation instructions further comprises determining the non-composite numerical signal values from an array of non-composite numerical signal values indexed by sequential indices.

7. The method of claim 1, wherein executing the accessed transformation instructions further comprises representing a parent node as a product of factors associated with one or more subtrees of the parent node.

8. The method of claim 1, wherein the transforming the tree to the array of numerical signal values comprises using digital signal values, responsive to executing the accessed transformation instructions, to select one or more numerical label values for portions of the tree and wherein the tree comprises a complex two dimensional graphical hierarchy, the complex two dimensional graphical hierarchy being in the form of a tree hierarchy.

9. The method of claim 8, wherein executing the accessed transformation instructions further comprises associating a binary one or zero for at least one of a new node or a new edge of the tree hierarchy.

10. The method of claim 8, wherein executing the accessed transformation instructions further comprises determining that the tree hierarchy comprises a node labeled tree.

11. The method of claim 8, wherein the array of numerical signal values comprises a condensed array of numerical signal values fixed in one dimension.

12. The method of claim 11, wherein the condensed array of numerical signal values comprises a condensed multi-dimensional array.

13. The method of claim 8, wherein executing the accessed transformation instructions further comprises:

accessing from one or more memories, one or more digital signal values comprising numeral values representing at least a portion of the tree hierarchy based at least in part on a stored ordered association between numeral values and tree hierarchies;

wherein the transforming the tree hierarchy to a condensed array of numerical signal values comprises transforming between at least one of the one or more digital signal values comprising numeral values representing at least a portion of the tree hierarchy; and

associating the at least one of the one or more digital signal values to represent one or more non-composite numerical signal values from the numeral values with at least one of a node or an edge of the tree hierarchy.

14. The method of claim 6, wherein executing the accessed transformation instructions further comprises:

deriving one or more additional digital signal values to represent one or more non-composite numerical signal values from the numeral values to be associated with the at least one of the node or the edge of the tree; and

associating the one or more additional digital signal values to represent a numerical label value with a parent node of the at least one node of the tree to be based, at least in part, on the derived one or more additional signal values to represent one or more non-composite numerical signal values.

15. An apparatus comprising:

means for accessing instructions from one or more physical memory devices for execution by one or more processors;

means for executing instructions accessed from the one or more physical memory devices by the one or more processors;

means for storing, in at least one of the physical memory devices, signals values resulting from having executed the instructions on the one or more processors;

wherein the accessed instructions to transform between a tree and an array of numerical signal values; and

wherein the means for executing the transformation instructions comprises;

means for transforming the tree to the array of numerical signal values, based at least in part on a unique mapping between tree structures and numerical signal values, the array of numerical signal values comprising one or more rows and columns of numerical signal values and an associated index for the one or more rows and columns of numerical signal values;

means for performing manipulation of the tree, wherein the performing manipulation of the tree comprises processing the array of numerical signal values to yield an updated array of numerical signal values, the updated array of numerical signal values utilizing less storage space in the one or more physical memory devices than the array of numerical signal values;

means for storing the updated array of numerical signal values in a memory of the apparatus; and

means for generating a resulting tree, wherein the generating the resulting tree comprises transforming the updated array of numerical signal values to an updated tree, based at least in part on the unique mapping between the tree structures and numerical signal values.

16. The apparatus of claim 15, wherein the updated array of numerical signal values comprises a condensed array of numerical signal values representing the tree in a compressed format.

17. The apparatus of claim 15, wherein the means for executing the accessed transformation instructions further comprises:

means for associating numerical label values with at least some nodes and/or edges in the tree; and

means for associating label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerical signal values derived, at least in part, from label values associated with the child nodes.

18. An article comprising:

a non-transitory storage medium comprising instructions stored thereon;

wherein the instructions being accessible from the non-transitory storage medium to store as physical memory states on one or more physical memory devices, the one or more physical memory devices coupled to one or more processors able to execute the instructions stored as physical memory states, the one or more physical memory devices also able to store binary digital signal quantities, if any, as physical memory states, that are to result from execution of the instructions on the one or more processors,

wherein the executable instructions to transform between a tree and an array of numerical signal values; and

wherein the transformation instructions further to;

transform the tree to the array of numerical signal values, based at least in part on a unique mapping between tree structures and numerical signal values, the array of numerical signal values comprising one or more rows and columns of numerical signal values and an associated index for the one or more rows and columns of numerical signal values;

perform manipulation of the tree to process the array of numerical signal values to yield an updated array of numerical signal values, the updated array of numerical signal values to utilize less storage space in the one or more physical memory devices than the array of numerical signal values;

store the updated array of numerical signal values in a memory of the computing device; and

generate a resulting tree and wherein to generate the resulting tree is to comprise transformation of the updated array of numerical signal values to an updated tree, to be based at least in part on the unique mapping between the tree structures and numerical signal values.

19. The article of claim 18, the transformation instructions being further executable by the one or more processors to:

associate numerical label values with at least some nodes and/or edges in the tree; and

associate label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerical signal values derived, at least in part, from label values associated with the child nodes.

20. The article of claim 19, the transformation instructions being further executable by the one or more processors to prune child nodes.

21. The article of claim 19, wherein a numerical label value associated with at least one of the parent nodes is to be based, at least in part, on a combination of non-composite numerical signal values to be derived, at least in part, from label values to be associated with the child nodes.

22. The article of claim 19, the transformation instructions being further executable by the one or more processors to determine the non-composite numerical signal values from an array of non-composite numerical signal values indexed by sequential indices.

23. The article of claim 18, the transformation instructions being further executable by the one or more processors to represent a parent node as a product of factors associated with one or more subtrees of the parent node.

24. An apparatus comprising:

one or more processors coupled to one or more physical memory devices to store executable instructions and to store binary digital storage quantities as physical memory states, wherein the executable instructions being accessible from the one or more physical memory devices for execution by one or more processors; and

the one or more processors able to store in at least one of the physical memory devices, binary digital signal quantities, if any, that are to result from execution of the instructions on the one or more processors, wherein the accessed executable instructions to transform between a tree and an array of numerical signal values; and

wherein the transformation instructions further to;

transform the tree to the array of numerical signal values, based at least in part on a unique mapping between tree structures and numerical signal values, the array of numerical signal values comprising one or more rows and columns of numerical signal values and an associated index for the one or more rows and columns of numerical signal values;

perform manipulation of the tree to process the array of numerical signal values to yield an updated array of numerical signal values, the updated array of numerical signal values to utilize less storage space in the one or more physical memory devices than the array of numerical signal values;

store the updated array of numerical signal values in a memory of the computing device; and

generate a resulting tree and wherein to generate the resulting tree is to comprise transformation of the updated array of numerical signal values to an updated tree, to be based at least in part on the unique mapping between the tree structures and numerical signal values.