Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/11063

Optimal symbol alignment distance: a new distance for sequences of symbols
Herranz Sotoca, Javier; Nin Guerrero, Jordi; Solé Simó, Marc
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. MAK - Matemàtica Aplicada a la Criptografia; Universitat Politècnica de Catalunya. ICARUS - Sistemes Aviònics i de Comunicació Intel·ligents per Avions no Tripulats Fiables
Comparison functions for sequences (of symbols) are important components of many applications, for example clustering, data cleansing and integration. For years, many efforts have been made to improve the performance of such comparison functions. Improvements have been done either at the cost of reducing the accuracy of the comparison, or by compromising certain basic characteristics of the functions, such as the triangular inequality. In this paper, we propose a new distance for sequences of symbols (or strings) called Optimal Symbol Alignment distance (OSA distance, for short). This distance has a very low cost in practice, which makes it a suitable candidate for computing distances in applications with large amounts of (very long) sequences. After providing a mathematical proof that the OSA distance is a real distance, we present some experiments for different scenarios (DNA sequences, record linkage, ...), showing that the proposed distance outperforms, in terms of execution time and/or accuracy, other well-known comparison functions such as the Edit or Jaro-Winkler distances.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computational complexity
Optimal Symbol Alignment distance (Computing)
Complexitat computacional
info:eu-repo/semantics/submittedVersion
Artículo
IEEE Press. Institute of Electrical and Electronics Engineers
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Herranz Sotoca, Javier; Nin Guerrero, Jordi; Solé Simó, Marc
Herranz Sotoca, Javier; Nin Guerrero, Jordi; Solé Simó, Marc
Sanchez Charles, David; Nin Guerrero, Jordi; Solé Simó, Marc; Muntés Mulero, Victor
Herranz Sotoca, Javier; Matwin, Stan; Nin Guerrero, Jordi; Torra i Reventós, Vicenç