Manipulation and/or analysis of hierarchical data

• US 9,245,050 B2
• Filed: 02/17/2011
• Issued: 01/26/2016
• Est. Priority Date: 04/29/2005
• Status: Expired due to Fees

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Schiffmann, Karl, LeTourneau, Jack J., Andrews, Mark
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US13/030,084
• Publication Number:
  US 20110282898A1
• Time in Patent Office: 1,804 Days
• Field of Search: None
• US Class Current: 1/1
• 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.

Claims

1. A method comprising:

representing a tree comprising at least a node or an edge in the form of binary digital signals, as one or more target numerals in the form of binary digital signals, using a processor of a computing platform, substantially in accordance with transformation of the tree to the one or more target numerals based at least in part on an association of trees and numerals, wherein the tree comprises one or more XML documents, the one or more XML documents comprising one or more electrical digital signals, the representing a tree comprising;

identifying a plurality of partial subtrees of the tree, the plurality of partial subtrees also in the form of binary digital signals;

enumerating rooted partial subtrees of the identified plurality of partial subtrees;

associating the one or more target numerals with the enumerated rooted partial subtrees; and

comparing, using the processor, a probe numeral in the form of binary digital signals with the one or more target numerals to detect a presence of a subtree in the tree, wherein the probe numeral is also based, at least in part, on the association of trees and numerals, and wherein a match between the probe numeral and at least one of the one or more target numerals is indicative of a presence of content in the one or more XML documents.

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

determining the one or more target numerals based, at least in part, on an association of numerals with the enumerated rooted partial subtrees of the identified plurality of partial subtrees.

3. The method of claim 2, wherein the identifying the plurality of partial subtrees of the tree further comprises:

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

identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees to be one or more nodes of an enumerated one of the rooted partial subtrees.

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

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

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

determining the probe numeral based, at least in part, on a probe tree in the form of binary digital signals, the probe tree comprising a subtree of interest; and

detecting a presence of the probe tree in the tree based, at least in part, on a match of the probe numeral with at least one of the target numerals.

7. The method of claim 6, and further comprising determining the probe numeral based, at least in part, on an association between trees and numerals, and wherein the match corresponds with a partial subtree of the tree matching the probe tree.

8. The method of claim 1, wherein the tree comprises a binary edge labeled tree.

9. The method of claim 1, wherein the probe numeral comprises a query to the one or more XML documents.

10. The method of claim 1, wherein the tree comprises a known pattern and the probe numeral comprises one or more features of a subject.

11. The method of claim 1 further comprising:

generating a first array of target numerals comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

updating the first array of target numerals by combining the one or more target numerals representing the tree with the numerals of the first array of target numerals.

12. The method of claim 11 further comprising:

generating a second array of target numerals comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

wherein the comparing the probe numeral with the one or more target numerals comprises comparing the probe numeral with the numerals of the first array of target numerals and with the numerals of the second array of target numerals.

13. An apparatus comprising:

means for representing a tree comprising at least a node or an edge in the form of binary digital signals as one or more target numerals in the form of binary digital signals substantially in accordance with transformation of the tree to the one or more target numerals based at least in part on an association of trees and numerals, wherein the tree comprises one or more XML documents, the one or more XML documents comprising one or more electrical digital signals, the means for representing a tree comprising;

means for identifying a plurality of partial subtrees of the tree, the plurality of partial subtrees also in the form of binary digital signals;

means for enumerating rooted partial subtrees of the identified plurality of partial subtrees;

means for associating the one or more target numerals with the enumerated rooted partial subtrees; and

means for comparing a probe numeral in the form of binary digital signals with the one or more target numerals to detect a presence of a subtree in the tree, the probe numeral to be based, at least in part, on the association of trees and numerals, and wherein a match between the probe numeral and at least one of the one or more target numerals is indicative of a presence of content in one or more XML documents.

14. The apparatus of claim 13, and further comprising:

