Rizo, David, Iñesta, José M.
New partially labelled tree similarity measure: a case study
RIZO VALERO, David; IÑESTA QUEREDA, José Manuel. "New partially labelled tree similarity measure: a case study". En: Structural, Syntactic, and Statistical Pattern Recognition : Joint IAPR International Workshop, SSPR&SPR 2010, Cesme, Izmir, Turkey, August 18-20, 2010, Proceedings / ed. by Edwin R. Hancock, Richard C. Wilson, Terry Windeatt, Ilkay Ulusoy and Francisco Escolano. Berlin : Springer, 2010. (Lecture Notes in Computer Science; 6218). ISBN 978-3-642-14979-5, pp. 296-305
URI: http://hdl.handle.net/10045/14332
DOI: 10.1007/978-3-642-14980-1_28
ISSN: 0302-9743
ISBN: 978-3-642-14979-5
Abstract: 
Trees are a powerful data structure for representing data for which hierarchical relations can be defined. They have been applied in a number of fields like image analysis, natural language processing, protein structure, or music retrieval, to name a few. Procedures for comparing trees are very relevant in many task where tree representations are involved. The computation of these measures is usually a time consuming tasks and different authors have proposed algorithms that are able to compute them in a reasonable time, through approximated versions of the similarity measure. Other methods require that the trees are fully labelled for the distance to be computed. In this paper, a new measure is presented able to deal with trees labelled only at the leaves, that runs in O(|TA|×|TB|) time. Experiments and comparative results are provided.
Keywords:Tree edit distance, Multimedia, Music comparison and retrieval
Springer Berlin / Heidelberg
info:eu-repo/semantics/bookPart