Juha Kärkkäinen
University lecturer
|
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]
Full list of publications
My publications at DBLP