Travis Gagie

Affiliations:
  • Dalhousie University, Halifax, NS, Canada


According to our database1, Travis Gagie authored at least 214 papers between 2003 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Two-Dimensional Block Trees.
Comput. J., January, 2024

Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests.
CoRR, 2024

Space-Efficient Conversions from SLPs.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024

Wheeler Maps.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024

2023
μ- PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data.
Bioinform., September, 2023

Faster compressed quadtrees.
J. Comput. Syst. Sci., 2023

Ruler Wrapping.
Int. J. Comput. Geom. Appl., 2023

r-indexing without backward searching.
CoRR, 2023

Faster Maximal Exact Matches with Lazy LCP Evaluation.
CoRR, 2023

Another virtue of wavelet forests?
CoRR, 2023

Acceleration of FM-Index Queries Through Prefix-Free Parsing.
Proceedings of the 23rd International Workshop on Algorithms in Bioinformatics, 2023

A Simple Grammar-Based Index for Finding Approximately Longest Common Substrings.
Proceedings of the String Processing and Information Retrieval, 2023

Dynamic Compact Planar Embeddings.
Proceedings of the String Processing and Information Retrieval, 2023

Space-Time Trade-Offs for the LCP Array of Wheeler DFAs.
Proceedings of the String Processing and Information Retrieval, 2023

Data Structures for SMEM-Finding in the PBWT.
Proceedings of the String Processing and Information Retrieval, 2023

Flexible Grammar-based Indexes (invited paper).
Proceedings of the 23rd Conference Information Technologies, 2023

Recursive Prefix-Free Parsing for Building Big BWTs.
Proceedings of the Data Compression Conference, 2023

Augmented Thresholds for MONI.
Proceedings of the Data Compression Conference, 2023

Computing matching statistics on Wheeler DFAs.
Proceedings of the Data Compression Conference, 2023

MONI Can Find k-MEMs.
Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

Sum-of-Local-Effects Data Structures for Separable Graphs.
Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

2022
Efficient and compact representations of some non-canonical prefix-free codes.
Theor. Comput. Sci., 2022

Correction to: Graph Compression for Adjacency-Matrix Multiplication.
SN Comput. Sci., 2022

Graph Compression for Adjacency-Matrix Multiplication.
SN Comput. Sci., 2022

Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices.
Proc. VLDB Endow., 2022

MONI: A Pangenomic Index for Finding Maximal Exact Matches.
J. Comput. Biol., 2022

Finding Maximal Exact Matches Using the r-Index.
J. Comput. Biol., 2022

Preface to Special Issue for DCC 2020.
Inf. Comput., 2022

Space-efficient conversions from SLPs.
CoRR, 2022

A fast and simple O(z log n)-space index for finding approximately longest common substrings.
CoRR, 2022

Space-efficient RLZ-to-LZ77 conversion.
CoRR, 2022

Rectangular Ruler Wrapping.
CoRR, 2022

MARIA: Multiple-alignment r-index with aggregation.
CoRR, 2022

Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform.
CoRR, 2022

KATKA: A KRAKEN-like tool with k given at query time.
CoRR, 2022

An n H<sub>k</sub>-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers.
CoRR, 2022

MONI can find k-MEMs.
CoRR, 2022

RLBWT Tricks.
Proceedings of the 20th International Symposium on Experimental Algorithms, 2022

KATKA: A KRAKEN-Like Tool with k Given at Query Time.
Proceedings of the String Processing and Information Retrieval, 2022

On Representing the Degree Sequences of Sublogarithmic-Degree Wheeler Graphs.
Proceedings of the String Processing and Information Retrieval, 2022

Simple Worst-Case Optimal Adaptive Prefix-Free Coding.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

CSTs for Terabyte-Sized Data.
Proceedings of the Data Compression Conference, 2022

2021
Maximal unbordered factors of random strings.
Theor. Comput. Sci., 2021

Block trees.
J. Comput. Syst. Sci., 2021

An index for moving objects with constant-time access to their compressed trajectories.
Int. J. Geogr. Inf. Sci., 2021

Compact Euler Tours of Trees with Small Maximum Degree.
CoRR, 2021

$r$-indexing Wheeler graphs.
CoRR, 2021

Range Majorities and Minorities in Arrays.
Algorithmica, 2021

