New partially labelled tree similarity measure: a case study
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/14332
Título: | New partially labelled tree similarity measure: a case study |
---|---|
Autor/es: | Rizo, David | Iñesta, José M. |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Tree edit distance | Multimedia | Music comparison and retrieval |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de creación: | ago-2010 |
Fecha de publicación: | ago-2010 |
Editor: | Springer Berlin / Heidelberg |
Cita 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 |
Resumen: | 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. |
Patrocinador/es: | 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 |
Tipo: | info:eu-repo/semantics/bookPart |
Derechos: | The original publication is available at www.springerlink.com |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1007/978-3-642-14980-1_28 |
Aparece en las colecciones: | INV - GRFIA - Comunicaciones a Congresos, Conferencias, etc. |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ssspr10-cr.pdf | Versión revisada (acceso libre) | 438,53 kB | Adobe PDF | Abrir Vista previa |
ssspr10-cr_final.pdf | Versión final (acceso restringido) | 515,25 kB | Adobe PDF | Abrir Solicitar una copia |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.