Faster Compressed Suffix Trees for Repetitive Text Collections

Event type: 
Guest lecture
Event time: 
12.09.2014 - 13:15 - 14:00
Lecturer : 
Alberto Ordóñez
Place: 
Exactum, C222
Description: 
Recent compressed suffix trees targeted to highly repetitive text collections
reach excellent compression performance, but operation times are in the order of
milliseconds. We design a new suffix tree representation for this scenario
that still achieves very low space usage, only slightly larger than the best
previous one, but supports the operations within microseconds. This puts the
data structure in the same performance level of compressed suffix trees
designed for standard text collections, which on repetitive collections use
many times more space than our new structure.
 
 
Welcome!
09.09.2014 - 12:42 Veli Mäkinen
09.09.2014 - 12:42 Veli Mäkinen