Average-Case Analysis of Approximate Trie Search

Abstract For the exact search of a pattern of length m in a database of n strings the trie data structureallows an optimal lookup time of O (m). If errors are allowed between the pattern and the databasestrings, 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. Weinvestigate 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 twostrings we bound the number of errors by D, which we consider a function of n. We study theaverage-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 withuniform 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, forinstance, mismatches (Hamming distance), don't cares, or geometric character distances. 1 Introduction We study the average-case behavior of the simple problem of finding a given pattern in a set of patternssubject to two conditions. The set of patterns is given in advance and may have been preprocessed with linear space, and we are also interested in occurrences where the pattern is found with a givennumber of errors