Speeding up the cyclic edit distance using LAESA with early abandon
Visualitza/
Metadades
Mostra el registre complet de l'elementcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONMetadades
Títol
Speeding up the cyclic edit distance using LAESA with early abandonData de publicació
2015Editor
ElsevierISSN
0167-8655Tipus de document
info:eu-repo/semantics/articleVersió de l'editorial
http://www.sciencedirect.com/science/article/pii/S0167865515001300Versió
info:eu-repo/semantics/submittedVersionParaules clau / Matèries
Resum
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
... [+]
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 [-]
Publicat a
Pattern Recognition Letters 62 (2015) 1–7Drets d'accés
© 2015 Elsevier B.V. All rights reserved.
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/openAccess
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/openAccess
Apareix a les col.leccions
- INIT_Articles [754]
- LSI_Articles [366]