Method and/or system for tree transformation

• US 8,615,530 B1
• Filed: 12/27/2005
• Issued: 12/24/2013
• Est. Priority Date: 01/31/2005
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Dated February 8, 2002
• Inventors: Letourneau, Jack J.
• Primary Examiner(s): GEBRESENBET, DINKU W
• Application Number:
  US11/320,538
• Time in Patent Office: 2,919 Days
• Field of Search: 707/791, 707/794, 707/796, 707/999.101
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

Embodiments of methods, apparatuses, devices and/or systems for manipulating hierarchical sets of data are disclosed. In one particular example, such methods, apparatuses, devices and/or systems may be directed to transforming between labeled and unlabeled trees which are elementary equivalents.

Claims

1. A method comprising:

executing instructions by a processor to;

transform an unlabeled tree in a set of unlabeled trees to a binary labeled tree (BLT) in a set of BLTs, said unlabeled tree and BLT being elementary equivalents in that there exists a transformation between said unlabeled tree and said BLT according to a one to one and onto mapping between said set of unlabeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree; and

further comprising executing said instructions by said processor to transform said unlabeled tree to said BLT by;

transforming said unlabeled tree to a node labeled tree, said unlabeled tree and said node labeled tree being elementary equivalents; and

transforming said node labeled tree to said BLT;

wherein said transforming said unlabeled tree to said node labeled tree further comprises;

identifying frontier nodes of said unlabeled tree;

pruning one or more terminal node children of said frontier nodes; and

expressing remaining unpruned terminal nodes of said unlabeled tree as representing node labels of nodes corresponding with parent nodes of said remaining unpruned terminal nodes.

2. The method of claim 1, wherein nodes in said node labeled tree are associated with node label values, and wherein said transforming said node labeled tree to said BLT further comprises representing node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes.

3. The method of claim 2, wherein said node label values are associated with numerals, and wherein said representing node label values of selected ones of said nodes in said node labeled tree further comprises:

associating said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

representing said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

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

5. A method comprising:

executing instructions by a processor to;

transform a node labeled tree in a set of node labeled trees to a binary labeled tree (BLT) in a set of BLTs, said node labeled tree and BLT being elementary equivalents in that there exists a transformation between said node labeled tree and said BLT according to a one to one and onto mapping between said set of node labeled trees and said set of BLTs, said transformation comprising one or more graphical operations applied to a tree;

wherein nodes in said node labeled tree are associated with node label values, and further comprising executing said instructions by said processor to represent node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes;

wherein said node label values are associated with numerals, and wherein said node label values of selected ones of said nodes are represented in said node labeled tree by;

associating said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

representing said node label values of said selected nodes in said BLT by extending said corresponding BLTs and/or BLT portions from nodes in said BLT associated with said selected nodes in said node labeled tree.

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

7. An apparatus comprising:

means for defining an unlabeled tree in a set of unlabeled trees; and

means for transforming said unlabeled tree to a binary labeled tree (BLT) in a set of BLTs, said unlabeled tree and BLT being elementary equivalents in that there exists a transformation between said unlabeled tree and said BLT according to a one to one and onto mapping between said set of unlabeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein said means for transforming said unlabeled tree to said BLT further comprises;

means for transforming said unlabeled tree to a node labeled tree, said unlabeled tree and said node labeled tree being elementary equivalents; and

means for transforming said node labeled tree to said BLT;

and

wherein said means for transforming said unlabeled tree to said node labeled tree further comprises;

means for identifying frontier nodes of said unlabeled tree;

means for pruning one or more terminal node children of said frontier nodes; and

means for expressing remaining unpruned terminal nodes of said unlabeled tree as node labels of nodes corresponding with parent nodes of said remaining unpruned terminal nodes.

8. The apparatus of claim 7, wherein nodes in said node labeled tree are associated with node label values, and wherein said means for transforming said node labeled tree to said BLT further comprises means for representing node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes.

9. The apparatus of claim 8, wherein said node label values are associated with numerals, and wherein said means for representing node label values of selected ones of said nodes in said node labeled tree further comprises:

means for associating said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

means for representing said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

10. The apparatus of claim 7, wherein said BLT comprises a binary edge labeled tree.

11. An apparatus comprising:

means for defining a node labeled tree in a set of node labeled trees; and

means for transforming said node labeled tree to a binary labeled tree (BLT) in a set of BLTs, said node labeled tree and BLT being elementary equivalents in that there exists a transformation between said node labeled tree and said BLT according to a one to one and onto mapping between said set of node labeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein nodes in said node labeled tree are associated with node label values, and further comprising means for representing node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes;

