Enumeration of trees from finite number of nodes

• US 9,411,841 B2
• Filed: 02/18/2015
• Issued: 08/09/2016
• 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:
  US14/625,473
• Publication Number:
  US 20150242449A1
• Time in Patent Office: 538 Days
• Field of Search: 707/755
• US Class Current: 1/1
• 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 possible complex two-dimensional graphical hierarchies for more convenience processing and/or storage, a complex two-dimensional graphical hierarchy being in the form of a tree hierarchy, the method comprising:

enumerating possible tree hierarchies, in which a tree hierarchy comprises one or more signal values, configurable from a finite number (N) of nodes;

determining for the enumerated tree hierarchies natural numerals associated with particular ones of the enumerated tree hierarchies, the natural numerals being based, at least in part, on a predetermined association between the tree hierarchies and the natural numerals; and

storing, in a memory, the natural numerals, a natural numeral comprising one or more signal values,

wherein the natural numeral comprises a product of two or more component natural numerals,

the product of two or more component natural numerals comprising a subtree hierarchy among subtree hierarchies which are merged at a root node to form the associated enumerated tree hierarchy.

2. The method of claim 1, the method further comprising:

identifying N−

1 arrangements of subtree hierarchy slots coupled to the 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 possible subtree hierarchies configurable from the portion of the N−

1 nodes allocated to the subtree hierarchy slot.

3. The method of claim 2, the method further comprising:

associating the enumerated one or more possible subtree hierarchies for a subtree hierarchy slot with a natural numeral, the natural numeral being based, at least in part, on the association; 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.

4. The method of claim 3, 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.

5. The method of claim 2, wherein the method 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.

6. The method of claim 2, wherein the method 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 based, at least in part, upon the association, and wherein the natural numeral associated with the tree hierarchy comprises a combination of the natural numerals associated with the subtrccs subtree hierarchies in the composite of subtree hierarchies.

7. The method of claim 2, 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 possible subtree hierarchies configurable from the portion of the N−

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

1 nodes allocated to the subtree hierarchy slot.

8. The method of claim 7, the method further comprising:

associating each of the enumerated one or more possible subtree hierarchies for each subtree hierarchy slot with a natural numeral, the natural numeral being based, at least in part, on the association; 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.

9. The method of claim 8, 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.

10. The method of claim 1, wherein the enumerating possible configurable tree hierarchies comprises enumerating the possible tree hierarchies configurable from exactly N nodes.

11. 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 enumerating possible tree hierarchies, a tree hierarchy to comprise one or more signal values, configurable from a finite number (N) of nodes;

means for determining, for the enumerated tree hierarchies, natural numerals associated with particular ones of the enumerated tree hierarchies, the natural numerals being based, at least in part, on a predetermined association between the tree hierarchies and the natural numerals; and

means for storing, in a memory, the natural numerals, a natural numeral to comprise one or more signal values,

wherein the natural numeral comprises a product of two or more component natural numerals,

the product of two or more component natural numerals comprising a subtree hierarchy among subtree hierarchies which are merged at a root node to form the associated enumerated tree hierarchy.

12. The apparatus of claim 11, the apparatus further comprising:

means for identifying N−

1 arrangements of subtree hierarchy slots coupled to the 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 possible subtree hierarchies, configurable from the portion of the N−

1 nodes allocated to the subtree hierarchy slot.

13. The apparatus of claim 12, the apparatus further comprising:

means for associating the enumerated one or more possible subtree hierarchies for a subtree hierarchy slot with a natural numeral, the natural numeral being based, at least in part, on the association; 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.

14. The apparatus of claim 13, 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.

15. The apparatus of claim 12, the apparatus further comprising:

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.

16. The apparatus of claim 12, the apparatus further comprising:

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 based, at least in part, upon the association, 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.

17. The apparatus of claim 12, the apparatus further comprising:

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;

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

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

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

1 nodes allocated to the subtree hierarchy slot.

18. The apparatus of claim 17, the apparatus further comprising:

means for associating each of the enumerated one or more possible subtree hierarchies for each subtree hierarchy slot with a natural numeral, the natural numeral being based, at least in part, on the association; 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.

