March 6, Tuesday
12:00 – 13:00
Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem
Computer Science seminar
Lecturer : Danny Breslauer
Affiliation : Caesarea Rothchild Institute, University of Haifa
Location : 202/37
Host : Prof. Michal Ziv-Ukelson
We contribute a further step towards the plausible real time
construction of suffix trees by presenting an on-line algorithm that spends
O(log log n) time processing each input symbol and takes O(n log log n)
time in total. Our results improve on a previously published algorithm
that take O(log n) time per symbol and O(n log n) time in total. The
improvements are achieved using a new data structure for the fringe
marked ancestor problem, a special case of the nearest marked ancestor
problem, which may be of independent interest.
Joint work with Pino Italiano, University of Rome.