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

Publications 2012 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

On Lempel-Ziv Decompression in Small Space

Puglisi, S. J. & Rossi, M., 2019, 2019 DATA COMPRESSION CONFERENCE (DCC). New York: IEEE, p. 221-230 10 p. (IEEE Data Compression Conference).

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

2018

Algorithms for anti-powers in strings

Badkobeh, G., Fici, G. & Puglisi, S. J., Sep 2018, In : Information Processing Letters. 137, p. 57-60 4 p.

Research output: Contribution to journalArticleScientificpeer-review

Bidirectional Variable-Order de Bruijn Graphs

Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M. & Puglisi, S. J., Dec 2018, In : International Journal of Foundations of Computer Science. 29, 8, p. 1279-1295 17 p.

Research output: Contribution to journalArticleScientificpeer-review

Editorial: Special Issue on "Combinatorial Algorithms" (IWOCA 2016)

Makinen, V. & Puglisi, S. J., Aug 2018, In : Theory of Computing Systems. 62, 6, p. 1349-1350 2 p.

Research output: Contribution to journalEditorialScientific

Open Access
File

Hybrid Indexing Revisited

Ferrada, H., Kempa, D. & Puglisi, S. J., 2018, 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX). Pagh, R. & Venkatasubramanian, S. (eds.). Society for Industrial and Applied Mathematics, p. 1-8 8 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

m-Bonsai: A Practical Compact Dynamic Trie

Poyias, A., Puglisi, S. J. & Raman, R., Dec 2018, In : International Journal of Foundations of Computer Science. 29, 8, p. 1257-1278 22 p.

Research output: Contribution to journalArticleScientificpeer-review

Relative Suffix Trees

Farruggia, A., Gagie, T., Navarro, G., Puglisi, S. J. & Sirén, J., May 2018, In : Computer Journal. 61, 5, p. 773-788 16 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

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

Block Graphs in Practice

Gagie, T., Hoobin, C. & Puglisi, S. J., Jun 2017, In : Mathematics in Computer Science. 11, 2, p. 191-196 6 p.

Research output: Contribution to journalArticleScientificpeer-review

Disentangled long-read de Bruijn graphs via optical maps

Alipahani, B., Salmela, L., Puglisi, S. J., Muggli, M. & Boucher, C., 2017, 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. Schwartz, R. & Reinert, K. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1:1-1:14 14 p. (Leibniz International Proceedings in Informatics; vol. 88).

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

emMAW: computing minimal absent words in external memory

Héliou, A., Pissis, S. P. & Puglisi, S. J., 1 Sep 2017, In : Bioinformatics. 33, 17, p. 2746-2749 4 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

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

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation

Kosolobov, D., Puglisi, S. J., Kociumaka, T., Gagie, T., Badkobeh, G. & Inenaga, S., 2017, String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017 Palermo, Italy, September 26–29, 2017 Proceedings 123. Fici, G., Sciortino, M. & Venturini, R. (eds.). Cham: Springer, p. 51-67 17 p. (Lecture Notes in Computer Science (LNCS); no. 10508).

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

Open Access

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

Succinct colored de Bruijn graphs

Muggli, M. D., Bowe, A., Noyes, N. R., Morley, P. S., Belk, K. E., Raymond, R., Gagie, T., Puglisi, S. J. & Boucher, C., 15 Oct 2017, In : Bioinformatics. 33, 20, p. 3181-3187 7 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
2016

Analyzing Relative Lempel-Ziv Reference Construction

Gagie, T., Puglisi, S. J. & Valenzuela, D., 18 Oct 2016, String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer, p. 160-165 6 p. (Lecture Notes in Computer Science; vol. 9954).

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

Bidirectional Variable-Order de Bruijn Graphs

Belazzougui, D., Gagie, T., Mäkinen, V. A. T., Previtali, M. & Puglisi, S. J., 2016, Theoretical informatics: LATIN 2016: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016 : proceedings. Kranakis, E., Navarro, G. & Chávez, E. (eds.). Berlin: Springer, p. 164-178 9 p. (Lecture Notes in Computer Science; vol. 9644).

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

Closed factorization

Badkobeh, G., Bannai, H., Goto, K., I, T., Iliopoulos, C. S., Inenaga, S., Puglisi, S. J. & Sugimoto, S., 30 Oct 2016, In : Discrete Applied Mathematics. 212, p. 23-29 7 p.

Research output: Contribution to journalArticleScientificpeer-review

Combinatorial Algorithms: 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings

Mäkinen, V. (ed.), Puglisi, S. J. (ed.) & Salmela, L. (ed.), 2016, Cham: Springer International Publishing . 434 p. (Theoretical Computer Science and General Issues; vol. 9843)

Research output: Book/ReportAnthology or special issueScientificpeer-review

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

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

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

Longest Common Abelian Factors and Large Alphabets

