ENUMERATION OF ROOTED PARTIAL SUBTREES

• US 20130151566A1
• Filed: 10/01/2012
• Published: 06/13/2013
• Est. Priority Date: 12/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, LeTourneau, Jack J., Andrews, Mark
• Granted Patent: US 9,330,128 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• 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 comprising:

enumerating possible component rooted partial subtrees of a tree; and

determining natural numerals associated with particular ones of said enumerated rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals.

2. The method of claim 1, wherein said enumerating possible component rooted partial subtrees of said tree further comprises:

identifying one more subtrees coupled to a root node of said tree; and

enumerating possible component rooted partial subtrees of said identified subtrees.

3. The method of claim 2, wherein said enumerating possible component rooted partial subtrees of said tree further comprises merging combinations of individual ones of said enumerated possible component rooted partial subtrees of said identified subtrees.

4. The method of claim 2, wherein said tree is represented as a composite natural numeral based, at least in part, on said association, and wherein identifying said one or more subtrees further comprises factoring said composite natural numeral into natural numerals representative of subtrees.

5. The method of claim 4, wherein said enumerating possible component rooted partial subtrees of said identified subtrees further comprises:

associating said one or more subtrees with one or more non-composite natural numerals based, at least in part, on said association;

performing an inverse push operation on the non-composite natural numerals to provide one or more natural numerals representative of one or more child trees of said identified subtrees; and

enumerating one or more rooted partial subtrees of said one or more child trees based, at least in part, on said one or more natural numerals representative of said child trees.

6. The method of claim 5, wherein said enumerating possible component rooted partial subtrees of said identified subtrees further comprises performing a push operation on said one or more natural numerals representative of said one or more enumerated rooted partial subtrees of said one or more child trees, and wherein said determining natural numerals associated with particular ones of said enumerated rooted partial subtrees further comprises determining said natural numerals based, at least in part, upon said push operation.

7. The method of claim 5, and further comprising:

determining natural numerals associated with rooted partial subtrees of said child trees according to said association;

combining said natural numerals representative of said rooted partial subtrees of said child trees with a natural numeral associated with a node based, at least in part, on said association to provide a combined set of natural numerals; and

performing a push operation on elements of said combined set of natural numerals to provide natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

8. The method of claim 1, wherein said enumerating possible component rooted partial subtrees of said tree further comprises:

performing an inverse push operation on a natural numeral representative of said tree to provide a natural numeral representative of a child tree; and

enumerating possible component rooted partial subtrees of said child tree.

9. The method of claim 8, wherein said child tree is coupled to a root node of said tree, and wherein enumerating possible component rooted partial subtrees of said child tree further comprises:

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

enumerating possible component rooted partial subtrees of said identified subtrees of said child tree.

10. The method of claim 9, wherein said child tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said identifying one or more subtrees of said child tree further comprises factoring said composite natural numeral into natural numerals representative of said subtrees.

11. The method of claim 8, and further comprising identifying said natural numeral representative of said tree as a non-composite numeral.

12. The method of claim 8, and further comprising:

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

performing a push operation on said one or more natural numbers representing said enumerated possible component rooted partial subtrees of said child tree to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

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

combining said natural numerals representing said enumerated possible component rooted partial subtrees of said child tree with a natural numeral representative of a node based, at least in part, upon said association to provide a combined set of natural numerals; and

performing a push operation on said one or more natural numeral elements of said combined set to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

14. The method of claim 1, wherein said tree comprises a binary edge labeled tree.

15. An apparatus comprising:

means for enumerating possible component rooted partial subtrees of a tree; and

means for determining natural numerals associated with particular ones of said enumerated rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals.

16. The apparatus of claim 15, wherein the apparatus further comprises:

means for identifying one more subtrees coupled to a root node of said tree; and

means for enumerating possible component rooted partial subtrees of said identified subtrees.

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

18. The apparatus of claim 16, wherein said tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said means for identifying said one or more subtrees further comprises means for factoring said composite natural numeral into natural numerals representative of subtrees.

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

