@InProceedings{Maas04,
author = {Moritz G. Maa{\ss}},
title = {Average-case Analysis of Approximate Trie Search.},
booktitle = {Proc. 15th Annual Symp. on Combinatorial
Pattern Matching ({CPM})},
pages = {472--484},
year = 2004,
volume = 3109,
series = {{LNCS}},
month = jul,
publisher = {Springer},
abstract = {For the exact search of a pattern of length $m$ in a
database of $n$ strings of (arbitrary) length the
trie data structure allows an optimal lookup time of
$O(m)$. If errors are allowed between the
pattern and the database strings, no such structure
with reasonable size is known. Using a trie some
work can be saved and running times superior to the
comparison with every string in the database can be
achieved. We investigate a comparison-based model
where ``errors'' and ``matches'' are defined between
pairs of characters. When comparing two characters,
let $p$ be the probability of an error. Between any
two strings we bound the number of errors by $D$,
which we consider a function of $n$. We study the
average-case complexity of the number of comparisons
for searching in a trie in dependence of the
parameters $p$ and $D$. Our analysis yields the
asymptotic behavior for memoryless sources with
uniform probabilities. It turns out that there is a
jump in the average-case complexity at certain
thresholds for $p$ and $D$. Our results can be
applied for any comparison-based error model, for
instance, mismatches (Hamming distance), don't
cares, or geometric character distances.}
}