Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem
13.3.12, 15:00
Room 426, Building 8
Room 426, Building 8
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
Light refreshments will be served at 14:45.
Anyone who is interested in giving a talk in the seminar, please contact us.
Dr.
