Skip to main content
SpringerLink
Log in
Book cover

International Workshop on Graph-Based Representations in Pattern Recognition

GbRPR 2003: Graph Based Representations in Pattern Recognition pp 71–82Cite as

Tree Edit Distance from Information Theory

  • Conference paper
  • First Online:

  • 568 Accesses

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2726))

Abstract

This paper presents a method for estimating the cost of tree edit operations. The approach poses the problem as that of estimating a generative model for a set of tree samples. The generative model uses the tree-union as the structural archetype for every tree in the distribution and assigns to each node in the archetype the probability that the node is present in a sample. A minimum descriptor length formulation is then used to estimate the structure and parameters of this tree model as well as the node-correspondences between trees in the sample-set and the tree model.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. H. G. Barrow and R. M. Burstall, Subgraph isomorphism, matching relational structures and maximal cliques, Inf. Proc. Letters, Vol. 4, pp.83, 84, 1976.

    Article  MATH  Google Scholar 

  2. H. Bunke and G. Allermann, Inexact graph matching for structural pattern recognition, Pattern Recognition Letters, Vol 1, pp. 245–253, 1983.

    Article  MATH  Google Scholar 

  3. H. Bunke and A. Kandel, Mean and maximum common subgraph of two graphs, Pattern Recognition Letters, Vol. 21, pp. 163–168, 2000.

    Article  Google Scholar 

  4. W. J. Christmas, J. V. Kittler, and M. Petrou, Structural matching in computer vision using probabilistic relaxation, PAMI, Vol. 17(8), pp. 749–764, 1995.

    Google Scholar 

  5. M. A. Eshera and K-S Fu, An image understanding system using attributed symbolic representation and inexact graph-matching, PAMI, Vol 8, pp. 604–618, 1986.

    Google Scholar 

  6. N. Friedman and D. Koller, Being Bayesian about Network Structure, Machine Learning, to appear, 2002

    Google Scholar 

  7. L. Getoor et al., Learning Probabilistic models of relational structure, in 8th Int. Conf. on Machine Learning, 2001.

    Google Scholar 

  8. D. Heckerman, D. Geiger, and D. M. Chickering, Learning Bayesian networks: the combination of knowledge and statistical data, Machine Learning, Vol. 20(3), pp. 197–243, 1995.

    MATH  Google Scholar 

  9. S. Ioffe and D. A. Forsyth, Human Tracking with Mixtures of Trees, ICCV, Vol. I, pp. 690–695, 2001.

    Google Scholar 

  10. X. Jiang, A. Muenger, and H. Bunke, Computing the generalized mean of a set of graphs, in Workshop on Graph-based Representations, GbR’99, pp. 115–124, 2000.

    Google Scholar 

  11. T. Liu and D. Geiger, Approximate Tree Matching and Shape Similarity, ICCV, pp. 456–462, 1999.

    Google Scholar 

  12. B. Luo, et al., A probabilistic framework for graph clustering, in CVPR, pp. 912–919, 2001.

    Google Scholar 

  13. M. Meilă. Learning with Mixtures of Trees. PhD thesis, MIT, 1999.

    Google Scholar 

  14. R. Myers, R. C. Wilson, E. R. Hancock, Bayesian graph edit distance, PAMI, Vol. 22(6), p. 628–635, 2000.

    Google Scholar 

  15. J. Riassen, Stochastic complexity and modeling, Annals of Statistics, Vol. 14, pp. 1080–1100, 1986.

    Article  MathSciNet  Google Scholar 

  16. A. Robles-Kelly and E. R. Hancock, String edit distance, random walks and graph matching, in Structural, Syntactic, and Statistical Pattern Recognition, pp.104–112, LNCS 2396, 2002.

    Chapter  Google Scholar 

  17. A. Sanfeliu and K. S. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man and Cybernetics, 13:353–362, 1983.

    MATH  Google Scholar 

  18. S. Sclaroff and A. P. Pentland, Modal matching for correspondence and recognition, PAMI, Vol. 17, pp. 545–661, 1995.

    Google Scholar 

  19. L. G. Shapiro and R. M. Haralick, Structural descriptions and inexact matching, PAMI, Vol. 3(5), pp. 504–519, 1981.

    Google Scholar 

  20. A. Shokoufandeh, S. J. Dickinson, K. Siddiqi, and S. W. Zucker, Indexing using a spectral encoding of topological structure, in CVPR, 1999.

    Google Scholar 

  21. A. Torsello and E. R. Hancock, Efficiently computing weighted tree edit distance using relaxation labeling, in EMMCVPR, LNCS 2134, pp. 438–453, 2001.

    Google Scholar 

  22. A. Torsello and E. R. Hancock, Matching and embedding through edit-union of trees, in ECCV, LNCS 2352, pp. 822–836, 2002.

    Google Scholar 

  23. A. Torsello and E. R. Hancock, Computing approximate tree edit-distance using relaxation labeling, Pattern REcognition Letters, Vol. 24(8), pp. 1089–1097

    Google Scholar 

  24. R. C. Wilson and E. R. Hancock, Structural matching by discrete relaxation, PAMI, 1997.

    Google Scholar 

  25. A. K. C. Wong and M. You, Entropy and distance of random graphs with application to structural pattern recognition, PAMI, Vol. 7(5), pp. 599–609, 1985.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of York Heslington, York, YO10 5DD, UK

    Andrea Torsello & Edwin R. Hancock

Authors
  1. Andrea Torsello
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edwin R. Hancock
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of York, York, YO1 5DD, UK

    Edwin Hancock

  2. D.I.I.I.E., Università degli Studi di Salerno, Via Ponte don Melillo, 1, 84084, Fisciano (SA), Italy

    Mario Vento

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Torsello, A., Hancock, E.R. (2003). Tree Edit Distance from Information Theory. In: Hancock, E., Vento, M. (eds) Graph Based Representations in Pattern Recognition. GbRPR 2003. Lecture Notes in Computer Science, vol 2726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45028-9_7

Download citation

  • DOI: https://doi.org/10.1007/3-540-45028-9_7

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40452-1

  • Online ISBN: 978-3-540-45028-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation