New partially labelled tree similarity measure: a case study
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/14332
Títol: | New partially labelled tree similarity measure: a case study |
---|---|
Autors: | Rizo, David | Iñesta, José M. |
Grups d'investigació o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Paraules clau: | Tree edit distance | Multimedia | Music comparison and retrieval |
Àrees de coneixement: | Lenguajes y Sistemas Informáticos |
Data de creació: | d’agost-2010 |
Data de publicació: | d’agost-2010 |
Editor: | Springer Berlin / Heidelberg |
Citació bibliogràfica: | 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 |
Resum: | 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. |
Patrocinadors: | This work was funded by the Spanish DRIMS project (TIN2009-14247-C02), and the research programme Consolider Ingenio 2010 (MIPRCV, CSD2007-00018). |
URI: | http://hdl.handle.net/10045/14332 |
ISBN: | 978-3-642-14979-5 |
ISSN: | 0302-9743 |
DOI: | 10.1007/978-3-642-14980-1_28 |
Idioma: | eng |
Tipus: | info:eu-repo/semantics/bookPart |
Drets: | The original publication is available at www.springerlink.com |
Revisió científica: | si |
Versió de l'editor: | http://dx.doi.org/10.1007/978-3-642-14980-1_28 |
Apareix a la col·lecció: | INV - GRFIA - Comunicaciones a Congresos, Conferencias, etc. |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
ssspr10-cr.pdf | Versión revisada (acceso libre) | 438,53 kB | Adobe PDF | Obrir Vista prèvia |
ssspr10-cr_final.pdf | Versión final (acceso restringido) | 515,25 kB | Adobe PDF | Obrir Sol·licitar una còpia |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.