Method and/or system for performing tree matching

• US 10,437,886 B2
• Filed: 10/05/2009
• Issued: 10/08/2019
• Est. Priority Date: 06/30/2004
• Status: Expired due to Fees

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. Jenkins
• Inventors: Andrews, Mark, LeTourneau, Jack J.
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US12/573,829
• Publication Number:
  US 20100094885A1
• Time in Patent Office: 3,655 Days
• Field of Search: 707758, 707797, 707999006
• 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 on a processor to;

subdivide a target tree and a query tree;

assign an individual and unique subdivided target tree numeral to at least one of subdivided target tree structures and assign an individual and unique subdivided query tree numeral to at least one of subdivided query tree structures, based at least in part on an association between trees and numerals, wherein the association between trees and numerals comprises to assign a list of individual and unique numerals to an associated list of individual and unique tree structures; and

match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral;

wherein the executing instructions on a processor to subdivide a target tree and a query tree comprises to subdivide the trees so that the size of the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral does not exceed a numeral expressible within a platform native integer of fixed size for the processor.

2. The method of claim 1, wherein the numeral expressible within the platform native integer of fixed size corresponds to a size of data registers in a computing device comprising the processor.

3. The method of claim 1, wherein the size of the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral in a number of bits does not exceed a number of bits in the numeral expressible within the platform native integer of fixed size for the processor.

4. The method of claim 1, and further comprising executing instructions on the processor to:

match another individual and unique subdivided query tree numeral with respect to another individual and unique subdivided target tree numeral.

5. The method of claim 1, wherein the trees comprising binary edge labeled trees (BELTs).

6. The method of claim 1, wherein the query tree comprising a partial subtree.

7. The method of claim 6, wherein the partial subtree comprising a rooted partial subtree.

8. The method of claim 6, wherein the partial subtree comprising a non-rooted partial subtree.

9. The method of claim 1, wherein the query tree comprising a full subtree.

10. The method of claim 1, wherein the executing instructions on the processor to match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral comprises to projection match the subdivided query tree numeral with respect to the subdivided target tree numeral.

11. The method of claim 1, wherein the executing instructions on the processor to match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral comprises to weighted match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral.

12. The method of claim 1, wherein the executing instructions on the processor to match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral comprises to partially match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral.

13. The method of claim 1, wherein the executing instructions on the processor to match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral comprises one of a closest match or a most remote match.

14. An article comprising:

a non-transitory storage medium having stored thereon computer-readable instructions;

a processor able to execute the computer-readable instructions, the executable computer-readable instructions to;

subdivide a target tree and a query tree;

assign an individual and unique subdivided target tree numeral to at least one of subdivided target tree structures and assign an individual and unique subdivided query tree numeral to at least one of subdivided query structures, respectively, with the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral based at least in part on an association between trees and numerals, wherein the association between trees and numerals comprises to assign a list of individual and unique numerals to an associated list of individual and unique tree structures; and

match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral;

wherein the instructions to subdivide the target tree and the query tree comprises to subdivide the trees so that the size of the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral does not exceed a numeral expressible within a platform native integer of fixed size for the processor.

15. The article of claim 14, wherein the numeral expressible within the native integer of fixed size corresponds to size of data registers in a computing device comprising the processor.

16. The article of claim 14, wherein the size of the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral in a number of bits does not exceed a number of bits of the numeral expressible within the platform native integer of fixed size for the processor.

17. The article of claim 14, wherein the instructions further being executable by the processor to match another individual and unique subdivided query tree numeral with respect to another individual and unique subdivided target tree numeral.

18. The article of claim 14, wherein the trees to comprise binary edge labeled trees (BELTs).

19. The article of claim 14, wherein the query tree to comprise a partial subtree.

20. The article of claim 19, wherein the partial subtree to comprise a rooted partial subtree.

21. The article of claim 19, wherein the partial subtree to comprise a non-rooted partial subtree.

22. The article of claim 14, wherein the query tree to comprise a full subtree.

23. An apparatus comprising:

a computing device, the computing device to subdivide a target tree and a query tree, to assign an individual and unique subdivided target tree numeral to at least one of subdivided target tree structures and an individual and unique subdivided query tree numeral to at least one of subdivided query tree structures, respectively, based at least in part on an association between trees and numerals, wherein the association between trees and numerals comprises to assign a list of individual and unique numerals to an associated list of individual and unique tree structures; and

to match the individual and unique subdivided query tree numeral with respect to the individual and unique subdivided target tree numeral;

wherein the computing device to subdivide the trees comprises to subdivide the trees so that a size of the individual and unique subdivided query tree numeral and the individual and unique subdivided target tree numeral do not exceed a numeral expressible within a platform native integer of fixed size for a processor.

24. The apparatus of claim 23, wherein the numeral expressible within the platform native integer of fixed size to correspond to a size of data registers in the computing device to comprise the processor.

25. The apparatus of claim 23, wherein the size of the individual and unique subdivided target tree numeral and the individual and unique subdivided query tree numeral in a number of bits does not exceed a number of bits for the numeral expressible for the platform native integer of fixed size for the computing device.

26. The apparatus of claim 23, wherein the computing device is further to match another individual and unique subdivided query tree numeral with respect to another individual and unique subdivided target tree numeral.

27. The apparatus of claim 23, wherein the trees to comprise binary edge labeled trees (BELTs).

28. The apparatus of claim 23, wherein the query tree to comprise a partial subtree.

29. The apparatus of claim 28, wherein the partial subtree to comprise a rooted partial subtree.

30. The apparatus of claim 28, wherein the partial subtree to comprise a non-rooted partial subtree.

31. The apparatus of claim 23, wherein the query tree to comprise a full subtree.