PADS: Practical Algorithms and Data structures on Strings

We develop fast and practical algorithms and data structures for fundamental problems arising in sequence analysis. The research is based on thorough understanding of both the combinatorial properties of the problems and the properties of modern computers. The goal is not only to obtain better algorithms but to understand why they are better.

Members

• Juha Kärkkäinen (contact person)
• Dominik Kempa
• Simon Puglisi

Former Members

• Pekka Mikkola
• Tommi Rantala

Software

• Data compressor based on Burrows-Wheeler transform
• String sorting algorithms

Publications

• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Lightweight Lempel-Ziv Parsing.
  In Proc. 12th Symposium on Experimental Algorithms (SEA), Springer 2013.
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
  In Proc. 24th Symposium on Combinatorial Pattern Matching (CPM), Springer 2013.
• Dominik Kempa, Simon J. Puglisi. Lempel-Ziv Factorization: Simple, Fast, Practical.
  In Proc. ALENEX 2013, SIAM 2013.
• Juha Kärkkäinen, Pekka Mikkola, Dominik Kempa. Grammar Precompression Speeds Up Burrows-Wheeler Compression.
  In Proc. 18th Symposium on String Processing and Information Retrieval (SPIRE 2012), Springer, 2012, pp. 330-335.
  [Springer]
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Slashing the Time for BWT Inversion.
  In Proc. 2012 Data Compression Conference (DCC), IEEE Computer Society 2012, pp. 99-108.
  [IEEE CS]
• Juha Kärkkäinen, Simon J. Puglisi. Fixed Block Compression Boosting in FM Indexes.
  In Proc. 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), Springer, 2011, pp. 174-184.
  [Springer]
• Juha Kärkkäinen, Simon Puglisi. Cache-Friendly Burrows-Wheeler Inversion.
  In Proc. 1st International Conference on Data Compression, Communication and Processing (CCP 2011), IEEE Computer Society, 2011, pp. 38-42.
  [IEEE] [pdf (preliminary)]
• Juha Kärkkäinen, Simon Puglisi. Medium-Space Algorithms for Inverse BWT.
  In Proc. 18th European Symposium on Algorithms (ESA 2010), Springer, 2010, pp. 451-462.
  [Springer]
• Juha Kärkkäinen, Giovanni Manzini, Simon Puglisi. Permuted Longest-Common-Prefix Array.
  In Proc. 20th Symposium on Combinatorial Pattern Matching (CPM 2009), Springer, 2009, pp. 181-192.
  [Springer]
• Juha Kärkkäinen, Tommi Rantala. Engineering radix sort for strings.
  In Proc. 15th String Processing and Information Retrieval Symposium (SPIRE 2008), Springer, 2008, pp. 3-14.
  [Springer]