wherein said node label values are associated with numerals, and wherein said means for representing node label values of selected ones of said nodes in said node labeled tree further comprises;

means for associating said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

means for representing said node label values of said selected nodes in said BLT by extending said corresponding BLTs and/or BLT portions from nodes in said BLT associated with said selected nodes in said node labeled tree.

12. The apparatus of claim 11, wherein said BLT comprises a binary edge labeled tree.

13. An article comprising:

a memory comprising instructions stored thereon which are executable to;

transform an unlabeled tree in a set of unlabeled trees to a binary labeled tree (BLT) in a set of BLTs, said unlabeled tree and BLT being elementary equivalents in that there exists a transformation between said unlabeled tree and said BLT according to a one to one and onto mapping between said set of unlabeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein said instructions are further executable to;

transform said unlabeled tree to a node labeled tree, said unlabeled tree and said node labeled tree being elementary equivalents; and

transform said node labeled tree to said BLT;

and

wherein said instructions are further executable to;

identify frontier nodes of said unlabeled tree;

prune one or more terminal node children of said frontier nodes; and

express remaining unpruned terminal nodes of said unlabeled tree as node labels of nodes corresponding with parent nodes of said remaining unpruned terminal nodes.

14. The article of claim 13, wherein nodes in said node labeled tree are associated with node label values, and wherein said instructions are further executable to represent node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes.

15. The article of claim 14, wherein said node label values are associated with numerals, and wherein said instructions are further executable to:

associate said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

represent said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

16. The article of claim 13, wherein said BLT comprises a binary edge labeled tree.

17. An article comprising:

a memory comprising instructions stored thereon which are executable to;

transform a node labeled tree in a set of node labeled trees to a binary labeled tree (BLT) in a set of BLTs, said node labeled tree and BLT being elementary equivalents in that there exists a transformation between said node labeled tree and said BLT according to a one to one and onto mapping between said set of node labeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein nodes in said node labeled tree are associated with node label values, and wherein said instructions are further executable to represent node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes; and

wherein said node label values are associated with numerals, and wherein said instructions are further executable to;

associate said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

represent said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

18. The article of claim 17, wherein said BLT comprises a binary edge labeled tree.

19. An apparatus comprising:

a computing platform comprising one or more processors programmed with instructions to;

transform an unlabeled tree in a set of unlabeled trees to a binary labeled tree (BLT) in a set of BLTs, said unlabeled tree and BLT being elementary equivalents in that there exists a transformation between said unlabeled tree and said BLT according to a one to one and onto mapping between said set of unlabeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein the one or more processors are further programmed with instructions to;

transform said unlabeled tree to a node labeled tree, said unlabeled tree and said node labeled tree being elementary equivalents; and

transform said node labeled tree to said BLT;

and

wherein the one or more processors are further programmed with instructions to;

identify frontier nodes of said unlabeled tree;

prune one or more terminal node children of said frontier nodes; and

express remaining unpruned terminal nodes of said unlabeled tree as node labels of nodes corresponding with parent nodes of said remaining unpruned terminal nodes.

20. The apparatus of claim 19, wherein nodes in said node labeled tree are associated with node label values, and wherein the one or more processors are further programmed with instructions to represent node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes.

21. The apparatus of claim 19, wherein said node label values are associated with numerals, and wherein the one or more processors are further programmed with instructions to:

associate said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

represent said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

22. The apparatus of claim 19, wherein said BLT further comprises a binary edge labeled tree.

23. An apparatus comprising:

a computing platform, the computing platform comprising one or more processors programmed with instructions to;

transform a node labeled tree in a set of node labeled trees to a binary labeled tree (BLT) in a set of BLTs, said node labeled tree and BLT being elementary equivalents in that there exists a transformation between said node labeled tree and said BLT according to a one to one and onto mapping between said set of node labeled trees and said set of BLTs, said transformation comprising application of one or more graphical operations to a tree;

wherein nodes in said node labeled tree are associated with node label values, and wherein the one or more processors are further programmed with instructions to represent node label values of selected ones of said nodes in said node labeled tree as one or more nodes coupled to nodes in said BLT corresponding with said selected nodes;

wherein said node label values are associated with numerals,

and

wherein the one or more processors are further programmed with instructions to;

associate said node label values of said selected nodes in said node labeled tree with corresponding BLTs and/or BLT portions according to an association of trees and numerals; and

represent said node label values of said selected nodes in said BLT with said corresponding BLTs and/or BLT portions.

24. The apparatus of claim 23, wherein said BLT further comprises a binary edge labeled tree.