Faster Compressed Suffix Trees for Repetitive Text Collections

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.

 

Link to the paper: http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2_36#page-1

 

Welcome!