Travis Gagie

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

Publications 2013 2017

2017

Compressed Spaced Suffix Arrays

Gagie, T., Manzini, G. & Valenzuela, D., Jun 2017, In : Mathematics in Computer Science. 11, 2, p. 151-157 7 p.

Research output: Contribution to journalArticleScientificpeer-review

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

Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes

Farina, A., Gagie, T., Manzini, G., Navarro, G. & Ordonez, A., 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. 50-60 11 p. (Lecture Notes in Computer Science; vol. 9954).

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

Fully Dynamic de Bruijn Graphs

Belazzougui, D., Gagie, T., Mäkinen, V. & Previtali, M., 2016, String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer, p. 145-152 8 p. (Lecture Notes in Computer Science; vol. 9954).

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

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

Approximating LZ77 via Small-Space Multiple-Pattern Matching

Fischer, J., Gagie, T., Gawrychowski, P. & Kociumaka, T., 2015, Algorithms – ESA 2015: 23rd Annual European Symposium Patras, Greece, September 14–16, 2015, Proceedings. Bansal, N. & Finocchi, I. (eds.). Heidelberg: Springer, p. 533-544 12 p. (Lecture Notes in Computer Science; vol. 9294).

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

Composite Repetition-Aware Data Structures

Belazzougui, D., Cunial, F., Gagie, T., Prezza, N. & Raffinot, M., 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.). Cham: Springer International Publishing AG, p. 26-39 14 p. (Lecture Notes in Computer Science ; no. 9133)(LNCS sublibrary. SL 1, Theoretical computer science and general issues).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-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 and Compact Representations of Prefix Codes

Gagie, T., Navarro, G., Nekrich, Y. & Ordonez, A., Sep 2015, In : IEEE Transactions on Information Theory. 61, 9, p. 4999-5011 13 p.

Research output: Contribution to journalArticleScientificpeer-review

Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly

Tomescu, A. I., Gagie, T., Popa, A., Rizzi, R., Kuosmanen, A. E. & Mäkinen, V. A. T., Dec 2015, In : IEEE/ACM Transactions on Computational Biology and Bioinformatics. 12, 6, p. 1345-1354 10 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Faster Compressed Quadtrees

Gonzalez-Nova, J., Gagie, T., Ladra, S., Navarro, G. & Seco, D., 2015, DCC 2015: 2015 Data Compression Conference, 7-9 April 2015, Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, E. J. & Storer, J. A. (eds.). Los Alamitos, CA: IEEE, p. 93-102 10 p. (Data Compression Conference. Proceedings ).

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

Rank and Select Operations on Sequences

Gagie, T., 2015, Encyclopedia of Algorithms. Kao, M-Y. (ed.). New York: Springer

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

Relative Select

Boucher, C., Bowe, A., Gagie, T., Manzini, G. & Siren, J., 2015, String Processing and Information Retrieval: 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings. Iliopoulos, C., Puglisi, S. & Yilmaz, E. (eds.). Cham: Springer International Publishing AG, p. 149-155 7 p. (Lecture Notes in Computer Science; vol. 9309).

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

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

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

Compressed Spaced Suffix Arrays

Gagie, T., Manzini, G. & Valenzuela, D., 2014, ICABD 2014, 2nd International Conference on Algorithms for Big Data: Palermo, Italy, April 7-9, 2014, Proceedings. Iliopoulos, C. S. & Langui, A. (eds.). p. 37-45 9 p. (CEUR Workshop Proceedings; vol. 1146).

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

Efficient Fully-Compressed Sequence Representations

Barbay, J., Claude, F., Gagie, T., Navarro, G. & Nekrich, Y., May 2014, In : Algorithmica. 69, 1, p. 232-268 37 p.

Research output: Contribution to journalArticleScientificpeer-review

Entropy-bounded representation of point grids

Farzan, A., Gagie, T. & Navarro, G., Jan 2014, In : Computational Geometry. 47, 1, p. 1-14 14 p.

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

Indexed Geometric Jumbled Pattern Matching

Durocher, S., Fraser, R., Gagie, T., Mondal, D., Skala, M. & Thankachan, S. V., 2014, Combinatorial Pattern Matching 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Kulikov, AS., Kuznetsov, SO. & Pevzner, P. (eds.). Cham: Springer, p. 110-119 10 p. (Lecture Notes in Computer Science; vol. 8486).

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

Relative FM-Indexes

Belazzougui, D., Gagie, T., Gog, S., Manzini, G. & Sirén, J., 2014, String Processing and Information Retrieval : 21st International Symposium, SPIRE 2014 Ouro Preto, Brazil, October 20-22, 2014 Proceedings. Moura, E. & Crochemore, M. (eds.). Cham: Springer, p. 52-64 13 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, 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

2013

Better Space Bounds for Parameterized Range Majority and Minority

Belazzougui, D., Gagie, T. & Navarro, G., 2013, Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Dehne, F., Solis-Oba, R. & Sack, J-R. (eds.). Springer-Verlag, p. 121-132 (Lecture Notes in Computer Science; vol. 8037).

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

Binary Jumbled Pattern Matching on Trees and Tree-Like Structures

Gagie, T., Hermelin, D., Landau, G. M. & Weimann, O., 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. 517-528 (Lecture Notes in Computer Science; vol. 8125).

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

Colored range queries and document retrieval

Gagie, T., Kärkkäinen, J., Navarro, G. & Puglisi, S. J., 29 Apr 2013, In : Theoretical Computer Science. 483, p. 36-50 15 p.

Research output: Contribution to journalArticleScientificpeer-review

Document Listing on Repetitive Collections

Gagie, T., Karhu, K., Navarro, G., Puglisi, S. & Siren, J., 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. 107-119 (Lecture Notes in Computer Science; vol. 7922).

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

Heaviest Induced Ancestors and Longest Common Substrings

Gagie, T., Gawrychowski, P. & Nekrich, Y., 2013, Proceedings of CCCG '13. 6 p.

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

Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs

Cicalese, F., Gagie, T., Giaquinta, E., Laber, E. S., Lipták, Z., Rizzi, R. & Tomescu, A., 2013, String Processing and Information Retrieval: 20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings. Kurland, O., Lewenstein, M. & Porat, E. (eds.). Springer-Verlag, p. 56-63 (Lecture Notes in Computer Science; vol. 8214).

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

Minimax trees in linear time with applications

Gagie, T. & Gawrychowski, P., 2013, In : European Journal of Combinatorics. 34, 1, p. 82-90

Research output: Contribution to journalArticleScientificpeer-review

New Algorithms for Position Heaps

Gagie, T., Hon, W-K. & Ku, T-H., 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. 95-106 (Lecture Notes in Computer Science; vol. 7922).

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

On the Value of Multiple Read/Write Streams for Data Compression

Gagie, T., 2013, Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede.

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