Enumeration of trees from finite number of nodes

• US 9,842,130 B2
• Filed: 07/19/2016
• Issued: 12/12/2017
• Est. Priority Date: 11/30/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Dated February 8, 2002
• Inventors: Schiffmann, Karl, Andrews, Mark, LeTourneau, Jack J.
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US15/214,168
• Publication Number:
  US 20160328431A1
• Time in Patent Office: 511 Days
• Field of Search: 707102, 707101, 707755, 707802
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

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

Claims

1. A method of enumerating complex two-dimensional graphical hierarchies for more convenient processing and/or storage, a complex two-dimensional graphical hierarchy being in the form of a tree hierarchy, the 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 enumerate tree hierarchies; and

wherein executing the accessed tree hierarchy enumeration instructions further comprising;

enumerating tree hierarchies, in which a tree hierarchy comprises one or more signal values, configured from a finite number (N) of nodes, wherein N comprises a natural numeral greater than one, the enumerating of tree hierarchies configured from the finite number of nodes further comprising;

identifying N−

1 arrangements of subtree hierarchy slots coupled to a root node;

for an arrangement of subtree hierarchy slots;

determining one or more allocations of N−

1 nodes among the subtree hierarchy slots in the arrangement, a subtree hierarchy slot being allocated a portion of the N−

1 nodes; and

for the subtree hierarchy slots, enumerating one or more subtree hierarchies configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot;

determining for the enumerated tree hierarchies natural numerals associated with particular ones of the enumerated tree hierarchies; and

storing, in a memory, the natural numerals.

2. The method of claim 1, wherein the executing the accessed tree hierarchy enumeration instructions further comprises:

associating the enumerated one or more subtree hierarchies for a subtree hierarchy slot with a natural numeral; and

determining the natural numeral associated with a tree hierarchy enumerated from an allocation of the N−

1 nodes among subtree hierarchies based, at least in part, upon a combination of the natural numerals associated with particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

3. The method of claim 2, wherein the natural numeral associated with a tree hierarchy enumerated from an allocation of the N−

1 nodes is based, at least in part, upon a product of the natural numerals associated with the particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

4. The method of claim 1, wherein the executing the accessed tree hierarchy enumeration instructions further comprises:

identifying each enumerated tree hierarchy as being a composite of subtree hierarchies according to one of the N−

1 arrangements of subtree hierarchy slots, N−

1 nodes being allocated among the composite of subtree hierarchies, each subtree hierarchy in the composite of subtree hierarchies having a particular configuration of nodes which are allocated to the subtree hierarchy and being associated with a natural numeral based, at least in part, upon the association among the allocated nodes, and wherein the natural numeral associated with the tree hierarchy comprises a combination of the natural numerals associated with the subtree hierarchies in the composite of subtree hierarchies.

5. The method of claim 1, wherein the executing the accessed tree hierarchy enumeration instructions further comprises:

identifying an enumerated tree as being a composite of subtree hierarchies according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes being allocated among the composite of subtree hierarchies, a subtree hierarchy in the composite of subtree hierarchies having a particular configuration of nodes which are allocated to the subtree hierarchy and being associated with a natural numeral, and wherein the natural numeral associated with the tree hierarchy comprises a combination of the natural numerals associated with the subtree hierarchies in the composite of subtree hierarchies.

6. The method of claim 1, wherein:

identifying N−

1 arrangements of subtree hierarchy slots, comprises identifying each of N−

1 arrangements of subtree hierarchy slots coupled to the root node;

determining one or more allocations of N−

1 nodes comprises determining the one or more allocations of N−

1 nodes among the subtree hierarchy slots in the arrangement, each subtree hierarchy slot being allocated a portion of the N−

1 nodes; and

enumerating one or more subtree hierarchies configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot comprises enumerating each of one or more subtree hierarchies configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot.

7. The method of claim 6, wherein the executing the accessed tree hierarchy enumeration instructions further comprises:

associating each of the enumerated one or more subtree hierarchies for each subtree hierarchy slot with a natural numeral; and

determining the natural numeral associated with each tree hierarchy enumerated from an allocation of the N−

1 nodes, among subtree hierarchies based, at least in part, upon a combination of the natural numerals associated with particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

