Method and/or system for performing tree matching

• US 20060004817A1
• Filed: 12/07/2004
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• 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: Andrews, Mark
• Granted Patent: US 7,620,632 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Embodiments of methods, apparatuses, devices and/or systems for performing tree matching are disclosed.

Claims

1. A method of performing tree matching comprising:

subdividing a target tree and a query tree; and

applying at least one of the subdivided query trees to at least one of the subdivided target trees.

2. The method of claim 1, wherein said subdividing comprises subdividing the trees so that the size of the subdivisions does not exceed a specific threshold.

3. The method of claim 2, wherein said subdividing comprises subdividing the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

4. The method of claim 2, wherein said specific threshold comprises a particular number of nodes.

5. The method of claim 2, wherein tree matching is executed by a computing device, and wherein said specific threshold comprises the platform native integer of fixed size for said computing device.

6. The method of claim 5, wherein said subdivisions are associated with natural numerals and said specific threshold comprises a natural numeral.

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

applying said query tree to said subdivided target trees.

8. The method of claim 1, wherein said trees comprise binary edge labeled trees (BELTs).

9. The method of claim 1, wherein said query tree comprises a partial subtree.

10. The method of claim 9, wherein said partial subtree comprises a rooted partial subtree.

11. The method of claim 9, wherein said partial subtree comprises a non-rooted partial subtree.

12. The method of claim 1, wherein said query tree comprises a full subtree.

13. An article comprising:

a storage medium having stored thereon instructions that, when executed, result in at least a method of performing tree matching as follows;

subdividing a target tree and a query tree; and

applying the subdivided query tree to the subdivided target tree.

14. The article of claim 13, wherein said instructions, when executed, further result in:

said subdividing comprising subdividing the trees so that the size of the subdivisions does not exceed a specific threshold.

15. The article of claim 14, wherein said instructions, when executed, further result in:

said subdividing comprising subdividing the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

16. The article of claim 14, wherein said instructions, when executed, further result in:

said specific threshold comprising a particular number of nodes.

17. The article of claim 14, wherein said instructions, when executed, further result in:

tree matching being executed by a computing device, and said specific threshold comprising the platform native integer of fixed size for said computing device.

18. The article of claim 14, wherein said instructions, when executed, further result in:

said subdivisions being associated with natural numerals and said specific threshold comprising a natural numeral.

19. The article of claim 13, wherein said instructions, when executed, further result in:

applying said query tree to said subdivided target trees.

20. The article of claim 13, wherein said instructions, when executed, further result in:

said trees comprising binary edge labeled trees (BELTs).

21. The article of claim 13, wherein said instructions, when executed, further result in:

said query tree comprising a partial subtree.

22. The article of claim 21, wherein said instructions, when executed, further result in:

said partial subtree comprising a rooted partial subtree.

23. The article of claim 21, wherein said instructions, when executed, further result in:

said partial subtree comprising a non-rooted partial subtree.

24. The article of claim 13, wherein said instructions, when executed, further result in:

said query tree comprising a full subtree.

25. An apparatus comprising:

means for subdividing a target tree and a query tree; and

means for applying the subdivided query tree to the subdivided target tree.

26. The apparatus of claim 25, wherein said means for subdividing comprises means for subdividing the trees so that the size of the subdivisions does not exceed a specific threshold.

27. The apparatus of claim 26, wherein said means for subdividing the trees so that the size of the subdivisions do not exceed a specific threshold comprising means for subdividing the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

28. The apparatus of claim 26, wherein said means for subdividing comprising means for subdividing the trees so that the size of the subdivisions do not exceed a specific threshold, said specific threshold comprising a particular number of nodes.

29. The apparatus of claim 26, wherein tree matching is executed by means for computing, and said specific threshold comprises the platform native integer of fixed size for said means for computing.

30. The apparatus of claim 26, wherein said means for subdividing comprising means for subdividing the trees so that the size of the subdivisions do not exceed a specific threshold, said specific threshold comprising a natural numeral.

31. The apparatus of claim 25, and further comprising means for applying said query tree to said subdivided target trees.

32. The apparatus of claim 25, wherein said trees comprise binary edge labeled trees (BELTs).

33. The apparatus of claim 25, wherein said query tree comprises a partial subtree.

34. The apparatus of claim 33, wherein said partial subtree comprises a rooted partial subtree.

35. The apparatus of claim 33, wherein said partial subtree comprises a non-rooted partial subtree.

36. The apparatus of claim 25, wherein said query tree comprises a full subtree.

37. A tree match formed by at least:

a target tree and a query tree having been subdivided; and

the subdivided query tree having been applied to the subdivided target tree.

38. The tree match of claim 37, wherein said subdivided target tree and said subdivided query tree being subdivided so that the size of the subdivisions does not exceed a specific threshold.

39. The tree match of claim 38, wherein the trees having been subdivided so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

40. The tree match of claim 38, wherein said specific threshold comprises a particular number of nodes.

41. The tree match of claim 38, wherein the tree matching having been executed by a computing device, and wherein said specific threshold comprises the platform native integer of fixed size for said computing device.

42. The tree match of claim 38, wherein said subdivisions are associated with natural numerals and said specific threshold comprises a natural numeral.

43. The tree match of claim 37, and further including:

said query tree having been applied to said subdivided target trees.

44. The tree match of claim 37, wherein said trees comprise binary edge labeled trees (BELTs).

45. The tree match of claim 37, wherein said query tree comprises a partial subtree.

46. The tree match of claim 45, wherein said partial subtree comprises a rooted partial subtree.

47. The tree match of claim 45, wherein said partial subtree comprises a non-rooted partial subtree.

48. The tree match of claim 37, wherein said query tree comprises a full subtree.

49. An apparatus comprising:

a computing platform, said computing platform being adapted to subdivide a target tree and a query tree and apply the subdivided query tree to the subdivided target tree.

50. The apparatus of claim 49, wherein said computing platform is further adapted to subdivide the trees so that the size of the subdivisions does not exceed a specific threshold.

51. The apparatus of claim 50, wherein said computing platform is further adapted to subdivide the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

52. The apparatus of claim 50, wherein said specific threshold comprising a particular number of nodes.

53. The apparatus of claim 50, wherein tree matching is executed by said computing platform, and said specific threshold comprises the platform native integer of fixed size for said computing platform.

54. The apparatus of claim 50, wherein said computing platform is further adapted to associated said subdivisions with natural numerals;

said specific threshold comprising a natural numeral.

55. The apparatus of claim 49, wherein said computing platform is further adapted to apply said query tree to said subdivided target trees.

56. The apparatus of claim 49, wherein said trees comprise binary edge labeled trees (BELTs).

57. The apparatus of claim 49, wherein said query tree comprises a partial subtree.

58. The apparatus of claim 57, wherein aid partial subtree comprises a rooted partial subtree.

59. The apparatus of claim 57, wherein said partial subtree comprises a non-rooted partial subtree.

60. The apparatus of claim 49, wherein said query tree comprises a full subtree.