means for determining the one or more target numerals based, at least in part, on an association of numerals with the enumerated rooted partial subtrees of the identified plurality of partial subtrees.

15. The apparatus of claim 14, wherein the means for identifying the plurality of partial subtrees of the tree further comprises:

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

means for identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees to be one or more nodes of an enumerated one of the rooted partial subtrees.

16. The apparatus of claim 15, wherein the means for identifying one or more nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises means for identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees down to a predetermined depth to be one or more nodes of an enumerated one of the rooted partial subtrees.

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

18. The apparatus of claim 13, and further comprising:

means for determining the probe numeral based, at least in part, on a probe tree, the probe tree comprising a subtree of interest; and

means for detecting a presence of the probe tree in the tree based, at least in part, on a match of the probe numeral with at least one of the target numerals.

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

20. The apparatus of claim 13, wherein the tree comprises a binary edge labeled tree.

21. The apparatus of claim 13, wherein the probe numeral comprising a query to the one or more XML documents.

22. The apparatus of claim 13, the tree comprising a known pattern and the probe numeral comprising one or more features of a subject.

23. The apparatus of claim 13 further comprising:

means for generating a first array of target numerals comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

means for updating the first array of target numerals by combining the one or more target numerals representing the tree with the numerals of the first array of target numerals.

24. The apparatus of claim 23 further comprising:

means for generating a second array of target numerals comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

wherein the means for comparing the probe numeral with the one or more target numerals comprises comparing the probe numeral with the numerals of the first array of target numerals and with the numerals of the second array of target numerals.

25. An article comprising:

a non-transitory computer storage medium comprising instructions stored thereon, the instructions capable of being executed by a computing platform comprising a processor, to represent a tree to comprise at least a node or an edge in the form of binary digital signals as one or more target numerals to be in the form of binary digital signals substantially in accordance with transformation of the tree to the one or more target numerals to be based at least in part on an association of trees and numerals, wherein the tree to comprise one or more XML documents, the one or more XML documents to comprise one or more electrical digital signals, the instructions to represent a tree comprising instructions to;

identify a plurality of partial subtrees of the tree, the plurality of partial subtrees also to be in the form of binary digital signals;

enumerate rooted partial subtrees of the to be identified plurality of partial subtrees;

associate the one or more target numerals with the to be enumerated rooted partial subtrees; and

compare a probe numeral in the form of binary digital signals with the one or more target numerals to detect a presence of a subtree in the tree, the probe numeral to be based, at least in part, on the association of trees and numerals, and wherein a match between the probe numeral and at least one of the one or more target numerals to indicate a presence of content in one or more XML documents.

26. The article of claim 25, wherein the storage medium further comprises instructions stored thereon to:

determine the one or more target numerals to be based, at least in part, on an association of numerals with the rooted partial subtrees of the plurality of partial subtrees.

27. The article of claim 26, wherein the storage medium further comprises instructions stored thereon to:

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

identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees to be one or more nodes of a to be enumerated one of the rooted partial subtrees.

28. The article of claim 27, wherein the storage medium further comprises instructions stored thereon to identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees down to a depth to be one or more nodes of a to be enumerated one of the rooted partial subtrees.

29. The article of claim 27, wherein the storage medium further comprises instructions stored thereon to identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees to be one or more nodes of a to be enumerated one of the rooted partial subtrees to be based, at least in part, on node and/or edge label values to be associated with the one or more nodes.

30. The article of claim 25, wherein the storage medium further comprises instructions stored thereon to:

determine the probe numeral to be based, at least in part, on a probe tree, the probe tree to comprise a subtree of interest; and

detect a presence of the probe tree in the tree to be based, at least in part, on a match of the probe numeral with at least one of the target numerals.

31. The article of claim 30, wherein the storage medium further comprises instructions stored thereon to determine the probe numeral to be based, at least in part, on an association between trees and numerals, and wherein the match to correspond with a partial subtree of the tree to match the probe tree.

