Manipulation and/or analysis of hierarchical data

• US 7,899,821 B1
• Filed: 04/26/2006
• Issued: 03/01/2011
• Est. Priority Date: 04/29/2005
• Status: Expired due to Fees

• 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: Andrews, Mark, Schiffmann, Karl, LeTourneau, Jack J.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Chbouki; Tarek
• Application Number:
  US11/412,417
• Time in Patent Office: 1,770 Days
• Field of Search: 707/6
• US Class Current: 707/736
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• 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 analyzing hierarchical data are disclosed. In a particular example, rooted partial subtrees of partial subtrees of a tree are enumerated and associated with target numerals according to an association of trees and numerals. A probe numeral, representing information of interest, may be compared with target numerals to find a match. In one particular example, such a match indicates a presence of particular information in the tree.

Claims

1. A method comprising:

identifying partial subtrees of a tree, said tree comprising hierarchical data representing one or more XML documents, said partial subtrees having depths up to a predetermined depth defining a longest separation between a root node and terminal node of said partial subtrees;

enumerating rooted partial subtrees of at least one of said identified partial subtrees;

representing said tree as one or more electrical digital signals representing one or more target numerals, said one or more target numerals being associated with said enumerated rooted partial subtrees according to an association between trees and numerals;

determining one or more signals representing a probe numeral representing a query to said one or more XML documents based, at least in part, on one or more electrical digital signals representing a probe tree, said probe tree comprising a piece of information of interest; and

comparing, using a processor, said one or more electrical digital signals representing said probe numeral with said one or more signals representing said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said one or more signals representing said probe tree in one or more electrical digital signals representing said tree based, at least in part, on a match of said one or more signals representing said probe numeral with one or more electrical digital signals representing at least one of said target numerals.

2. The method of claim 1, wherein said probe numeral is based, at least in part, on said association of trees and numerals.

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

identifying non-terminal nodes of said tree as root nodes of said partial subtrees; and

identifying one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree.

4. The method of claim 3, wherein said identifying one or more nodes descending from a root node of at least one of said partial subtrees further comprises identifying nodes descending from a root node of at least one of said partial subtrees down to said predetermined depth to be one or more nodes of said partial subtree.

5. The method of claim 3, wherein said identifying one or more nodes descending from a root node of at least one of said partial subtrees further comprises identifying one or more nodes descending from a root node of at least one of said partial subtrees based, at least in part, on electrical digital signals representing node and/or edge label values associated with said nodes.

6. The method of claim 1, and further comprising determining said one or more signals representing said probe numeral based, at least in part, on said association between trees and numerals, and wherein said match corresponds with a partial subtree of said tree matching said probe tree.

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

8. The method of claim 1, wherein said tree comprises hierarchical data representative of a known biometric pattern and said probe numeral is representative of one or more features of a subject and/or specimen.

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

determine target numerals associated with enumerated rooted partial subtrees having a root node with at least two nodes directly descending nodes as composite natural numerals; and

determine target numerals associated with enumerated rooted partial subtrees having a root node with a single directly descend nodes as non-composite natural numerals.

10. A method comprising:

representing a tree as one or more electrical digital signals representing one or more target numerals, said one or more target numerals being associated with partial subtrees of said tree according to an association between trees and numerals, said partial subtrees having depths up to a predetermined depth defining a longest separation between a root node and terminal node of said partial subtrees;

determining one or more signals representing a probe numeral based, at least in part, on one or more electrical digital signals representing a probe tree, said probe tree comprising a piece of information of interest; and

comparing, using a processor, said one or more signals representing said probe numeral with said one or more signals representing said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said one or more signals representing said probe tree in one or more electrical digital signals representing said tree based, at least in part, on a match of said one or more signals representing said probe numeral with one or more electrical digital signals representing at least one of said target numerals,

wherein said tree comprises hierarchical data representative of a known biometric pattern and said probe numeral is representative of one or more features of a subject and/or specimen.

11. An apparatus comprising:

means, comprising one or more processors, for identifying subtrees of a tree, said tree comprising hierarchical data representing one or more XML documents, said subtrees having depths up to a predetermined depth defining a longest separation between a root node and terminal node of said subtrees;

means, comprising said one or more processors, for enumerating rooted partial subtrees of at least one of said identified subtrees;

