If you made any changes in Pure these will be visible here soon.

Publications 2005 2019

  • 41 Conference contribution
  • 16 Article
  • 6 Chapter
  • 2 Anthology or special issue
Filter
Conference contribution
2018

Run compressed rank/select for large alphabets

Fuentes-Sepulveda, J., Karkkainen, J., Kosolobov, D. & Puglisi, S., 2018, 2018 Data Compression Conference 27–30 March 2018 Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). IEEE, p. 315-324 10 p. (DCC).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2017

Engineering External Memory Induced Suffix Sorting

Kärkkäinen, J., Kempa, D., Puglisi, S. J. & Zhukova, B., 2017, 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Fekete, S. & Ramachandran, V. (eds.). Society for Industrial and Applied Mathematics, p. 98-108 11 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet

Kärkkäinen, J. & Kempa, D., 2017, 16th International Symposium on Experimental Algorithms (SEA 2017). Iliopoulos, C. S., Pissis, S. P., Puglisi, S. J. & Raman, R. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 17. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 75).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

On Suffix Tree Breadth

Badkobeh, G., Kärkkäinen, J., Puglisi, S. J. & Zhukova, B., Sep 2017, String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017. Palermo, Italy, September 26-29, 2017. Proceedings. Fici, G., Sciortino, M. & Venturini, R. (eds.). Cham: Springer, p. 68-73 6 p. (Lecture Notes in Computer Science; vol. 10508).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

On the Size of Lempel-Ziv and Lyndon Factorizations

Kärkkäinen, J., Kempa, D., Nakashima, Y., Puglisi, S. J. & Shur, A. M., 2017, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Vollmer, H. & Vallée, B. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 13 p. 45. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 66).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

String Inference from Longest-Common-Prefix Array

Kärkkäinen, J., Piątkowski, M. & Puglisi, S. J., 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Chatzigiannakis, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 62. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 80).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
2016

Faster, Minuter

Gog, S., Kärkkäinen, J., Kempa, D., Petri, M. & Puglisi, S. J., 2016, DCC 2016: 2016 Data Compression Conference, 29 March-1 April 2016, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). New York, NY: IEEE, p. 53-62 10 p. ( IEEE Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Faster External Memory LCP Array Construction

Kärkkäinen, J. & Kempa, D., 2016, 24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark. Sankowski, P. & Zaroliagis, C. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 61. (Leibniz International Proceedings in Informatics; vol. 57).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

LCP Array Construction Using O(sort(n)) (or Less) I/Os

Kärkkäinen, J. & Kempa, D., 21 Sep 2016, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Inenaga, S., Sadakane, K. & Sakai, T. (eds.). Springer, Vol. 9954. p. 204-217 14 p. (Lecture Notes in Computer Science (LNCS); vol. 9954).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Lempel-Ziv Decoding in External Memory

Belazzougui, D., Kärkkäinen, J., Kempa, D. & Puglisi, S. J., 2016, Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. Goldberg, A. V. & Kulikov, A. S. (eds.). Cham: Springer International Publishing , p. 63-74 12 p. (Lecture Notes in Computer Science; vol. 9685).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2015

Diverse Palindromic Factorization is NP-Complete

Bannai, H., Gagie, T., Inenaga, S., Kärkkäinen, J. T., Kempa, D., Piątkowski, M., Puglisi, S. J. & Sugimoto, S., 2015, Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. Potapov, I. (ed.). Cham: Springer International Publishing AG, p. 85-96 12 p. (Lecture Notes in Computer Science; vol. 9168).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Document Counting in Compressed Space

Gagie, T., Hartikainen, A., Kärkkäinen, J., Navarro, G., Puglisi, S. J. & Sirén, J., 2015, DCC 2015: 2015 Data Compression Conference, 7-9 April 2015, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). Los Alamitos, CA: IEEE, p. 103-112 10 p. (Data Compression Conference. Proceedings ).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Parallel External Memory Suffix Sorting

Kärkkäinen, J., Kempa, D. & Puglisi, S. J., 16 Jun 2015, Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. Cicalese, F., Porat, E. & Vaccaro, U. (eds.). Springer International Publishing AG, p. 329-342 14 p. (Lecture Notes in Computer Science; vol. 9133).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Queries on LZ-Bounded Encodings

