Enumeration of rooted partial subtrees

• US 9,330,128 B2
• Filed: 10/01/2012
• Issued: 05/03/2016
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Schiffmann, Karl, LeTourneau, Jack J., Andrews, Mark
• Primary Examiner(s): TRAN, ANHTAI V
• Application Number:
  US13/632,581
• Publication Number:
  US 20130151566A1
• Time in Patent Office: 1,310 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments of methods, apparatuses, devices and/or systems for manipulating hierarchical sets of data are disclosed. In particular, methods, apparatus devices and or/or systems for enumerating rooted partial subtrees are disclosed.

Claims

1. A method of executing instructions on at least one computing device in which the at least one computing device includes at least one processor and at least one memory, the method comprising:

executing the instructions on the at least one processor of the at least one computing device; and

wherein the instructions to be executed comprise instructions for enumeration;

wherein the executing the enumeration instructions comprises enumerating a set of component rooted partial subtrees for a graphical representation of a full hierarchical tree comprising a node labeled tree, wherein the set of component rooted partial subtrees comprises at least one component rooted partial subtree having a same root node as a second component rooted partial subtree;

wherein the executing the enumeration instructions further comprises;

determining one or more digital signals for natural numerals associated with the enumerated component rooted partial subtrees of the set, the one or more digital signals being based, at least in part, on an association between trees and numerals;

wherein at least one of the set of the enumerated component rooted partial subtrees comprises at least one of the following;

an empty tree, a single node tree, a tree comprising a single subtree connected to a root node by an edge or two or more trees connected to a root node by respective edges; and

further comprising storing one or more digital signals in the at least one memory of the at least one computing device any results of having executed the enumeration instructions on the at least one processor of the at least one computing device.

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

enumerating the set of the component rooted partial subtrees, wherein enumerating the set of the component rooted partial subtrees comprises;

identifying one or more subtrees coupled to a root node; and

enumerating a set of component rooted partial subtrees of the identified subtrees.

3. The method of claim 2, wherein the executing the enumeration instructions further comprises:

enumerating the set of the component rooted partial subtrees to merge combinations of individual ones of the enumerated component rooted partial subtrees of the identified subtrees.

4. The method of claim 2, wherein the executing the enumeration instructions further comprises:

representing the full tree as a composite natural numeral in the form of one or more digital signals based, at least in part, on the association, and identifying the one or more subtrees further in which the one or more digital signals comprise factors representative of subtrees.

5. The method of claim 4, wherein the executing the enumeration instructions further comprises:

enumerating a set of component rooted partial subtrees of the identified subtrees further comprising;

associating the one or more subtrees with one or more non-composite natural numerals in the form of one or more digital signals based, at least in part, on the association;

performing an inverse push operation on one or more digital signals for one or more child trees of the identified subtrees; and

enumerating one or more rooted partial subtrees of the one or more child trees.

6. The method of claim 5, wherein the executing the enumeration instructions further comprises:

enumerating the set of the component rooted partial subtrees of the identified subtrees further comprising;

performing a push operation on the one or more digital signals for the one or more child trees, and wherein the executing the fetched enumeration instructions further comprises;

determining natural numerals in the form of one or more digital signals associated with particular ones of the enumerated rooted partial subtrees further comprising;

the one or more digital signals for the one or more child trees.

7. The method of claim 5, wherein the executing the enumeration instructions further comprises:

determining natural numerals in the form of one or more digital signals associated with rooted partial subtrees of the child trees according to the association;

combining the one or more digital signals associated with the rooted partial subtrees of the child trees with a natural numeral in the form of one or more digital signals associated with a node based, at least in part, on the association to provide a combined set in the form of one or more digital signals; and

performing a push operation on elements of the one or more digital signals of the combined set.

8. The method of claim 1, wherein the executing the enumeration instructions further comprises:

enumerating the set of the component rooted partial subtrees further comprising;

performing an inverse push operation on a natural numeral in the form of one or more digital signals representative of the graphical representation of the full tree to provide one or more digital signals representative of a child tree; and

enumerating a set of component rooted partial subtrees of the child tree.