means, comprising said one or more processors, for representing said tree as one or more target numerals, said one or more target numerals being associated with said enumerated rooted partial subtrees according to an association of trees and numerals;

means, comprising said one or more processors, for determining a probe numeral representing a query to said one or more XML documents based, at least in part, on a probe tree, said probe tree comprising a piece of information of interest; and

means, comprising said one or more processors, for comparing said probe numeral with said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said probe tree in said tree based, at least in part, on a match of said probe numeral with at least one of said target numerals.

12. The apparatus of claim 11, wherein said probe numeral is based, at least in part, on said association of trees and numerals.

13. The apparatus of claim 11, wherein said means for identifying said partial subtrees of said tree further comprises:

means for identifying non-terminal nodes of said tree as root nodes of said partial subtrees; and

means for identifying one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree.

14. The apparatus of claim 13, wherein said means for identifying one or more nodes descending from a root node of at least one of said partial subtrees further comprises means for identifying one or more nodes descending from a root node of at least one of said partial subtrees down to a predetermined depth to be one or more nodes of said partial subtree.

15. The apparatus of claim 13, wherein said means for identifying one or more nodes descending from a root node of at least one of said partial subtrees further comprises means for identifying nodes descending from a root node of at least one of said partial subtrees based, at least in part, on node and/or edge label values associated with said nodes.

16. The apparatus of claim 11, and further comprising means for determining said probe numeral based, at least in part, on said association between trees and numerals, and wherein said match corresponds with a partial subtree of said tree matching said probe tree.

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

18. The apparatus of claim 11, and further comprising means for representing hierarchical data representative of a known biometric pattern as said tree and representing one or more features of a subject and/or specimen as said probe numeral.

19. An apparatus comprising:

means, comprising one or more processors, for representing a tree as one or more target numerals, said one or more target numerals being associated with partial subtrees of said tree according to an association between trees and numerals, said partial subtrees having depths up to a predetermined depth defining a longest separation between a root node and terminal node of said partial subtrees;

means, comprising said one or more processors, for determining a probe numeral based, at least in part, on one or more electrical digital signals representing a probe tree, said probe tree comprising a piece of information of interest;

means, comprising one or more processors, for comparing said probe numeral with said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said probe tree in said tree based, at least in part, on a match of said probe numeral with at least one of said target numerals; and

means, comprising one or more processors, for representing hierarchical data representative of a known biometric pattern as said tree and representing one or more features of a subject and/or specimen as said probe numeral.

20. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which are executable by a processor to;

identify subtrees of a tree, said tree comprising hierarchical data representing one or more XML documents, said subtrees having depths up to a predetermined depth defining a longest separation between a root node and terminal node of said subtrees;

enumerate rooted partial subtrees of at least one of said identified subtrees;

represent said tree as one or more target numerals, said one or more target numerals being associated with said enumerated rooted partial subtrees according to an association between trees and numerals;

determine a probe numeral representative of a query to said one or more XML documents based, at least in part, on a probe tree, said probe tree comprising a piece of information of interest; and

compare said probe numeral with said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said probe tree in said tree based, at least in part, on a match of said probe numeral with at least one of said target numerals.

21. The article of claim 20, wherein said machine-readable instructions are further executable by said processor to generate said one or more target numerals based, at least in part, on one or more numerals representing rooted partial subtrees of at least one of said partial subtrees.

22. The article of claim 20, wherein said machine-readable instructions are further executable by said processor to determine said probe numeral based, at least in part, on said association between trees and numerals.

23. The article of claim 20, wherein said instructions are further executable by said processor to:

identify non-terminal nodes of said tree as root nodes of said partial subtrees; and

identify one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree.

24. The article of claim 23, wherein said instructions are further executable by said processor to identify one or more nodes descending from a root node of at least one of said partial subtrees down to said predetermined depth to be one or more nodes of said partial subtree.

25. The article of claim 23, wherein said instructions are further executable by said processor to identify one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree based, at least in part, on node and/or edge label values associated with said one or more nodes.

26. The article of claim 20, wherein said instructions are further executable by said processor to determine said probe numeral based, at least in part, on said association between trees and numerals, and wherein said match corresponds with a partial subtree of said tree matching said probe tree.

