Enumeration of rooted partial subtrees

• US 8,316,059 B1
• Filed: 12/27/2005
• Issued: 11/20/2012
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Schiffmann, Karl, LeTourneau, Jack J., Andrews, Mark
• Primary Examiner(s): Le, Debbie
• Assistant Examiner(s): TRAN, ANHTAI V
• Application Number:
  US11/319,758
• Time in Patent Office: 2,520 Days
• Field of Search: None
• 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:

executing instructions by a processor to;

exhaustively enumerate possible component rooted partial subtrees of a tree to model logical branches of a query, said component rooted partial subtrees defining respective connectable paths between a root node of the tree and nodes in respective component rooted partial subtrees along one or more edges in the tree; and

determine one or more electrical digital signals representing natural numerals associated with particular ones of said enumerated component rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals;

further comprising executing said instructions by said processor to exhaustively enumerate said possible component rooted partial subtrees of said tree by;

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

exhaustively enumerating possible component rooted partial subtrees of the identified subtrees;

wherein said tree is represented as one or more electrical digital signals representing a composite natural numeral based, at least in part, on said association, and wherein the method further comprises executing said instructions by said processor to identify said one or more subtrees by factoring said composite natural numeral into one or more electrical digital signals representing natural numerals representative of subtrees;

wherein said tree comprises an edge or node labeled tree, and wherein the labels comprise discrete values.

2. The method of claim 1, and further comprising executing said instructions by said processor to exhaustively enumerate said possible component rooted partial subtrees of said tree by merging one or more electrical digital signals representing combinations of individual ones of said enumerated possible component rooted partial subtrees of said identified subtrees.

3. The method of claim 1, and further comprising executing said instructions by said processor to exhaustively enumerate said possible component rooted partial subtrees of said identified subtrees by:

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

performing an inverse push operation on one or more signals representing the non-composite natural numerals to provide one or more electrical digital signals representing 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 signals representing said one or more natural numerals representative of said child trees.

4. The method of claim 1, and further comprising executing said instructions by said processor to exhaustively enumerate said possible component rooted partial subtrees of said tree by:

performing an inverse push operation on one or more electrical digital signals representing a natural numeral representative of said tree to provide one or more electrical digital signals representing a natural numeral representative of a child tree; and

enumerating possible component rooted partial subtrees of said child tree.

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

6. The method of claim 3, and further comprising executing said instructions by said processor to:

exhaustively enumerate said possible component rooted partial subtrees of said identified subtrees by performing a push operation on said one or more signals representing 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 one or more signals representing said natural numerals associated with particular ones of said enumerated rooted partial subtrees by determining said one or more signals representing said natural numerals based, at least in part, upon said push operation.

7. The method of claim 3, and further comprising executing said instructions by said processor to:

determine one or more electrical digital signals representing natural numerals associated with rooted partial subtrees of said child trees according to said association;

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

perform a push operation on one or more electrical digital signals representing of elements of said combined set of natural numerals to provide one or more electrical digital signals representing natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

8. The method of claim 4, wherein said child tree is coupled to a root node of said tree, and further comprising further executing said instructions by said processor to exhaustively enumerate said possible component rooted partial subtrees of said child tree by:

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.

9. The method of claim 4, and further comprising executing said instructions by said processor to identify said natural numeral representative of said tree as a non-composite numeral.

10. The method of claim 4, and further comprising executing said instructions by said processor to:

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

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

11. The method of claim 8, wherein said child tree is represented as one or more electrical digital signals representing a composite natural numeral based, at least in part, on said association, and wherein said method further comprises further executing said instructions by said processor to identify one or more subtrees of said child tree by factoring said one or more signals representing said composite natural numeral into electrical digital signals representing natural numerals representative of said subtrees.

12. The method of claim 10, the method further comprising executing said instructions by said processor to:

combine said one or more signals representing said natural numerals representing said exhaustively 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

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

