Database Reference
In-Depth Information
CHAPTER 8
MEDIAN STRINGS: A REVIEW
Xiaoyi Jiang
Department of Electrical Engineering and Computer Science
Technical University of Berlin
Franklinstrasse 28/29, D-10587 Berlin, Germany
E-mail: jiang@iam.unibe.ch
Horst Bunke
Department of Computer Science, University of Bern
Neubruckstrasse 10, CH-3012 Bern, Switzerland
Email: bunke@iam.unibe.ch
Janos Csirik
Department of Computer Science, Attila Jozsef University
Arpad ter 2, H-6720 Szeged, Hungary
Time series can be effectively represented by strings. The median con-
cept 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 algo-
rithmic procedures for eciently computing median strings. Some exper-
imental 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.
1. Introduction
Strings provide a simple and yet powerful representation scheme for sequen-
tial 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].
173
