Method of comparing the closeness of a target tree to other...

Details Method of comparing the closeness of a target tree to other... Method of comparing the closeness of a target tree to other...

2007-10-23

2007-10-23

Gaffin, Jeffrey (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

10116970

ABSTRACT:
A method of comparing the closeness of a target tree to other trees located in a database of trees, said method comprising the steps of: (a) calculating a constraint in respect of each tree in the database based on an estimated number of edit operations and a characteristic of the target tree; (b) calculating a constrained tree edit distance between the target tree and each tree in the database using the constraint obtained in step (a); and (c) comparing the calculated constrained tree edit distances. The method can also be applied to matching a target tree representable structure to its closest tree representable structure.

REFERENCES:
patent: 5761538 (1998-06-01), Hull
patent: 5836003 (1998-11-01), Sadeh
patent: 6219833 (2001-04-01), Solomon et al.
patent: 6260042 (2001-07-01), Curbera et al.
patent: 6289354 (2001-09-01), Aggarwal et al.
patent: 6377945 (2002-04-01), Risvik
patent: 6446068 (2002-09-01), Kortge
patent: 6647141 (2003-11-01), Li
patent: 6662180 (2003-12-01), Aref et al.
patent: 6742003 (2004-05-01), Heckerman et al.
patent: 6778970 (2004-08-01), Au
patent: 2002/0193981 (2002-12-01), Keung et al.
patent: 2003/0061213 (2003-03-01), Yu et al.
patent: 2003/0144994 (2003-07-01), Wen et al.
patent: 2003/0163437 (2003-08-01), Lee
patent: 2005/0027681 (2005-02-01), Bernstein et al.
patent: 2279678 (2001-02-01), None
B. John Oommen, and Richar Loke. On the Pattern Recognition of Noisy Subsequence Trees. IEEE 2001.
B. John Oommen and R. L. Kashyap. A Formal Theory For Optimal and Information Theoretic Syntactic Pattern Recognition. Pergamon. Pattern Recognition, vol. 31, No. 8, pp. 1159-1177, 1998.
B. John Oommen, K. Zhang, W. Lee. Numerical Similarity and Dissimilarity Measures Between Two Trees. IEEE 1996.
Kaizhong Zhang. Algorithms for The Constrained Editing Distance Between Ordered Labeled Trees and Related Problem. Dept. of Computer Science, The University of Western Ontario, London, Ontario, Canada. Received Dec. 29, 1993.
DasGupta B., He X., Jiang, T., Li M., Tromp J., & Zhang, L. On Distances Between Phylogenetic Trees (Extended Abstract). Society for Industrial & Applied Mathematics, Philadelphia, PA. 1997.
B.J. Oommen and R.L. Kashyap, “A Formal Theory for Optimal and Information Theoretic Syntactic Pattern Recognition” (Pattern Recognition) 1998, 1159-1177; 31(8).
B. J. Oommen and R.K.S. Loke, “The Noisy Subsequences Tree Recognition Problem”, (Proc. of SSPR-98, International Symposium on Syntactic Statistical Pattern Recognition) 1998, 169-180 Sydney, Australia.
B.J. Oommen and R.K.S. Loke, “On Using Parametric String Distances and Vector Quantization in Designing Syntactic Pattern Recognition Systems”, (Proc. of the 1997 IEEE Intl Conf. on Sys., Man and Cybernetics) Oct. 1997, 511-517 Orlando, Florida.
B.J. Oommen et al., “Numerical Similarity and Dissimilarity Measures Between Two Trees” (IEEE Transactions on Computers) Dec. 1996, 1426-1434; 45.
K. Zhang, “Algorithms For The Constrained Editing Distance Between Ordered Labeled Trees and Related Problems” (Pattern Recognition) 1995, 463-474; 28(3).
B.J. Oommen and W. Lee, “Constrained Tree Editing” (Information Sciences) 1994, 253-273; 77(3-4).
K. Zhang and T. Jiang, “Some MAX SNP-Hard Results Concerning Unordered Labeled Trees”, (Information Processing Letters) 1994, 249-254; 49.
K. Zhang et al. “On the Editing Distance Between Unordered Labeled Trees” (Information Processing Letters) May 25, 1992, 133-139; 42.
K. Zhang et al., “Fast Serial and Paralled Algorithms for Approximate Tree Matching with VLDC's”, (Proc. of the 1992 Symp. on Combinatorial Pattern Matching) 1992, 148-161; 92.
R.M. Haralick and L.G. Shapiro, “Binary Machine Vision” (Addison Wesley) 1992, 13-40 Reading, Mass.
B. Shapiro and K. Zhang, “Compairing Multiple RNA Secondary Structures Using Tree Comparisions”, (Comp Appl Biosci) 1990, 309-318; 6(4).
K. Zhang, “Constrained String and Tree Editing Distance”, (Proceedings of the IASTED International Symposium) 1990, 92-95 New York.
K. Zhang and D. Shasha, “Simple Fast Algorithms For The Editing Distance Between Trees and Related Problems”, (SIAM J. Comput.) Dec. 1989, 1245-1262 18(6).
B. Shapiro, “An Algorithm for Comparing Mutiple RNA Secondary Structures” (Comput. Appl. Biosci.) 1988, 387-393; 4(3).
B.J. Oommen, “Recognition of Noisy Subsequences Using Constrained Edit Distances” (IEEE Trans. Pattern Anal. and Mach. Intell.) Sep. 1987, 676-685; 9(5).
B.J. Oommen, “Constrained String Editing” (Information Sciences) 1986, 40: 267-284.
YC. Chen and SY. Lu, “Waveform Correlation by Tree Matching”, (IEEE Trans. Pattern Anal. and Mach. Intell.) May 1985, 299-305; 7(3).
A. Noetzel and S. Selkow, “An Overview of Sequence Comparison” Sankoff and Kruskal (Eds.) Time Warps, String Edits, and Macromolecules: Theory and Practice of Sequence Comparison, Addison Wesley 1983, 1-43 Chapter 1.
A. Noetzel and S. Selkow, “An Analysis of the General Tree-Editing Problem” Sankoff and Kruskal (Eds.) Time Warps, String Edits, and Macromolecules: Theory and Practice of Sequence Comparison, Addison Wesley 1983, 237-252, Chapter 8.
P.A.V. Hall and G.R. Dowling, “Approximate String Matching” (Comput Sur) Dec. 1980, 381-402; 12(4).
SY. Lu, “A Tree-to-Tree Distance and Its Application to Cluter Analysis”, (IEEE Trans. Pattern Anal. and Mach. Intell.) Apr. 1979, 219-224; 1(2).
KC. Tai, “The Tree-to-Tree Correction Problem”, (J Assoc. for Computing Machinery) Jul. 1979, 422-433; 26(3).
S.M. Selkow, “The Tree-to-Tree Editing Problem”, (Info. Proc. Letters) Dec. 1977, 184-186; 6(6).
R. Lowrance and R.A. Wagner, “An Extension of the String-to-String Correction Problem”, (J. ACM) Apr. 1995, 177-183; 22.
R.A. Wagner and M.J. Fischer, The String-to-String Correction Problem (J. Assoc. Comput. Mach.) Jan. 1974, 168-173; 21.
A.V. Aho et al., The Design and Analysis of Computer Algorithms, (Addison Wesley) 1974, 171-189; 5.
R.O. Duda and P.E. Hart Pattern Classification and Scene Analysis, (John Wiley and Sons) 1973, 1-76; 1.

Affiliated with

Also associated with

Rating

Method of comparing the closeness of a target tree to other... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of comparing the closeness of a target tree to other..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of comparing the closeness of a target tree to other... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3869284