Thumbnail
Access Restriction
Subscribed

Author Navarro, Gonzalo ♦ Pereira, Alberto Ordez
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Grammar compressed trees ♦ Bioinformatics ♦ Repetitive sequence collections ♦ Suffix trees
Abstract Recent compressed suffix trees targeted to highly repetitive sequence collections reach excellent compression performance, but operation times are very high. 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 orders of magnitude faster. Our suffix tree is still orders of magnitude slower than general-purpose compressed suffix trees, but these use several times more space when the collection is repetitive. Our main novelty is a practical grammar-compressed tree representation with full navigation functionality, which is useful in all applications where large trees with repetitive topology must be represented.
Description Author Affiliation: University of Chile, Santiago, Chile (Navarro, Gonzalo); University of A Coruña, A Coruña, Spain (Pereira, Alberto Ordez)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 38
Starting Page 1
Ending Page 38


Open content in new tab

   Open content in new tab
Source: ACM Digital Library