774 citations
- Helsinki Institute of PhysicsFI5 papers
- University of HelsinkiFI4 papers
- Donostia International Physics CenterES3 papers
- Goddard Space Flight CenterUS3 papers
- Harvard UniversityUS3 papers
- Institute for Scientific InterchangeIT3 papers
- Instituto de Astrofísica de AndalucíaES3 papers
- King's College LondonGB3 papers
- Landau Institute for Theoretical PhysicsRU3 papers
- Material Physics CenterES3 papers
- Universidad Autónoma de MadridES3 papers
- University of MichiganUS3 papers
Showing 2009Show all
2 papers · 1 filter
cs.DS2009
Lightweight Data Indexing and Compression in External Memory
Paolo Ferragina, Travis Gagie, Giovanni Manzini
In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are light…
cs.DS2009
Tight Bounds for Online Stable Sorting
Travis Gagie, Yakov Nekrich
Although many authors have considered how many ternary comparisons it takes to sort a multiset of size , the best known upper and lower bounds still differ by a term linear…