Enumeration of trees from finite number of nodes

• US 7,636,727 B2
• Filed: 12/06/2004
• Issued: 12/22/2009
• Est. Priority Date: 12/06/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Skyler Technology Incorporated
• Inventors: Andrews, Mark, Schiffmann, Karl, LeTourneau, Jack J.
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US11/006,440
• Publication Number:
  US 20060129582A1
• Time in Patent Office: 1,842 Days
• Field of Search: 707/102, 707/101
• 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 comprising:

executing instructions on one or more processors to;

enumerate possible trees configurable from a finite number (N) of nodes greater than one, said possible trees being representative of possible answers to a query, by;

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;

allocating a portion of N−

1 nodes to a subtree slot in an arrangement of subtree slots;

for a subtree slot in the arrangement of subtree slots, enumerating one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

performing a push operation on the enumerated one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot to determine one or more natural numerals, each natural numeral being associated with a corresponding one of said pushed one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

determine for the enumerated trees particular natural numerals associated with particular ones of the enumerated trees, the natural numerals associated with said particular ones of enumerated trees being based, at least in part, on an association between trees and natural numerals,

wherein each of said particular natural numerals associated with particular ones of the enumerated trees is associated with exactly one of said enumerated trees.

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

3. The method of claim 1, wherein at least one of said natural numerals associated with a particular one of said enumerated trees 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 particular one of said enumerated trees.

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

5. An apparatus comprising:

means comprising one or more processors for enumerating possible trees configurable from a finite number (N) of nodes greater than one, said possible trees being representative of possible answers to a query, 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;

means for allocating a portion of N−

1 nodes to a subtree slot in an arrangement of subtree slots;

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

1 nodes allocated to the subtree slot; and

means for performing a push operation on the enumerated one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot to determine one or more natural numerals, each natural numeral being associated with a corresponding one of said pushed one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

means comprising one or more processors for determining for the enumerated trees particular natural numerals associated with particular ones of the enumerated trees, the particular natural numerals being based, at least in part, on a predetermined association between trees and natural numerals,

wherein each of said natural numerals associated with particular ones of the enumerated trees is associated with exactly one of said enumerated trees.

6. The apparatus of claim 5, wherein the enumerated trees comprise binary edge labeled trees.

7. The apparatus of claim 5, wherein at least one of the natural numerals associated with a particular one of said enumerated trees 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 particular one of said enumerated trees.

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

9. An apparatus comprising:

one or more processors programmed with instructions to;

enumerate possible trees configurable from a finite number (N) of nodes greater than one, said possible trees being representative of possible answers to a query, by;

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;

allocating a portion of N−

1 nodes to a subtree slot in an arrangement of subtree slots;

for a subtree slot in the arrangement of subtree slots, enumerating one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

performing a push operation on the enumerated one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot to determine one or more natural numerals, each natural numeral being associated with a corresponding one of said pushed one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

determine for the enumerated trees particular natural numerals associated with particular ones of the enumerated trees, the particular natural numerals being based, at least in part, on a predetermined association between trees and natural numerals,

wherein each of said particular natural numerals associated with particular ones of the enumerated trees is associated with exactly one of said enumerated trees.

10. The apparatus of claim 9, wherein the enumerated trees comprise binary edge labeled trees.

11. The apparatus of claim 9, wherein at least one of said natural numerals associated with a particular one of said enumerated trees 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 particular one of said enumerated trees.

12. The apparatus of claim 9, wherein the one or more processors are further programmed with instructions to enumerate the possible trees configurable from exactly N nodes.

13. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which, in response to being executed by a one or more processors, enable said one or more processors to;

enumerate possible trees configurable from a finite number (N) of nodes greater than one, said possible trees being representative of possible answers to a query, by;

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;

allocating a portion of N−

1 nodes to a subtree slot in an arrangement of subtree slots;

for a subtree slot in the arrangement of subtree slots, enumerating one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

performing a push operation on the enumerated one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot to determine one or more natural numerals, each natural numeral being associated with a corresponding one of said pushed one or more possible subtrees configurable from the portion of the N−

1 nodes allocated to the subtree slot; and

determine for the enumerated trees particular natural numerals associated with particular ones of the enumerated trees, the particular natural numerals being based, at least in part, on a predetermined association between trees and natural numerals,

wherein each of said particular natural numerals associated with particular ones of the enumerated trees is associated with exactly one of said enumerated trees.

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

15. The article of claim 13, wherein at least one of said natural numerals associated with a particular one of said enumerated trees 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 particular one of said enumerated trees.

16. The article of claim 13, wherein the machine-readable instructions, in response to being executed by said one or more processors, further enable said computing platform to enumerate the possible trees configurable from exactly N nodes.