means for associating said one or more subtrees with one or more non-composite natural numerals based, at least in part, on said association;

means for performing an inverse push operation on said non-composite natural numerals to provide one or more natural numerals representative of one or more child trees of said identified subtrees; and

means for enumerating one or more rooted partial subtrees of said one or more child trees based, at least in part, on said one or more natural numerals representative of said child trees.

20. The apparatus of claim 19, wherein said means for enumerating possible component rooted partial subtrees of said identified subtrees further comprises means for performing a push operation on said one or more natural numerals representative of said one or more enumerated rooted partial subtrees of said one or more subtree children, and wherein said means for determining said natural numerals associated with particular ones of said enumerated rooted partial subtrees further comprises means for determining said natural numerals based, at least in part, upon said push operation.

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

means for determining natural numerals associated with rooted partial subtrees of said child trees according to said association;

means for combining said natural numerals representative of said rooted partial subtrees of said child trees with a natural numeral associated with a node based, at least in part, on said association to provide a combined set of natural numerals; and

means for performing a push operation on elements of said combined set of natural numerals to provide natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

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

means for performing an inverse push operation on a natural numeral representative of said tree to provide a natural numeral representative of a child tree; and

means for enumerating possible component rooted partial subtrees of said child tree.

23. The apparatus of claim 22, wherein said child tree is coupled to a root node of said tree, and wherein said means for enumerating possible component rooted partial subtrees of said child tree further comprises:

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

means for enumerating possible component rooted partial subtrees of said identified subtrees.

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

25. The apparatus of claim 22, said apparatus further comprising means for identifying said natural numeral representative of said tree as a non-composite numeral.

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

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

means for performing a push operation on said one or more natural numbers representing said enumerated possible component rooted partial subtrees of said child tree to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

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

means for combining said natural numerals representing said enumerated possible component rooted partial subtrees of said child tree with a natural numeral representative of a node based upon said association to provide a combined set of natural numerals; and

means for performing a push operation on said one or more natural numeral elements of said combined set to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

28. The apparatus of claim 15, wherein said tree comprises a binary edge labeled tree.

29. An apparatus comprising a computing platform, said computing platform being adapted to:

enumerate possible component rooted partial subtrees of a tree; and

determine natural numerals associated with particular ones of said enumerated rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals.

30. The apparatus of claim 29, wherein said computing platform is further adapted to:

identify one more subtrees coupled to a root node of said tree; and

enumerate possible component rooted partial subtrees of said identified subtrees.

31. The apparatus of claim 30, wherein computing platform is further adapted to merge combinations of individual ones of said enumerated possible component rooted partial subtrees of said identified subtrees.

32. The apparatus of claim 30, wherein said tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said computing platform is further adapted to identify said one or more subtrees by factoring said composite natural numeral into natural numerals representative of subtrees.

33. The apparatus of claim 32, wherein said computing platform is further adapted to:

associate said one or more subtrees with one or more non-composite natural numerals based, at least in part, on said association;

perform an inverse push operation on said non-composite natural numerals to provide one or more natural numerals representative of one or more child trees of said identified subtrees; and

enumerate one or more rooted partial subtrees of said one or more child trees based, at least in part, on said one or more natural numerals representative of said child trees.

34. The apparatus of claim 33, wherein said computing platform is further adapted to:

perform a push operation on said one or more natural numerals representative of said one or more enumerated rooted partial subtrees of said one or more child trees; and

determine said natural numerals associated with said particular ones of said enumerated rooted partial subtrees based, at least in part, upon said push operation.

35. The apparatus of claim 33, wherein said computing platform is further adapted to:

determine natural numerals associated with rooted partial subtrees of said child trees according to said association;

combine said natural numerals associated with said rooted partial subtrees of said child trees with a natural numeral associated with a node based, at least in part, on said association to provide a combined set of natural numerals; and

,

perform a push operation on elements of said combined set of natural numerals to provide natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

36. The apparatus of claim 29, wherein said computing platform is further adapted to:

perform an inverse push operation on a natural numeral representative of said tree to provide a natural numeral representative of a child tree; and

enumerate possible component rooted partial subtrees of said child tree.

37. The apparatus of claim 36, wherein said child tree is coupled to a root node of said tree, and wherein said computing platform is further adapted to:

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

enumerate possible component rooted partial subtrees of said identified subtrees.

38. The apparatus of claim 37, wherein said child tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said computing platform is further adapted to identify one or more subtrees of said child tree by factoring said composite natural numeral into natural numerals representative of said subtrees.

39. The apparatus of claim 36, wherein said computing platform is further adapted to identify said natural numeral representative of said tree as a non-composite numeral.

40. The apparatus of claim 36, wherein said computing platform is further adapted to:

represent said enumerated possible component rooted partial subtrees of said child tree as one or more natural numerals based, at least in part, on said association; and

perform a push operation on said one or more natural numbers representing said enumerated possible component rooted partial subtrees of said child tree to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

41. The apparatus of claim 40, wherein said computing platform is further adapted to:

combine said natural numerals representing said enumerated possible component rooted partial subtrees of said child tree with a natural numeral representative of a node based upon said association to provide a combined set of natural numerals; and

perform a push operation on said one or more natural numeral elements of said combined set to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

42. The apparatus of claim 29, wherein said tree comprises a binary edge labeled tree.

43. An article comprising:

a storage medium comprising machine-readable instructions stored thereon to;

enumerate possible component rooted partial subtrees of a tree; and

determine natural numerals associated with particular ones of said enumerated rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals.

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

identify one more subtrees coupled to a root node of said tree; and

enumerate possible component rooted partial subtrees of said identified subtrees.

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

46. The article of claim 44, wherein said tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said storage medium further comprises machine-readable instructions stored thereon to identify said one or more subtrees by factoring said composite natural numeral into natural numerals representative of subtrees.

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

associate said one or more subtrees with one or more non-composite natural numerals based, at least in part, on said association;

perform an inverse push operation on said non-composite natural numerals to provide one or more natural numerals representative of one or more child trees of said identified subtrees; and

enumerate one or more rooted partial subtrees of said one or more child trees based, at least in part, on said one or more natural numerals representative of said child trees.

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

perform a push operation on said one or more natural numerals representative of said one or more enumerated rooted partial subtrees of said one or more child trees; and

determine said natural numerals associated with said particular ones of said enumerated rooted partial subtrees based, at least in part, upon said push operation.

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

determine natural numerals associated with rooted partial subtrees of said child trees according to said association;

combine said natural numerals associated with said rooted partial subtrees of said child trees with a natural numeral representative of a node based, at least in part, on said association to provide a combined set of natural numerals; and

perform a push operation on elements of said combined set of natural numerals to provide natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

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

perform an inverse push operation on a natural numeral representative of said tree to provide a natural numeral representative of a child tree; and

enumerate possible component rooted partial subtrees of said child tree.

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

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

enumerate possible component rooted partial subtrees of said identified subtrees.

52. The article of claim 51, wherein said child tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said storage medium further comprises machine-readable instructions stored thereon to identify one or more subtrees of said child tree by factoring said composite natural numeral into natural numerals representative of said subtrees.

53. The article of claim 50, wherein said storage medium further comprises machine-readable instructions stored thereon to identify said natural numeral representative of said tree as a non-composite numeral.

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

represent said enumerated possible component rooted partial subtrees of said child tree as one or more natural numerals based, at least in part, on said association; and

perform a push operation on said one or more natural numbers representing said enumerated possible component rooted partial subtrees of said child tree to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

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

combine said natural numerals representing said enumerated possible component rooted partial subtrees of said child tree with a natural numeral representative of a node based upon said association to provide a combined set of natural numerals; and

perform a push operation on said one or more natural numeral elements of said combined set to provide at least some of said natural numbers associated with said particular ones of said enumerated rooted partial subtrees.

56. The article of claim 43, wherein said tree comprises a binary edge labeled tree.