13. An apparatus comprising:

means, comprising an electronic computing device, for exhaustively enumerating possible component rooted partial subtrees of a tree to model logical branches of a query, said component rooted partial subtrees defining respective connectable paths between a root node of the tree and nodes in respective component rooted partial subtrees along one or more edges in the tree;

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

means, comprising said electronic computing device, for identifying one more subtrees coupled to a root node of said tree; and

means, comprising said electronic computing device, for exhaustively enumerating possible component rooted partial subtrees of said identified subtrees;

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;

wherein said tree comprises an edge or node labeled tree, and wherein the labels comprise discrete values.

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

15. The apparatus of claim 13, wherein said means for exhaustively 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.

16. The apparatus of claim 13, wherein said means for exhaustively 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 exhaustively enumerating possible component rooted partial subtrees of said child tree.

17. The apparatus of claim 13, wherein said tree comprises a binary edge labeled tree.

18. The apparatus of claim 15, wherein said means for exhaustively 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.

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

means, comprising said electronic computing device, for determining natural numerals associated with rooted partial subtrees of said child trees according to said association;

means, comprising said electronic computing device, 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, comprising said electronic computing device, 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.

20. The apparatus of claim 16, wherein said child tree is coupled to a root node of said tree, and wherein said means for exhaustively 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 exhaustively enumerating possible component rooted partial subtrees of said identified subtrees.

21. The apparatus of claim 16, said apparatus further comprising means, comprising said electronic computing device, for identifying said natural numeral representative of said tree as a non-composite numeral.

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

means, comprising said electronic computing device, for representing said exhaustively 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, comprising said electronic computing device, for performing a push operation on said one or more natural numbers representing said exhaustively 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.

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

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

means, comprising said electronic computing device, 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, comprising said electronic computing device, 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.

25. An apparatus comprising:

a computing platform, said computing platform comprising an electronic computing device programmed with instructions to;

exhaustively enumerate possible component rooted partial subtrees of a tree to model logical branches of a query, said component rooted partial subtrees defining respective connectable paths between a root node of the tree and nodes in respective component rooted partial subtrees along one or more edges in the tree; and

determine one or more electrical digital signals representing natural numerals associated with particular ones of said enumerated component rooted partial subtrees, said natural numerals being based, at least in part, on an association between trees and natural numerals;

wherein said electronic computing device is further programmed with instructions to;

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

enumerate possible component rooted partial subtrees of said identified subtrees;

wherein said tree is represented as one or more electrical digital signals representing a composite natural numeral based, at least in part, on said association, and wherein said electronic computing device is further programmed with instructions to identify said one or more subtrees by factoring said one or more signals representing said composite natural numeral into one or more electrical digital signals representing natural numerals representative of subtrees;

wherein said tree comprises an edge or node labeled tree, and wherein the labels comprise discrete values.

26. The apparatus of claim 25, wherein electronic computing device is further programmed with instructions to merge combinations of individual ones of said enumerated possible component rooted partial subtrees of said identified subtrees.

27. The apparatus of claim 25, wherein said electronic computing device is further programmed with instructions to:

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

perform an inverse push operation on said one or more signals representing said non-composite natural numerals to provide one or more electrical digital signals representing 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 signals representing said one or more natural numerals representative of said child trees.

28. The apparatus of claim 25, wherein said electronic computing device is further programmed with instructions to:

perform an inverse push operation on one or more electrical digital signals representing a natural numeral representative of said tree to provide one or more electrical digital signals representing a natural numeral representative of a child tree; and

exhaustively enumerate possible component rooted partial subtrees of said child tree.

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

30. The apparatus of claim 27, wherein said electronic computing device is further programmed with instructions to:

perform a push operation on said one or more signals representing 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 one or more signals representing said natural numerals associated with said particular ones of said exhaustively enumerated rooted partial subtrees based, at least in part, upon said push operation.