8. The method of claim 7, wherein the natural numeral associated with each tree hierarchy enumerated from an allocation of the N−

1 nodes is based, at least in part, upon a product of the natural numerals associated with the particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

9. The method of claim 1, wherein the executing the accessed tree hierarchy enumeration instructions further comprises enumerating the tree hierarchies configured from exactly N nodes.

10. An apparatus to enumerate a complex two-dimensional graphical hierarchy for more convenient processing and/or storage, a complex two-dimensional graphical hierarchy being in the form of a tree hierarchy, the 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, signal values resulting from having executed the instructions on the one or more processors;

wherein the accessed instructions to enumerate tree hierarchies; and

wherein the means for executing the accessed tree hierarchy enumeration instructions comprises;

means for enumerating tree hierarchies, a tree hierarchy to comprise one or more signal values, configured from a finite number (N) of nodes, wherein N comprises a natural numeral greater than one;

the means for enumerating tree hierarchies configured from the finite number of nodes further comprises;

means for identifying N−

1 arrangements of subtree hierarchy slots coupled to a root node;

means for determining one or more allocations of N−

1 nodes among the subtree hierarchy slots in an identified arrangement of subtree hierarchy slots, a subtree hierarchy slot being allocated a portion of the N−

1 nodes; and

means for enumerating one or more subtree hierarchies, configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot;

means for determining, for the enumerated tree hierarchies, natural numerals associated with particular ones of the enumerated tree hierarchies; and

means for storing, in a memory, the natural numerals.

11. The apparatus of claim 10, wherein the means for executing the accessed tree hierarchy enumeration instructions further comprises:

means for associating the enumerated one or more subtree hierarchies for a subtree hierarchy slot with a natural numeral; and

means for determining the natural numeral associated with a tree hierarchy enumerated from an allocation of the N−

1 nodes among subtree hierarchies based, at least in part, upon a combination of the natural numerals, associated with particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

12. The apparatus of claim 11, wherein the natural numeral associated with a tree hierarchy enumerated from an allocation of the N−

1 nodes is based, at least in part, upon a product of the natural numerals associated with the particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

13. The apparatus of claim 10, wherein the means for executing the accessed tree hierarchy enumeration instructions further comprises:

means for identifying each enumerated tree hierarchy, represented by one or more signal values, as being a composite of subtree hierarchies according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes being allocated among the composite of subtree hierarchies, each subtree hierarchy, in the composite of subtree hierarchies, having a particular configuration of nodes which are allocated to the subtree hierarchy and being associated with a natural numeral based, at least in part, upon the association among the allocated nodes, and wherein the natural numeral associated with the tree hierarchy comprises a combination of the natural numerals associated with the subtree hierarchies in the composite of subtree hierarchies.

14. The apparatus of claim 10, wherein the means for executing the accessed tree hierarchy enumeration instructions further comprises:

means for identifying an enumerated tree hierarchy as being a composite of subtree hierarchies according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes being allocated among the composite of subtree hierarchies, a subtree hierarchy in the composite of subtree hierarchies having a particular configuration of nodes which are allocated to the subtree hierarchy and being associated with a natural numeral, and wherein the natural numeral associated with the tree hierarchy comprises a combination of the natural numerals associated with the subtree hierarchies in the composite of subtree hierarchies.

15. The apparatus of claim 10, wherein:

the means for identifying N−

1 arrangements of subtree hierarchy slots comprises means for identifying each of N−

1 arrangements of subtree hierarchy slots coupled to the root node;

the means for determining one or more allocations of N−

1 nodes comprises means for determining one or more allocations of N−

1 nodes among the subtree hierarchy slots in the arrangement, each subtree hierarchy slot being allocated a portion of the N−

1 nodes; and

the means for enumerating one or more subtree hierarchies, configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot comprises means for enumerating each of one or more subtree hierarchies configured from the portion of the N−

1 nodes allocated to the subtree hierarchy slot.

16. The apparatus of claim 15, wherein the means for executing the accessed tree hierarchy enumeration instructions further comprises:

means for associating each of the enumerated one or more subtree hierarchies for each subtree hierarchy slot with a natural numeral; and