Compressing and Indexing Aligned Readsets.
Proceedings of the 21st International Workshop on Algorithms in Bioinformatics, 2021

Efficiently Merging r-indexes.
Proceedings of the 31st Data Compression Conference, 2021

PHONI: Streamed Matching Statistics with Multi-Genome References.
Proceedings of the 31st Data Compression Conference, 2021

A Fast and Small Subsampled R-Index.
Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching, 2021

Succinct Euler-Tour Trees.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

PFP Compressed Suffix Trees.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2021

2020
Tree path majority data structures.
Theor. Comput. Sci., 2020

Refining the <i>r</i>-index.
Theor. Comput. Sci., 2020

Matching Reads to Many Genomes with the r-Index.
J. Comput. Biol., 2020

Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.
J. Comput. Biol., 2020

Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space.
J. ACM, 2020

Computation over compressed data.
Inf. Comput., 2020

PFP Data Structures.
CoRR, 2020

Fast and compact planar embeddings.
Comput. Geom., 2020

More Time-Space Tradeoffs for Finding a Shortest Unique Substring.
Algorithms, 2020

Compressed Dynamic Range Majority and Minority Data Structures.
Algorithmica, 2020

Practical Random Access to SLP-Compressed Texts.
Proceedings of the String Processing and Information Retrieval, 2020

Decompressing Lempel-Ziv Compressed Text.
Proceedings of the Data Compression Conference, 2020

2019
Compressed Indexes for Repetitive Textual Datasets.
Proceedings of the Encyclopedia of Big Data Technologies., 2019

Path queries on functions.
Theor. Comput. Sci., 2019

Sparse Dynamic Programming on DAGs with Small Width.
ACM Trans. Algorithms, 2019

A compact index for order-preserving pattern matching.
Softw. Pract. Exp., 2019

25 Years of the Burrows-Wheeler Transform (Dagstuhl Seminar 19241).
Dagstuhl Reports, 2019

Tree-Shape Grammars for Random Access.
CoRR, 2019

Simulating the DNA String Graph in Succinct Space.
CoRR, 2019

Prefix-free parsing for building big BWTs.
Algorithms Mol. Biol., 2019

Rpair: Rescaling RePair with Rsync.
Proceedings of the String Processing and Information Retrieval, 2019

Faster Dynamic Compressed d-ary Relations.
Proceedings of the String Processing and Information Retrieval, 2019

Tunneling on Wheeler Graphs.
Proceedings of the Data Compression Conference, 2019

Simulating the DNA Overlap Graph in Succinct Space.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

2018
A separation between RLSLPs and LZ77.
J. Discrete Algorithms, 2018

Bidirectional Variable-Order de Bruijn Graphs.
Int. J. Found. Comput. Sci., 2018

Diverse Palindromic Factorization is NP-Complete.
Int. J. Found. Comput. Sci., 2018

Relative compression of trajectories.
CoRR, 2018

The Read-Optimized Burrows-Wheeler Transform.
CoRR, 2018

Assembling Omnitigs using Hidden-Order de Bruijn Graphs.
CoRR, 2018

Prefix-Free Parsing for Building Big BWTs.
CoRR, 2018

Fast Lempel-Ziv Decompression in Linear Space.
CoRR, 2018

Relative Suffix Trees.
Comput. J., 2018

Practical dynamic de Bruijn graphs.
Bioinform., 2018

Guest Editorial: Special Issue on Compact Data Structures.
Algorithmica, 2018

Prefix-Free Parsing for Building Big BWTs.
Proceedings of the 18th International Workshop on Algorithms in Bioinformatics, 2018

Optimal-Time Text Indexing in BWT-runs Bounded Space.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended.
Proceedings of the Research in Computational Molecular Biology, 2018

On the Approximation Ratio of Lempel-Ziv Parsing.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Tree Path Majority Data Structures.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication.
Proceedings of the 2018 Data Compression Conference, 2018

Online LZ77 Parsing and Matching Statistics with RLBWTs.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017
Wheeler graphs: A framework for BWT-based data structures.
Theor. Comput. Sci., 2017

String cadences.
Theor. Comput. Sci., 2017

Compressed Spaced Suffix Arrays.
Math. Comput. Sci., 2017

Block Graphs in Practice.
Math. Comput. Sci., 2017

Burrows-Wheeler transform and LCP array construction in constant space.
J. Discrete Algorithms, 2017