9. The method of claim 8, wherein the executing the enumeration instructions on further comprises:

coupling the root node of the full tree to the child tree, and wherein the executing the enumeration instructions further comprises;

enumerating the set of the component rooted partial subtrees of the child tree further comprising;

identifying one or more subtrees of the child tree, the one or more subtrees being coupled to a root node of the child tree; and

enumerating a set of component rooted partial subtrees of the identified subtrees of the child tree.

10. The method of claim 9, wherein the executing the enumeration instructions further comprises:

representing the child tree as a composite natural numeral in the form of one or more digital signals based, at least in part, on the association, and identifying the one or more subtrees further in which the one or more digital signals comprise factors representative of subtrees.

11. The method of claim 8, wherein the executing the enumeration instructions further comprises:

identifying the one or more digital signals for the graphical representation of the full tree as a non-composite numeral in the form of one or more digital signals.

12. The method of claim 8, wherein the executing the enumeration instructions further comprises:

representing the enumerated component rooted partial subtrees of the child tree as one or more natural numerals in the form of one or more digital signals based, at least in part, on the association; and

performing a push operation on the one or more digital signals for the enumerated component rooted partial subtrees of the child tree to provide at least some of the one or more digital signals of particular ones of the enumerated rooted partial subtrees.

13. The method of claim 12, wherein the executing the enumeration instructions further comprises:

combining the one or more digital signals for the enumerated component rooted partial subtrees of the child tree with a natural numeral in the form of one or more digital signals representative of a node based, at least in part, upon the association so as to provide a combined set; and

performing a push operation on one or more digital signals for the combined set so as to provide at least some of the one or more digital signals associated with the particular ones of the enumerated rooted partial subtrees.

14. The method of claim 1, wherein the graphical representation of the full hierarchical tree comprises a binary node labeled tree.

15. An apparatus comprising:

means for executing instructions comprising at least one processor;

wherein the instructions being executed comprise instructions for enumeration;

wherein the means for executing instructions comprises means for enumerating a set of component rooted partial subtrees for a graphical representation of a full hierarchical tree comprising a node labeled tree, wherein the set of component rooted partial subtrees comprises at least one component rooted partial subtree having a same root node as a second component rooted partial subtree;

wherein the means for executing instructions further comprises means for determining one or more digital signals for natural numerals associated with the enumerated component rooted partial subtrees of the set, the one or more digital signals being based, at least in part, on an association between trees and natural numerals;

wherein at least one of the set of the enumerated component rooted partial subtrees comprises at least one of the following;

an empty tree, a single node tree, a tree comprising a single subtree connected to a root node by an edge or two or more trees connected to a root node by respective edges; and

further comprising means for storing as one or more digital signals any results of having executed the enumeration instructions.

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

means for identifying one more subtrees coupled to a root node of the graphical representation of the full hierarchical tree; and

means for enumerating a set of component rooted partial subtrees of the identified subtrees.

17. The apparatus of claim 16, wherein the means for enumerating the set of the component rooted partial subtrees further comprises means for merging combinations of individual ones of the enumerated component rooted partial subtrees of the identified subtrees.

18. The apparatus of claim 16, wherein the full tree is to be represented as a composite natural numeral in the form of one or more digital signals based, at least in part, on the association, and wherein the means for identifying the one or more subtrees further comprises means for factoring the one or more digital signals.

19. The apparatus of claim 18, wherein, the means for enumerating the set of component rooted partial subtrees of the identified subtrees further comprises:

means for associating the one or more subtrees with one or more non-composite natural numerals in the form of one or more digital signals based, at least in part, on the association;

means for performing an inverse push operation on one or more digital signals for one or more child trees of the identified subtrees; and

means for enumerating a set of one or more rooted partial subtrees of the one or more child trees.

20. The apparatus of claim 19, wherein the means for enumerating the set of the component rooted partial subtrees of the identified subtrees further comprises means for performing a push operation on the one or more digital signals for the one or more subtree children, and wherein the means for determining the one or more digital signals associated with particular ones of the enumerated rooted partial subtrees further comprises means for determining the one or more digital signals for the one or more subtree children.

21. The apparatus of claim 19, the apparatus further comprising:

means for determining natural numerals in the form of one or more digital signals associated with rooted partial subtrees of the child trees according to the association;

means for combining the one or more digital signals associated with the rooted partial subtrees of the child trees with a natural numeral in the form of one or more digital signals associated with a node based, at least in part, on the association to provide a combined set; and

means for performing a push operation on elements of one or more digital signals of the combined set.

22. The apparatus of claim 15, wherein the means for enumerating the set of the component rooted partial subtrees of the full tree further comprises:

means for performing an inverse push operation on one or more digital signals representative of the graphical representation of the full hierarchical tree to provide one or more digital signals representative of a child tree; and

means for enumerating a set of component rooted partial subtrees of the child tree.

23. The apparatus of claim 22, wherein the child tree is coupled to the root node of the graphical representation of the full hierarchical tree, and wherein the means for enumerating the set of the component rooted partial subtrees of the child tree further comprises:

means for identifying one or more subtrees of the child tree, the one or more subtrees being coupled to the root node of the child tree; and

means for enumerating a set of component rooted partial subtrees of the identified subtrees.

24. The apparatus of claim 23, wherein the child tree is represented as a composite natural numeral in the form of one or more digital signals based, at least in part, on the association, and wherein the means for identifying one or more subtrees of the child tree further comprises means for factoring the one or more digital signals.

25. The apparatus of claim 22, the apparatus further comprising means for identifying the one or more digital signals for the graphical representation of the full hierarchical tree as a non-composite numeral in the form of one or more digital signals.

26. The apparatus of claim 22, the apparatus further comprising:

means for representing the enumerated component rooted partial subtrees of the child tree as one or more natural numerals in the form of one or more digital signals based, at least in part, on the association; and

means for performing a push operation on the one or more digital signals for the enumerated component rooted partial subtrees of the child tree to provide at least some of the one or more digital signals for the natural numerals associated with particular ones of the enumerated rooted partial subtrees.

27. The apparatus of claim 26, the apparatus further comprising:

means for combining the one or more digital signals for the enumerated component rooted partial subtrees of the child tree with a natural numeral in the form of one or more digital signals representative of a node based upon the association to provide a combined set of natural numerals in the form of one or more digital signals; and

means for performing a push operation on the one or more digital signals for the combined set.

28. The apparatus of claim 15, wherein the graphical representation of the full hierarchical tree comprises a binary node labeled tree.

29. An apparatus comprising:

at least one computing device including at least one processor and at least one memory, the at least one computing device to execute instructions on the at least one processor;

the instructions to be executed comprising instructions for enumeration;

wherein execution of the enumeration instructions to comprise instructions to enumerate, via the at least one processor, a set of component rooted partial subtrees for a graphical representation of a full hierarchical tree to comprise a node labeled tree, wherein the set of component rooted partial subtrees to comprise at least one component rooted partial subtree to have a same root node as a second component rooted partial subtree;

wherein the enumeration instructions to comprise instructions to determine, via the at least one processor, one or more digital signals for natural numerals to be associated with particular ones of the set of the to be enumerated component rooted partial subtrees, the one or more digital signals to be based, at least in part, on an association between trees and natural numerals;

wherein at least one of the set of the enumerated component rooted partial subtrees to comprise at least one of the following;

an empty tree, a single node tree, a tree comprising a single subtree connected to a root node by an edge or two or more trees connected to a root node by respective edges; and

further comprising instructions to be executed to store in the at least one memory of the at least one computing device any results to be generated from the execution on the at least one processor of the to be executed enumeration instructions.

30. The apparatus of claim 29, wherein the instructions further comprise instructions executable to:

identify one more subtrees to be coupled to a root node of the graphical representation of the full hierarchical tree; and

enumerate a set of component rooted partial subtrees of the to be identified subtrees.

31. The apparatus of claim 30, wherein the instructions further comprise instructions executable to merge combinations of individual ones of the to be enumerated component rooted partial subtrees of the to be identified subtrees.

32. The apparatus of claim 30, wherein the graphical representation of the full tree is to be represented as a composite natural numeral to be in the form of one or more digital signals and to be based, at least in part, on the association, and wherein the instructions executable to identify the one or more subtrees in which the one or more digital signals to comprise factors to be representative of subtrees.