19. The apparatus of claim 18, 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.

20. The apparatus of claim 11, the means for enumerating possible configurable tree hierarchies comprises means for enumerating the possible tree hierarchies configurable from exactly N nodes.

21. An apparatus comprising a computing device, the computing device to:

enumerate possible tree hierarchies, a tree hierarchy to comprise one or more signal values, configurable from a finite number (N) of nodes;

determine for the to be enumerated tree hierarchies natural numerals to be associated with particular ones of the to be enumerated tree hierarchies, the natural numerals to be based, at least in part, on a predetermined association between tree hierarchies and natural numerals; and

store, in the memory, the natural numerals, a natural numeral to comprise one or more signal values,

wherein the natural numeral to comprise a product of two or more component natural numerals,

the product of two or more component natural numerals to comprise a subtree hierarchy among subtree hierarchies which are merged at a root node to form the associated enumerated tree hierarchy.

22. The apparatus of claim 21, the computing device is further to:

identify N−

1 arrangements of subtree hierarchy slots to be coupled to the 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 possible subtree hierarchies configurable from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

23. The apparatus of claim 22, wherein the computing device is further to:

associate the to be enumerated one or more possible subtree hierarchies for a subtree hierarchy slot with a natural numeral, the to be natural numeral being based, at least in part, on the association; 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.

24. The apparatus of claim 23, 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.

25. The apparatus of claim 22, wherein the computing device is 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.

26. The apparatus of claim 22, wherein the computing device is 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 to be based, at least in part, upon the association, 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.

27. The apparatus of claim 22, wherein the computing device is further adapted 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 possible subtree hierarchies configurable 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 possible subtree hierarchies configurable from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

28. The apparatus of claim 27, wherein the computing device is further to:

associate each of the to be enumerated one or more possible subtree hierarchies for each subtree hierarchy slot with a natural numeral, the natural numeral to be based, at least in part, on the association; 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.

29. The apparatus of claim 28, 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.

30. The apparatus of claim 21, wherein the computing device is further to enumerate the possible tree hierarchies configurable from exactly N nodes.

31. An article comprising:

a non-transitory storage medium comprising instructions stored thereon, the instructions being executable by one or more processors of one or more computing devices to;

enumerate possible tree hierarchies, a tree hierarchy to comprise one or more signal values, configurable from a finite number (N) of nodes;

determine for the to be enumerated tree hierarchies natural numerals to be associated with particular ones of the to be enumerated tree hierarchies, the natural numerals to be based, at least in part, on a predetermined association between tree hierarchies and natural numerals; and

store, in the memory, the natural numerals, a natural numeral to comprise one or more signal values

wherein the natural numeral to comprise a product of two or more component natural numerals,

the product of two or more component natural numerals to comprise a subtree hierarchy among subtree hierarchies which are merged at a root node to form the associated enumerated tree hierarchy.

32. The article of claim 31, the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices to:

identify N−

1 arrangements of subtree hierarchy slots to be coupled to the 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 possible subtree hierarchies configurable from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

33. The article of claim 32, the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices to:

associate the to be enumerated one or more possible subtree hierarchies for subtree hierarchy slot with a natural numeral, the natural numeral to be based, at least in part, on the association; 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.

34. The article of claim 33, 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.

35. The article of claim 32, wherein the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices 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 to be based, at least in part, upon the association among the to be 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.

36. The article of claim 32, wherein the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices 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 to be based, at least in part, upon the association, 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.

37. The article of claim 32, wherein the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices 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 possible subtree hierarchies configurable 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 possible subtree hierarchies configurable from the portion of the N−

1 nodes to be allocated to the subtree hierarchy slot.

38. The article of claim 37, wherein the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices to:

associate each of the to be enumerated one or more possible subtree hierarchies for each subtree hierarchy slot with a natural numeral, the natural numeral being to be based, at least in part, on the association; 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.

39. The article of claim 38, 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.

40. The article of claim 31, wherein the non-transitory storage medium further to comprise instructions stored thereon, the instructions being executable by the one or more processors of the one or more computing devices to enumerate the possible tree hierarchies configurable from exactly N nodes.