Campus Event Calendar
Event Entry
What and Who
Alphabet-dependent string searching with wexponential search trees
Pawel Gawrychowski
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 4 July 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
It is widely assumed that O(m+lg(s)) is the best one can do for finding a pattern of length m in a compacted trie storing strings over an alphabet of size s, if one insists on linear-size data structures and deterministic worst-case running times. We show that a rather straightforward combination of well-known ideas yields O(m+lglg(s)) deterministic worst-case searching time for static tries.
Then we move on to dynamic tries, where we achieve a worst-case bound of O(m+lg^2(s)/lglg(s)) per query or update, which should again be compared to the previously known O(m+lg(s)) deterministic worst-case bounds [Cole et al., ICALP'06], and to the alphabet independent O(m+sqrt(lg(n)/lglg(n))) deterministic worst-case bounds [Andersson and Thorup, SODA'01], where n is the number of nodes in the trie. The basis of our update procedure is a weighted variant of exponential search trees which, while simple, might be of independent interest.
As one particular application, the above bounds (static and dynamic) apply to suffix trees.
Contact
Pawel Gawrychowski
--email hidden
passcode not visible
logged in users only
Pawel Gawrychowski, 06/10/2013 15:46 -- Created document.