33. The apparatus of claim 32, wherein the instructions further comprise instructions executable to:

associate the one or more subtrees with one or more non-composite natural numerals to be in the form of one or more digital signals and to be based, at least in part, on the association;

perform an inverse push operation on one or more digital signals for one or more child trees of the to be identified one or more subtrees; and

enumerate a set of one or more rooted partial subtrees of the one or more child trees.

34. The apparatus of claim 33, wherein the instructions further comprise instructions executable to:

perform a push operation on the one or more digital signals for the one or more child trees; and

determine the one or more digital signals to be associated with the particular ones of the to be enumerated component rooted partial subtrees to be based, at least in part, upon the push operation.

35. The apparatus of claim 33, wherein the instructions further comprise instructions executable to:

determine natural numerals to be in the form of one or more digital signals and to be associated with rooted partial subtrees of the child trees according to the association;

combine the one or more digital signals to be associated with the rooted partial subtrees of the child trees with a natural numeral to be in the form of one or more digital signals and to be associated with a node to be based, at least in part, on the association to provide a combined set; and

perform a push operation on elements of one or more digital signals of the combined set.

36. The apparatus of claim 29, wherein the instructions further comprise instructions executable to:

perform an inverse push operation on one or more digital signals to be representative of the graphical representation of the full tree to provide one or more digital signals to be representative of a child tree; and

enumerate a set of component rooted partial subtrees of the child tree.

37. The apparatus of claim 36, wherein the child tree is to be coupled to a root node of the full tree, and wherein the instructions further comprise instructions executable to:

identify one or more subtrees of the child tree, the one or more subtrees to be coupled to a root node of the child tree; and

enumerate a set of component rooted partial subtrees of the to be identified subtrees.

38. The apparatus of claim 37, wherein the child tree is to be represented as a composite natural numeral to be based, at least in part, on the association, and wherein the instructions further comprise instructions executable to identify the one or more subtrees in which the one or more digital signals to comprise factors to be representative of the subtrees.

39. The apparatus of claim 36, wherein the instructions further comprise instructions executable to identify the one or more digital signals for the graphical representation of the full tree as a non-composite numeral to be in the form of one or more digital signals.

40. The apparatus of claim 36, wherein the instructions further comprise instructions executable to:

represent the to be enumerated component rooted partial subtrees of the child tree as one or more natural numerals to be in the form of one or more digital signals and to be based, at least in part, on the association; and

perform a push operation on the one or more digital signals for the to be enumerated component rooted partial subtrees of the child tree to provide at least some of the one or more digital signals for the natural numerals to be associated with the particular ones of the to be enumerated rooted partial subtrees.

41. The apparatus of claim 40, wherein the instructions further comprise instructions executable to:

combine the one or more digital signals for the to be enumerated component rooted partial subtrees of the child tree with a natural numeral to be in the form of one or more digital signals and to be representative of a node to be based at least in part upon the association to provide a combined set of natural numerals to be in the form of one or more digital signals; and

perform a push operation on the one or more digital signals for the combined set.

42. The apparatus of claim 29, wherein the full tree is to comprise a binary node labeled tree.

43. An article comprising:

a non-transitory storage medium comprising machine-readable instructions stored thereon executable by at least one computing device, the at least one computing device comprising at least one processor and at least one memory, to;

execute instructions on the at least one processor;

the instructions to be executed to comprise instructions for enumeration;

wherein execution of the enumeration instructions to comprise execution of instructions to enumerate a set of component rooted partial subtrees of a graphical representation of a full hierarchical tree to comprise a node labeled tree, wherein the set of component rooted partial subtrees to comprise at least one component rooted partial subtree to have a same root node as a second component rooted partial subtree;

wherein the enumeration instructions to comprise instructions to determine one or more digital signals for natural numerals to be associated with particular ones of the set of the to be enumerated rooted partial subtrees, the one or more digital signals to be based, at least in part, on an association between trees and natural numerals; and

