Compressed Spaced Suffix Arrays

Näytä kaikki kuvailutiedot



Gagie , T , Manzini , G & Valenzuela , D 2017 , ' Compressed Spaced Suffix Arrays ' , Mathematics in Computer Science , vol. 11 , no. 2 , pp. 151-157 .

Julkaisun nimi: Compressed Spaced Suffix Arrays
Tekijä: Gagie, Travis; Manzini, Giovanni; Valenzuela, Daniel
Tekijän organisaatio: Department of Computer Science
Helsinki Institute for Information Technology
Päiväys: 2017-06
Kieli: eng
Sivumäärä: 7
Kuuluu julkaisusarjaan: Mathematics in Computer Science
ISSN: 1661-8289
Tiivistelmä: 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.
Avainsanat: 111 Mathematics
113 Computer and information sciences
Vertaisarvioitu: Kyllä
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: acceptedVersion


Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
1312.3422.pdf 140.2KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot