TABLE OF CONTENTS Time series can be effectively represented by strings. The median concept is useful in various contexts. In this chapter its adaptation to the domain of strings is discussed. We introduce the notion of median string and provide related theoretical results. Then, we give a review of algorithmic procedures for efficiently computing median strings. Some experimental results will be reported to demonstrate the median concept and to compare some of the considered algorithms.
Keywords: String distance; set median string; generalized median string; online handwritten digits.
Strings provide a simple and yet powerful representation scheme for sequential data. In particular time series can be effectively represented by strings. Numerous applications have been found in a broad range of fields including computer vision [2], speech recognition, and molecular biology [13], [34].
A large number of operations and algorithms have been proposed to deal with strings [1] , [5] , [13] , [34] , [36]. Some of them are inherent to the special nature of strings such as the shortest common superstring and the longest common substring, while others are adapted from other domains.
In data mining, clustering and machine learning, a typical...