Belazzougui, D., Gagie, T., Gawrychowski, P., Kärkkäinen, J., Pereira, A. O., Puglisi, S. J. & Tabei, Y., 2015, Proceedings DCC 2015 Data Compression Conference: 7-9 April 2015, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). Los Alamitos, CA: IEEE Computer Society Conference Publishing Services, p. 83-92 10 p. (IEEE Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Tighter Bounds for the Sum of Irreducible LCP Values

Kärkkäinen, J., Kempa, D. & Piątkowski, M., 16 Jun 2015, Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings. Cicalese, F., Porat, E. & Vaccaro, U. (eds.). Springer International Publishing AG, p. 316-328 13 p. (Lecture Notes in Computer Science; vol. 9133).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2014

Engineering a Lightweight External Memory Suffix Array Construction Algorithm

Kärkkäinen, J. & Kempa, D., 2014, ICABD 2014 2nd International Conference on Algorithms for Big Data: Proceedings of the 2nd International Conference on Algorithms for Big Data : Palermo, Italy, April 07-09, 2014.. Iliopoulos, C. S. & Langiu, A. (eds.). CEUR-WS.org, p. 53-60 8 p. (CEUR Workshop Proceedings; vol. 1146).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Faster Sparse Suffix Sorting

I, T., Kärkkäinen, J. & Kempa, D., 2014, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Mayr, E. W. & Portier, N. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 386-396 11 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 25).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Hybrid Compression of Bitvectors for the FM-Index