means for determining the natural numeral associated with each tree hierarchy enumerated from an allocation of the N−

1 nodes among subtree hierarchies based, at least in part, upon a combination of the natural numerals associated with particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

17. The apparatus of claim 16, wherein the natural numeral associated with each tree enumerated from an allocation of the N−

1 nodes is based, at least in part, upon a product of the natural numerals associated with the particular subtree hierarchies enumerated from the allocation of N−

1 nodes.

18. The apparatus of claim 10, wherein the means for enumerating configured tree hierarchies comprises means for enumerating the tree hierarchies configured from exactly N nodes.

19. An apparatus comprising:

one or more processors coupled to one or more physical memory devices to store executable instructions and to store binary digital signal quantities as physical memory states, wherein the executable instructions being;

accessible from the physical memory devices for execution by one or more processors;

executable by the one or more processors; and

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 enumerate tree hierarchies; and

wherein the accessed tree hierarchy enumeration instructions further;

to enumerate tree hierarchies, a tree hierarchy to comprise one or more signal values, configured from a finite number (N) of nodes, wherein N comprises a natural numeral greater than one, wherein to enumerate tree hierarchies configured from the finite number of nodes further comprises to;

identify N−

1 arrangements of subtree hierarchy slots to be coupled to a root node;

determine one or more allocations of N−

1 nodes among the subtree hierarchy slots in a to be identified arrangement of subtree hierarchy slots, a subtree hierarchy slot to be allocated a portion of the N−

1 nodes; and

enumerate one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot;

to determine for the to be enumerated tree hierarchies natural numerals to be associated with particular ones of the to be enumerated tree hierarchies; and

to store, in a memory, the natural numerals.

20. The apparatus of claim 19, wherein the accessed tree hierarchy instructions further to:

associate the to be enumerated one or more subtree hierarchies for a subtree hierarchy slot with a natural numeral; and

determine the natural numeral to be associated with a tree hierarchy to be enumerated from an allocation of the N−

1 nodes among subtree hierarchies to be based, at least in part, upon a combination of the natural numerals to be associated with particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

21. The apparatus of claim 20, wherein the natural numeral to be associated with a tree hierarchy to be enumerated from an allocation of the N−

1 nodes is to be based, at least in part, upon a product of the natural numerals to be associated with the particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

22. The apparatus of claim 19, wherein the accessed tree hierarchy instructions further to:

identify each enumerated tree hierarchy as being a composite of subtree hierarchies to be according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes to be allocated among the composite of subtree hierarchies, each subtree hierarchy in the composite of subtree hierarchies to have a particular configuration of nodes which are to be allocated to the subtree hierarchy and to be associated with a natural numeral to be based, at least in part, upon the association among the allocated nodes, and wherein the natural numeral to be associated with the tree hierarchy to comprise a combination of the natural numerals to be associated with the subtree hierarchies in the composite of subtree hierarchies.

23. The apparatus of claim 19, wherein the accessed tree hierarchy instructions further to:

identify an enumerated tree hierarchy as being a composite of subtree hierarchies to be according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes to be allocated among the composite of subtree hierarchies, a subtree hierarchy in the composite of subtree hierarchies to have a particular configuration of nodes which are to be allocated to the subtree hierarchy and to be associated with a natural numeral, and wherein the natural numeral associated with the tree hierarchy to comprise a combination of the natural numerals to be associated with the subtree hierarchies in the composite of subtree hierarchies.

24. The apparatus of claim 19, wherein the accessed tree hierarchy instructions further to:

identify each of N−

1 arrangements of subtree hierarchy slots to be coupled to the root node;

determine one or more allocations of N−

1 nodes to be among the subtree hierarchy slots in the arrangement, each subtree hierarchy slot to be allocated a portion of the N−

1 nodes; and

enumerate one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot to comprise an enumeration of each of one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

25. The apparatus of claim 24, wherein the accessed tree hierarchy instructions further to:

associate each of the to be enumerated one or more subtree hierarchies for each subtree hierarchy slot with a natural numeral; and

determine the natural numeral to be associated with each tree hierarchy to be enumerated from an allocation of the N−

1 nodes among subtree hierarchies to be based, at least in part, upon a combination of the natural numerals to be associated with particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

