Database Reference
In-Depth Information
i
position
, the following operations are performed:
(i) Build perturbations
•
Substitution: Replace the
i
-th symbol of ¯
p
by each symbol of Σ in
turn and choose the resulting string
x
with the smallest consensus
error relative to
S
.
•
Insertion: Insert each symbol of Σ in turn at the
i
-th position of ¯
p
and choose the resulting string
y
with the smallest consensus error
relative to
S
.
•
Deletion: Delete the
i
-th symbol of ¯
p
to generate
z
.
(ii) Replace ¯
p
by the one from
{
p, x, y, z}
¯
with the smallest consensus error
relative to
S
.
For the Levenshtein distance one global iteration that handles all posi-
tions of the initial ¯
n
3
N|
p
needs
O
(
Σ
|
) time. The process is repeated until
there is more improvement possible.
5.3.
Dynamic Computation of Generalized Median Strings
In a dynamic context we are faced with the situation of a steady arrival of
new data items, represented by strings. At each point of time,
t
S
t
,theset
of existing strings is incremented by a new string, resulting in
S
t
+1
,and
its generalized median string is to be computed. Doubtlessly, a trivial solu-
tion consists in applying any of the approaches discussed above to
S
t
+1
.By
S
t
+1
from
doing this, however, we compute the generalized median string of
S
t
, in particular its general-
ized median string. All algorithms for computing generalized median strings
are of such a static nature and thus not optimal in a dynamic context. The
work [18] proposes a genuinely dynamic approach, in which the update
scheme only considers the generalized median string of
scratch without utilizing any knowledge about
S
t
together with
S
t
.
The inspiration for the algorithm comes from a fundamental fact
in real space. Under the distance function
the new data item, but not the individual members of
d
(
p
i
,p
j
)=(
p
i
− p
j
)
·
(
p
i
− p
j
),
i.e.
the
squared
Euclidean
distance
of
p
i
and
p
j
,
S
t
the
generalized
median
of
a
given
set
=
{p
1
,p
2
,...,p
t
}
of
t
points is the well-known mean:
t
p
t
=
1
t
¯
·
p
i
.
i
=1
