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
Full metadata record
Full metadata record
DC FieldValueLanguage
dc.contributorReconocimiento de Formas e Inteligencia Artificiales
dc.contributor.authorAbreu Salas, José Ignacio-
dc.contributor.authorRico Juan, Juan Ramón-
dc.contributor.otherUniversidad de Alicante. Departamento de Lenguajes y Sistemas Informáticoses
dc.date.accessioned2014-06-03T09:14:34Z-
dc.date.available2014-06-03T09:14:34Z-
dc.date.issued2014-01-15-
dc.identifier.citationPattern Recognition Letters. 2014, 36: 74-80. doi:10.1016/j.patrec.2013.09.014es
dc.identifier.issn0167-8655 (Print)-
dc.identifier.issn1872-7344 (Online)-
dc.identifier.urihttp://hdl.handle.net/10045/37803-
dc.description.abstractThis 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.es
dc.description.sponsorshipThis 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).es
dc.languageenges
dc.publisherElsevieres
dc.subjectApproximate median stringes
dc.subjectEdit distancees
dc.subjectEdit operationses
dc.subject.otherLenguajes y Sistemas Informáticoses
dc.titleA new iterative algorithm for computing a quality approximate median of strings based on edit operationses
dc.typeinfo:eu-repo/semantics/articlees
dc.peerreviewedsies
dc.identifier.doi10.1016/j.patrec.2013.09.014-
dc.relation.publisherversionhttp://dx.doi.org/10.1016/j.patrec.2013.09.014es
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses
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.