Method and/or system for performing tree matching

• US 7,620,632 B2
• Filed: 12/07/2004
• Issued: 11/17/2009
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Skyler Technology Incorporated
• Inventors: Andrews, Mark
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): TIMBLIN, ROBERT M
• Application Number:
  US11/006,848
• Publication Number:
  US 20060004817A1
• Time in Patent Office: 1,806 Days
• Field of Search: 707/100.S, 707/2, 707/3, 707/6, 707/101, 707/102, 715/500.S
• 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:

executing instructions by a processor to;

subdivide a target tree and a query tree, said target tree being associated with a target tree numeral according to an association between trees and numerals, said query tree being associated with a query tree numeral according to said association;

associate at least one of said subdivided target trees with one or more electrical digital signals representative of one or more subdivided target tree numerals based, at least in part, on said target tree numeral;

associate at least one of said subdivided query trees with one or more electrical digital signals representative of one or more subdivided query tree numerals based, at least in part, on said query tree numeral; and

apply said at least one of the subdivided query trees to said at least one of the subdivided target trees based, at least in part, on a comparison of one or more electrical digital signals representative of said one or more subdivided target tree numerals with one or more electrical digital signals representative of said one or more subdivided query tree numerals,

wherein said target trees numeral is an integer, and wherein said one or more subdivided target tree numerals comprises integer factors of said target tree numeral such that dividing said target tree numeral by a subdivided target tree numeral provides an integer quotient.

2. The method of claim 1, and further comprising executing said instructions by said processor to subdivide the trees so that the size of the subdivisions does not exceed a specific threshold.

3. The method of claim 2, and further comprising executing said instructions by said processor to subdivide 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, and wherein said specific threshold comprises a platform native integer of fixed size for said processor.

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

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

executing said instructions by said processor to apply one or more electrical digital signals representative of said query tree to one or more electrical digital signals representative of 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. The method of claim 1, wherein said query tree numeral is an integer, and wherein said one or more subdivided query tree numerals comprise an integer factor of said query tree numeral such that dividing said query tree numeral by a subdivided query tree numeral provides an integer quotient.

14. The method of claim 5, wherein said target tree is subdivided such that said one or more subdivided target tree numerals do not exceed said native integer of fixed size for said processor.

15. The method of claim 5, wherein said query tree is subdivided such that said one or more subdivided query tree numerals subdivided query tree numerals do not exceed said native integer of fixed size for said processor.

16. An article comprising:

a storage medium having stored thereon instructions that, in response to being executed by a processor, direct said processor to;

subdivide a target tree and a query tree, said target tree being associated with a target tree numeral according to an association between trees and numerals, said query tree being associated with a query tree numeral according to said association;

associating at least one of said subdivided target trees with one or more electrical digital signals representative of one or more subdivided target tree numerals based, at least in part, on said target tree numeral;

associating at least one of said subdivided query trees with one or more electrical digital signals representative of one or more subdivided query tree numerals based, at least in part, on said query tree numeral; and

applying the subdivided query tree to the subdivided target tree based, at least in part, on a comparison of said one or more electrical digital signals representative of said one or more subdivided target tree numerals with one or more electrical digital signals representative of said one or more subdivided query tree numerals,

wherein said target tree numeral is an integer, and wherein said one or more subdivided target tree numerals comprises integer factors of said target tree numeral such that dividing said target tree numeral by a subdivided target tree numeral provides an integer quotient.

17. The article of claim 16, wherein said instructions, in response to being executed by said processor, further direct said processor to subdivide said target tree and said query tree by subdividing the trees so that the size of the subdivisions does not exceed a specific threshold.

18. The article of claim 17, wherein said instructions, in response to being executed by said processor, further direct said processor to subdivide said target tree and said query tree by subdividing the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

19. The article of claim 17, wherein said specific threshold comprises a particular number of nodes.

20. The article of claim 17, wherein said specific threshold comprises a platform native integer of fixed size for said processor.

21. The article of claim 17, wherein said subdivisions are associated with natural numerals and said specific threshold comprising a natural numeral.

22. The article of claim 16, wherein said instructions, in response to being executed by said processor, are further adapted to direct said processor to apply said query tree to said subdivided target trees.

23. The article of claim 16, wherein comprise binary edge labeled trees (BELTs).

24. The article of claim 16, wherein, said query tree comprises a partial subtree.

25. The article of claim 24, wherein said partial subtree comprises a rooted partial subtree.

26. The article of claim 24, wherein said partial subtree comprise a non-rooted partial subtree.

27. The article of claim 16, wherein said query tree comprises a full subtree.

28. The article of claim 16, wherein said query tree numeral is an integer, and wherein said one or more subdivided query tree numerals comprise an integer factor of said query tree numeral such that dividing said query tree numeral by a subdivided query tree numeral provides an integer quotient.

