Partial symbol ordering distance

Javier Herranz, Jordi Nin

Producció científica: Capítol de llibreContribució a una conferènciaAvaluat per experts


Nowadays sequences of symbols are becoming more important, as they are the standard format for representing information in a large variety of domains such as ontologies, sequential patterns or non numerical attributes in databases. Therefore, the development of new distances for this kind of data is a crucial need. Recently, many similarity functions have been proposed for managing sequences of symbols; however, such functions do not always hold the triangular inequality. This property is a mandatory requirement in many data mining algorithms like clustering or k-nearest neighbors algorithms, where the presence of a metric space is a must. In this paper, we propose a new distance for sequences of (non-repeated) symbols based on the partial distances between the positions of the common symbols. We prove that this Partial Symbol Ordering distance satisfies the triangular inequality property, and we finally describe a set of experiments supporting that the new distance outperforms the Edit distance in those scenarios where sequence similarity is related to the positions occupied by the symbols.

Idioma originalAnglès
Títol de la publicacióModeling Decisions for Artificial Intelligence - 6th International Conference, MDAI 2009, Proceedings
Nombre de pàgines10
Estat de la publicacióPublicada - 2009
Publicat externament
Esdeveniment6th International Conference on Modeling Decisions for Artificial Intelligence, MDAI 2009 - Awaji Island, Japan
Durada: 30 de nov. 20092 de des. 2009

Sèrie de publicacions

NomLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volum5861 LNAI
ISSN (imprès)0302-9743
ISSN (electrònic)1611-3349


Conferència6th International Conference on Modeling Decisions for Artificial Intelligence, MDAI 2009
CiutatAwaji Island


Navegar pels temes de recerca de 'Partial symbol ordering distance'. Junts formen un fingerprint únic.

Com citar-ho