Badkobeh, G., Gagie, T., Grabowski, S., Nakashima, Y., Puglisi, S. J. & Sugimoto, S., 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 International Publishing AG, p. 254-259 6 p. (Lecture Notes in Computer Science; vol. 9954).

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

2015

Access, Rank, and Select in Grammar-compressed Strings

Belazzougui, D., Cording, P. H., Puglisi, S. J. & Tabei, Y., 2015, Algorithms – ESA 2015: 23rd Annual European Symposium Patras, Greece, September 14–16, 2015, Proceedings. Bansal, N. & Finocchi, I. (eds.). Heidelberg: Springer, p. 142-154 13 p. (Lecture Notes in Computer Science; vol. 9294).

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

Approximate pattern matching in LZ77-compressed texts

Gagie, T., Gawrychowski, P. & Puglisi, S. J., 2015, In : Journal of Discrete Algorithms. 32, p. 64-68 5 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

Fast and efficient compression of high-throughput sequencing reads

Hoobin, C., Kind, T., Boucher, C. & Puglisi, S. J., 2015, Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics . New York: ACM , p. 325-334 10 p.

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

General Document Retrieval in Compact Space

Navarro, G., Puglisi, S. J. & Valenzuela, D., 1 Jan 2015, In : ACM Journal of Experimental Algorithmics. 19, p. 2.3:1.1-2.3:1.46

Research output: Contribution to journalArticleScientificpeer-review

Misassembly detection using paired-end sequence reads and optical mapping data

Muggli, M. D., Puglisi, S. J., Ronen, R. & Boucher, C., 2015, In : Bioinformatics. 31, 12, p. 80-88 9 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

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

String Processing and Information Retrieval: 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings

Iliopoulos, C. S. (ed.), Puglisi, S. J. (ed.) & Yilmaz, E. (ed.), 2015, Cham: Springer International Publishing AG. 373 p. (Lecture Notes in Computer Science; vol. 9309)

Research output: Book/ReportAnthology or special issueScientificpeer-review

Variable-Order de Bruijn Graphs

Boucher, C., Bowe, A., Gagie, T., Puglisi, S. J. & Sadakane, K., 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. 383-392 10 p. (Data Compression Conference. Proceedings ).

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

2014

Block Graphs in Practice

Gagie, T., Hoobin, C. & Puglisi, S. J., 2014, Unknown host publication. Iliopoulos, C. S. & Langiu, A. (eds.). CEUR-WS.org, p. 30-36 7 p. (CEUR Workshop Proceedings; vol. 1146).

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

Closed Factorization

Badkobeh, G., Bannai, H., Goto, K., I, T., Iliopoulos, C. S., Inenaga, S., Puglisi, S. J. & Sugimoto, S., 2014, Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, September 1-3, 2014. Holub, J. & Zdárek, J. (eds.). Prague: Czech Technical University in Prague, Department of Theoretical Computer Science, Faculty of Information Technology, p. 162-168 7 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

Document Retrieval on Repetitive Collections

Navarro, G., Puglisi, S. J. & Sirén, J., 2014, Proceedings of the 22th Annual European Symposium on Algorithms (ESA 2014): 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. Schulz, A. S. & Wagner, D. (eds.). Berlin: Springer, p. 725-736 12 p. (Lecture Notes in Computer Science; vol. 8737).

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

Efficient Indexed Alignment of Contigs to Optical Maps

Muggli, M. D., Puglisi, S. J. & Boucher, C., 2014, Algorithms in Bioinformatics : 14th International Workshop, WABI 2014 Wroclaw, Poland, September 8-10, 2014 Proceedings. Brown, D. & Morgenstern, B. (eds.). Heidelberg: Springer, p. 68-81 14 p. (Lecture Notes in Computer Science; vol. 8701).

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

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

Hybrid indexes for repetitive datasets

Ferrada Escobar, H. R., Gagie, T., Hirvola, T. & Puglisi, S. J., 28 May 2014, In : Philosophical transactions - Royal Society. Mathematical, Physical and engineering sciences. 372, 2016, 9 p., 20130137.

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

Order-preserving matching

Kim, J., Eades, P., Fleischer, R., Hong, S-H., Iliopoulos, C. S., Park, K., Puglisi, S. J. & Tokuyama, T., 13 Mar 2014, In : Theoretical Computer Science. 525, p. 68-79 12 p.

Research output: Contribution to journalArticleScientificpeer-review

Relative Lempel-Ziv with Constant-Time Random Access

Ferrada, H., Gagie, T., Gog, S. & Puglisi, S. J., 2014, String Processing and Information Retrieval : 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20-22, 2014. Proceedings. Moura, E. S. D. & Crochemore, M. (eds.). Cham: Springer, p. 13-17 5 p. (Lecture Notes in Computer Science; vol. 8799).

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

Relative Lempel-Ziv with Constant-Time Random Access.

Ferrada Escobar, H. R., Puglisi, S. J., Gagie, T. & Navarro, G., 2014, Unknown host publication.

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