Method and/or system for simplifying tree expressions such as for query reduction

• US 9,646,107 B2
• Filed: 12/07/2004
• Issued: 05/09/2017
• Est. Priority Date: 05/28/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: LeTourneau, Jack J.
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US11/007,139
• Publication Number:
  US 20050267908A1
• Time in Patent Office: 4,536 Days
• Field of Search: 707 2- 3, 707100-101, 715513
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments of methods, apparatuses, devices and/or systems for simplifying tree expressions, such as for pattern matching, are disclosed.

Claims

1. A method of using pattern matching on a complex tree expression of a complex tree hierarchy, the method comprising:

forming another complex tree expression for a rooted partial subtree query using, at least in part, a plurality of operations usable for determining a one-to-one association between tree hierarchies and natural numerals;

forming the complex tree expression for the complex tree hierarchy using at least in part the plurality of operations usable for determining the one-to-one association between tree hierarchies and natural numerals;

reducing, using at least in part a plurality of algebraic expressions, the formed complex tree expression for the complex tree hierarchy into a plurality of interrelated portions; and

comparing the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression.

2. The method of claim 1, wherein the plurality of operations comprise at least one of an inversion operation or a merger operation.

3. The method of claim 1, wherein the plurality of operations comprise at least one of a zero-push or a one-push operation.

4. The method of claim 3, wherein the zero-push operation comprises, at least in part, adding a child node and an edge to a parent node and labeling the added edge with a binary zero.

5. The method of claim 3, wherein the one-push operation comprises, at least in part, adding a child node and an edge to a parent node and labeling the added edge with a binary one.

6. The method of claim 1, wherein the plurality of interrelated portions comprise one or more queries.

7. The method of claim 6, wherein the one or more queries are interrelated by one or more Boolean operations.

8. The method of claim 1, wherein the plurality of algebraic expressions comprise one or more basis expressions.

9. The method of claim 1, wherein the complex tree hierarchy comprises an ordered tree hierarchy.

10. The method of claim 1, wherein the comparing the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression comprises identifying at least one partial match, at least one match, or a combination thereof.

11. The method of claim 10 further comprising generating one or more matching portions from the reduced plurality of interrelated portions.

12. The method of claim 10 further comprising generating a Boolean true or false responsive to an identification of a match or a partial match between the another complex tree expression for the rooted partial subtree query and the reduced plurality of interrelated portions for the complex tree expression.

13. The method of claim 1 further comprising using, at least in part, one or more algebraic expressions on at least one of the plurality of interrelated portions to manipulate the complex tree hierarchy.

14. The method of claim 13, wherein to manipulate the complex tree hierarchy comprises merging the at least one of the plurality of interrelated portions with a portion of a second complex tree hierarchy.

15. An article comprising:

a non-transitory storage medium, the storage medium having stored thereon instructions executable to;

form a complex tree expression for a complex tree hierarchy via use at least in part of a plurality of operations to determine a one-to-one association between tree hierarchies and natural numerals;

form another complex tree expression for a rooted partial subtree query using, at least in part, the plurality of operations usable to determine a one-to-one association between tree hierarchies and natural numerals;

reduce, via use at least in part of a plurality of algebraic expressions, the formed complex tree expression for the complex tree hierarchy into a plurality of interrelated portions; and

compare the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression.

16. The article of claim 15, wherein the plurality of operations to comprise at least one of an inversion operation or a merger operation.

17. The article of claim 15, wherein the plurality of operations to comprise at least one of a zero-push or a one-push operation.

18. The article of claim 17, wherein the zero-push operation to comprise, at least in part, addition of a child node and an edge to a parent node and addition of a binary zero label to the edge.

19. The article of claim 17, wherein the one-push operation to comprise, at least in part, addition of a child node and an edge to a parent node and addition of a binary one label to the edge.

20. The article of claim 15, wherein the plurality of interrelated portions to comprise one or more queries.

21. The article of claim 20, wherein the one or more queries are to be interrelated by one or more Boolean operations.

22. The article of claim 15, wherein the plurality of algebraic expressions to comprise one or more basis expressions.

23. The article of claim 15, wherein the complex tree hierarchy to comprise an ordered tree hierarchy.

24. The article of claim 15, wherein the instructions executable to compare the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression comprise instructions executable to identify at least one partial match, at least one match, or a combination thereof.

25. The article of claim 24, wherein the non-transitory storage medium further comprises instructions executable to:

generate one or more matching portions from the reduced plurality of interrelated portions.

26. The article of claim 24, wherein the non-transitory storage medium further comprises instructions executable to:

generate a Boolean true or false responsive to an identification of a match or a partial match between the another complex tree expression for the rooted partial subtree query and the reduced plurality of interrelated portions for the complex tree expression.

27. The article of claim 15, wherein the non-transitory storage medium further comprises instructions executable to:

use, at least in part, one or more algebraic expressions on at least one of the plurality of interrelated portions to manipulate the complex tree hierarchy.

28. The article of claim 27, wherein the non-transitory storage medium further comprises executable instructions to manipulate the complex tree hierarchy so as to merge the at least one of the plurality of interrelated portions with a portion of a second complex tree hierarchy.

