Photo of Dominik Kempa

Dominik Kempa

Department of Computer Science
P. O. Box 68 (Gustaf Hällströmin katu 2b)
FIN-00014 University of Helsinki, FINLAND

Email: dkempa "at" cs "dot"
helsinki "dot" fi

I'm currently a postdoc at the University of Helsinki where I recently obtained a PhD under the supervision of Juha Kärkkäinen and Esko Ukkonen. I'm affiliated with Practical Algorithms and Data structures on Strings and Combinatorial Pattern Matching groups.

Research Interests

  • External memory algorithms
  • Parallel algorithms
  • Text indexing
  • Practical algorithms on strings
  • String combinatorics

News

  • 2017-07-07: Our paper (together with Dima Kosolobov) on linear-time construction of LZ-End parsing (a variation of LZ77) has been accepted to ESA 2017 (pdf)
  • 2017-06-04: New versions (0.2.0) of EM-SparsePhi and EM-SuccinctIrreducible external-memory LCP array construction algorithms available: link
  • 2017-05-22: Initial release of the external-memory LZ-End parsing algorithm: link
  • 2016-11-28: I will be on the PC of SEA 2017
  • 2016-08-23: New external-memory (+parallel) algorithms for constructing the LCP array: link
  • 2016-01-01: New version of LCPscan (0.2.0) available

Software

Suffix/(P)LCP array construction: Lempel-Ziv parsing: Other:

Short CV

Honours

  • 2016 Outstanding doctoral dissertation award,
    Awarded to five selected disserations in the Faculty of Science (consisting of seven departments), University of Helsinki
  • 2014 Junior researcher of 2014,
    Department of Computer Science, University of Helsinki (photo)

Teaching

Selected Talks

About

Before starting my PhD I was into problem solving: my spoj profile (feel free to contact me about solutions!). In my free time I like to play badminton. I also enjoy swimming and skiing and try to do it whenever I get a chance. I listen to a variety of music, most recently texas blues.

Publications

2017:
  • Dominik Kempa, Dmitry Kosolobov: LZ-End Parsing in
    Linear Time
    , ESA 2017 (pdf) (slides)
  • Juha Kärkkäinen, Dominik Kempa: Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet, SEA 2017 (pdf) (code)
  • Dominik Kempa, Dmitry Kosolobov: LZ-End Parsing in Compressed Space, DCC 2017 (arxiv) (code)
  • Juha Kärkkäinen, Dominik Kempa: Engineering a Lightweight External Memory Suffix Array Construction Algorithm, Mathematics in Computer Science, 2017 (code)
  • Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima, Simon J. Puglisi, Arseny M. Shur: On the Size of Lempel-Ziv and Lyndon Factorizations, STACS 2017 (pdf) (slides)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, Bella Zhukova: Engineering External Memory Induced Suffix Sorting, ALENEX 2017 (pdf) (code)
2016:
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lazy Lempel-Ziv Factorization Algorithms, ACM Journal of Experimental Algorithmics 2016 (pdf) (code)
  • Juha Kärkkäinen, Dominik Kempa: Faster External Memory LCP Array Construction, ESA 2016, invited to ACM JEA special issue (pdf) (code) (slides)
  • Juha Kärkkäinen, Dominik Kempa: LCP Array Construction Using O(sort(n)) (or Less) I/Os, SPIRE 2016
  • Juha Kärkkäinen, Dominik Kempa, Marcin Piątkowski: Tighter Bounds for the Sum of Irreducible LCP Values, Theoretical Computer Science, 2016
  • Juha Kärkkäinen, Dominik Kempa: LCP Array Construction in External Memory, ACM Journal of Experimental Algorithmics 2016 (pdf) (code)
  • Djamal Belazzougui, Juha Kärkkäinen, Dominik Kempa and Simon J. Puglisi: Lempel-Ziv Decoding in External Memory, SEA 2016 (arxiv) (code)
  • Simon Gog, Juha Kärkkäinen, Dominik Kempa, Matthias Petri, Simon J. Puglisi: Faster, Minuter, DCC 2016 (code)
2015:
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Parallel External Memory Suffix Sorting, CPM 2015 (code) (slides)
  • Juha Kärkkäinen, Dominik Kempa, Marcin Piątkowski: Tighter Bounds for the Sum of Irreducible LCP Values, CPM 2015
  • Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piątkowski, Simon J. Puglisi, Shiho Sugimoto: Diverse Palindromic Factorization is NP-Complete, DLT 2015 (arxiv)
2014:
  • Gabriele Fici, Travis Gagie, Juha Kärkkäinen, Dominik Kempa: A Subquadratic Algorithm for Minimum Palindromic Factorization, Journal of Discrete Algorithms, 2014 (arxiv)
  • Juha Kärkkäinen, Dominik Kempa: LCP Array Construction in External Memory, SEA 2014, invited to ACM JEA special issue (code)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: String Range Matching, CPM 2014 (video) (slides)
  • Juha Kärkkäinen, Dominik Kempa: Engineering a Lightweight External Memory Suffix Array Construction Algorithm, ICABD 2014 (pdf) (code)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lempel-Ziv Parsing in External Memory, DCC 2014 (code) (slides)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Hybrid Compression of Bitvectors for the FM-Index, DCC 2014 (code) (slides)
  • Tomohiro I, Juha Kärkkäinen, Dominik Kempa: Faster Sparse Suffix Sorting, STACS 2014 (pdf)
2013:
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Crochemore's String Matching Algorithm: Simplification, Extensions, Applications, PSC 2013 (pdf) (slides)
  • Dominik Kempa, Simon J. Puglisi: Lempel-Ziv Factorization: Simple, Fast, Practical, ALENEX 2013, invited to ACM JEA special issue (pdf) (code)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Linear Time Lempel-Ziv Factorization: Simple, Fast, Small, CPM 2013 (arxiv) (code) (slides)
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lightweight Lempel-Ziv Parsing, SEA 2013 (arxiv) (code)
2012:
  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Slashing the Time for BWT Inversion, DCC 2012 (slides)
  • Juha Kärkkäinen, Pekka Mikkola, Dominik Kempa: Grammar Precompression Speeds Up Burrows-Wheeler Compression, SPIRE 2012

See also DBLP and Google Scholar.

Thesis
  • Dominik Kempa: Efficient Construction of Fundamental Data Structures in Large-Scale Text Indexing, PhD thesis, University of Helsinki, 2015 (pdf)