29. The article of claim 20, wherein said target tree is subdivided such that said one or more subdivided target tree numerals do not exceed said native integer of fixed size for said processor.

30. The article of claim 20, wherein said query tree is subdivided such that said one or more subdivided query tree numerals subdivided query tree numerals do not exceed said native integer of fixed size for said processor.

31. An apparatus comprising:

means, comprising a processor, for subdividing a target tree and a query tree, said target tree being associated with a target tree numeral according to an association between trees and numerals, said query tree being associated with a query tree numeral according to said association;

means, comprising said processor, for associating at least one of said subdivided target trees with one or more subdivided target tree numerals based, at least in part, on said target tree numeral;

means, comprising said processor, for associating at least one of said subdivided query trees with one or more subdivided query tree numerals based, at least in part, on said query tree numeral; and

means, comprising said processor, for applying the subdivided query tree to the subdivided target tree based, at least in part, on a comparison of said one or more subdivided target tree numerals with said one or more subdivided query tree numerals.

wherein said target tree numeral is an integer, and wherein said one or more subdivided target tree numerals comprises integer factors of said target tree numeral such that dividing said target tree numeral by a subdivided target tree numeral provides an integer guotient.

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

33. The apparatus of claim 32, 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.

34. The apparatus of claim 32, 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.

35. The apparatus of claim 32, wherein said specific threshold comprises a platform native integer of fixed size for said processor.

36. The apparatus of claim 32, 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.

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

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

39. The apparatus of claim 31, wherein said query tree comprises a partial subtree.

40. The apparatus of claim 39, wherein said partial subtree comprises a rooted partial subtree.

41. The apparatus of claim 39, wherein said partial subtree comprises a non-rooted partial subtree.

42. The apparatus of claim 31, wherein said query tree comprises a full subtree.

43. The apparatus of claim 31, wherein said query tree numeral is an integer, and wherein said one or more subdivided query tree numerals comprise an integer factor of said query tree numeral such that dividing said query tree numeral by a subdivided query tree numeral provides an integer quotient.

44. The apparatus of claim 35, wherein said target tree is subdivided such that said one or more subdivided target tree numerals do not exceed said native integer of fixed size for said processor.

45. The apparatus of claim 35, wherein said query tree is subdivided such that said one or more subdivided query tree numerals subdivided query tree numerals do not exceed said native integer of fixed size for said processor.

46. An apparatus comprising:

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

subdivide a target tree and a query tree, said target tree being associated with a target tree numeral according to an association between trees and numerals, said query tree being associated with a query tree numeral according to said association;

associate at least one of said subdivided target trees with one or more electrical digital signals representative of one or more subdivided target tree numerals based, at least in part, on said target tree numeral;

associate at least one of said subdivided query trees with one or more electrical digital signals representative of one or more subdivided query tree numerals based, at least in part, on said query tree numeral; and

apply the subdivided query tree to the subdivided target tree based, at least in part, on a comparison of said one or more signals representative of said one or more subdivided target tree numerals with said one or more signals representative of said one or more subdivided query tree numerals,

wherein said target tree numeral is an integer, and wherein said one or more subdivided target tree numerals comprises integer factors of said target tree numeral such that dividing said target tree numeral by a subdivided target tree numeral provides an integer guotient.

47. The apparatus of claim 46, wherein said one or more processors are further programmed with instructions to subdivide the trees so that the size of the subdivisions does not exceed a specific threshold.

48. The apparatus of claim 47, wherein said one or more processors are further programmed with instructions to subdivide the trees so that the subdivisions are the largest subdivisions of the trees without exceeding said specific threshold.

49. The apparatus of claim 47, wherein said specific threshold comprises a particular number of nodes.

50. The apparatus of claim 47, wherein said specific threshold comprises a platform native integer of fixed size for said computing platform.

51. The apparatus of claim 47, wherein said specific threshold comprises a natural numeral.

52. The apparatus of claim 46, wherein said one or more processors are further programmed with instructions to apply said query tree to said subdivided target trees.

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

54. The apparatus of claim 46, wherein said query tree comprises a partial subtree.

55. The apparatus of claim 54, wherein said partial subtree comprises a rooted partial subtree.

56. The apparatus of claim 54, wherein said partial subtree comprises a non-rooted partial subtree.

57. The apparatus of claim 46, wherein said query tree comprises a full subtree.

58. The apparatus of claim 46, wherein said query tree numeral is an integer, and wherein said one or more subdivided query tree numerals comprise an integer factor of said query tree numeral such that dividing said query tree numeral by a subdivided query tree numeral provides an integer quotient.

59. The apparatus of claim 50, wherein said target tree is subdivided such that said one or more subdivided target tree numerals do not exceed said native integer of fixed size for said processor.

60. The apparatus of claim 50, wherein said query tree is subdivided such that said one or more subdivided query tree numerals subdivided query tree numerals do not exceed said native integer of fixed size for said processor.