Publications of Juha Kärkkäinen

Books, Book Chapters, etc.

• 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, Jens Stoye (editors). Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012). Springer, 2012.
  [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]
• Juha Kärkkäinen and S. Srinivasa Rao. Full-Text Indexes in External Memory.
  Chapter 7 in U. Meyer, P. Sanders, J. Sibeyn (eds.), Algorithms for Memory Hierarchies (Advanced Lectures). LNCS 2625, Springer 2003, pp. 149-170.
  [Springer (chapter)] [Springer (volume)] [.pdf (local)]
• Juha Kärkkäinen. Repetition-Based Text Indexes, PhD Thesis, Report A-1999-4, Department of Computer Science, University of Helsinki, December 1999.

Journal Papers

• 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]
• 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, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction.
  J. ACM, 53 (6), pp. 918-936, 2006.
  [JACM] [.pdf (preliminary version)]
• Marc Fontaine, Stefan Burkhardt and Juha Kärkkäinen. BDD-Based Analysis of Gapped q-Gram Filters.
  International Journal of Foundations of Computer Science, 6 (16), pp. 1121-1134, 2005.
  [IJFCS] [.ps.gz (preliminary version)]
• Juha Kärkkäinen, Gonzalo Navarro and Esko Ukkonen. Approximate String Matching over Ziv-Lempel Compressed Text.
  Journal of Discrete Algorithms 1 (3/4), pp. 313-338, 2003.
  [ScienceDirect] [.ps.gz (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)]
• 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)]
• Ykä Huhtala, Juha Kärkkäinen, Pasi Porkka and Hannu Toivonen.
  TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies.
  The Computer Journal 42 (2), 1999, pp. 100-111.
  [The Computer Journal] [code, etc.]
• Juha Kärkkäinen and Erkki Sutinen. Lempel-Ziv index for q-grams.
  Algorithmica 21 (1), pp. 137-154, 1998.
  [Springer] [.ps.gz (preliminary version)]

Conference Papers

• 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]
• 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]
• 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]
• Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Niko Välimäki. Multi-Pattern Matching with Bidirectional Indexes.
  In Proc. 18th International Computing and Combinatorics Conference (COCOON 2012).
  [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]
• 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 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 CS] [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 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. Alphabets in Generic Programming.
  In Proc. Prague Stringology Conference (PSC '05). Czech Technical University, Prague, 2005, pp. 163-173.
  [PSC]
• Roman Dementiev, Juha Kärkkäinen, Jens Mehnert and Peter Sanders. Better external memory suffix array construction.
  In Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX '05), SIAM, 2005.
  [pdf]
• Marc Fontaine, Stefan Burkhardt and Juha Kärkkäinen. BDD-Based Analysis of Gapped q-Gram Filters.
  In Proc. Prague Stringology Conference (PSC '04). Czech Technical University, Prague, 2004, pp. 56-68.
  [PSC]
• Juha Kärkkäinen. Fast BWT in small space by blockwise suffix sorting (extended abstract).
  In DIMACS Working Group on The Burrows-Wheeler Transform: Ten Years Later. DIMACS, 2004.
  [.pdf]
• Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction.
  In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955.
  [Springer] [.pdf] [code]
• 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. Computing the threshold for q-gram filters.
  In Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT '02). LNCS 2368, Springer 2002, pp. 348-357.
  [Springer] [.pdf]
• Stefan Burkhardt and Juha Kärkkäinen. One-gapped q-gram filters for Levenshtein distance.
  In Proc. 13th Symposium on Combinatorial Pattern Matching (CPM '02). LNCS 2373, Springer 2002, pp. 225-234.
  [Springer] [.pdf]
• Stefan Burkhardt and Juha Kärkkäinen. Better filtering with gapped q-grams.
  In Proc. 12th Symposium on Combinatorial Pattern Matching (CPM '01), LNCS 2089, Springer 2001, pp. 73-85.
  [journal version]
• Juha Kärkkäinen, Gonzalo Navarro and Esko Ukkonen. Approximate String Matching over Ziv-Lempel Compressed Text.
  In Proc. 11th Symposium on Combinatorial Pattern Matching (CPM '00), LNCS 1848, Springer 2000, pp. 195-209.
  [journal version]
• Ykä Huhtala, Juha Kärkkäinen and Hannu Toivonen. Mining for similarities in aligned time series using wavelets.
  In Data Mining and Knowledge Discovery: Theory, Tools and Technology, Proceedings of SPIE Vol. 3695, SPIE 1999, pp. 150-160.
  [.ps.gz]
• Ykä Huhtala, Juha Kärkkäinen, Pasi Porkka and Hannu Toivonen. Efficient Discovery of Functional and Approximate Dependencies Using Partitions.
  In 14th International Conference on Data Engineering (ICDE '98), 1998, pp. 392-401.
  [paper, code, etc.]
• 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]
• Juha Kärkkäinen and Erkki Sutinen. Lempel-Ziv index for q-grams.
  In Proc 4th Annual European Symposium on Algorithms (ESA '96), LNCS 1136, Springer 1996, pp. 378-391.
  [journal version]
• Juha Kärkkäinen and Esko Ukkonen. Lempel-Ziv parsing and sublinear-size index structures for string matching.
  In Proc. 3rd South American Workshop on String Processing (WSP '96), Carleton University Press 1996, pp. 141-155.
  [.ps.gz]
• Juha Kärkkäinen and Esko Ukkonen: Sparse suffix trees.
  In Proc. Second Annual International Computing and Combinatorics Conference (COCOON '96), LNCS 1090, Springer 1996, pp. 219-230.
  [.ps.gz]
• Juha Kärkkäinen. Suffix cactus: A cross between suffix tree and suffix array.
  In Proc. 6th Symposium on Combinatorial Pattern Matching (CPM '95), LNCS 937, Springer 1995, pp. 191-204.
  [.ps.gz]
• Juha Kärkkäinen and Esko Ukkonen. Two and higher dimensional pattern matching in optimal expected time.
  In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA '94), ACM-SIAM 1994, pp. 715-723.
  [journal version]