Mostrar el registro sencillo del ítem
Speeding up the cyclic edit distance using LAESA with early abandon
dc.contributor.author | Palazón González, Vicente | |
dc.contributor.author | Marzal Varó, Andrés | |
dc.date.accessioned | 2016-05-25T17:25:18Z | |
dc.date.available | 2016-05-25T17:25:18Z | |
dc.date.issued | 2015 | |
dc.identifier.issn | 0167-8655 | |
dc.identifier.uri | http://hdl.handle.net/10234/159984 | |
dc.description.abstract | The cyclic edit distance between two strings is the minimum edit distance between one of this strings and every possible cyclic shift of the other. This can be useful, for example, in image analysis where strings describe the contour of shapes or in computational biology for classifying circular permuted proteins or circular DNA/RNA molecules. The cyclic edit distance can be computed in O(mnlog m) time, however, in real recognition tasks this is a high computational cost because of the size of databases. A method to reduce the number of comparisons and avoid an exhaustive search is convenient. In this work, we present a new algorithm based on a modification of LAESA (linear approximating and eliminating search algorithm) for applying pruning in the computation of distances. It is an efficient procedure for classification and retrieval of cyclic strings. Experimental results show that our proposal considerably outperforms LAESA | ca_CA |
dc.description.sponsorShip | Work partially supported by the Spanish Government (TIN2010-18958), and the Generalitat Valenciana (PROMETEOII/2014/062). | ca_CA |
dc.format.extent | 9 p. | ca_CA |
dc.language.iso | eng | ca_CA |
dc.publisher | Elsevier | ca_CA |
dc.relation.isPartOf | Pattern Recognition Letters 62 (2015) 1–7 | ca_CA |
dc.rights | © 2015 Elsevier B.V. All rights reserved. | ca_CA |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | * |
dc.subject | Cyclic strings | ca_CA |
dc.subject | Cyclic edit distance | ca_CA |
dc.subject | AESA | ca_CA |
dc.subject | LAESA | ca_CA |
dc.subject | Shape recognition | ca_CA |
dc.subject | Circular permuted proteins | ca_CA |
dc.subject | Circular DNA/RNA | ca_CA |
dc.title | Speeding up the cyclic edit distance using LAESA with early abandon | ca_CA |
dc.type | info:eu-repo/semantics/article | ca_CA |
dc.identifier.doi | http://dx.doi.org/10.1016/j.patrec.2015.04.013 | |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca_CA |
dc.relation.publisherVersion | http://www.sciencedirect.com/science/article/pii/S0167865515001300 | ca_CA |
dc.type.version | info:eu-repo/semantics/submittedVersion |
Ficheros en el ítem
Este ítem aparece en la(s) siguiente(s) colección(ones)
-
INIT_Articles [742]
-
LSI_Articles [360]
Articles de publicacions periòdiques escrits per professors del Departament de Llenguatges i Sistemes Informàtics