Compressed Spaced Suffix Arrays

Show simple item record Gagie, Travis Manzini, Giovanni Valenzuela, Daniel 2020-02-28T13:32:01Z 2020-02-28T13:32:01Z 2017-06
dc.identifier.citation Gagie , T , Manzini , G & Valenzuela , D 2017 , ' Compressed Spaced Suffix Arrays ' , Mathematics in Computer Science , vol. 11 , no. 2 , pp. 151-157 .
dc.identifier.other PURE: 95974880
dc.identifier.other PURE UUID: 41380717-edd1-44b4-8f58-aaf0dbb1668f
dc.identifier.other Bibtex: urn:f15438182271ad3453b38239d22814d6
dc.identifier.other Scopus: 85011579531
dc.identifier.other WOS: 000402079600005
dc.description.abstract As a first step in designing relatively-compressed data structures---i.e., such that storing an instance for one dataset helps us store instances for similar datasets---we consider how to compress spaced suffix arrays relative to normal suffix arrays and still support fast access to them. This problem is of practical interest when performing similarity search with spaced seeds because using several seeds in parallel significantly improves their performance, but with existing approaches we keep a separate linear-space hash table or spaced suffix array for each seed. We first prove a theoretical upper bound on the space needed to store a spaced suffix array when we already have the suffix array. We then present experiments indicating that our approach works even better in practice. en
dc.format.extent 7
dc.language.iso eng
dc.relation.ispartof Mathematics in Computer Science
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 111 Mathematics
dc.subject 113 Computer and information sciences
dc.title Compressed Spaced Suffix Arrays en
dc.type Article
dc.contributor.organization Department of Computer Science
dc.contributor.organization Helsinki Institute for Information Technology
dc.description.reviewstatus Peer reviewed
dc.relation.issn 1661-8289
dc.rights.accesslevel openAccess
dc.type.version acceptedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
1312.3422.pdf 140.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record