26. The apparatus of claim 25, wherein the natural numeral to be associated with each tree hierarchy to be enumerated from an allocation of the N−

1 nodes is to be based, at least in part, upon a product of the natural numerals to be associated with the particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

27. The apparatus of claim 19, wherein the accessed tree hierarchy instructions further to enumerate the tree hierarchies configured from exactly N nodes.

28. 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 enumerate tree hierarchies; and

wherein tree hierarchy enumeration instructions further;

to enumerate tree hierarchies, a tree hierarchy to comprise one or more signal values, configured from a finite number (N) of nodes, wherein N comprises a natural numeral greater than one, wherein to enumerate tree hierarchies configured from the finite number of nodes further to;

identify N−

1 arrangements of subtree hierarchy slots to be coupled to a root node;

determine one or more allocations of N−

1 nodes among the subtree hierarchy slots in a to be identified arrangement of subtree hierarchy slots, a subtree hierarchy slot to be being allocated a portion of the N−

1 nodes; and

enumerate one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot;

to determine for the to be enumerated tree hierarchies natural numerals to be associated with particular ones of the to be enumerated tree hierarchies; and

to store, in a memory, the natural numerals.

29. The article of claim 28, the instructions being further executable by the one or more processors to:

associate the to be enumerated one or more subtree hierarchies for subtree hierarchy slot with a natural numeral; and

determine the natural numeral to be associated with a tree hierarchy to be enumerated from an allocation of the N−

1 nodes among subtree hierarchies to be based, at least in part, upon a combination of the natural numerals to be associated with particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

30. The article of claim 29, wherein the natural numeral to be associated with a tree hierarchy to be enumerated from an allocation of the N−

1 nodes is to be based, at least in part, upon a product of the natural numerals to be associated with the particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

31. The article of claim 28, the instructions being further executable by the one or more processors to:

identify each enumerated tree hierarchy as being a composite of subtree hierarchies to be according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes to be allocated among the composite of subtree hierarchies, each subtree hierarchy in the composite of subtree hierarchies have a particular configuration of nodes which are to be allocated to the subtree hierarchy and to be associated with a natural numeral based, at least in part, upon said association among the allocated nodes, and wherein the natural numeral to be associated with the tree hierarchy to comprise a combination of the natural numerals to be associated with the subtree hierarchies in the composite of subtree hierarchies.

32. The article of claim 28, the instructions being further executable by the one or more processors to:

identify an enumerated tree hierarchy as being a composite of subtree hierarchies to be according to one of the N−

1 arrangement of subtree hierarchy slots, N−

1 nodes to be allocated among the composite of subtree hierarchies, a subtree hierarchy in the composite of subtree hierarchies to be a particular configuration of nodes which are to be allocated to the subtree hierarchy and to be associated with a natural numeral, and wherein the natural numeral to be associated with the tree hierarchy to comprise a combination of the natural numerals to be associated with the subtree hierarchies in the composite of subtree hierarchies.

33. The article of claim 28, the instructions being further executable by the one or more processors to:

identify each of N−

1 arrangements of subtree hierarchy slots to be coupled to the root node;

determine one or more allocations of N−

1 nodes to be among the subtree hierarchy slots in the arrangement, each subtree hierarchy slot to be allocated a portion of the N−

1 nodes; and

enumerate one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot to comprise an enumeration of each of one or more subtree hierarchies configured from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

34. The article of claim 33, the instructions being further executable by the one or more processors to:

associate each of the to be enumerated one or more subtree hierarchies for each subtree hierarchy slot with a natural numeral; and

determine the natural numeral to be associated with each tree hierarchy to be enumerated from an allocation of the N−

1 nodes among subtree hierarchies to be based, at least in part, upon a combination of the natural numerals to be associated with particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

35. The article of claim 34, wherein the natural numeral to be associated with each tree hierarchy to be enumerated from an allocation of the N−

1 nodes is to be based, at least in part, upon a product of the natural numerals to be associated with the particular subtree hierarchies to be enumerated from the allocation of N−

1 nodes.

36. The article of claim 28, the instructions being further executable by the one or more processors to enumerate the tree hierarchies configured from exactly N nodes.