Preface - Compact Data Structures.
J. Discrete Algorithms, 2017

Document retrieval on repetitive string collections.
Inf. Retr. J., 2017

A Separation Between Run-Length SLPs and LZ77.
CoRR, 2017

Exploiting Computation-Friendly Graph Compression Methods.
CoRR, 2017

Speeding up Dynamic Programming on DAGs through a Fast Approximation of Path Cover.
CoRR, 2017

Fast Locating with the RLBWT.
CoRR, 2017

Parallel Construction of Compact Planar Embeddings.
CoRR, 2017

Fast and Simple Jumbled Indexing for Binary RLE Strings.
CoRR, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
CoRR, 2017

Succinct colored de Bruijn graphs.
Bioinform., 2017

Efficient Compression and Indexing of Trajectories.
Proceedings of the String Processing and Information Retrieval, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
Proceedings of the String Processing and Information Retrieval, 2017

An Encoding for Order-Preserving Matching.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Compressed Dynamic Range Majority Data Structures.
Proceedings of the 2017 Data Compression Conference, 2017

Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Flexible Indexing of Repetitive Collections.
Proceedings of the Unveiling Dynamics and Complexity, 2017

2016
Dictionary-Based Data Compression.
Encyclopedia of Algorithms, 2016

Rank and Select Operations on Sequences.
Encyclopedia of Algorithms, 2016

Toward a Succinct Index for Order-Preserving Pattern Matching.
CoRR, 2016

Practical combinations of repetition-aware data structures.
CoRR, 2016

Analyzing Relative Lempel-Ziv Reference Construction.
Proceedings of the String Processing and Information Retrieval, 2016

Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes.
Proceedings of the String Processing and Information Retrieval, 2016

RLZAP: Relative Lempel-Ziv with Adaptive Pointers.
Proceedings of the String Processing and Information Retrieval, 2016

Fully Dynamic de Bruijn Graphs.
Proceedings of the String Processing and Information Retrieval, 2016

Longest Common Abelian Factors and Large Alphabets.
Proceedings of the String Processing and Information Retrieval, 2016

2015
Efficient and Compact Representations of Prefix Codes.
IEEE Trans. Inf. Theory, 2015

Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly.
IEEE ACM Trans. Comput. Biol. Bioinform., 2015

Approximate pattern matching in LZ77-compressed texts.
J. Discrete Algorithms, 2015

Relative Compressed Suffix Trees.
CoRR, 2015

Diverse Palindromic Factorization is NP-Complete.
CoRR, 2015

Approximating LZ77 in Small Space.
CoRR, 2015

Binary Jumbled Pattern Matching on Trees and Tree-Like Structures.
Algorithmica, 2015

Relative Select.
Proceedings of the String Processing and Information Retrieval, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.
Proceedings of the Algorithms - ESA 2015, 2015

Diverse Palindromic Factorization Is NP-complete.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Document Counting in Compressed Space.
Proceedings of the 2015 Data Compression Conference, 2015

Faster Compressed Quadtrees.
Proceedings of the 2015 Data Compression Conference, 2015

Variable-Order de Bruijn Graphs.
Proceedings of the 2015 Data Compression Conference, 2015

Queries on LZ-Bounded Encodings.
Proceedings of the 2015 Data Compression Conference, 2015

Composite Repetition-Aware Data Structures.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014
A subquadratic algorithm for minimum palindromic factorization.
J. Discrete Algorithms, 2014

Searching and Indexing Genomic Databases via Kernelization.
CoRR, 2014

Reusing an FM-index.
CoRR, 2014

Document Counting in Practice.
CoRR, 2014

Suffix Arrays for Spaced-SNP Databases.
CoRR, 2014

Entropy-bounded representation of point grids.
Comput. Geom., 2014

Efficient Fully-Compressed Sequence Representations.
Algorithmica, 2014

Relative Lempel-Ziv with Constant-Time Random Access.
Proceedings of the String Processing and Information Retrieval, 2014

Relative FM-Indexes.
Proceedings of the String Processing and Information Retrieval, 2014

LZ77-Based Self-indexing with Faster Pattern Matching.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Relative Lempel-Ziv with Constant-Time Random Access.
Proceedings of the Data Compression Conference, 2014

Indexed Geometric Jumbled Pattern Matching.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
Colored range queries and document retrieval.
Theor. Comput. Sci., 2013

