Enumeration of trees from finite number of nodes

• US 9,002,862 B2
• Filed: 11/21/2013
• Issued: 04/07/2015
• Est. Priority Date: 11/30/2004
• Status: Expired due to Fees

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Schiffmann, Karl, Andrews, Mark, LeTourneau, Jack J.
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US14/086,808
• Publication Number:
  US 20140289278A1
• Time in Patent Office: 502 Days
• Field of Search: 707/102, 707/101, 707/755, 707/802
• US Class Current: 707/755
• 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 comprising:

enumerating one or more possible trees configurable from a finite number (N) of nodes;

determining for the enumerated trees natural numerals associated with particular ones of the enumerated trees,

the natural numerals being based, at least in part, on a predetermined association between trees and natural numerals;

wherein said enumerating comprises enumeration of each of the one or more possible trees, and

wherein said determining natural numerals for the enumerated trees comprises determining a natural numeral for each one of the enumerated trees;

determining one or more allocations of the finite number of nodes among subtree slots,

an allocation defining a portion of the finite number of nodes to a subtree slot in the allocation; and

for the subtree slot in the allocation, enumerating a set containing one or more possible subtrees configurable from the portion of the finite number of nodes allocated to the subtree slot.

2. The method of claim 1, wherein the enumerated trees comprise binary edge labeled trees.

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

identifying N−

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

determining possible allocations of N−

1 nodes among subtree slots in arrangements of subtree slots;

for a subtree slot in a possible allocation of the N−

1 nodes, determining one or more natural numerals for possible configurations of a subtree from nodes allocated to the subtree slot.

4. The method of claim 1, wherein the natural numeral comprises a product of one or more component natural numerals, the one or more component natural numerals representing a subtree among subtrees which are merged at a root node to form the associated enumerated tree.

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

identifying N−

1 arrangements of subtree slots coupled to a root node;

for an arrangement of subtree slots;

determining one or more allocations of N−

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

1 nodes; and

for the subtree slots, enumerating one or more possible subtrees configurable from the portion of said N−

1 nodes allocated to the subtree slot.

6. The method of claim 1, wherein said enumerating possible configurable trees comprises enumerating the possible trees configurable from exactly N nodes.

7. An apparatus comprising:

means for enumerating one or more possible trees configurable from a finite number (N) of nodes;

means for determining for the enumerated trees natural numerals associated with particular ones of the enumerated trees,

the natural numerals being based, at least in part, on a predetermined association between trees and natural numerals;

wherein said means for enumerating comprises means for enumerating each of the one or more possible trees, and

wherein said means for determining natural numerals for the enumerated trees comprises means for determining a natural numeral for each one of the enumerated trees;

means for determining one or more allocations of the finite number of nodes among subtree slots,

an allocation defining a portion of the finite number of nodes to a subtree slot in the allocation; and

for the subtree slot in the allocation, means for enumerating a set containing one or more possible subtrees configurable from the portion of the finite number of nodes allocated to the subtree slot.

8. The apparatus of claim 7, wherein the enumerated trees comprise binary edge labeled trees.

9. The apparatus of claim 7, the apparatus further comprising:

means for identifying N−

1 arrangements of subtree slots coupled to a root node;

means for determining possible allocations of N−

1 nodes among subtree slots in arrangements of subtree slots; and

for a subtree slot in a possible allocation of the N−

1 nodes, means for determining one or more natural numerals for possible configurations of a subtree from nodes allocated to the subtree slot.

10. The apparatus of claim 7, wherein the natural numeral comprises a product of one or more component natural numerals, the one or more component natural numerals representing a subtree among subtrees which are merged at a root node to form the associated enumerated tree.

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

means for identifying N−

1 arrangements of subtree slots coupled to a root node;

means for determining one or more allocations of N−

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

1 nodes; and

means for enumerating one or more possible subtrees configurable from the portion of said N−

1 nodes allocated to the subtree slot.

12. The apparatus of claim 7, wherein said means for enumerating possible configurable trees comprises means for enumerating the possible trees configurable from exactly N nodes.

13. An apparatus comprising a computing platform, the computing platform being adapted to:

enumerate one or more possible trees configurable from a finite number (N) of nodes;

determine for the enumerated trees natural numerals associated with particular ones of the enumerated trees,

the natural numerals being based, at least in part on a predetermined association between trees and natural numerals;

wherein said enumerating comprises enumeration of each of the one or more possible trees, and

wherein said determining natural numerals for the enumerated trees comprises determining a natural numeral for each one of the enumerated trees;

determine one or more allocations of the finite number of nodes among subtree slots,

an allocation defining a portion of the finite number of nodes to a subtree slot in the allocation; and

for the subtree slot in the allocation,

enumerate a set containing one or more possible subtrees configurable from the portion of the finite number of nodes allocated to the subtree slot.

14. The apparatus of claim 13, wherein the enumerated trees comprise binary edge labeled trees.

15. The apparatus of claim 13, wherein the computing platform is further adapted to:

identify N−

1 arrangements of subtree slots coupled to a root node;

determine possible allocations of N−

1 nodes among subtree slots in arrangements of subtree slots; and

for a subtree slot in a possible allocation of the N−

1 nodes, determine one or more natural numerals for possible configurations of a subtree from nodes allocated to the subtree slot.

16. The apparatus of claim 13, wherein the natural numeral comprises a product of one or more component natural numerals, the one or more component natural numerals representing a subtree among subtrees which are merged at a root node to form the associated enumerated tree.

17. The apparatus of claim 13, wherein the computing platform is further adapted to:

identify N−

1 arrangements of subtree slots coupled to a root node;

determine one or more allocations of N−

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

1 nodes; and

enumerate one or more possible subtrees configurable from the portion of said N−

1 nodes allocated to the subtree slot.

18. The apparatus of claim 13, wherein the computing platform is further adapted to enumerating the possible trees configurable from exactly N nodes.

19. An article comprising:

a storage medium comprising machine readable instructions stored thereon to;

enumerate one or more possible trees configurable from a finite number (N) of nodes;

determine for the enumerated trees natural numerals associated with particular ones of the enumerated trees,

the natural numerals being based, at least in part on a predetermined association between trees and natural numerals;

wherein said enumerating comprises enumeration of each of the one or more possible trees, and

wherein said determining natural numerals for the enumerated trees comprises determining a natural numeral for each one of the enumerated trees;

determine one or more allocations of the finite number of nodes among subtree slots,

an allocation defining a portion of the finite number of nodes to a subtree slot in the allocation; and

for a subtree slot in an allocation, enumerate a set containing one or more possible subtrees configurable from the portion of the finite number of nodes allocated to the subtree slot.

20. The article of claim 19, wherein the enumerated trees comprise binary edge labeled trees.

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

identify N−

1 arrangements of subtree slots coupled to a root node;

determine possible allocations of N−

1 nodes among subtree slots in arrangements of subtree slots; and

for a subtree slot in a possible allocation of the N−

1 nodes, determine one or more natural numerals for possible configurations of a subtree from nodes allocated to the subtree slot.

22. The article of claim 19, wherein the natural numeral comprises a product of one or more component natural numerals, the one or more component natural numerals representing a subtree among subtrees which are merged at a root node to form the associated enumerated tree.

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

identify N−

1 arrangements of subtree slots coupled to a root node;

determine one or more allocations of N−

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

1 nodes; and

enumerate one or more possible subtrees configurable from the portion of said N−

1 nodes allocated to the subtree slot.

24. The article of claim 19, wherein the storage medium further comprises machine-readable instructions stored thereon to enumerating the possible trees configurable from exactly N nodes.