29. An apparatus comprising:

means for forming a complex tree expression for a complex tree hierarchy using at least in part a plurality of operations usable for determining a one-to-one association between tree hierarchies and natural numerals;

means for forming another complex tree expression for a rooted partial subtree query using, at least in part, the plurality of operations usable for determining the one-to-one association between tree hierarchies and natural numerals;

means for reducing, using at least in part a plurality of algebraic expressions, the formed complex tree expression for the complex tree hierarchy into a plurality of interrelated portions; and

means for comparing the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression.

30. The apparatus of claim 29, wherein the plurality of operations comprise at least one of an inversion operation or a merger operation.

31. The apparatus of claim 29, wherein the plurality of operations comprise at least one of a zero-push or a one-push operation.

32. The apparatus of claim 31, wherein the means for forming the tree expression using at least in part the zero-push operation comprises, at least in part, means for adding a child node and an edge to a parent node and labeling the added edge with a binary zero.

33. The apparatus of claim 31, wherein the means for forming the tree expression using at least in part the one-push operation comprises, at least in part, means for adding a child node and an edge to a parent node and labeling the added edge with a binary one.

34. The apparatus of claim 29, wherein the plurality of interrelated portions comprise one or more queries.

35. The apparatus of claim 34, wherein the one or more queries are interrelated by one or more Boolean operations.

36. The apparatus of claim 29, wherein the plurality of algebraic expressions comprise one or more basis expressions.

37. The apparatus of claim 29, wherein the complex tree hierarchy comprises an ordered tree hierarchy.

38. The apparatus of claim 29 further comprising means for identifying at least one partial match, at least one match, or a combination thereof based, at least in part, on the comparison of the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression.

39. The apparatus of claim 38 further comprising means for generating one or more matching portions from the reduced plurality of interrelated portions.

40. The apparatus of claim 38 further comprising means for generating a Boolean true or false responsive to an identification of a match or a partial match between the another complex tree expression for the rooted partial subtree query and the reduced plurality of interrelated portions for the complex tree expression.

41. The apparatus of claim 29, wherein the means for reducing the formed tree expression further comprises means for using, at least in part, one or more algebraic expressions on at least one of the plurality of interrelated portions to manipulate the complex tree hierarchy.

42. The apparatus of claim 41, wherein the means for using, at least in part, one or more algebraic expressions to manipulate the complex hierarchy comprises means for merging the at least one of the plurality of interrelated portions with a portion of a second complex tree hierarchy.

43. An apparatus comprising:

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

form a complex tree expression for a complex tree hierarchy via use at least in part of a plurality of operations to determine a one-to-one association between tree hierarchies and natural numerals;

form another complex tree expression for a rooted partial subtree query using, at least in part, the plurality of operations usable to determine the one-to-one association between tree hierarchies and natural numerals;

reduce, via use at least in part of a plurality of algebraic expressions, the formed complex tree expression for the complex tree hierarchy into a plurality of interrelated portions; and

compare the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression.

44. The apparatus of claim 43, wherein the plurality of operations to comprise at least one of an inversion operation or a merger operation.

45. The apparatus of claim 43, wherein the plurality of operations to comprise at least one of a zero-push or a one-push operation.

46. The apparatus of claim 45, wherein the zero-push operation to comprise, at least in part, addition of a child node and an edge to a parent node and addition of a binary zero label to the edge.

47. The apparatus of claim 45, wherein the one-push operation to comprise, at least in part, addition of a child node and an edge to a parent node and addition of a binary one label to the edge.

48. The apparatus of claim 43, wherein the plurality of interrelated portions to comprise one or more queries.

49. The apparatus of claim 48, wherein the one or more queries are to be interrelated by one or more Boolean operations.

50. The apparatus of claim 43, wherein the plurality of algebraic expressions to comprise one or more basis expressions.

51. The apparatus of claim 43, wherein the complex tree hierarchy to comprise an ordered tree hierarchy.

52. The apparatus of claim 43, wherein the one or more processors programmed with instructions executable to compare the another complex tree expression for the rooted partial subtree query with the reduced plurality of interrelated portions for the complex tree expression comprise instructions executable to identify at least one partial match, at least one match, or a combination thereof.

53. The apparatus of claim 52, wherein the one or more processors are further programmed with instructions executable to:

generate one or more matching portions from the reduced plurality of interrelated portions.

54. The apparatus of claim 52, wherein the one or more processors are further programmed with instructions executable to:

generate a Boolean true or false responsive to an identification of a match or a partial match between the another complex tree expression for the rooted partial subtree query and the reduced plurality of interrelated portions for the complex tree expression.

55. The apparatus of claim 43, wherein the one or more processors are further programmed with instructions executable to:

use, at least in part, one or more algebraic expressions on at least one of the plurality of interrelated portions to manipulate the complex tree hierarchy.

56. The apparatus of claim 55, wherein the one or more processors are further programmed with instructions executable to merge the at least one of the plurality of interrelated portions with a portion of a second complex tree hierarchy.