Minimax trees in linear time with applications.
Eur. J. Comb., 2013

AliBI: An Alignment-Based Index for Genomic Datasets.
CoRR, 2013

Hybrid Indexes for Repetitive Datasets.
CoRR, 2013

Better Space Bounds for Parameterized Range Majority and Minority.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs.
Proceedings of the String Processing and Information Retrieval, 2013

Document Listing on Repetitive Collections.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

New Algorithms for Position Heaps.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Heaviest Induced Ancestors and Longest Common Substrings.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2012
New algorithms on wavelet trees and applications to information retrieval.
Theor. Comput. Sci., 2012

Bounds from a card trick.
J. Discrete Algorithms, 2012

An efficient algorithm to test square-freeness of strings compressed by straight-line programs.
Inf. Process. Lett., 2012

Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching
CoRR, 2012

Sequential-Access FM-Indexes
CoRR, 2012

Linear-Space Substring Range Counting over Polylogarithmic Alphabets
CoRR, 2012

A Note on Sequence Prediction over Large Alphabets.
Algorithms, 2012

Lightweight Data Indexing and Compression in External Memory.
Algorithmica, 2012

Indexed Multi-pattern Matching.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Forbidden Patterns.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

A Faster Grammar-Based Self-index.
Proceedings of the Language and Automata Theory and Applications, 2012

2011
Tight bounds for online stable sorting.
J. Discrete Algorithms, 2011

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case.
Discret. Appl. Math., 2011

A Compressed Self-Index for Genomic Databases
CoRR, 2011

A Faster LZ77-Based Index
CoRR, 2011

Finding Frequent Elements in Compressed 2D Arrays and Strings.
Proceedings of the String Processing and Information Retrieval, 2011

Faster Approximate Pattern Matching in Compressed Repetitive Texts.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Counting Colours in Compressed Strings.
Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

2010
Move-to-Front, Distance Coding, and Inversion Frequencies revisited.
Theor. Comput. Sci., 2010

Pattern Kits
CoRR, 2010

Colored Range Queries and Document Retrieval.
Proceedings of the String Processing and Information Retrieval, 2010

Fast and Compact Prefix Codes.
Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Grammar-Based Compression in a Streaming Model.
Proceedings of the Language and Automata Theory and Applications, 2010

Alphabet Partitioning for Compressed Rank/Select and Applications.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

A Better Bouncer's Algorithm.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

2009
New algorithms and lower bounds for sequential access data compression.
PhD thesis, 2009

Compressed depth sequences.
Theor. Comput. Sci., 2009

A New Algorithm for Building Alphabetic Minimax Trees.
Fundam. Informaticae, 2009

A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source
CoRR, 2009

Grammar-Based Compression in a Streaming Model
CoRR, 2009

Alphabet Partitioning for Compressed Rank/Select with Applications
CoRR, 2009

Another Virtue of Wavelet Trees
CoRR, 2009

New Algorithms and Lower Bounds for Sequential-Access Data Compression
CoRR, 2009

Worst-Case Optimal Adaptive Prefix Coding.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Range Quantile Queries: Another Virtue of Wavelet Trees.
Proceedings of the String Processing and Information Retrieval, 2009

Low-Memory Adaptive Prefix Coding.
Proceedings of the 2009 Data Compression Conference (DCC 2009), 2009

On the Value of Multiple Read/Write Streams for Data Compression.
Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008
Dictionary-Based Data Compression.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Sorting streamed multisets.
Inf. Process. Lett., 2008

Dynamic asymmetric communication.
Inf. Process. Lett., 2008

Minimax Trees in Linear Time
CoRR, 2008

2007
Dynamic Shannon coding.
Inf. Process. Lett., 2007

Bounds for Compression in Streaming Models
CoRR, 2007

Empirical entropy in context
CoRR, 2007

A nearly tight memory-redundancy trade-off for one-pass compression
CoRR, 2007

Space-Conscious Compression.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006
Large alphabets and incompressibility.
Inf. Process. Lett., 2006

Compressing probability distributions.
Inf. Process. Lett., 2006

On the space complexity of one-pass compression
CoRR, 2006

2005
Restructuring binary search trees revisited.
Inf. Process. Lett., 2005

Sorting a Low-Entropy Sequence
CoRR, 2005

2003
New Ways to Construct Binary Search Trees.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003


  Loading...