wherein the instructions to be executed further to comprise instructions to store in the at least one memory of the at least one computing device any results to be generated from the execution on the at least one processor of the to be executed enumeration instructions.

44. The article of claim 43, wherein the storage medium further comprises machine-readable instructions stored thereon to:

identify one more subtrees to be coupled to a root node of the full tree; and

enumerate a set of component rooted partial subtrees of the to be identified subtrees.

45. The article of claim 44, wherein the storage medium further comprises machine-readable instructions stored thereon to merge combinations of individual ones of the to be enumerated component rooted partial subtrees of the to be identified subtrees.

46. The article of claim 44, wherein the graphical representation of the full tree is to be represented as a composite natural numeral to be in the form of one or more digital signals and to be based, at least in part, on the association, and wherein the storage medium further comprises machine-readable instructions stored thereon to identify the one or more subtrees further in which the one or more digital signals to comprise factors to be representative of subtrees.

47. The article of claim 46, wherein the storage medium further comprises machine-readable instructions stored thereon to:

associate the one or more subtrees with one or more non-composite natural numerals to be in the form of one or more digital signals and to be based, at least in part, on the association;

perform an inverse push operation on one or more digital signals for one or more child trees of the to be identified subtrees; and

enumerate a set of one or more rooted partial subtrees of the one or more child trees.

48. The article of claim 47, wherein the storage medium further comprises machine-readable instructions stored thereon to:

perform a push operation on the one or more digital signals for the one or more child trees; and

determine the one or more digital signals to be associated with the particular ones of the to be enumerated rooted partial subtrees to be based, at least in part, upon the push operation.

49. The article of claim 47, wherein the storage medium further comprises machine-readable instructions stored thereon to:

determine natural numerals to be in the form of one or more digital signals and to be associated with rooted partial subtrees of the child trees according to the association;

combine the one or more digital signals to be associated with the rooted partial subtrees of the child trees with a natural numeral to be in the form of one or more digital signals and to be representative of a node to be based, at least in part, on the association to provide a combined set; and

perform a push operation on elements of one or more digital signals of the combined set.

50. The article of claim 43, wherein the storage medium further comprises machine-readable instructions stored thereon to:

perform an inverse push operation on one or more digital signals to be representative of the graphical representation of the full tree to provide one or more digital signals and to be representative of a child tree; and

enumerate a set of component rooted partial subtrees of the child tree.

51. The article of claim 50, wherein the child tree to comprises a root node to be coupled to the root node of the full tree, and wherein the storage medium further comprises machine-readable instructions stored thereon to:

identify one or more subtrees of the child tree, the one or more subtrees to be coupled to the root node of the child tree; and

enumerate a set of component rooted partial subtrees of the to be identified subtrees.

52. The article of claim 51, wherein the child tree is to be represented as a composite natural numeral to be in the form of one or more digital signals and to be based, at least in part, on the association, and wherein the storage medium further comprises machine-readable instructions stored thereon to identify the one or more subtrees in which the one or more digital signals to comprise factors to be representative of the subtrees.

53. The article of claim 50, wherein the storage medium further comprises machine-readable instructions stored thereon to identify the one or more digital signals for the graphical representation of the full tree as a non-composite numeral in the form of one or more digital signals.

54. The article of claim 50, wherein the storage medium further comprises machine-readable instructions stored thereon to:

represent the to be enumerated component rooted partial subtrees of the child tree as one or more natural numerals to be in the form of one or more digital signals and to be based, at least in part, on the association; and

perform a push operation on the one or more digital signals for the to be enumerated component rooted partial subtrees of the child tree to provide at least some of the one or more digital signals for the natural numerals to be associated with the particular ones of the to be enumerated rooted partial subtrees.

55. The article of claim 54, wherein the storage medium further comprises machine-readable instructions stored thereon to:

combine the one or more digital signals for the to be enumerated component rooted partial subtrees of the child tree with a natural numeral to be in the form of one or more digital signals and to be representative of a node to be based upon the association to provide a combined set of natural numerals to be in the form of one or more digital signals; and

perform a push operation on the one or more digital signals for the combined set.

56. The article of claim 43, wherein the full tree to comprise a binary node labeled tree.