Publications of Juha Kärkkäinen

Book Chapters

• 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)]

Journal Papers

• 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, Simon J. Puglisi. Slashing the Time for BWT Inversion.
  To appear in Proc. 2012 Data Compression Conference.
• Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela, Jorma Tarhio. Indexed Multi-Pattern Matching
  To appear in 10th Latin American Theoretical Informatics Symposium (LATIN) 2012.
• Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and and Simon J. Puglisi. A Faster Grammar-Based Self-Index.
  To appear in 6th Conference on Language and Automata Theory and Applications (LATA) 2012.
• 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]

PhD Thesis

• Repetition-Based Text Indexes, Report A-1999-4, Department of Computer Science, University of Helsinki, December 1999.