Department information

Juha Kärkkäinen

University lecturer Department of Computer Science P. O. Box 68 (Gustaf Hällströmin katu 2 b) FIN-00014 University of Helsinki, FINLAND Phone: +358 9 191 51265; Fax: +358 9 191 51120 Email: Firstname.Lastname(ä->a)@cs.Helsinki.FI Room: B214

Research

Research groups

• PADS (Practical Algorithms and Data structures for Strings)
• ALGODAN (Algorithmic Data Analysis Centre-of-Excellence)

Research interests

• String algorithms, text indexes, text compression
• Succinct and compressed data structures
• Algorithms on memory hierarchies
• Algorithms and data structures
• Algorithm engineering, algorithm libraries
• Data mining
• Computational biology

Activities

• 23rd Annual Symposium on Combinatorial Pattern Matching (CPM2012), co-chair of program and organizing committees.

Teaching

• Kandidaatintutkielma, Ryhmä 6 (ohjaaja)
• 582668 Project in String Processing Algorithms (Merkkijonomenetelmien harjoitustyö), Spring 2016
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2015
• 582670 Algorithms for Bioinformatics (Algoritmit bioinformatiikassa), Autumn 2015
• 582668 Project in String Processing Algorithms (Merkkijonomenetelmien harjoitustyö), Spring 2015
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2014
• 582670 Algorithms for Bioinformatics (Algoritmit bioinformatiikassa), Autumn 2014
• 582668 Project in String Processing Algorithms (Merkkijonomenetelmien harjoitustyö), Spring 2014
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2013
• 58313302 Seminar on Advanced Data Structures, Autumn 2013
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2012
• 582487 Data Compression Techniques (Tiedon tiivistämisen tekniikat), Spring 2012
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2011
• 582668 Project in String Processing Algorithms (Merkkijonomenetelmien harjoitustyö), Spring 2011
• 58093 String Processing Algorithms (Merkkijonomenetelmät), Autumn 2010
• 582206 Laskennan mallit (Models of Computation), syksy 09
• 582633 Diskreetin optimoinnin harjoitustyö, kevät 09
• 58304101 Seminaari: Muistihierarkia-algoritmit, kevät 09
• 58093-3 Merkkijonomenetelmät (String Processing Algorithms), syksy 08
• 582484 Approximation Algorithms, spring 08
• 582603 Advanced Data Structures, spring 07
• 58093-3 Merkkijonomenetelmät (String Processing Algorithms), kevät 07
• 582484 Algorithm Libraries, spring 06
• 58093-3 Merkkijonomenetelmät (String Processing Algorithms), kevät 05

Publications

Recent publications

• Juha Kärkkäinen, Jens Stoye (editors). Special Issue on the 23rd Annual Symposium on Combinatorial Pattern Matching.
  Journal of Discrete Algorithms 25, 2014.
  [Elsevier]
• Juha Kärkkäinen, Dominik Kempa. LCP Array Construction in External Memory.
  In Proc. 13th Symposium on Experimental Algorithms (SEA 2014) Springer, 2014. To appear.
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. String range matching.
  In Proc. 25th Symposium on Combinatorial Pattern Matching (CPM 2014), Springer, 2014. To appear.
• Juha Kärkkäinen, Dominik Kempa. Engineering a Lightweight External Memory Suffix Array Construction Algorithm.
  In Proc. 2nd Conference on Algorithms for Big Data (ICABD 2014). To appear.
• Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and Simon Puglisi. LZ77-Based Self-Indexing with Faster Pattern Matching
  In Proc. 11th Latin American Theoretical INformatics Symposium (LATIN 2014), Springer, 2014, pp. 731-742.
  [Springer]
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Lempel-Ziv Parsing in External Memory.
  In Proc. 2014 Data Compression Conference (DCC 2014), IEEE Computer Society, 2014.
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Hybrid Compression of Bitvectors for the FM-Index.
  In Proc. 2014 Data Compression Conference (DCC 2014), IEEE Computer Society 2014.