27. The article of claim 20, wherein said tree comprises a binary edge labeled tree.

28. The article of claim 20, wherein said instructions are further executable by said processor to represent hierarchical data representative of a known biometric pattern as said tree and represent one or more features of a subject and/or specimen as said probe numeral.

29. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which are executable by a processor to;

represent a tree as one or more target numerals, said one or more target numerals being associated with identified partial subtrees of said tree according to an association between trees and numerals, said identified partial subtrees having depths up to a predetermined depth defining a longest separation between a root node and a terminal node of said partial subtrees;

determine a probe numeral based, at least in part, on a probe tree, said probe tree comprising a piece of information of interest;

compare said probe numeral with said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said probe tree in said tree based, at least in part, on a match of said probe numeral with at least one of said target numerals; and

represent hierarchical data representative of a known biometric pattern as said tree and represent one or more features of a subject and/or specimen as said probe numeral.

30. An apparatus comprising:

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

identify subtrees of a tree, said tree comprising hierarchical data representing one or more XML documents, said subtrees having depths up to a predetermined depth defining a longest separation between a root node and a terminal node of said subtrees;

enumerate rooted partial subtrees of at least one of said identified subtrees;

represent said tree as one or more electrical digital signals representing one or more target numerals, said one or more target numerals being associated with said enumerated rooted partial subtrees according to an association between trees and numerals;

determine a probe numeral representative of a query to said one or more XML documents based, at least in part, said probe tree comprising a piece of information of interest; and

compare one or more electrical digital signals representing said probe numeral with said one or more signals representing said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said probe tree in said tree based, at least in part, on a match of said probe numeral with at least one of said target numerals.

31. The apparatus of claim 30, wherein said one or more processors are further programmed with instructions to determine said one or more signals representing said probe numeral based, at least in part, on an association of trees and numerals.

32. The apparatus of claim 30, wherein said one or more processors are further programmed with instructions to:

identify said one or more partial subtrees of said tree; and

determine said one or more signals representing said one or more target numerals based, at least in part, on at least a portion of said partial subtrees and according to said association between trees and numerals.

33. The apparatus of claim 30, wherein said one or more processors are further programmed with instructions to:

identify non-terminal nodes of said tree as root nodes of said partial subtrees; and

identify one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree.

34. The apparatus of claim 33, wherein said one or more processors are further programmed with instructions to identify one or more nodes descending from a root node of at least one of said partial subtrees down to said predetermined depth to be one or more nodes of said partial subtree.

35. The apparatus of claim 33, wherein said one or more processors are further programmed with instructions to identify one or more nodes descending from a root node of at least one of said partial subtrees to be one or more nodes of said partial subtree based, at least in part, on one or more electrical digital signals representing node and/or edge label values associated with said one or more nodes.

36. The apparatus of claim 30, wherein said one or more processors are further adapted to determine said one or more signals representing said probe numeral based, at least in part, on said association between trees and numerals, and wherein said match corresponds with a partial subtree of said tree matching said probe tree.

37. The apparatus of claim 30, wherein said tree comprises a binary edge labeled tree.

38. The apparatus of claim 30, wherein said one or more processors are further programmed with instructions to represent hierarchical data representative of a known biometric pattern as said tree and represent one or more features of a subject and/or specimen as said one or more signals representing said probe numeral.

39. An apparatus comprising:

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

represent a tree as one or more electrical digital signals representing one or more target numerals, said one or more target numerals being associated with identified partial subtrees of said tree according to an association between trees and numerals, said partial subtrees having depths up to a predetermined depth defining a longest separation between a root node and a terminal node of said partial subtrees;

determine one or more signals representing a probe numeral based, at least in part, on one or more electrical digital signals representing a probe tree, said probe tree comprising a piece of information of interest;

compare one or more electrical digital signals representing said probe numeral with said one or more signals representing said one or more target numerals to detect a presence of said piece of information in said tree by detecting a presence of said one or more signals representing said probe tree in one or more electrical digital signals representing said tree based, at least in part, on a match of said one or more signals representing said probe numeral with one or more electrical digital signals representing at least one of said target numerals; and

represent hierarchical data representative of a known biometric pattern as said tree and represent one or more features of a subject and/or specimen as said one or more signals representing said probe numeral.