Department information

 

Juha Kärkkäinen

University researcher 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 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

• 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

• Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Niko Välimäki. Multi-Pattern Matching with Bidirectional Indexes.
  To appear in 18th International Computing and Combinatorics Conference (COCOON 2012).
• 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]
• Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela, Jorma Tarhio. Indexed Multi-Pattern Matching.
  In Proc. 10th Latin American Theoretical Informatics Symposium (LATIN 2012), Springer 2012, pp. 399-407.
  [Springer]
• Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and and Simon J. Puglisi. A Faster Grammar-Based Self-Index.
  In Proc. 6th Conference on Language and Automata Theory and Applications (LATA 2012), Springer 2012, pp. 240-251.
  [Springer]
• 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, 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, 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]
• Juha Kärkkäinen, Esko Ukkonen. Multidimensional String Matching.
  In M. Kao (editor), Encyclopedia of Algorithms, Springer, 2008, pp. 559-561.
  [Springer]
• Juha Kärkkäinen. Suffix Array Construction.
  In M. Kao (editor), Encyclopedia of Algorithms, Springer, 2008, pp. 919-921.
  [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. 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)]

Full list of publications

My publications at DBLP

Software

• Experimental Burrows-Wheeler compressor