Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 15, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Moritz Maaß (TU München)
We present an analysis of the average-case number of comparisons when searching a pattern P in a trie of n string X1,...,Xn allowing D errors which occur between two characters with probability p under a memoryless uniform model. Using techniques from complex analysis, we get exact asymptotics for the case of a constant number D=O(1) of errors. If the number of errors D is allowed to grow with the database size, we get a threshold up to where using a trie is more efficient than searching the database naively string by string. Our results can be applied for any comparison-based error model, for instance, mismatches (Hamming distance), don't cares, or geometric character distances.
Automatic MiSe System Software Version 1.4803M | admin login