31. The apparatus of claim 27, wherein said electronic computing device is further programmed with instructions to:

determine one or more electrical digital signals representing natural numerals associated with rooted partial subtrees of said child trees according to said association;

combine said one or more signals representing said natural numerals associated with said rooted partial subtrees of said child trees with one or more electrical digital signals representing 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 one or more electrical digital signals representing elements of said combined set of natural numerals to provide one or more electrical digital signals representing natural numerals representative of said particular ones of said enumerated rooted partial subtrees.

32. The apparatus of claim 28, wherein said child tree is coupled to a root node of said tree, and wherein said electronic computing device is further programmed with instructions 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

exhaustively enumerate possible component rooted partial subtrees of said identified subtrees.

33. The apparatus of claim 28, wherein said electronic computing device is further programmed with instructions to identify said natural numeral representative of said tree as one or more signals representing a non-composite numeral.

34. The apparatus of claim 28, wherein said electronic computing device is further programmed with instructions to:

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

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

35. The apparatus of claim 32, wherein said child tree is represented as one or more electrical digital signals representing a composite natural numeral based, at least in part, on said association, and wherein said electronic computing device is further programmed with instructions to identify one or more subtrees of said child tree by factoring said one or more signals representing said composite natural numeral into one or more electrical digital signals representing natural numerals representative of said subtrees.

36. The apparatus of claim 34, wherein said electronic computing device is further programmed with instructions to:

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

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

37. An article comprising:

a storage memory comprising machine-readable instructions which, in response to being executed by a processor, direct said processor to;

exhaustively enumerate possible component rooted partial subtrees of a tree to model logical branches of a query, said component rooted partial subtrees defining respective connectable paths between a root node of the tree and nodes in respective component rooted partial subtrees along one or more edges in the tree; and

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

wherein said instructions, in response to being executed by said processor, further direct said processor to;

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

exhaustively enumerate possible component rooted partial subtrees of said identified subtrees;

wherein said tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said instructions, in response to being executed by said processor, further direct said processor to identify said one or more subtrees by factoring said composite natural numeral into natural numerals representative of subtrees;

wherein said tree comprises an edge or node labeled tree, and wherein the labels comprise discrete values.

38. The article of claim 37, wherein said instructions, in response to being executed by said processor, further direct said processor to merge combinations of individual ones of said exhaustively enumerated possible component rooted partial subtrees of said identified subtrees.

39. The article of claim 37, wherein said instructions, in response to being executed by said processor, further direct said processor 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.

40. The article of claim 37, wherein said instructions, in response to being executed by said processor, further direct said processor 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

exhaustively enumerate possible component rooted partial subtrees of said child tree.

41. The article of claim 37, wherein said tree comprises a binary edge labeled tree.

42. The article of claim 39, wherein said instructions, in response to being executed by said processor, further direct said processor 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.

43. The article of claim 39, wherein said instructions, in response to being executed by said processor, further direct said processor 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 exhaustively enumerated rooted partial subtrees.

44. The article of claim 40, wherein said child tree comprises a root node coupled to a root node of said tree, and wherein said instructions, in response to being executed by said processor, further direct said processor 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

exhaustively enumerate possible component rooted partial subtrees of said identified subtrees.

45. The article of claim 40, wherein said instructions, in response to being executed by said processor, further direct said processor to identify said natural numeral representative of said tree as a non-composite numeral.

46. The article of claim 40, wherein said instructions, in response to being executed by said processor, further direct said processor to:

represent said exhaustively 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 exhaustively 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.

47. The article of claim 44, wherein said child tree is represented as a composite natural numeral based, at least in part, on said association, and wherein said instructions, in response to being executed by said processor, further direct said processor to identify one or more subtrees of said child tree by factoring said composite natural numeral into natural numerals representative of said subtrees.

48. The article of claim 46, wherein said instructions, in response to being executed by said processor, further direct said processor to:

combine said natural numerals representing said exhaustively 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.