Practical Algorithms and Data Structures on Strings research group / Juha Kärkkäinen

  • PL 68 (Gustaf Hällströmin katu 2b), B214

    HELSINGIN YLIOPISTO

    Finland

Publications 1998 2019

2019

Fixed Block Compression Boosting in FM-Indexes: Theory and Practice

Gog, S., Kärkkäinen, J., Kempa, D., Petri, M. & Puglisi, S. J., Apr 2019, In : Algorithmica. 81, 4, p. 1370-1391 22 p.

Research output: Contribution to journalArticleScientificpeer-review

2017

28th Annual Symposium on Combinatorial Pattern Matching: CPM 2017, July 4-6, 2017, Warsaw, Poland

Kärkkäinen, J. (ed.), Radoszewski, J. (ed.) & Rytter, W. (ed.), Jul 2017, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 78)

Research output: Book/ReportAnthology or special issueScientificpeer-review

Open Access
File

Document retrieval on repetitive string collections

Gagie, T., Hartikainen, A., Karhu, K., Kärkkäinen, J., Navarro, G., Puglisi, S. J. & Sirén, J., Jun 2017, In : Information Retrieval Journal. 20, 3, p. 253-291 39 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Engineering a Lightweight External Memory Suffix Array Construction Algorithm

Kärkkäinen, J. T. & Kempa, D., 2017, In : Mathematics in Computer Science. 11, 2, p. 137-149 13 p.

Research output: Contribution to journalArticleScientificpeer-review

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

LZ-End Parsing in Linear Time

Kempa, D. & Kosolobov, D., 2017, 25th Annual European Symposium on Algorithms (ESA 2017). Pruhs, K. & Sohler, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 53. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 87).

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

Lazy Lempel-Ziv Factorization Algorithms

Kärkkäinen, J., Kempa, D. & Puglisi, S. J., Oct 2016, In : ACM Journal of Experimental Algorithmics. 21, 2, 19 p., 2.4.

Research output: Contribution to journalArticleScientificpeer-review

LCP Array Construction in External Memory

Kärkkäinen, J. & Kempa, D., Jan 2016, In : ACM Journal of Experimental Algorithmics. 21, 1, 22 p., 1.7.

Research output: Contribution to journalArticleScientificpeer-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

Tighter bounds for the sum of irreducible LCP values

Kärkkäinen, J., Kempa, D. & Piatkowski, M., 20 Dec 2016, In : Theoretical Computer Science. 656, p. 265-278 14 p.

Research output: Contribution to journalArticleScientificpeer-review

V-Order: New combinatorial properties & a simple comparison algorithm

Kärkkäinen, J., Alatabbi, A., Daykin, J. W., Rahman, M. S. & Smyth, W. F., 31 Dec 2016, In : Discrete Applied Mathematics. 215, p. 41-46 6 p.

Research output: Contribution to journalArticleScientificpeer-review

2015

Computing the Burrows-Wheeler transform in place and in small space

Crochemore, M., Grossi, R., Kärkkäinen, J. T. & Landau, G. M., 2015, In : Journal of Discrete Algorithms. 32, p. 44-52 9 p.

Research output: Contribution to journalArticleScientificpeer-review

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

Efficient Construction of Fundamental Data Structures in Large-Scale Text Indexing

Kempa, D., 2015, Helsinki: University of Helsinki. 78 p.

Research output: ThesisDoctoral Thesis

Multidimensional String Matching

Kärkkäinen, J. T., 2015, Encyclopedia of Algorithms. Kao, M-Y. (ed.). New York: Springer Science+Business Media, 5 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-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

Suffix Array Construction

Kärkkäinen, J. T., 2015, Encyclopedia of Algorithms. Kao, M-Y. (ed.). New York: Springer, 6 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-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

A Subquadratic Algorithm for Minimum Palindromic Factorization

Fici, G., Gagie, T., Kärkkäinen, J. & Kempa, D., Sep 2014, In : Journal of Discrete Algorithms. 28, September 2014, p. 41-48 8 p.

Research output: Contribution to journalArticleScientificpeer-review

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

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

LZ77-Based Self-indexing with Faster Pattern Matching

Gagie, T., Gawrychowski, P., Kärkkäinen, J., Nekrich, Y. & Puglisi, S. J., 2014, LATIN 2014: Theoretical Informatics : 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings. Pardo, A. & Viola, A. (eds.). Cham: Springer, p. 731-742 12 p. (Lecture Notes in Computer Science; vol. 8392).

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

2013

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

2010

Pattern Kits

Gagie, T., Karhu, K., Kärkkäinen, J., Mäkinen, V. & Salmela, L., 2010, (Submitted) arXiv. arXiv:1011.3491v2

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

File
1999

Mining for similarities in aligned time series using wavelets

Huhtala, Y., Karkkainen, J. & Toivonen, H., Apr 1999, Data Mining and Knowledge Discovery: Theory, Tools, and Technology. Orlando, Florida: SPIE, p. 150-160 11 p. (SPIE Proceedings Series Vol. 3695).

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

Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies

Huhtala, Y., Kärkkäinen, J., Porkka, P. & Toivonen, H., 1999, In : Computer Journal. 42, 2, p. 100-111 12 p.

Research output: Contribution to journalArticleScientificpeer-review

1998

Efficient Discovery of Functional and Approximate Dependencies Using Partitions

Huhtala, Y., Kärkkäinen, J., Porkka, P. & Toivonen, H., Feb 1998, Proceedings of the Fourteenth International Conference on Data Engineering (ICDE'98). Orlando, Florida: IEEE Computer Society, p. 392-401 10 p.

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