• Tomohiro I, Juha Kärkkäinen, Dominik Kempa. Faster Sparse Suffix Sorting.
  In Proc. Symposium on Theoretical Aspects of Computer Science (STACS 2014), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 386-396.
  [DROPS]
• Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Niko Välimäki. Multi-pattern matching with bidirectional indexes.
  Journal of Discrete Algorithms 24, pp. 26-39, 2014.
  [Elsevier]
• Travis Gagie, Juha Kärkkäinen, Gonzalo Navarro, Simon J. Puglisi. Colored range queries and document retrieval.
  Theoretical Computer Science 483, pp. 36-50, 2013.
  [Elsevier]
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Crochemore’s String Matching Algorithm: Simplification, Extensions, Applications
  In Proc. Prague Stringology Conference 2013, Czech Technical University in Prague, Czech Republic, 2013, pp. 168-175.
  [PSC]
• Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen. Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform.
  In Proc. 21st European Symposium on Algorithm (ESA 2013), Springer, 2013, pp. 133-144.
  [Springer]
• Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen, Gad M. Landau. A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform.
  In Proc. 24th Symposium on Combinatorial Pattern Matching (CPM 2013), Springer, 2013, pp. 74-82.
  [Springer]
• 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 2013), Springer, 2013, pp. 189-200.
  [Springer]
• Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Lightweight Lempel-Ziv Parsing.
  In Proc. 12th Symposium on Experimental Algorithms (SEA 2013), Springer, 2013, pp. 139-150.
  [Springer]
• Juha Kärkkäinen, German Tischler. Near in Place Linear Time Minimum Redundancy Coding.
  In Proc. 2013 Data Compression Conference (DCC), IEEE Computer Society 2013, pp. 411-420.
  [IEEE]

Selected older publications

• 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 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, Travis Gagie. Counting Colours in Compressed Strings
  In Proc. 22nd Symposium on Combinatorial Pattern Matching (CPM 2011), Springer, 2011, pp. 197-207.
  [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]
• Roman Dementiev, Juha Kärkkäinen, Jens Mehnert and Peter Sanders. Better external memory suffix array construction.
  In ACM Journal of Experimental Algorithmics, Volume 12, Article 3.4, June 2008.
  [JEA]
• 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]
• Juha Kärkkäinen. Fast BWT in Small Space by Blockwise Suffix Sorting.
  In Theoretical Computer Science, 387 (3), pp. 249-257, 2007.
  [TCS] [.pdf (preliminary version)]
• Juha Kärkkäinen and Joong Chae Na. Faster Filters for Approximate String Matching.
  In Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX07), SIAM, 2007, pp. 84-90.
  [pdf]
• Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction.
  J. ACM, 53 (6), pp. 918-936, 2006.
  [JACM] [.pdf (preliminary version)]
• Stefan Burkhardt and Juha Kärkkäinen. Better filtering with gapped q-grams.
  Fundamenta Informaticae 56 (1-2), 2003, pp. 51-70. Special issue: Computing Patterns in Strings.
  [IOS Press] [.ps.gz (preliminary version)]
• Stefan Burkhardt and Juha Kärkkäinen. Fast lightweight suffix array construction and checking.
  In Proc. 14th Symposium on Combinatorial Pattern Matching (CPM '03). LNCS 2676, Springer, 2003, pp. 55-69.
  [Springer] [.pdf] [code]
• Juha Kärkkäinen and Esko Ukkonen. Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time.
  SIAM Journal on Computing 29 (2), 1999, pp. 571-589.
  [SIAM] [.ps.gz (preliminary version)]
• Gautam Das, Rudolph Fleischer, Leszek Gasieniec, Dimitris Gunopulos, and Juha Kärkkäinen. Episode Matching.
  In Proc. Eight Symposium on Combinatorial Pattern Matching (CPM '97), LNCS 1264, Springer 1997, pp. 12-27.
  [.ps.gz]

Software