32. The article of claim 25, wherein the storage medium further comprises instructions stored thereon so that the tree to be represented comprises a binary edge labeled tree.

33. The article of claim 25, wherein the probe numeral to comprise a query to the one or more XML documents.

34. The article of claim 25, wherein the tree to comprise a known pattern and the probe numeral to comprise one or more features of a subject.

35. The article of claim 25, wherein the storage medium further comprises instructions stored thereon to:

generate a first array of target numerals to comprise numerals in the form of binary digital signals to be associated with the rooted partial subtrees of the tree; and

update the first array of target numerals to be based at least in part on a combination of the one or more target numerals to represent the tree with the numerals of the first array of target numerals.

36. The article of claim 35, wherein the storage medium further comprises instructions stored thereon to:

generate a second array of target numerals to comprise numerals in the form of binary digital signals to be associated with the rooted partial subtrees of the tree; and

wherein the comparison of the probe numeral with the one or more target numerals to comprise a comparison of the probe numeral with the numerals of the first array of target numerals and with the numerals of the second array of target numerals.

37. An apparatus comprising:

a computing platform comprising a processor to represent a tree to comprise at least a node or an edge in the form of binary digital signals as one or more target numerals to be in the form of binary digital signals substantially in accordance with transformation of the tree to the one or more target numerals to be based at least in part on an association of trees and numerals, wherein the tree to comprise one or more XML documents, the one or more XML documents to comprise one or more electrical digital signals, the processor to represent a tree further comprising a processor to;

identify a plurality of partial subtrees of the tree, the plurality of partial subtrees also to be in the form of binary digital signals;

enumerate rooted partial subtrees of the to be identified plurality of partial subtrees;

associate the one or more target numerals with the to be enumerated rooted partial subtrees; and

compare a probe numeral in the form of binary digital signals with the one or more target numerals to detect a presence of a subtree in the tree, the probe numeral to be based, at least in part, on the association of trees and numerals, and wherein a match between the probe numeral and at least one of the one or more target numerals to indicate a presence of content in one or more XML documents.

38. The apparatus of claim 37, wherein the computing platform is further to:

determine the one or more target numerals to be based, at least in part, on an association of numerals with the rooted partial subtrees of the plurality of partial subtrees.

39. The apparatus of claim 38, wherein the computing platform is further to:

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

identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees to be one or more nodes of a to be enumerated one of the rooted partial subtrees.

40. The apparatus of claim 39, wherein the computing platform is further to identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees down to a depth to be one or more nodes of a to be enumerated one of the rooted partial subtrees.

41. The apparatus of claim 39, wherein the computing platform is further to identify one or more nodes to descend from a root node of at least one of the plurality of partial subtrees to be one or more nodes of a to be enumerated one of the rooted partial subtrees to be based, at least in part, on node and/or edge label values to be associated with the one or more nodes.

42. The apparatus of claim 37, wherein the computing platform is further to:

determine the probe numeral to be based, at least in part, on a probe tree, the probe tree to comprise a subtree of interest; and

detect a presence of the probe tree in the tree to be based, at least in part, on a match of the probe numeral with at least one of the target numerals.

43. The apparatus of claim 42, wherein the computing platform is further to determine the probe numeral to be based, at least in part, on an association between trees and numerals, and wherein the match to correspond with a partial subtree of the tree to match the probe tree.

44. The apparatus of claim 37, wherein the computing platform is further so that the tree to be represented comprises a binary edge labeled tree.

45. The apparatus of claim 37, wherein the probe numeral to comprise a query to the one or more XML documents.

46. The apparatus of claim 37, wherein the tree to comprise a known pattern and the probe numeral to comprise one or more features of a subject.

47. The apparatus of claim 37, wherein the computing platform is further to:

generate a first array of target numerals to comprise numerals in the form of binary digital signals to be associated with the rooted partial subtrees of the tree; and

