A new iterative algorithm for computing a quality approximate median of strings based on edit operations

Please use this identifier to cite or link to this item: http://hdl.handle.net/10045/37803
Información del item - Informació de l'item - Item information
Title: A new iterative algorithm for computing a quality approximate median of strings based on edit operations
Authors: Abreu Salas, José Ignacio | Rico-Juan, Juan Ramón
Research Group/s: Reconocimiento de Formas e Inteligencia Artificial
Center, Department or Service: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos
Keywords: Approximate median string | Edit distance | Edit operations
Knowledge Area: Lenguajes y Sistemas Informáticos
Issue Date: 15-Jan-2014
Publisher: Elsevier
Citation: Pattern Recognition Letters. 2014, 36: 74-80. doi:10.1016/j.patrec.2013.09.014
Abstract: This paper presents a new algorithm that can be used to compute an approximation to the median of a set of strings. The approximate median is obtained through the successive improvements of a partial solution. The edit distance from the partial solution to all the strings in the set is computed in each iteration, thus accounting for the frequency of each of the edit operations in all the positions of the approximate median. A goodness index for edit operations is later computed by multiplying their frequency by the cost. Each operation is tested, starting from that with the highest index, in order to verify whether applying it to the partial solution leads to an improvement. If successful, a new iteration begins from the new approximate median. The algorithm finishes when all the operations have been examined without a better solution being found. Comparative experiments involving Freeman chain codes encoding 2D shapes and the Copenhagen chromosome database show that the quality of the approximate median string is similar to benchmark approaches but achieves a much faster convergence.
Sponsor: This work is partially supported by the Spanish CICYT under project DPI2006-15542-C04-01, the Spanish MICINN through project TIN2009-14205-CO4-01 and by the Spanish research program Consolider Ingenio 2010: MIPRCV (CSD2007-00018).
URI: http://hdl.handle.net/10045/37803
ISSN: 0167-8655 (Print) | 1872-7344 (Online)
DOI: 10.1016/j.patrec.2013.09.014
Language: eng
Type: info:eu-repo/semantics/article
Peer Review: si
Publisher version: http://dx.doi.org/10.1016/j.patrec.2013.09.014
Appears in Collections:INV - GRFIA - Artículos de Revistas

Files in This Item:
Files in This Item:
File Description SizeFormat 
Thumbnail2014_Abreu_Rico_PRL_final.pdfVersión final (acceso restringido)639,85 kBAdobe PDFOpen    Request a copy
Thumbnail2014_Abreu_Rico_PRL.pdfVersión revisada (acceso abierto)145,1 kBAdobe PDFOpen Preview

Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.