Kärkkäinen, J., Kempa, D. & Puglisi, S., 2014, Proceedings [of] Data Compression Conference 26-28 March 2014, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagristà, J. & Storer, J. A. (eds.). Los Alamitos, CA: IEEE, p. 302-311 10 p. (Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

LCP Array Construction in External Memory

Kärkkäinen, J. & Kempa, D., 2014, Experimental Algorithms: 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 – July 1, 2014. Proceedings. Gudmundsson, J. & Katajainen, J. (eds.). Springer, p. 412-423 12 p. (Lecture Notes in Computer Science; vol. 8504).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Lempel-Ziv Parsing in External Memory

Kärkkäinen, J., Kempa, D. & Puglisi, S. J., 2014, Proceedings [of] Data Compression Conference 26-28 March 2014, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagristà, J. & Storer, J. A. (eds.). Los Alamitos, CA: IEEE, p. 153-162 10 p. (Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

String Range Matching

Kärkkäinen, J., Kempa, D. & Puglisi, S. J., 2014, Combinatorial Pattern Matching: 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings. Kulikov, A. S., Kuznetsov, S. O. & Pevzner, P. (eds.). Springer International Publishing AG, p. 232-241 10 p. (Lecture Notes in Computer Science; vol. 8486).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2013

A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform

Crochemore, M., Grossi, R., Kärkkäinen, J. & Landau, G. M., 2013, Combinatorial Pattern Matching: 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings. Fischer, J. & Sanders, P. (eds.). Springer-Verlag, p. 74-82 9 p. (Lecture Notes in Computer Science; vol. 7922).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Crochemore’s String Matching Algorithm: Simplification, Extensions, Applications

Kärkkäinen, J., Kempa, D. & Puglisi, S., 2013, Proceedings of the Prague Stringology Conference 2013. Holub, J. & Žďárek, J. (eds.). Czech Technical University in Prague, Department of Theoretical Computer Science, Faculty of Information Technology, p. 168-175 8 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Lightweight Lempel-Ziv Parsing

Kärkkäinen, J., Kempa, D. & Puglisi, S., 2013, Experimental Algorithms: 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings. Bonifaci, V., Demetrescu, C. & Marchetti-Spaccamela, A. (eds.). Springer-Verlag, p. 139-150 12 p. (Lecture Notes in Computer Science; vol. 7933).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Linear Time Lempel-Ziv Factorization: Simple, Fast, Small

Kärkkäinen, J., Kempa, D. & Puglisi, S., 2013, Combinatorial Pattern Matching: 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings. Fischer, J. & Sanders, P. (eds.). Springer-Verlag, p. 189-200 12 p. (Lecture Notes in Computer Science; vol. 7922).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Near in Place Linear Time Minimum Redundancy Coding

Kärkkäinen, J. & Tischler, G., 2013, Data Compression Conference (DCC), 2013. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). IEEE Computer Society, p. 411-420 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Versatile succinct representations of the bidirectional Burrows-Wheeler transform

Belazzougui, D., Cunial, F., Kärkkäinen, J. & Mäkinen, V., 2013, Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. Bodlaender, H. L. & Italiano, G. F. (eds.). Springer-Verlag, p. 133-144 (Lecture Notes in Computer Science; vol. 8125).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2012

Faster Grammar-based Self-index

Gagie, T., Gawrychowski, P., Kärkkäinen, J., Nekrich, Y. & Puglisi, S. J., 2012, Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. Dediu, A-H. & Martín-Vide, C. (eds.). Springer-Verlag, p. 240-251 12 p. (Lecture Notes in Computer Science; vol. 7183).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Grammar Precompression Speeds Up Burrows-Wheeler Compression

Kärkkäinen, J., Mikkola, P. & Kempa, D., 2012, String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. Springer-Verlag, p. 330-335 6 p. (Lecture Notes in Computer Science; vol. 2012, no. 7608).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Indexed Multi-Pattern Matching

Gagie, T., Karhu, K., Kärkkäinen, J., Mäkinen, V., Salmela, L. & Tarhio, J., 2012, LATIN 2012: Theoretical Informatics: 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings. Springer-Verlag, p. 399-407 10 p. (Lecture Notes in Computer Science; vol. 7256).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Multi-Pattern Matching with Bidirectional Indexes

Gog, S., Karhu, K., Kärkkäinen, J., Mäkinen, V. & Välimäki, N., 2012, Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings. Gudmundsson, J., Mestre, J. & Viglas, T. (eds.). Springer-Verlag, p. 384-395 (Lecture Notes in Computer Science; vol. 7434).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Slashing the Time for BWT Inversion

Kärkkäinen, J., Kempa, D. & Puglisi, S. J., 2012, Data Compression Conference (DCC), 2012. Storer, J. A. & Marcellin, M. W. (eds.). IEEE Computer Society, p. 99-108 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2011

Cache-Friendly Burrows-Wheeler Inversion

Kärkkäinen, J. & Puglisi, S. J., 2011, CCP 2011 First International Conference on Data Compression, Communications and Processing. Carpentieri, B. (ed.). IEEE Computer Society, p. 38-42 5 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Counting Colours in Compressed Strings

Kärkkäinen, J. & Gagie, T., 2011, Combinatorial Pattern Matching: 22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings. Giancarlo, R. & Manzini, G. (eds.). Springer, p. 197-207 11 p. (Lecture Notes in Computer Science; vol. 6818).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Fixed Block Compression Boosting in FM Indexes

Kärkkäinen, J. & Puglisi, S. J., 2011, String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. / Proceedings. Springer, p. 174-184 11 p. (Lecture Notes in Computer Science; vol. 2011, no. 7024).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2010

Medium-Space Algorithms for Inverse BWT

Kärkkäinen, J. & Puglisi, S. J., 2010, Algorithms - ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. de Berg, M. & Meyer, U. (eds.). Springer, p. 451-462 12 p. (Lecture Notes in Computer Science; vol. 2010, no. 6346).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
2009

Permuted Longest-Common-Prefix Array

Kärkkäinen, J., Manzini, G. & Puglisi, S. J., 2009, Combinatorial Pattern Matching: 20th Annual Symposium, CPM 2009 Lille, France, June 22-24, 2009 / Proceedings. Kucherov, G. & Ukkonen, E. (eds.). Springer, p. 181-192 12 p. (Lecture Notes in Computer Sience; vol. 5577).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2008

Engineering radix sort for strings

Kärkkäinen, J. & Rantala, T., 2008, String Processing and Information Retrieval: 15th International Symposium, SPIRE 2008, Melbourne, Australia, November 10-12, 2008. Proceedings. Amihood, A., Turpin, A. & Moffat, A. (eds.). Springer, p. 3-14 12 p. (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2007

Faster Filters for approximate string matching

Kärkkäinen, J. & Na, J. C., 2007, Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007 2007. p. 84-90 7 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2005

Alphabets in generic programming

Kärkkäinen, J., 2005, Proceedings of the Prague Stringology Conference, Prague, Czech Republic, August 29-31, 2005: Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University 2005. Holub, J. & Simánek, M. (eds.). p. 163-173

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Better external memory suffix array construction

Dementiev, R., Kärkkäinen, J., Mehnert, J. & Sanders, P., 2005, Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics. Society for Industrial and Applied Mathematics, p. 86-97

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review