update the first array of target numerals to be based at least in part on a combination of the one or more target numerals to represent the tree with the numerals of the first array of target numerals.

48. The apparatus of claim 47, wherein the computing platform is further to:

generate a second array of target numerals to comprise numerals in the form of binary digital signals to be associated with the rooted partial subtrees of the tree; and

wherein the comparison of the probe numeral with the one or more target numerals to comprise a comparison of the probe numeral with the numerals of the first array of target numerals and with the numerals of the second array of target numerals.

49. An article comprising:

a non-transitory storage medium comprising binary digital signals stored thereon indicative of a presence of a subtree in a tree, the binary digital signals being based, at least in part, on;

a representation of the tree, comprising at least a node or an edge, as one or more target numerals substantially in accordance with transformation of the tree to the one or more target numerals based at least in part on an association of trees and numerals, wherein the tree comprises one or more XML documents, the one or more XML documents comprising one or more electrical digital signals,

an identification of a plurality of partial subtrees of the tree, the plurality of partial subtrees also in the form of binary digital signals;

an enumeration of rooted partial subtrees of the identified plurality of partial subtrees; and

an association of the one or more target numerals with the enumerated rooted partial subtrees; and

a comparison of a probe numeral with the one or more target numerals, the probe numeral based, at least in part, on the association of trees and numerals, and wherein a match between the probe numeral and at least one of the one or more target numerals is indicative of a presence of content in one or more XML documents.

50. The article of claim 49, wherein the binary digital signals are further based, at least in part on:

a determination of the one or more target numerals based, at least in part, on an association of numerals with the rooted partial subtrees of the plurality of partial subtrees.

51. The article of claim 50, wherein the identification of the plurality of partial subtrees of the tree is further based, at least in part, on:

an identification of non-terminal nodes of the tree as root nodes of the plurality of partial subtrees; and

an identification of one or more nodes descending from a root node of at least one of the plurality of partial subtrees as one or more nodes of an enumerated one of the rooted partial subtrees.

52. The article of claim 51, wherein the identification of nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises an identification of one or more nodes descending from a root node of at least one of the plurality of partial subtrees down to a depth of one or more nodes of an enumerated one of the rooted partial subtrees.

53. The article of claim 51, wherein the identification of nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises an identification of one or more nodes descending from a root node of at least one of the plurality of partial subtrees as one or more nodes of an enumerated one of the rooted partial subtrees based, at least in part, on node and/or edge label values associated with the one or more nodes.

54. The article of claim 53, wherein the binary digital signals are further based, at least in part, on a determination of the probe numeral based, at least in part, on an association between trees and numerals, and wherein the match to correspond with a partial subtree of the tree matching the probe tree.

55. The article of claim 49, wherein the binary digital signals are further based, at least in part on:

a determination of the probe numeral based, at least in part, on a probe tree, the probe tree comprising a subtree of interest; and

a detection of a presence of the probe tree in the tree based, at least in part, on a match of the probe numeral with at least one of the target numerals.

56. The article of claim 49, wherein the tree comprises a binary edge labeled tree.

57. The article of claim 49, wherein the probe numeral comprises a query to the one or more XML documents.

58. The article of claim 49, wherein the tree comprises a known pattern and the probe numeral comprises one or more features of a subject.

59. The apparatus of claim 49, wherein the binary digital signals are further based, at least in part, on:

a first array of target numerals generated comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

the first array of target numerals updated based at least in part on a combination of the one or more target numerals representing the tree with the numerals of the first array of target numerals.

60. The apparatus of claim 59, wherein the binary digital signals are further based, at least in part, on:

a second array of target numerals generated comprising numerals in the form of binary digital signals associated with the rooted partial subtrees of the tree; and

the comparison of the probe numeral with the one or more target numerals comprising a comparison of the probe numeral with the numerals of the first array of target numerals and with the numerals of the second array of target numerals.