774 citations
- Helsinki Institute of PhysicsFI5 papers
- University of HelsinkiFI4 papers
- Goddard Space Flight CenterUS3 papers
- Institute for Scientific InterchangeIT3 papers
- Landau Institute for Theoretical PhysicsRU3 papers
- University of MichiganUS3 papers
- Agenzia Spaziale ItalianaIT2 papers
- AlbaNovaSE2 papers
- Astronomical Observatory of RomeIT2 papers
- Australian Research CouncilAU2 papers
- Austrian Academy of SciencesAT2 papers
- Boston UniversityUS2 papers
Showing 2009 · cs.DSShow all
2 papers · 2 filters
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…