@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.}
}