arXiv Papers
2024
2024/11
- An Implementation and Experimental Comparison of Dynamic Ordered Sets
- Top-k Stabbing Interval Queries
2024/10
- Faster and Simpler Online Computation of String Net Frequency
- Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
- On the Complexity of Computing the Co-lexicographic Width of a Regular Language
- Small Space Encoding and Recognition of $k$-Palindromic Prefixes
- Closed Repeats
- TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
- The Quasi-probability Method and Applications for Trace Reconstruction
- Stability properties for subgroups generated by return words
- Incremental computation of the set of period sets
- Palindromic length of infinite aperiodic words
- Utilizing ChatGPT in a Data Structures and Algorithms Course: A Teaching Assistant’s Perspective
- Many Flavors of Edit Distance
- Palindromes Compression and Retrieval
- Subsequence Matching and Analysis Problems for Formal Languages
- Packed Acyclic Deterministic Finite Automata
- Lyndon-like cyclic sieving and Gauss congruence
- An Algorithm for a Variation of the Shortest Common Superstring Problem
- Deterministic Suffix-reading Automata
- On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
- Faster two-dimensional pattern matching with $k$ mismatches
- A Family of LZ78-based Universal Sequential Probability Assignments
- New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
- On the longest increasing subsequence and number of cycles of butterfly permutations
- Relating Left and Right Extensions of Maximal Repeats
- Relative position in binary substitutions
2024/9
- Substring Compression Variations and LZ78-Derivates
- Fast and Small Subsampled R-indexes
- Computing String Covers in Sublinear Time
- Lempel-Ziv (LZ77) Factorization in Sublinear Time
- The repetition threshold for ternary rich words
- Christoffel Matrices and Sturmian Determinants
- Compression with wildcards: All induced metric subgraphs
- An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
- Computing the LZ-End parsing: Easy to implement and practically efficient
- V-Words, Lyndon Words and Galois Words
- Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
- Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
- An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
- Toward Greener Matrix Operations by Lossless Compressed Formats
2024/8
- Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences
- New Compressed Indices for Multijoins on Graph Databases
- Online Computation of String Net Frequency
- A Connection Between Unbordered Partial Words and Sparse Rulers
- Avoiding abelian and additive powers in rich words
- Exponent-Strings and Their Edit Distance
- On the Number of Non-equivalent Parameterized Squares in a String
- Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
- Constant-time $ψ$ queries in $O \left( r \log \frac{n}{r} + r \log σ\right)$ bits
- Simple Linear-time Repetition Factorization
- Longest Common Extensions with Wildcards: Trade-off and Applications
- Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
2024/7
- Words Avoiding Tangrams
- Upper bounds on the average edit distance between two random strings
- Fast computation of the period and of the shortest cover of a string using its Character-Distance-Sampling representation
- All-Pairs Suffix-Prefix on Dynamic Set of Strings
- Online String Attractors
- Text Indexing for Long Patterns using Locally Consistent Anchors
- Some Remarks on Palindromic Periodicities
- Improved Lower Bounds on the Expected Length of Longest Common Subsequences
- The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
- Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
- Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings
- MIOV: Reordering MOVI for even better locality
- Standard Lyndon loop words: weighted orders
- Subsequence Pattern Matching with Segment Number Constraint
- Rollercoasters with Plateaus
- Tight Bounds for the Number of Absent Scattered Factors
- On Computing the Smallest Suffixient Set
2024/6
- Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
- Counting on General Run-Length Grammars
- Space-efficient SLP Encoding for $O(\log N)$-time Random Access
- Implementation Of Dynamic De Bruijn Graphs Via Learned Index
- Almost Linear Size Edit Distance Sketch
- String Partition for Building Big BWTs
- The reflection complexity of sequences over finite alphabets
- Repetition Threshold for Binary Automatic Sequences
- Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
- Indexing Finite-State Automata Using Forward-Stable Partitions
- Maximal number of subword occurrences in a word
- Word equations, constraints, and formal languages
- A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs
- A Symmetry Property of Christoffel Words
- Evaluating $n$-Gram Novelty of Language Models Using Rusty-DAWG
- The Repetition Threshold for Rote Sequences
- Unveiling the connection between the Lyndon factorization and the Canonical Inverse Lyndon factorization via a border property
- Perfectly Clustering Words and Iterated Palindromes over a Ternary Alphabet
- Bijective BWT based compression schemes
2024/5
- A Lock-free Binary Trie
- Querying in Constant Time with Learned Indexes
- Minimizing the Minimizers via Alphabet Reordering
- SPIDER: Improved Succinct Rank and Select Performance
- Finding Diverse Strings and Longest Common Subsequences in a Graph
- De Bruijn Polyominoes
- Theoretical insights and an experimental comparison of tango trees and multi-splay trees
- Lyndon pairs and the lexicographically greatest perfect necklace
- Adaptive Dynamic Bitvectors
- String 2-Covers with No Length Restrictions
- Lock-Free Augmented Trees
- Kolmogorov complexity as a combinatorial tool
- Counting overlapping pairs of strings
2024/4
- Generalized Straight-Line Programs
- Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
- Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality
- Fast and Simple Sorting Using Partial Information
- Enumerating runs, valleys, and peaks in Catalan words
- Characterization of Isometric Words based on Swap and Mismatch Distance
- On multidimensional generalization of binary search
- Computing the LCP Array of a Labeled Graph
- Hairpin Completion Distance Lower Bound
- Better space-time-robustness trade-offs for set reconciliation
- Bit catastrophes for the Burrows-Wheeler Transform
- Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
- Dynamic Suffix Array in Optimal Compressed Space
- Frogs, hats and common subsequences
- Exploring Repetitiveness Measures for Two-Dimensional Strings
- From the Lyndon factorization to the Canonical Inverse Lyndon factorization: back and forth
- Internal Pattern Matching in Small Space and Applications
- Scalable Distributed String Sorting
- Exploiting New Properties of String Net Frequency for Efficient Computation
2024/3
- How to Find Long Maximal Exact Matches and Ignore Short Ones
- String attractors and bi-infinite words
- A simpler data structure for dynamic strings
- BAT-LZ Out of Hell
- Height-bounded Lempel-Ziv encodings
- Simplified Tight Bounds for Monotone Minimal Perfect Hashing
- Optimal Bounds for Distinct Quartics
- NP-Completeness for the Space-Optimality of Double-Array Tries
- Enumeration for MSO-Queries on Compressed Trees
- A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
- Algorithms for Galois Words: Detection, Factorization, and Rotation
- On the Communication Complexity of Approximate Pattern Matching
- On the complexity and approximability of Bounded access Lempel Ziv coding
- Exploring the Crochemore and Ziv-Lempel factorizations of some automatic sequences with the software Walnut
- Space-Efficient Indexes for Uncertain Strings
2024/2
- Consecutive Power Occurrences in Sturmian Words
- Iterated Straight-Line Programs
- Pattern Matching with Mismatches and Wildcards
- Palindromic Periodicities
- ShiftDTW: adapting the DTW metric for cyclic time series clustering
- A visualization tool to explore alphabet orderings for the Burrows-Wheeler Transform
- Computing Longest Common Subsequence under Cartesian-Tree Matching Model
- Edit and Alphabet-Ordering Sensitivity of Lex-parse
- Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
- Shortest cover after edit
- A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
- Enhanced Graph Pattern Matching
- Regular Languages in the Sliding Window Model
- Approximate Circular Pattern Matching under Edit Distance
- Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
- Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
2024/1
- Combinatorics on words and generating Dirichlet series of automatic sequences
- Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
- Heuristics for the Run-length Encoded Burrows-Wheeler Transform Alphabet Ordering Problem
- Towards Optimal Grammars for RNA Structures
- Efficient Construction of Long Orientable Sequences
2023
2023/12
- Range Entropy Queries and Partitioning
- Selective Run-Length Encoding
- Phylogenetic tree distance computation over succinct representations
- A Huffman based short message service compression technique using adjacent distance array
- Faster Algorithms for Internal Dictionary Queries
- Some Fibonacci-Related Sequences
- More characterizations of morphic words
- Staircase graph words
- A symbolic-arithmetic for teaching double-black node removal in red-black trees
- r-indexing without backward searching
2023/11
- Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
- Dynamic Dictionary with Subconstant Wasted Bits per Key
- On the piecewise complexity of words and periodic words
- Enumeration and Succinct Encoding of AVL Trees
- Repetition factorization of automatic sequences
- The analogue of overlap-freeness for the Fibonacci morphism
- Critical exponent of binary words with few distinct palindromes
- Pairwise sequence alignment with block and character edit operations
- Differentially Private Approximate Pattern Matching
- Faster Maximal Exact Matches with Lazy LCP Evaluation
- Exact Shortest Paths with Rational Weights on the Word RAM
- Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
- Space-Efficient Data Structures for Polyominoes and Bar Graphs
- Size-constrained Weighted Ancestors with Applications
2023/10
- Optimization with pattern-avoiding input
- Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
- The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold
- Searching 2D-Strings for Matching Frames
- Finding a reconfiguration sequence between longest increasing subsequences
- Structure and growth of $\mathbb{R}$-bonacci words
- Dynamic Dynamic Time Warping
- Rank and Select on Degenerate Strings
- Fast and simple unrooted dynamic forests
- Sketching and Streaming for Dictionary Compression
- Efficient Online String Matching through Linked Weak Factors
- Faster Algorithms for Text-to-Pattern Hamming Distances
- Deterministic 3SUM-Hardness
2023/9
- Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
- The repetition threshold of episturmian sequences
- $(\min,+)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
- On Unique Factorization of Non-periodic Words
- Dynamic “Succincter”
- Correlations of minimal forbidden factors of the Fibonacci word
- Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time
2023/8
- Linear Time Construction of Cover Suffix Tree and Applications
- An Algorithm for the Constrained Longest Common Subsequence and Substring Problem
- Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
- Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
- String attractors of Rote sequences
- An Algorithm for the Longest Common Subsequence and Substring Problem
- Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions
- Quantum Circuits for Fixed Substring Matching Problems
- Adaptive Encoding Strategies for Erasing-Based Lossless Floating-Point Compression
- Hierarchical Lowrank Arithmetic with Binary Compression
- Wheeler maps
- Matching Patterns with Variables Under Simon’s Congruence
- Another virtue of wavelet forests?
- Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
- Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
2023/7
- Approximating Edit Distance in the Fully Dynamic Model
- Computing SEQ-IC-LCS of Labeled Graphs
- Random Wheeler Automata
- Compressibility measures for two-dimensional data
- Sliding suffix trees simplified
- Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
- Linear-time computation of generalized minimal absent words for multiple strings
- Two-dimensional Dyck words
- Evaluating Regular Path Queries on Compressed Adjacency Matrices
- Shorter and faster than Sort3AlphaDev
- A Compact DAG for Storing and Searching Maximal Common Subsequences
- Efficient algorithms for enumerating maximal common subsequences of two strings
- Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
2023/6
- Optimal Wheeler Language Recognition
- Longest Common Prefix Arrays for Succinct k-Spectra
- Maintaining the cycle structure of dynamic permutations
- Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
- Pb-Hash: Partitioned b-bit Hashing
- Erasing-based lossless compression method for streaming floating-point time series
- Approximate Cartesian Tree Matching: an Approach Using Swaps
- Prefix-free graphs and suffix array construction in sublinear space
- Faster Compression of Deterministic Finite Automata
- Counting occurrences of patterns in permutations
- Efficient Parameterized Pattern Matching in Sublinear Space
- On the $k$-Hamming and $k$-Edit Distances
- Subsequence frequency in binary words
- Space-time Trade-offs for the LCP Array of Wheeler DFAs
- Efficient Parallel Output-Sensitive Edit Distance
- Computing all-vs-all MEMs in grammar-compressed text
2023/5
- Optimal Algorithms for Bounded Weighted Edit Distance
- Acceleration of FM-index Queries Through Prefix-free Parsing
- Sorting Finite Automata via Partition Refinement
- Sum-of-Local-Effects Data Structures for Separable Graphs
- Ranking and unranking bordered and unbordered words
- Prefix Sorting DFAs: a Recursive Algorithm
- The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing
- Streaming $k$-edit approximate pattern matching via string decomposition
- CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
- Can You Solve Closest String Faster than Exhaustive Search?
- Affine Standard Lyndon words: A-type
- Engineering Rank/Select Data Structures for Big-Alphabet Strings
- Finding Maximal Exact Matches in Graphs
- Matching Statistics speed up BWT construction
2023/4
- Faster Prefix-Sorting Algorithms for Deterministic Finite Automata
- Subcubic algorithm for (Unweighted) Unrooted Tree Edit Distance
- Lossy Compressor preserving variant calling through Extended BWT
- The Longest Subsequence-Repeated Subsequence Problem
- The 2-Attractor Problem is NP-Complete
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
- Longest Common Subsequence with Gap Constraints
- Ranking and Unranking k-subsequence universal words
- Fast computation of approximate weak common intervals in multiple indeterminate strings
- On arch factorization and subword universality for words and compressed words
- Learned Monotone Minimal Perfect Hashing
- Compressed Indexing for Consecutive Occurrences
2023/3
- Enumerating all minimal hitting sets in polynomial total time
- Optimal Square Detection Over General Alphabets
- Optimal-Hash Exact String Matching Algorithms
- B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load
- Change a Bit to save Bytes: Compression for Floating Point Time-Series Data
- On Sensitivity of Compact Directed Acyclic Word Graphs
- The analogue of overlap-freeness for the period-doubling sequence
- On the Maximal Independent Sets of $k$-mers with the Edit Distance
- The Many Qualities of a New Directly Accessible Compression Scheme
- Sturmian and infinitely desubstitutable words accepted by an ω-automaton
2023/2
- Optimal Heaviest Induced Ancestors
- Order-Preserving Squares in Strings
- Faster Wavelet Trees with Quad Vectors
- Compressibility-Aware Quantum Algorithms on Strings
- A Simple Data Structure for Maintaining a Discrete Probability Distribution
- Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
- Prefixes of the Fibonacci word
- Chaining of Maximal Exact Matches in Graphs
- Locally consistent decomposition of strings with applications to edit distance sketching
- Storing a Trie with Compact and Predictable Space
- Weighted Edit Distance Computation: Strings, Trees and Dyck
- Optimal LZ-End Parsing is Hard
- Runs of Ones in Binary Strings
- An Efficient B-tree Implementation for Memory-Constrained Embedded Systems
- Smallest and Largest Block Palindrome Factorizations
- String attractors of fixed points of k-bonacci-like morphisms
- From Bit-Parallelism to Quantum String Matching for Labelled Graphs
- Rudin-Shapiro Sums Via Automata Theory and Logic
- A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
2023/1
- Algorithms for Massive Data – Lecture Notes
- The Thue-Morse sequence in base 3/2
- Succinct Planar Encoding with Minor Operations
- Sliding Window String Indexing in Streams
- Computing matching statistics on Wheeler DFAs
- Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
- SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree
- Reconstructing words using queries on subwords or factors
- Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
- Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
- Dyck Words, Pattern Avoidance, and Automatic Sequences
2022
2022/12
- High Performance Construction of RecSplit Based Minimal Perfect Hash Functions
- Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
- Transcoding Unicode Characters with AVX-512 Instructions
- Pareto Optimal Compression of Genomic Dictionaries, with or without Random Access in Main Memory
- Word Equations in Synergy with Regular Constraints (Technical Report)
- Space-efficient conversions from SLPs
- Trie-Compressed Intersectable Sets
- Computing the optimal BWT of very large string collections
2022/11
- Polyominoes and graphs built from Fibonacci words
- 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
- Computing palindromes on a trie in linear time
- Comparing Two Counting Methods for Estimating the Probabilities of Strings
- String attractors of episturmian sequences
- An Algorithmic Bridge Between Hamming and Levenshtein Distances
- String Covering: A Survey
- Reversible Programming: A Case Study of Two String-Matching Algorithms
- Optimal resizable arrays
- Some Results on Digital Segments and Balanced Words
- Genome-on-Diet: Taming Large-Scale Genomic Analyses via Sparsified Genomics
- On the Power of Learning-Augmented BSTs
- Augmented Thresholds for MONI
- Bounds and Estimates on the Average Edit Distance
- External-memory dictionaries with worst-case update cost
- Gapped String Indexing in Subquadratic Space and Sublinear Query Time
- Approximating binary longest common subsequence in almost-linear time
- Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
- On fractal patterns in Ulam words
- A fast and simple $O (z \log n)$-space index for finding approximately longest common substrings
- Space-efficient RLZ-to-LZ77 conversion
- CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams
2022/10
- Computing MEMs on Repetitive Text Collections
- Space-Efficient STR-IC-LCS Computation
- SicHash - Small Irregular Cuckoo Tables for Perfect Hashing
- A nearly optimal randomized algorithm for explorable heap selection
- Internal Longest Palindrome Queries in Optimal Time
- Computing maximal generalized palindromes
- Double-Ended Palindromic Trees: A Linear-Time Data Structure and Its Applications
- Designing a parallel suffix sort
- Finding binary words with a given number of subsequences
- The appearance function for paper-folding words
- On word-representability of simplified de Bruijn graphs
- Locality-Preserving Minimal Perfect Hashing of k-mers
- A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees
- Splay Top Trees
2022/9
- Space-efficient data structure for next/previous larger/smaller value queries
- Maximal Closed Substrings
- Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching
- Elastic-Degenerate String Matching with 1 Error
- Inferring strings from position heaps in linear time
- Complement Avoidance in Binary Words
- Convergence of the number of period sets in strings
- Antisquares and Critical Exponents
- MARIA: Multiple-alignment $r$-index with aggregation
- Cache-Oblivious Representation of B-Tree Structures
- Concurrent Size
- Multiway Powersort
- $\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance
- Constant-delay enumeration for SLP-compressed documents
- A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
2022/8
- Merging Sorted Lists of Similar Strings
- Walking on Words
- Algorithm to derive shortest edit script using Levenshtein distance algorithm
- Approximate Circular Pattern Matching
- New Parallel Order Maintenance Data Structure
- Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev
- Co-lexicographically ordering automata and regular languages. Part I
- Almost optimal searching of maximal subrepetitions in a word
- Fast detection of specific fragments against a set of sequences
- Watson-Crick conjugates of words and languages
- Combinatorial Algorithms for Subsequence Matching: A Survey
- Pattern matching under DTW distance
- Computing all-vs-all MEMs in run-length encoded collections of HiFi reads
- Sorting Genomes by Prefix Double-Cut-and-Joins
- A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion
- Hierarchical Relative Lempel-Ziv Compression
- A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence
- Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform
- Unbalancing Binary Trees
- Simpler and Better Cardinality Estimators for HyperLogLog and PCSA
2022/7
- Enumerating and Locating the Subwords of the Two-dimensional Infinite Fibonacci Word
- Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
- Computing NP-hard Repetitiveness Measures via MAX-SAT
- Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
- Suffix sorting via matching statistics
- Pattern matching algorithms in Blockchain for network fees reduction
- Engineering faster double-array Aho-Corasick automata
- Simple O(1) Query Algorithm for Level Ancestors
- Tight Bounds for Monotone Minimal Perfect Hashing
- Pseudoperiodic Words and a Question of Shevelev
- Abelian Combinatorics on Words: a Survey
- Subsequences in Bounded Ranges: Matching and Analysis Problems
- On the Practical Power of Automata in Pattern Matching
- Matching Patterns with Variables Under Edit Distance
- Implementing the Comparison-Based External Sort
- An Improved Algorithm for Finding the Shortest Synchronizing Words
2022/6
- Hinted Dictionaries: Efficient Functional Ordered Sets and Maps
- Fast Exact String to D-Texts Alignments
- Properties of a Ternary Infinite Word
- L-systems for Measuring Repetitiveness*
- On the Lie complexity of Sturmian words
- Near-Optimal Search Time in $δ$-Optimal Space
- Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
- String Attractors and Infinite Words
- Efficient Algorithms for Sorting in Trees
- Asymptotic bounds for the number of closed and privileged words
- Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
- Learning Augmented Binary Search Trees
- PalFM-index: FM-index for Palindrome Pattern Matching
- Balancing Run-Length Straight-Line Programs*
- On the Optimisation of the GSACA Suffix Array Construction Algorithm
- Longest Common Subsequence: Tabular vs. Closed-Form Equation Computation of Subsequence Probability
- The Complexity of the Co-Occurrence Problem
- Lower Bounds for Sorting 16, 17, and 18 Elements
- KATKA: A KRAKEN-like tool with $k$ given at query time
- Which arithmetic operations can be performed in constant time in the RAM model with addition?
- Prefix-free parsing for building large tunnelled Wheeler graphs
- On extended boundary sequences of morphic and Sturmian words
- Computing the Parameterized Burrows–Wheeler Transform Online
- Onesweep: A Faster Least Significant Digit Radix Sort for GPUs
2022/5
- Computing Maximal Unique Matches with the r-index
- Dynamic data structures for parameterized string problems
- Cut-Down de Bruijn Sequences
- A New Class of String Transformations for Compressed Text Indexing
- Substring Complexities on Run-length Compressed Strings
- A note on the maximum number of $k$-powers in a finite word
- On Lyndon-Word Representable Graphs
2022/4
- Reduction ratio of the IS-algorithm: worst and random cases
- Faster Min-Plus Product for Monotone Instances
- Faster Pattern Matching under Edit Distance
- Speeding Hirschberg Algorithm for Sequence Alignment
- Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
- String Rearrangement Inequalities and a Total Order Between Primitive Words
- Theoretical analysis of edit distance algorithms: an applied perspective
- On the number of squares in a finite word
- Fast Circular Pattern Matching
- Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
- An $n H_k$-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers
- Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
- Efficient Construction of the BWT for Repetitive Text Using String Compression
- Two-dimensional Fibonacci Words: Tandem Repeats and Factor Complexity
- Improved Sublinear-Time Edit Distance for Preprocessed Strings
- Prefix Filter: Practically and Theoretically Better Than Bloom
2022/3
- Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems
- Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
- Binary codes that do not preserve primitivity
- Note on a Fibonacci Parity Sequence
- Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches
- Online List Labeling: Breaking the $\log^2n$ Barrier
- Quantum jumbled pattern matching
2022/2
- RePair Grammars are the Smallest Grammars for Fibonacci Words
- Longest (Sub-)Periodic Subsequence
- Memory Efficient Tries for Sequential Pattern Mining
- MONI can find k-MEMs
- Cartesian Tree Subsequence Matching
- Logarithmic equal-letter runs for BWT of purely morphic words
- An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
- A theoretical and experimental analysis of BWT variants for string collections
- Minimal Absent Words on Run-Length Encoded Strings
- LCP-dropout: Compression-based Multiple Subword Segmentation for Neural Machine Translation
- Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
- OSM-tree: A Sortedness-Aware Index
2022/1
- X3: Lossless Data Compressor
- Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
- What Does Dynamic Optimality Mean in External Memory?
- Dynamic Suffix Array with Polylogarithmic Queries and Updates
- Predecessor on the Ultra-Wide Word RAM
- Safety and Completeness in Flow Decompositions for RNA Assembly
- Computing Longest (Common) Lyndon Subsequences
- Multiple Genome Analytics Framework: The Case of All SARS-CoV-2 Complete Variants
- Linear Time Construction of Indexable Elastic Founder Graphs
- The Efficiency of the ANS Entropy Encoding
2021
2021/12
- String Sampling with Bidirectional String Anchors
- Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
- How Compression and Approximation Affect Efficiency in String Distance Measures
- Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
- Beyond the Longest Letter-duplicated Subsequence Problem
- Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
- Estimating the Longest Increasing Subsequence in Nearly Optimal Time
- RLBWT Tricks
- Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time
- Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model
- Optimal Gap Sequences in Shellsort for $n\leq16$ Elements
- Empirically Improved Tokuda Gap Sequence in Shellsort
- Parallel Batch-Dynamic $k$d-Trees
- SIMD-Optimized Search Over Sorted Data
- Approximating Length-Restricted Means under Dynamic Time Warping
- A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
2021/11
- Pattern Matching on Grammar-Compressed Strings in Linear Time
- Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
- Succinct Data Structure for Path Graphs
- Graphs can be succinctly indexed for pattern matching in $ O(│E│^2 + │V│^{5 / 2}) $ time
- An Improved Algorithm for The $k$-Dyck Edit Distance Problem
- Nearly Tight Lower Bounds for Succinct Range Minimum Query
- HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
- On the Optimal Time/Space Tradeoff for Hash Tables
- Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
- Approximation Algorithms for LCS and LIS with Truly Improved Running Times
- Prefixes of the Fibonacci word that end with a cube
- Tiny Pointers
- Linear-time Minimization of Wheeler DFAs
- Stochastic and Worst-Case Generalized Sorting Revisited
- Approximate Membership Query Filters with a False Positive Free Set
2021/10
- Near-Optimal Quantum Algorithms for String Problems
- Computing Matching Statistics on Repetitive Texts
- Counting and Verifying Abelian Border Arrays of Binary Words
- An $O(k \log{n})$ algorithm for prefix based ranked autocomplete
- Approximating LCS and Alignment Distance over Multiple Sequences
- Linear Approximate Pattern Matching Algorithm
- On Solving the Minimum Common String Partition Problem by Decision Diagrams
- Is this the simplest (and most surprising) sorting algorithm ever?
- FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
- Parallel Batched Interpolation Search Tree
- Reconstruction of Sets of Strings from Prefix/Suffix Compositions
- Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
2021/9
- Abelian Repetition Threshold Revisited
- Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees
- Simple Worst-Case Optimal Adaptive Prefix-Free Coding
- Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report
- Absent Subsequences in Words
- Ruler Wrapping
- Fast Succinct Retrieval and Approximate Membership using Ribbon
2021/8
- Arbitrary-length analogs to de Bruijn sequences
- Space-Efficient Huffman Codes Revisited
- Practical evaluation of Lyndon factors via alphabet reordering
- A Tight Analysis of Slim Heaps and Smooth Heaps
- Faster Exponential Algorithm for Permutation Pattern Matching
- Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs
- Does Preprocessing help in Fast Sequence Comparisons?
- A Conditional Lower Bound for Episode Matching
- Hierarchical Bitmap Indexing for Range and Membership Queries on Multidimensional Arrays
- On Specialization of a Program Model of Naive Pattern Matching in Strings (Extended Abstract)
2021/7
- Compression by Contracting Straight-Line Programs
- String Comparison on a Quantum Computer Using Hamming Distance
- Optimal Space and Time for Streaming Pattern Matching
- Analysis of Smooth Heaps and Slim Heaps
- Defeating duplicates: A re-design of the LearnedSort algorithm
- Burrows Wheeler Transform on a Large Scale: Algorithms Implemented in Apache Spark
- On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
- Space Efficient Two-Dimensional Orthogonal Colored Range Counting
- A New Lossless Data Compression Algorithm Exploiting Positional Redundancy
- Critical factorisation in square-free words
- Learned Sorted Table Search and Static Indexes in Small Space: Methodological and Practical Insights via an Experimental Study
- Hardness of Detecting Abelian and Additive Square Factors in Strings
- Sensitivity of string compressors and repetitiveness measures
- Fast direct access to variable length codes
2021/6
- Pattern-defeating Quicksort
- Closed Ziv-Lempel factorization of the $m$-bonacci words
- Counting Lyndon Subsequences
- On (co-lex) Ordering Automata
- Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash
- Position Heaps for Cartesian-tree Matching on Strings and Tries
- Internal Shortest Absent Word Queries in Constant Time and Linear Space
- Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
- On the approximation ratio of LZ-End to LZ77
- Matching Patterns with Variables under Hamming Distance
- A Bloom Filter Survey: Variants for Different Domain Applications
- Breaking the $O(n)$-Barrier in the Construction of Compressed Suffix Arrays
- Checking whether a word is Hamming-isometric in linear time
- Computing the original eBWT faster, simpler, and with less memory
- Small space and streaming pattern matching with k edits
- ExtendedHyperLogLog: Analysis of a new Cardinality Estimator
- An efficient way to manage ranges of data with Wise Red-Black Trees
- The k-mappability problem revisited
- Boosting the Search Performance of B+-tree for Non-volatile Memory with Sentinels
- APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
2021/5
- N-ary Huffman Encoding Using High-Degree Trees – A Performance Comparison
- Weighted Burrows-Wheeler Compression
- Combinatorics of minimal absent words for a sliding window
- The Dynamic k-Mismatch Problem
- Tree Edit Distance with Variables. Measuring the Similarity between Mathematical Formulas
- Compact Euler Tours of Trees with Small Maximum Degree
- Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
- Improved Approximation for Longest Common Subsequence over Small Alphabets
- Faster Algorithms for Longest Common Substring
- Faster Algorithms for Bounded Tree Edit Distance
- Lower Bounds for the Number of Repetitions in 2D Strings
- A new distance based on minimal absent words and applications to biological sequences
- On Stricter Reachable Repetitiveness Measures*
- Grammar Index By Induced Suffix Sorting
- Minimal unique palindromic substrings after single-character substitution
- Support Optimality and Adaptive Cuckoo Filters
- Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
2021/4
- Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures
- HINT: A Hierarchical Index for Intervals in Main Memory
- PTHash: Revisiting FCH Minimal Perfect Hashing
- Engineering Predecessor Data Structures for Dynamic Integer Sets
- A Separation of $γ$ and $b$ via Thue–Morse Words
- Load-Balancing Succinct B Trees
- Sorted Range Reporting
- Scalable Hash Table for NUMA Systems
- Memory-Optimal Non-Blocking Queues
2021/3
- Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
- On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons
- A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons
- Dynamic Range Mode Enumeration
- Compressed Communication Complexity of Hamming Distance
- An Almost Optimal Edit Distance Oracle
- A Fast and Small Subsampled R-index
2021/2
- Efficient construction of the extended BWT from grammar-compressed DNA sequencing reads
- Gapped Indexing for Consecutive Occurrences
- Weighted Ancestors in Suffix Trees Revisited
- A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
- Algorithms and Complexity on Indexing Founder Graphs
- Conditional Lower Bounds for Variants of Dynamic LIS
- Range Minimum Queries in Minimal Space
- Linear Time Runs over General Ordered Alphabets
- Which Regular Languages can be Efficiently Indexed?
- Sorting Short Integers
- All instantiations of the greedy algorithm for the shortest superstring problem are equivalent
- Optimal Sorting Circuits for Short Keys
2021/1
- Improving Run Length Encoding by Preprocessing
- Strictly In-Place Algorithms for Permuting and Inverting Permutations
- Cantor Mapping Technique
- SetSketch: Filling the Gap between MinHash and HyperLogLog
- Chunk List: Concurrent Data Structures
- Text Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations
- Binary Dynamic Time Warping in Linear Time
- $r$-indexing Wheeler graphs
- Deriving monadic quicksort (Declarative Pearl)
- Entropy of Mersenne-Twisters
- Number Parsing at a Gigabyte per Second
- Spanner Evaluation over SLP-Compressed Documents
- Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
- Solving one variable word equations in the free group in cubic time
- Algorithms and Hardness for Multidimensional Range Updates and Queries
2020
2020/12
- Sorting Lists with Equal Keys Using Mergesort in Linear Time
- Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring
- The Parameterized Suffix Tray
- Quantum Algorithm for Lexicographically Minimal String Rotation
- A New Approach to Regular & Indeterminate Strings
- Counting ternary square-free words quickly
- Galloping in natural merge sorts
- Huskysort
- Integer Division by Constants: Optimal Bounds
- Arithmetic Binary Search Trees: Static Optimality in the Matching Model
- String Attractors for Automatic Sequences
- SARS-CoV-2 Coronavirus Data Compression Benchmark
- Learning Halfspaces With Membership Queries
- Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
2020/11
- Erdös-Szekeres Partitioning Problem
- Selectable Heaps and Optimal Lazy Search Trees
- Improved Dynamic Algorithms for Longest Increasing Subsequence
- Fully Dynamic Approximation of LIS in Polylogarithmic Time
- Subpath Queries on Compressed Graphs: a Survey
- The Longest Run Subsequence Problem: Further Complexity Results
- A grammar compressor for collections of reads with applications to the construction of the BWT
- Substring Query Complexity of String Reconstruction
- PHONI: Streamed Matching Statistics with Multi-Genome References
- Scout Algorithm For Fast Substring Matching
- Left Lyndon tree construction
- Grammar Compression By Induced Suffix Sorting
- Searching and Sorting with O(n^2) processors in O(1) time
- Competitive Data-Structure Dynamization
2020/10
- Lazy Search Trees
- Solving Shisen-Sho boards
- Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
- Contextual Pattern Matching
- New Sublinear Algorithms and Lower Bounds for LIS Estimation
- Decode efficient prefix codes
- A Tale of Two Trees: New Analysis for AVL Tree and Binary Heap
- Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
- Splay trees on trees
- Generalized Sorting with Predictions
- Dynamic Boundary Time Warping for Sub-sequence Matching with Few Examples
- An Improved Sketching Algorithm for Edit Distance
- Sorting Short Keys in Circuits of Size o(n log n)
- Impossibility Results for Grammar-Compressed Linear Algebra
2020/9
- TADOC: Text Analytics Directly on Compression
- Longest Common Subsequence in Sublinear Space
- Pushdown and Lempel-Ziv Depth
- A Normal Sequence Compressed by PPM$^*$ but not by Lempel-Ziv 78
- A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
- Space efficient merging of de Bruijn graphs and Wheeler graphs
- On prefix palindromic length of automatic words
- Access-Adaptive Priority Search Tree
- Zuckerli: A New Compressed Representation for Graphs
- A Case for Partitioned Bloom Filters
- Dynamic Similarity Search on Integer Sketches
- Space/time-efficient RDF stores based on circular suffix sorting
- On One-way Functions and Kolmogorov Complexity
2020/8
- Tight Bound for the Number of Distinct Palindromes in a Tree
- Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
- Fast and Simple Modular Subset Sum
- Cadences in Grammar-Compressed Strings
- Soft Sequence Heaps
- Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
- A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings
- Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
- Blocksequences of k-local Words
2020/7
- The Edit Distance to $k$-Subsequence Universality
- Substring Complexity in Sublinear Space
- The Simplest Binary Word with Only Three Squares
- On Indexing and Compressing Finite Automata
- Update Query Time Trade-off for dynamic Suffix Arrays
- Local Editing in LZ-End Compressed Data
- String Indexing for Top-$k$ Close Consecutive Occurrences
- Near-Linear Time Edit Distance for Indel Channels
- A New Upper Bound for Separating Words
- Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
- Optimal construction of a layer-ordered heap
- Beyond the Worst-Case Analysis of Algorithms (Introduction)
- A Big Data Approach for Sequences Indexing on the Cloud via Burrows Wheeler Transform
- String Sanitization Under Edit Distance: Improved and Generalized
- New Data Structures for Orthogonal Range Reporting and Range Minima Queries
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- A Simple Sublinear Algorithm for Gap Edit Distance
- Internal Quasiperiod Queries
- A linear-time parameterized algorithm for computing the width of a DAG
2020/6
- A Fast Algorithm for Online k-servers Problem on Trees
- Efficient tree-structured categorical retrieval
- Dynamic Longest Common Substring in Polylogarithmic Time
- Computing Palindromic Trees for a Sliding Window and Its Applications
- LCP-Aware Parallel String Sorting
- Random Access in Persistent Strings
- Lyndon Words, the Three Squares Lemma, and Primitive Squares
- Small Longest Tandem Scattered Subsequences
- PFP Data Structures
- Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
- Extremal overlap-free and extremal $β$-free binary words
- Sumsets of Wythoff Sequences, Fibonacci Representation, and Beyond
- Optimal-Time Queries on BWT-runs Compressed Indexes
- Tailoring r-index for metagenomics
- Efficient Semi-External Depth-First Search
- The Number of Repetitions in 2D-Strings
- Pattern Masking for Dictionary Matching
- Analysis of Compression Techniques for DNA Sequence Data
- Improved Circular $k$-Mismatch Sketches
2020/5
- Edit Distance in Near-Linear Time: it’s a Constant Factor
- Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
- Efficient and Effective Query Auto-Completion
- k-Approximate Quasiperiodicity under Hamming and Edit Distance
- Counting Distinct Patterns in Internal Dictionary Matching
- Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings
- Palindromic Length of Words with Many Periodic Palindromes
- Incremental Multiple Longest Common Sub-Sequences
- On Weighted Prefix Normal Words
- Quantum string comparison method
- A reduction of the dynamic time warping distance to the longest increasing subsequence length
- Linear Time Construction of Indexable Founder Block Graphs
- On repetitiveness measures of Thue-Morse words
- Towards Efficient Interactive Computation of Dynamic Time Warping Distance
- Classical and Quantum Algorithms for Constructing Text from Dictionary Problem
- Longest Square Subsequence Problem Revisited
- On the improvement of the in-place merge algorithm parallelization
- An inequality for the number of periods in a word
- Succinct Trit-array Trie for Scalable Trajectory Similarity Search
- Still Simpler Static Level Ancestors
- Primitive Sets of Words
- New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
- The K-Centre Problem for Necklaces
- A Dynamic Space-Efficient Filter with Constant Time Operations
- Efficiently Testing Simon’s Congruence
2020/4
- SOPanG 2: online searching over a pan-genome without false positives
- Zipping Segment Trees
- Indexing Highly Repetitive String Collections
- Enumeration of LCP values, LCP intervals and Maximal repeats in BWT-runs Bounded Space
- Grammar-Compressed Indexes with Logarithmic Search Time
- On Locating Paths in Compressed Cardinal Trees
- No Repetition: Fast Streaming with Highly Concentrated Hashing
- In-Place Bijective Burrows-Wheeler Transforms
- Faster Approximate Pattern Matching: A Unified Approach
- Black-White Array: A New Data Structure for Dynamic Data Sets
- Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring
- Lower Bound for Succinct Range Minimum Query
- Grammar-compressed Self-index with Lyndon Words
- Two halves of a meaningful text are statistically different
- Pattern Discovery in Colored Strings
- A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm
- Storing Set Families More Compactly with Top ZDDs
- Approximating longest common substring with $k$ mismatches: Theory and practice
- The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
- Efficient Constrained Pattern Mining Using Dynamic Item Ordering for Explainable Classification
- The n-dimensional k-vector and its application to orthogonal range searching
2020/3
- Multiset Synchronization with Counting Cuckoo Filters
- Adaptive Fibonacci and Pairing Heaps
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- Approximating Optimal Bidirectional Macro Schemes
- Time-Space Tradeoffs for Finding a Long Common Substring
- Concurrent Disjoint Set Union
- An Efficient Implementation of Manacher’s Algorithm
- Grammar compression with probabilistic context-free grammar
- Approximating LCS in Linear Time: Beating the $\sqrt{n}$ Barrier
- Four-Dimensional Dominance Range Reporting in Linear Space
- Shorter Labels for Routing in Trees
- Scattered Factor-Universality of Words
- A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
- Further Results on Colored Range Searching
- Succinct Dynamic Ordered Sets with Random Access
- Hidden Words Statistics for Large Patterns
- Notes on Randomized Algorithms
2020/2
- Approximating Text-to-Pattern Distance via Dimensionality Reduction
- On Extensions of Maximal Repeats in Compressed Strings
- Computing Covers under Substring Consistent Equivalence Relations
- DAWGs for parameterized matching: online construction and related indexing structures
- Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
- Engineering Faster Sorters for Small Sets of Items
- On Two Measures of Distance between Fully-Labelled Trees
- On Rearrangement of Items Stored in Stacks
- Uniform Linked Lists Contraction
- Palindromic k-Factorization in Pure Linear Time
- The Bloom Tree
- 2-Dimensional Palindromes with $k$ Mismatches
- Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
- Bitvectors with runs and the successor/predecessor problem
- Wheeler Languages
- Compression with wildcards: All spanning trees
- Chronofold: a data structure for versioned text
- Compressed Data Structures for Binary Relations in Practice
- Space Efficient Deterministic Approximation of String Measures
- Translating Between Wavelet Tree and Wavelet Matrix Construction
- Fast and linear-time string matching algorithms based on the distances of $q$-gram occurrences
- Learning Directly from Grammar Compressed Text
- Fast Indexes for Gapped Pattern Matching
- Semantrix: A Compressed Semantic Matrix
- Revisiting compact RDF stores based on k2-trees
- Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
- Faster Binary Mean Computation Under Dynamic Time Warping
2020/1
- Optimal Skeleton Huffman Trees Revisited
- Fast Generation of Big Random Binary Trees
- Simulation computation in grammar-compressed graphs
- Age-Partitioned Bloom Filters
- Data Structure Primitives on Persistent Memory: An Evaluation
- Computing the rearrangement distance of natural genomes
- Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
- A Hybrid Approach to Temporal Pattern Matching
- Approximating Text-to-Pattern Hamming Distances
- Lossless Compression of Deep Neural Networks
- Reconstructing Words from Right-Bounded-Block Words
- Lengths of extremal square-free ternary words
- On the binomial equivalence classes of finite words
- Communication-Efficient String Sorting
- $O(\log \log n)$ Worst-Case Local Decoding and Update Efficiency for Data Compression
- Chaining with overlaps revisited
- Generalised Pattern Matching Revisited
- Faster STR-EC-LCS Computation
- Optimally selecting the top $k$ values from $X+Y$ with layer-ordered heaps
- Optimal Entropy Compression and Purification in Quantum Bits
- Analysis and Evaluation of Non-Blocking Interpolation Search Trees
2019
2019/12
- String factorisations with maximum or minimum dimension
- Circ-Tree: A B+-Tree Variant with Circular Design for Persistent Memory
- Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
- New Bounds on Antipowers in Binary Words
- Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
- Gardens of Eden in the Game of Life
- On the Reproducibility of Experiments of Indexing Repetitive Document Collections
- Efficient processing of raster and vector data
- The Weak Circular Repetition Threshold Over Large Alphabets
- Flat combined Red Black Trees
- Learning Multi-dimensional Indexes
2019/11
- Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
- An Efficient Word Lookup System by using Improved Trie Algorithm
- Fast Multiple Pattern Cartesian Tree Matching
- Counting Small Permutation Patterns
- Nearly Optimal Static Las Vegas Succinct Dictionary
- Optimal Adaptive Detection of Monotone Patterns
- Edge minimization in de Bruijn graphs
- In Search of the Fastest Concurrent Union-Find Algorithm
- Enumerative Data Compression with Non-Uniquely Decodable Codes
- Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses
- Space Efficient Construction of Lyndon Arrays in Linear Time
- Dv2v: A Dynamic Variable-to-Variable Compressor
- GraCT: A Grammar-based Compressed Index for Trajectory Data
- Lock-Free Hopscotch Hashing
- Towards Better Compressed Representations
- On the Complexity of BWT-runs Minimization via Alphabet Reordering
- On dynamic succinct graph representations
- Listing Conflicting Triples in Optimal Time
- Implementing the Topological Model Succinctly
- Energy consumption in compact integer vectors: A study case
- Faster Dynamic Compressed d-ary Relations
- Grammar Compressed Sequences with Rank/Select Support
- Extending General Compact Querieable Representations to GIS Applications
- Improved Compressed String Dictionaries
- Faster Integer Multiplication Using Preprocessing
- Constructing the Bijective BWT
- Words With Few Palindromes, Revisited
- Words Avoiding Reversed Factors, Revisited
- Fast Fibonacci heaps with worst case extensions
- Faster Privacy-Preserving Computation of Edit Distance with Moves
- SOSD: A Benchmark for Learned Indexes
2019/10
- The PGM-index: a multicriteria, compressed and learned approach to data indexing
- E2FM: an encrypted and compressed full-text index for collections of genomic sequences
- LISA: Towards Learned DNA Sequence Search
- Stack Sorting with Increasing and Decreasing Stacks
- RAMBO: Repeated And Merged Bloom Filter for Multiple Set Membership Testing (MSMT) in Sub-linear time
- Practical Random Access to Large SLP-Compressed Texts
- It is high time we let go of the Mersenne Twister
- Apply Sorting Algorithms to FAST Problem
- RecSplit: Minimal Perfect Hashing via Recursive Splitting
- Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
- Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms
- Resolution of the Burrows-Wheeler Transform Conjecture
- EvoZip: Efficient Compression of Large Collections of Evolutionary Trees
- Engineering Top-Down Weight-Balanced Trees
- Practical Repetition-Aware Grammar Compression
- Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps
- ALLSAT compressed with wildcards: Frequent Set Mining
- Towards a Definitive Measure of Repetitiveness
- ER-index: a referential index for encrypted genomic databases
- Sublinear Algorithms for Gap Edit Distance
- Approximating the Geometric Edit Distance
- Superset Technique for Approximate Recovery in One-Bit Compressed Sensing
- Finding monotone patterns in sublinear time
2019/9
- Run-Length Encoding in a Finite Universe
- Local Decode and Update for Big Data Compression
- Generalized Dictionary Matching under Substring Consistent Equivalence Relations
- Leyenda: An Adaptive, Hybrid Sorting Algorithm for Large Scale Data with Limited Memory
- Weighted Shortest Common Supersequence Problem Revisited
- Internal Dictionary Matching
- String Indexing with Compressed Patterns
- RECIPE : Converting Concurrent DRAM Indexes to Persistent-Memory Indexes
- Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
- A New Deterministic Algorithm for Dynamic Set Cover
- A Simple Reduction for Full-Permuted Pattern Matching Problems on Multi-Track Strings
- An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping
2019/8
- Engineering Faster Sorters for Small Sets of Items
- Revisiting Consistent Hashing with Bounded Loads
- When a Dollar Makes a BWT
- Partial Sums on the Ultra-Wide Word RAM
- Bloom filter variants for multiple sets: a comparative assessment
- An Incompressibility Theorem for Automatic Complexity
- Compacted binary trees admit a stretched exponential
- Techniques for Inverted Index Compression
- Parallel Finger Search Structures
- The repetition threshold for binary rich words
- Space-Efficient Construction of Compressed Suffix Trees
- Beyond the Inverted Index
- Fast Cartesian Tree Matching
- Re-Pair In Small Space
- On Occupancy Moments and Bloom Filter Efficiency
- New Results on Nyldon Words Derived Using an Algorithm from Hall Set Theory
- Efficient Online String Matching Based on Characters Distance Text Sampling
- The smallest grammar problem revisited
- Competitive Online Search Trees on Trees
- Dynamic Optimality Refuted – For Tournament Heaps
- On the cyclic regularities of strings
- Matching reads to many genomes with the $r$-index
- An Index for Sequencing Reads Based on The Colored de Bruijn Graph
- Optimal Joins using Compact Data Structures
2019/7
- Quantum Computing: Lecture Notes
- Enumerating Range Modes
- How to Store a Random Walk
- Exhaustive Exact String Matching: The Analysis of the Full Human Genome
- Minimal Absent Words in Rooted and Unrooted Trees
- On Approximate Range Mode and Range Selection
- Data Structures Meet Cryptography: 3SUM with Preprocessing
- Finding First and Most-Beautiful Queens by Integer Programming
- Succinct Representation for (Non)Deterministic Finite Automata
- Optimal In-place Algorithms for Basic Graph Problems
- Constant Delay Traversal of Grammar-Compressed Graphs with Bounded Rank
- The Strong 3SUM-INDEXING Conjecture is False
- Abelian-square factors and binary words
- New Paths from Splay to Dynamic Optimality
- Splaying Preorders and Postorders
- Stack sorting with restricted stacks
- Efficient computation of the Jacobi symbol
- Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
- Cache-Friendly Search Trees; or, In Which Everything Beats std::set
- Circular Pattern Matching with $k$ Mismatches
- The Alternating BWT: an algorithmic perspective
- Bidirectional Text Compression in External Memory
- Sparse Regular Expression Matching
- String Attractors and Combinatorics on Words
- $L_p$ Pattern Matching in a Stream
- DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks
- Improved local search for graph edit distance
- On Slicing Sorted Integer Sequences
2019/6
- Recurrence along directions in multidimensional words
- Vector Programming Using Generative Recursion
- On Longest Common Property Preserved Substring Queries
- Loop Programming Practices that Simplify Quicksort Implementations
- Dynamic Path-Decomposed Tries
- Matching Patterns with Variables
- Space Efficient Algorithms for Breadth-Depth Search
- Indexing Graph Search Trees and Applications
- Dynamic Palindrome Detection
- Pseudo-solutions of word equations
- Combinatorial Algorithms for String Sanitization
- Survey of Information Encoding Techniques for DNA
- Rpair: Rescaling RePair with Rsync
- Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
- Characteristic Parameters and Special Trapezoidal Words
- Every nonnegative real number is an abelian critical exponent
- Borders, Palindrome Prefixes, and Square Prefixes
- Sorted Top-k in Rounds
- The Tandem Duplication Distance is NP-hard
2019/5
- Separating many words by counting occurrences of factors
- Prefix Block-Interchanges on Binary and Ternary Strings
- Speeding up the Karatsuba algorithm
- Memory lower bounds for deterministic self-stabilization
- Cartesian Tree Matching and Indexing
- A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets
- On the Average Case of MergeInsertion
- Inducing the Lyndon Array
- Compact Data Structures for Shortest Unique Substring Queries
- The Bloom Clock
- Parallel decompression of gzip-compressed files and random access to DNA sequences
- Fast hashing with Strong Concentration Bounds
- Separate Chaining Meets Compact Hashing
- Using Non-Linear Difference Equations to Study Quicksort Algorithms
- RLE edit distance in near optimal time
- Palindromic Ziv-Lempel and Crochemore Factorizations of $m$-Bonacci Infinite Words
- Order-Preserving Pattern Matching Indeterminate Strings
- Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
- Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
- Abelian periods of factors of Sturmian words
- Constrained Orthogonal Segment Stabbing
- Don’t Persist All : Efficient Persistent Data Structures
- An invertible transform for efficient string matching in labeled digraphs
2019/4
- Compact Fenwick trees for dynamic ranking and selection
- The power word problem
- About Fibonacci trees. I
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Constant-factor approximation of near-linear edit distance in near-linear time
- What Storage Access Privacy is Achievable with Small Overhead?
- Dynamic Packed Compact Tries Revisited
- Compressed Indexes for Fast Search of Semantic Data
- Repetitions in infinite palindrome-rich words
- New results on pseudosquare avoidance
- k-Spectra of weakly-c-Balanced Words
- Proving tree algorithms for succinct data structures
- String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
- Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries
- Heuristic algorithms for the Longest Filled Common Subsequence Problem
- Reducing approximate Longest Common Subsequence to approximate Edit Distance
- Convex Graph Invariant Relaxations For Graph Edit Distance
2019/3
- Matching strings in encoded sequences
- Data structures to represent sets of k-long DNA sequences
- Multiplication method for factoring natural numbers
- Shed More Light on Bloom Filter’s Variants
- Determining satisfiability of 3-SAT in polynomial time
- Algorithms to compute the Burrows-Wheeler Similarity Distribution
- A New Lower Bound for Semigroup Orthogonal Range Searching
- QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations
- Belga B-trees
- How far away must forced letters be so that squares are still avoidable?
- The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time
- Maximal State Complexity and Generalized de Bruijn Words
- scaleBF: A High Scalable Membership Filter using 3D Bloom Filter
- Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
- The Parameterized Position Heap of a Trie
- A Simple Solution to the Level-Ancestor Problem
- Lempel-Ziv-like Parsing in Small Space
- Lightweight merging of compressed indices based on BWT variants
- Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
- Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
- Encoding 3SUM
- The One-Way Communication Complexity of Dynamic Time Warping Distance
2019/2
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- Faster and simpler algorithms for finding large patterns in permutations
- Succinct Data Structures for Families of Interval Graphs
- Padovan heaps
- Fast Concurrent Data Sketches
- Constructing Antidictionaries in Output-Sensitive Space
- Conversion from RLBWT to LZ77
- Space-Efficient Data Structures for Lattices
- A New Class of Searchable and Provably Highly Compressible String Transformations
- On long words avoiding Zimin patterns
- Finite test sets for morphisms which are square-free on some of Thue’s square-free ternary words
- A sub-quadratic algorithm for the longest common increasing subsequence problem
- Fast, Small, and Simple Document Listing on Repetitive Text Collections
- In oder Aus
- On Greedy Algorithms for Binary de Bruijn Sequences
- Regular Languages meet Prefix Sorting
- Top Tree Compression of Tries
- A fast algorithm for constructing balanced binary search trees
- Space-efficient merging of succinct de Bruijn graphs
- Faster Repetition-Aware Compressed Suffix Trees based on Block Trees
- Balancing Straight-Line Programs
- Set Cover in Sub-linear Time
- On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching
- Fast Sequence Segmentation using Log-Linear Models
- Compressed Range Minimum Queries
- An efficient sorting algorithm - Ultimate Heapsort(UHS)
- An Extension of Linear-size Suffix Tries for Parameterized Strings
2019/1
- Simulating the DNA String Graph in Succinct Space
- Fully-functional bidirectional Burrows-Wheeler indexes
- Online Algorithms for Constructing Linear-size Suffix Trie
- A study for Image compression using Re-Pair algorithm
- Faster queries for longest substring palindrome after block edit
- Computing runs on a trie
- Quasi-Linear-Time Algorithm for Longest Common Circular Factor
- Longest Common Subsequence on Weighted Sequences
- On Huang and Wong’s Algorithm for Generalized Binary Split Trees
- Quotient Hash Tables - Efficiently Detecting Duplicates in Streaming Data
- Unconstrained Church-Turing thesis cannot possibly be true
- Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
- On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree
- Dynamic Partition Bloom Filters: A Bounded False Positive Solution For Dynamic Set Membership (Extended Abstract)
- Palindromic Subsequences in Finite Words
- A randomized strategy in the mirror game
- Learning Space Partitions for Nearest Neighbor Search
- Mergeable Dictionaries With Shifts
- Communication cost of consensus for nodes with limited memory
- Multiple Set Matching and Pre-Filtering with Bloom Multifilters
- An in-place, subquadratic algorithm for permutation inversion
- A Compact Representation of Raster Time Series
- Entropy Bounds for Grammar-Based Tree Compressors
- Depth First Search in the Semi-streaming Model
2018
2018/12
- Computing the $k$-binomial complexity of the Thue–Morse word
- Lower bounds for text indexing with mismatches and differences
- A Grammar-based Compressed Representation of 3D Trajectories
- Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs
- A Compact Representation for Trips over Networks built on self-indexes
- ALLSAT compressed with wildcards: Partitionings and face-numbers of simplicial complexes
- LZRR: LZ77 Parsing with Right Reference
- Optimal Algorithm for Profiling Dynamic Arrays with Finite Values
- Simple Concurrent Labeling Algorithms for Connected Components
- Minuet: A method to solve Sudoku puzzles by hand
- A Fast Combination of AES Encryption and LZ4 Compression Algorithms
- Efficient Representation and Counting of Antipower Factors in Words
- A Simple Algorithm for Computing the Document Array
- Fast Breadth-First Search in Still Less Space
- Locally Consistent Parsing for Text Indexing in Small Space
- Improving Similarity Search with High-dimensional Locality-sensitive Hashing
2018/11
- On Infinite Prefix Normal Words
- DeepZip: Lossless Data Compression using Recurrent Neural Networks
- Tunneling on Wheeler Graphs
- The entropy of lies: playing twenty questions with a liar
- Static Data Structure Lower Bounds Imply Rigidity
- MR-RePair: Grammar Compression based on Maximal Repeats
- Efficiently Approximating Edit Distance Between Pseudorandom Strings
- Efficient Construction of a Complete Index for Pan-Genomics Read Alignment
- An optimized Parallel Failure-less Aho-Corasick algorithm for DNA sequence matching
- Optimal-Time Dictionary-Compressed Indexes
- Worst-Case Efficient Sorting with QuickMergesort
- RePair in Compressed Space and Time
- QuickXsort - A Fast Sorting Scheme in Theory and Practice
- Compressed Multiple Pattern Matching
- Multidimensional segment trees can do range queries and updates in logarithmic time
- Optimal Rank and Select Queries on Dictionary-Compressed Text
- Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
- Vectorized Character Counting for Faster Pattern Matching
2018/10
- MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
- Distinct Sampling on Streaming Data with Near-Duplicates
- Non-Empty Bins with Simple Tabulation Hashing
- Fast and Longest Rollercoasters
- Parallelism in Randomized Incremental Algorithms
- Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity
- Relative compression of trajectories
- Nearly Optimal Space Efficient Algorithm for Depth First Search
- Lower Bounds for Oblivious Data Structures
- Sub-O(log n) Out-of-Order Sliding-Window Aggregation
- Some comments on the structure of the best known networks sorting 16 elements
- Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
- Simple and Fast BlockQuicksort using Lomuto’s Partitioning Scheme
- Sesquickselect: One and a half pivots for cache-efficient selection
- Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
- Approximating Approximate Pattern Matching
- Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient
- Weighted dynamic finger in binary search trees
- Compound Binary Search Tree and Algorithms
- Longest Property-Preserved Common Factor
- Randen - fast backtracking-resistant random generator with AES+Feistel+Reverie
- Approximate Online Pattern Matching in Sub-linear Time
- On the discrepancy of random low degree set systems
- Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
2018/9
- Streaming dictionary matching with mismatches
- Multi-finger binary search trees
- Massively Parallel Dynamic Programming on Trees
- Approximate Query Processing over Static Sets and Sliding Windows
- Calculation of extended gcd by normalization
- Encoding two-dimensional range top-k queries revisited
- Relaxing Wheeler Graphs for Indexing Reads
- Small Uncolored and Colored Choice Dictionaries
- Adaptive Shivers Sort: An Alternative Sorting Algorithm
- Collapsing Superstring Conjecture
- Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra
- Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space
2018/8
- List Decoding with Double Samplers
- Finding a Small Number of Colourful Components
- Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms
- Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools
- Right-to-left online construction of parameterized position heaps
- Dynamic all scores matrices for LCS score
- Longest Increasing Subsequence under Persistent Comparison Errors
- Local Decodability of the Burrows-Wheeler Transform
- The effective entropy of next/previous larger/smaller value queries
- Cardinality Estimators do not Preserve Privacy
- On the tails of the limiting QuickSort density
2018/7
- Enumerating Cryptarithms Using Deterministic Finite Automata
- Improved Time and Space Bounds for Dynamic Range Mode
- Push-Down Trees: Optimal Self-Adjusting Complete Trees
- Know When to Fold ‘Em: Self-Assembly of Shapes by Folding in Oritatami
- A Simple and Space Efficient Segment Tree Implementation
- Using statistical encoding to achieve tree succinctness never seen before
- The colored longest common prefix array computed via sequential scans
- Two Algorithms to Find Primes in Patterns
- Faster Recovery of Approximate Periods over Edit Distance
- Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model
- Optimal Ball Recycling
- Efficient Computation of Sequence Mappability
2018/6
- Enhanced string factoring from alphabet orderings
- Zip Trees
- A Faster External Memory Priority Queue with DecreaseKeys
- Improved bounds for multipass pairing heaps and path-balanced binary search trees
- Fast entropy-bounded string dictionary look-up with mismatches
- Dynamic Trees with Almost-Optimal Access Cost
- BDDs Naturally Represent Boolean Functions, and ZDDs Naturally Represent Sets of Sets
- Practical Access to Dynamic Programming on Tree Decompositions
- Approximate Nearest Neighbors in Limited Space
- Efficient Genomic Interval Queries Using Augmented Range Trees
- Fast Locality Sensitive Hashing for Beam Search on GPU
- Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
- Tree Path Majority Data Structures
- Another Proof of Cuckoo hashing with New Variants
- Alignment-free sequence comparison using absent words
- Compressed Communication Complexity of Longest Common Prefixes
- CuCoTrack: Cuckoo Filter Based Connection Tracking
- Indexed Dynamic Programming to boost Edit Distance and LCSS Computation
- $O(n \log n)$-time text compression by LZ-style longest first substitution
- Block Palindromes: A New Generalization of Palindromes
2018/5
- On the Worst-Case Complexity of TimSort
- Orthogonal Point Location and Rectangle Stabbing Queries in 3-d
- copMEM: Finding maximal exact matches via sampling both genomes
- Optimal Hashing in External Memory
- Strong link between BWT and XBW via Aho-Corasick automaton and applications to Run-Length Encoding
- Algorithms for Anti-Powers in Strings
- Longest Unbordered Factor in Quasilinear Time
- Succinct data structure for dynamic trees with faster queries
- Space-Efficient DFS and Applications: Simpler, Leaner, Faster
- Haplotype-aware graph indexes
- Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
- An $O(N)$ Sorting Algorithm: Machine Learning Sort
- Beating Fredman-Komlós for perfect $k$-hashing
- Assembling Omnitigs using Hidden-Order de Bruijn Graphs
- Parallel Working-Set Search Structures
- Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
- On Computing Average Common Substring Over Run Length Encoded Sequences
- External memory BWT and LCP computation for sequence collections with applications
- Revisiting the tree edit distance and its backtracing: A tutorial
- On improving the approximation ratio of the r-shortest common superstring problem
- Detecting Mutations by eBWT
- Wormhole: A Fast Ordered Index for In-memory Data Management
- Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables
- Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
2018/4
- Longest Common Substring Made Fully Dynamic
- Succinct Oblivious RAM
- Entropy bounds for grammar compression
- Edit Distance between Unrooted Trees in Cubic Time
- QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
- On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
- Graph Pattern Matching Preserving Label-Repetition Constraints
- Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
- Fast Prefix Search in Little Space, with Applications
- Optimizing Bloom Filter: Challenges, Solutions, and Comparisons
- Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
- A Weighted Generalization of the Graham-Diaconis Inequality for Ranked List Similarity
- Design and Implementation of Dynamic Memory Management in a Reversible Object-Oriented Programming Language
- k-Maximum Subarrays for Small k: Divide-and-Conquer made simpler
- On Abelian Longest Common Factor with and without RLE
- Optimal Sorting with Persistent Comparison Errors
- On Undetected Redundancy in the Burrows-Wheeler Transform
- Optimal streaming and tracking distinct elements with high probability
- Red-Black Trees with Constant Update Time
- From Regular Expression Matching to Parsing
- Optimal Document Exchange and New Codes for Insertions and Deletions
- Restructuring expression dags for efficient parallelization
- Dualities in Tree Representations
- Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
2018/3
- Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
- Prefix-Free Parsing for Building Big BWTs
- On the Diameter of Tree Associahedra
- Optimal Substring-Equality Queries with Applications to Sparse Text Indexing
- String Attractors: Verification and Optimization
- Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
- Parallel Range, Segment and Rectangle Queries with Augmented Maps
- On the Approximation Ratio of Ordered Parsings
- Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
- Universal Compressed Text Indexing
- Linear-Time In-Place DFS and BFS on the Word RAM
- Average Cost of QuickXsort with Pivot Sampling
- Twelve Simple Algorithms to Compute Fibonacci Numbers
- Two-Dimensional Block Trees
- Compact Representations of Event Sequences
- Flexible and Efficient Algorithms for Abelian Matching in Strings
- Multivariate Fine-Grained Complexity of Longest Common Subsequence
- Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
2018/2
- Decompressing Lempel-Ziv Compressed Text
- Refining the $r$-index
- Improved Upper Bounds on all Maximal $α$-gapped Repeats and Palindromes
- Linear-Time Algorithm for Long LCF with $k$ Mismatches
- Upper and lower bounds for dynamic data structures on strings
- Periodicity in Data Streams with Wildcards
- Smooth heaps and a dual view of self-adjusting data structures
- Grammar-based Compression of Unranked Trees
- Synchronization Strings: List Decoding for Insertions and Deletions
2018/1
- String Periods in the Order-Preserving Model
- On Periodicity Lemma for Partial Words
- Longest Common Prefixes with $k$-Errors and Applications
- Sliding Suffix Tree using LCA
- Generalized Leapfrogging Samplesort: A Class of $O(n \log^2 n)$ Worst-Case Complexity and $O(n \log n)$ Average-Case Complexity Sorting Algorithms
- Faster Approximate(d) Text-to-Pattern L1 Distance
- Strategies for Stable Merge Sorting
2017
2017/12
- Optimal Construction of Compressed Indexes for Highly Repetitive Texts
- Text Indexing and Searching in Sublinear Time
- Longest common substring with approximately $k$ mismatches
- Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space
- Cartesian trees and Lyndon trees
- Bubble-Flip—A New Generation Algorithm for Prefix Normal Words
- Optimal top dag compression
- B-slack trees: Highly Space Efficient B-trees
- The Case for Learned Index Structures
- On the Decision Tree Complexity of String Matching
- Space-Efficient Algorithms for Longest Increasing Subsequence
2017/11
- Compressed Indexing with Signature Grammars
- A Separation Between Run-Length SLPs and LZ77
- A compressed dynamic self-index for highly repetitive text collections
- Fast Dynamic Arrays
- Run Compressed Rank/Select for Large Alphabets
- Faster range minimum queries
- The Hidden Binary Search Tree:A Balanced Rotation-Free Search Tree in the AVL RAM Model
- A Grammar Compression Algorithm based on Induced Suffix Sorting
- Bloom Filters, Adaptivity, and the Dictionary Problem
- Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index
2017/10
- At the Roots of Dictionary Compression: String Attractors
- Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
- Dismantling DivSufSort
- Lyndon Array Construction during Burrows-Wheeler Inversion
- Efficient Compression and Indexing of Trajectories
- Improved Bounds for Testing Forbidden Order Patterns
- Exact Mean Computation in Dynamic Time Warping Spaces
- HyperMinHash: MinHash in LogLog space
- Twin Sort Technique
- Probabilistic Analysis of the Dual-Pivot Quicksort “Count”
- Ordered Dags: HypercubeSort
- Orthogonal Vectors Indexing
2017/9
- String Attractors
- In-Place Initializable Arrays
- On-the-Fly Array Initialization in Less Space
- Fast Computation of Graph Edit Distance
- Whole Genome Phylogenetic Tree Reconstruction Using Colored de Bruijn Graphs
2017/8
- Distinct Squares in Circular Words
- The streaming $k$-mismatch problem
- Comparison of LZ77-type Parsings
- Exploiting Computation-Friendly Graph Compression Methods
- Streaming Periodicity with Mismatches
- Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform
2017/7
- Document Listing on Repetitive Collections with Guaranteed Performance
- Relations Between Greedy and Bit-Optimal LZ77 Encodings
- Lempel-Ziv: a “one-bit catastrophe” but not a tragedy
- A succinct data structure for self-indexing ternary relations
- Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
- Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
- Improved bounds for testing Dyck languages
- Fast Label Extraction in the CDAWG
- Persistent Cache-oblivious Streaming Indexes
- Greedy Shortest Common Superstring Approximation in Compact Space
- The Compressed Overlap Index
- Compressed Representation of Dynamic Binary Relations with Applications
- Biased Predecessor Search
- Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
2017/6
- Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
- Order preserving pattern matching on trees and DAGs
- Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
- Compaction of Church Numerals for Higher-Order Compression
- The complexity of the Multiple Pattern Matching Problem for random strings
- On-line Assembling Mitochondrial DNA from de novo transcriptome
- New Cardinality Estimation Methods for HyperLogLog Sketches
- Faster batched range minimum queries
2017/5
- On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
- Optimal-Time Text Indexing in BWT-runs Bounded Space
- Linear-size CDAWG: new repetition-aware indexing and grammar compression
- Near-optimal linear decision trees for k-SUM and related problems
- Succinct Partial Sums and Fenwick Trees
- How to answer a small batch of RMQs or LCA queries in practice
- Faster algorithms for 1-mappability of a sequence
- Optimal Computation of Overabundant Words
- Representing the suffix tree with the CDAWG
- Inverse Lyndon words and Inverse Lyndon factorizations of words
- Multiresolution Priority Queues
- New Variants of Pattern Matching with Constants and Variables
- Duel and sweep algorithm for order-preserving pattern matching
- Assembling sequences of DNA using an on-line algorithm based on DeBruijn graphs
- Improved Average Complexity for Comparison-Based Sorting
2017/4
- Practical and Effective Re-Pair Compression
- A Faster Implementation of Online Run-Length Burrows-Wheeler Transform
- Optimal trade-offs for pattern matching with $k$ mismatches
- m-Bonsai: a Practical Compact Dynamic Trie
- Indexing Weighted Sequences: Neat and Efficient
- Grammar-Based Graph Compression
- FMtree: A fast locating algorithm of FM-indexes for genomic data
- Maximal Unbordered Factors of Random Strings
- Hybridizing Non-dominated Sorting Algorithms: Divide-and-Conquer Meets Best Order Sort
- Streaming Pattern Matching with d Wildcards
- Succinct Approximate Rank Queries
- Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching
2017/3
- Faster STR-IC-LCS computation via RLE
- Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets
- Palindromic Decompositions with Gaps and Errors
- Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
- Near-Optimal Compression for the Planar Graph Metric
- Reoptimization of the Closest Substring Problem under Pattern Length Modification
- Approximation ratio of RePair
- Space-efficient K-MER algorithm for generalized suffix tree
- Faster truncated integer multiplication
- Even faster sorting of (not only) integers
2017/2
- Compression with the tudocomp Framework
- From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back
- Small-space encoding LCE data structure with constant-time queries
- Simple, Fast and Lightweight Parallel Wavelet Tree Construction
- Fast and Simple Jumbled Indexing for Binary RLE Strings
- Trie Compression for GPU Accelerated Multi-Pattern Matching
- A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem
- Position Heaps for Parameterized Strings
- A local search 2.917-approximation algorithm for duo-preservation string mapping
- New cardinality estimation algorithms for HyperLogLog sketches
2017/1
- Computing Abelian regularities on RLE strings
- A Framework of Dynamic Data Structures for String Processing
2016
2016/12
- A hardness result and new algorithm for the longest common palindromic subsequence problem
- Deterministic Indexing for Packed Strings
- Efficient Representation of Multidimensional Data over Hierarchical Domains
- GraCT: A Grammar based Compressed representation of Trajectories
- Monte Carlo Sort for unreliable human comparisons
- Oblivious Sorting and Queues
2016/11
- Space-Efficient Re-Pair Compression
- LZ-End Parsing in Compressed Space
- Burrows-Wheeler transform and LCP array construction in constant space
- Compressed Dynamic Range Majority and Minority Data Structures
- On the Size of Lempel-Ziv and Lyndon Factorizations
- Longest Common Extensions with Recompression
- Tight Lower Bounds for the Longest Common Extension Problem
- Twenty (simple) questions
- A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs
- Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
- Optimizing run-length algorithm using octonary repetition tree
2016/10
- Computing All Distinct Squares in Linear Time for Integer Alphabets
- Engineering a Distributed Full-Text Index
- Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
- Efficient Pattern Matching in Elastic-Degenerate Strings
- String Cadences
- An Encoding for Order-Preserving Matching
- Sort well with energy-constrained comparisons
- Optimal In-Place Suffix Sorting
- Scalable Construction of Text Indexes
- Comments on Dumitrescu’s “A Selectable Sloppy Heap”
2016/9
- Practical Data Compression for Modern Memory Hierarchies
- Tight bounds on the maximum number of shortest unique substrings
- Longest Common Subsequence in at Least $k$ Length Order-Isomorphic Substrings
- Efficient computation of longest single-arm-gapped palindromes in a string
- From H&M to Gap for Lightweight BWT Merging
- Linear-time string indexing and analysis in small space
- Sort Race
- Succinct data-structure for nearest colored node in a tree
- The Generalized Smallest Grammar Problem
2016/8
- Shortest unique palindromic substring queries in optimal time
- In-Place Sparse Suffix Sorting
- Sparse Suffix Tree Construction in Optimal Time and Space
- Hardness of Permutation Pattern Matching
- A family of fast exact pattern matching algorithms
- Quicksort Is Optimal For Many Equal Keys
- Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort
2016/7
- Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- Fast Longest Common Extensions in Small Space
- Online Grammar Compression for Frequent Pattern Discovery
- Streaming k-mismatch with error correcting and applications
- Fully Dynamic de Bruijn Graphs
- Edit Distance: Sketching, Streaming and Document Exchange
- A New Lightweight Algorithm to compute the BWT and the LCP array of a Set of Strings
- Suffix arrays with a twist
- Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
- Multi-view pattern matching
- Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
- An Optimal Algorithm for Range Search on Multidimensional Points
- Representing Pattern Matching Algorithms by Polynomial-Size Automata
2016/6
- A Self-Index on Block Trees
- Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices
- On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
- String Inference from the LCP Array
- A Compact Index for Order-Preserving Pattern Matching
- Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
- Range Majorities and Minorities in Arrays
- Improved Space efficient linear time algorithms for BFS, DFS and applications
- Randomized Ternary Search Tries
- Two-stage algorithms for covering array construction
- A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching
2016/5
- Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes
- Dynamic index and LZ factorization in compressed space
- Fully dynamic data structure for LCE queries in compressed space
- Document Retrieval on Repetitive String Collections
- RLZAP: Relative Lempel-Ziv with Adaptive Pointers
- Rank and select: Another lesson learned
- Algorithms to Compute the Lyndon Array
- Energy-Efficient Algorithms
- CSA++: Fast Pattern Search for Large Alphabets
- Games from Basic Data Structures
- Variance of the Internal Profile in Suffix Trees
- Lightweight LCP Construction for Very Large Collections of Strings
- Average Size of a Suffix Tree for Markov Sources
- Asymmetric Rényi Problem and PATRICIA Tries
2016/4
- Universal Indexes for Highly Repetitive Document Collections
- Practical combinations of repetition-aware data structures
- Detecting One-variable Patterns
- Optimal Computation of Avoided Words
- Designing optimal- and fast-on-average pattern matching algorithms
- Data Structure Lower Bounds for Document Indexing Problems
- Succinct Choice Dictionaries
- Efficient Index Maintenance Under Dynamic Genome Modification
- Computing Longest Increasing Subsequence Over Sequential Data Streams
- GateKeeper: A New Hardware Architecture for Accelerating Pre-Alignment in DNA Short Read Mapping
- New Error Tolerant Method to Search Long Repeats in Symbol Sequences
- An Estimation of the Size of Non-Compact Suffix Trees
2016/3
- Aggregated 2D Range Queries on Clustered Points
- Parameterized Pattern Matching – Succinctly
- The landscape of bounds for binary search trees
- Encoding Arguments
2016/2
- Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
- Efficient Index for Weighted Sequences
- Faster Longest Common Extension Queries in Strings over General Alphabets
- Approximate Hamming distance in a stream
- siEDM: an efficient string index and search algorithm for edit distance with moves
- Lempel-Ziv Decoding in External Memory
- Compressing Graphs and Indexes with Recursive Graph Bisection
- Access Time Tradeoffs in Archive Compression
- A loopless and branchless $O(1)$ algorithm to generate the next Dyck word
- Distortion-Resistant Hashing for rapid search of similar DNA subsequence
- TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes
- On the circuit complexity of the standard and the Karatsuba methods of multiplying integers
- On pattern matching with k mismatches and few don’t cares
2016/1
- Pachinko
- Deterministic sub-linear space LCE data structures with efficient construction
- Simple and Efficient Fully-Functional Succinct Trees
- Optimal Prefix Free Codes With Partial Sorting
- Minimal Suffix and Rotation of a Substring in Optimal Time
- Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array
- The complexity of bit retrieval
2015
2015/12
- Fast Average-Case Pattern Matching on Weighted Sequences
- A Quadratic Assignment Formulation of the Graph Edit Distance
- A Fast Heuristic for Exact String Matching
2015/11
- Burrows-Wheeler transform for terabases
- Longest Gapped Repeats and Palindromes
- Optimal Dynamic Strings
- Efficient Deterministic Single Round Document Exchange for Edit Distance
- Word Existence Algorithm
- On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
- A Study on Splay Trees
- Traversing Grammar-Compressed Trees with Constant Delay
2015/10
- Computing LZ77 in Run-Compressed Space
- Efficiently Finding All Maximal $α$-gapped Repeats
- Lempel-Ziv Computation In Compressed Space (LZ-CICS)
- Subsequence Automata with Default Transitions
- How Good is Multi-Pivot Quicksort?
- Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
- Layered Heaps Beating Standard and Fibonacci Heaps in Practice
- A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
- Fast Algorithms for Exact String Matching
- Permutations sortable by two stacks in series
- Multiple sequence alignment for short sequences
- The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations
2015/9
- Deterministic Sparse Suffix Sorting in the Restore Model
- Finding the Leftmost Critical Factorization on Unordered Alphabet
- Testing k-binomial equivalence
- Communication Complexity (for Algorithm Designers)
- Parallel Query in the Suffix Tree
- Lower bounds for approximation schemes for Closest String
- Probabilistic Threshold Indexing for Uncertain Strings
- Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations
- External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates
- Practical Concurrent Priority Queues
- Dynamic concurrent van Emde Boas array
2015/8
- Relative Suffix Trees
- Space-efficient detection of unusual words
- The k-mismatch problem revisited
- Full-text and Keyword Indexes for String Searching
- A Practical O(R\log\log n+n) time Algorithm for Computing the Longest Common Subsequence
2015/7
- Range Predecessor and Lempel-Ziv Parsing
- Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
- Finger Search in Grammar-Compressed Strings
- Compressed Data Structures for Dynamic Sequences
- Computing Runs on a General Alphabet
- Online Self-Indexed Grammar Compression
- A numerical analysis of Quicksort: How many cases are bad cases?
- A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays
- Pattern-avoiding access in binary search trees
- A Bloom filter based semi-index on $q$-grams
2015/6
- Relative Select
- Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
- Fast Computation of Abelian Runs
- Linear Algorithms for Computing the Lyndon Border Array and the Lyndon Suffix Array
- Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables
- FM-index for dummies
- Linear Algorithm for Conservative Degenerate Pattern Matching
- Error Tree: A Tree Structure for Hamming & Edit Distances & Wildcards Matching
- Tree Compression with Top Trees Revisited
- Amortized Rotation Cost in AVL Trees
- Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers
2015/5
- Optimal Search Trees with 2-Way Comparisons
- Linear-Time Superbubble Identification Algorithm for Genome Assembly
- Triple State QuickSort, A replacement for the C/C++ library qsort
- Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
- Read Mapping on de Bruijn graph
- An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints
- An Efficient Dynamic Programming Algorithm for STR-IC-SEQ-EC-LCS Problem
- Fast and Powerful Hashing using Tabulation
- Implementation of BT-trees
2015/4
- Faster Lightweight Lempel-Ziv Parsing
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Dynamic index, LZ factorization, and LCE queries in compressed space
- Lempel Ziv Computation In Small Space (LZ-CISS)
- Longest Common Extensions in Sublinear Space
- Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
- On Maximal Unbordered Factors
- Dictionary matching in a stream
- Tree compression using string grammars
- The complexity of computation in bit streams
2015/3
- Approximating LZ77 in Small Space
- Diverse Palindromic Factorization is NP-Complete
- Mind the Gap
- Dynamic Data Structures for Document Collections and Graphs
- Binary Coding in Stream
- A note on the longest common Abelian factor problem
- Dual pivot Quicksort
2015/2
- Composite repetition-aware data structures
- A Compressed-Gap Data-Aware Measure
- A framework for space-efficient string kernels
- Algorithms for Longest Common Abelian Factors
- Compressed Tree Canonization
- Adaptive Search over Sorted Sets
- Parameterized Complexity of Superstring Problems
- Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
2015/1
- Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets
- On Longest Repeat Queries
- Mespotine-RLE-basic v0.9 - An overhead-reduced and improved Run-Length-Encoding Method
- Efficient Algorithms for the Order Preserving Pattern Matching Problem
- Online Computation of Abelian Runs
- A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms
- Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
- On The Average-Case Complexity of Shellsort
2014
2014/12
- Queries on LZ-Bounded Encodings
- Longest Common Extensions in Trees
- Searching and Indexing Genomic Databases via Kernelization
- Online Detection of Repetitions with Backtracking
- Run-Length Encoded Nondeterministic KMP and Suffix Automata
- Covering Problems for Partial Words and for Indeterminate Strings
- Computing Covers Using Prefix Tables
- Simple Balanced Binary Search Trees
- Compression of high throughput sequencing data with probabilistic de Bruijn graph
- Fewer runs than word length
- Pattern Matching and Local Alignment for RNA Structures
2014/11
- Variable-Order de Bruijn Graphs
- Faster Compressed Quadtrees
- Online Square Detection
- Optimal Encodings for Range Top-k, Selection, and Min-Max
- PivotCompress: Compression by Sorting
- Analysis of Branch Misses in Quicksort
- Towards Tight Lower Bounds for Range Reporting on the RAM
- Fusion Tree Sorting
- Analysis of Pivot Sampling in Dual-Pivot Quicksort
- Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems
- Algorithms in the Ultra-Wide Word Model
2014/10
- Efficient and Compact Representations of Prefix Codes
- Encodings of Range Maximum-Sum Segment Queries and Applications
- A massively parallel algorithm for constructing the BWT of large string sets
- Practical Massively Parallel Sorting
- Tight tradeoffs for approximating palindromes in streams
- Building a Balanced k-d Tree in O(kn log n) Time
- Optimal Time Random Access to Grammar-Compressed Strings in Small Space
- Faster Sorting Networks for $17$, $19$ and $20$ Inputs
2014/9
- Document Counting in Practice
- Lempel-Ziv Factorization May Be Harder Than Computing All Runs
- Approximating solution structure of the Weighted Sentence Alignment problem
- Path algebra algorithm for finding longest increasing subsequence
- A Parameterized Study of Maximum Generalized Pattern Matching Problems
- Longest common substrings with k mismatches
2014/8
- Wavelet Trees Meet Suffix Trees
- Strong inapproximability of the shortest reset word
- Rank, select and access in grammar-compressed strings
- Online Pattern Matching for String Edit Distance with Moves
- Dictionary Matching with One Gap
- Analysis of String Sorting using Heapsort
- Quantum pattern matching fast on average
2014/7
- Suffix Arrays for Spaced-SNP Databases
- Sublinear Space Algorithms for the Longest Common Substring Problem
- Fibonacci Heaps Revisited
- Constructing small tree grammars and small circuits for formulas
- $LCSk$++: Practical similarity metric for long strings
- On the Average-case Complexity of Pattern Matching with Wildcards
- Parallel Wavelet Tree Construction
- A note on multipivot Quicksort
- GCD Computation of n Integers
2014/6
- The “Runs” Theorem
- Weighted ancestors in suffix trees
- Linear-time Computation of Minimal Absent Words Using Suffix Array
- Average-Case Optimal Approximate Circular String Matching
- How inefficient can a sort algorithm be?
- Fast construction of FM-index for long sequence reads
- Compact Indexes for Flexible Top-k Retrieval
- A note on the largest number of red nodes in red-black trees
- Multilevel polynomial partitions and simplified range searching
- Sampling the suffix array with minimizers
- ARC Sort: Enhanced and Time Efficient Sorting Algorithm
- Kernelization lower bound for Permutation Pattern Matching
2014/5
- Efficient Compressed Wavelet Trees over Large Alphabets
- On Hardness of Jumbled Indexing
- Alternative Algorithms for Lyndon Factorization
- Introduction to Dynamic Unary Encoding
- An External-Memory Algorithm for String Graph Construction
- Disk-based genome sequencing data compression
- Two simple full-text indexes based on the suffix array
- Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
- Compressive Mining: Fast and Optimal Data Mining in the Compressed Domain
- Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
- The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm
- Multiple pattern matching revisited
2014/4
- Reusing an FM-index
- Optimal Encodings for Range Majority Queries
- Document Retrieval on Repetitive Collections
- Improved ESP-index: a practical self-index for highly repetitive texts
- Combining pattern-based CRFs and weighted context-free grammars
- Normal, Abby Normal, Prefix Normal
2014/3
- A really simple approximation of smallest grammar
- Compressed Subsequence Matching and Packed Tree Coloring
- A Subquadratic Algorithm for Minimum Palindromic Factorization
- A Suffix Tree Or Not A Suffix Tree?
- Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time
- String Reconstruction from Substring Compositions
- Engineering Parallel String Sorting
- Efficient Representation for Online Suffix Tree Construction
- Most Recent Match Queries in On-Line Suffix Trees (with appendix)
2014/2
- Longest Common Subsequence in k-length substrings
- Static Level Ancestors in Practice
- Dynamic Partial Sorting
- Data Compaction - Compression without Decompression
- How Fast Can We Multiply Large Integers on an Actual Computer?
- Integer Set Compression and Statistical Modeling
2014/1
- Linear time construction of compressed text indices in compact space
- Fast Algorithm for Partial Covers in Words
- Space-Efficient String Indexing for Wildcard Pattern Matching
- Fully Online Grammar Compression in Constant Space
- Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
- A Comparative Study on String Matching Algorithm of Biological Sequences
- GPU-Accelerated BWT Construction for Large Collection of Short Reads
- A Fast String Matching Algorithm Based on Lowlight Characters in the Pattern
- On Combinatorial Generation of Prefix Normal Words
- On the representation of de Bruijn graphs
2013
2013/12
- Compressed Spaced Suffix Arrays
- Simple, compact and robust approximate string dictionary
- Succinct representation of labeled trees
- A Functional Approach to Standard Binary Heaps
- Near-optimal labeling schemes for nearest common ancestors
- Shortest Unique Substring Query Revisited
- A Note on the Longest Common Compatible Prefix Problem for Partial Words
- RAM-Efficient External Memory Sorting
2013/11
- Encoding Range Minimum Queries
- A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays
- Efficient algorithms for the longest common subsequence in $k$-length substrings
- Efficiently Computing Edit Distance to Dyck Language
- Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
- From Theory to Practice: Plug and Play with Succinct Data Structures
- Internal Pattern Matching Queries in a Text and Applications
2013/10
- Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets
- Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression
- Approximate String Matching using a Bidirectional Index
- Dynamic Gomory-Hu Tree Construction – fast and simple
2013/9
- Order-preserving pattern matching with k mismatches
- Substring Suffix Selection
- The Swap Matching Problem Revisited
- TRANS outperforms MTF for two special types of request sequences without locality of reference
- O-notation in algorithm analysis
- The Dynamic Longest Increasing Subsequence Problem
- XML Compression via DAGs
- Approximation of smallest linear tree grammar
2013/8
- Beating O(nm) in approximate LZW-compressed pattern matching
- ELB-Trees, An Efficient and Lock-free B-tree Derivative
- Sublinear Matching With Finite Automata Using Reverse Suffix Scanning
- Sorted Range Reporting Revisited
- Estimating the longest increasing sequence in polylogarithmic time
- Data Structures in Classical and Quantum Computing
2013/7
- Lempel-Ziv Parsing in External Memory
- AliBI: An Alignment-Based Index for Genomic Datasets
- Optimal Top-k Document Retrieval
- Bicriteria data compression
- First-Come-First-Served for Online Slot Allocation and Huffman Coding
- Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead
- Finding small patterns in permutations in linear time
- QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average
- The technique of in-place associative sorting
- Complexity of the FIFO Stack-Up Problem
- Compressed Pattern-Matching with Ranked Variables in Zimin Words
- An Elegant Algorithm for the Construction of Suffix Arrays
- On string matching with k mismatches
- Domain Specific Hierarchical Huffman Encoding
- A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications
2013/6
- Hybrid Indexes for Repetitive Datasets
- Succinct data structures for representing equivalence classes
- Optimal Color Range Reporting in One Dimension
- On a compact encoding of the swap automaton
- Parallel Algorithm for Longest Common Subsequence in a String
- Minimal Indices for Successor Search
- Set-Difference Range Queries
- Motif matching using gapped patterns
- Sorting suffixes of a text via its Lyndon Factorization
- Orthogonal Range Searching for Text Indexing
2013/5
- Faster Compact On-Line Lempel-Ziv Factorization
- LZ-Compressed String Dictionaries
- Fingerprints in Compressed Strings
- Heaviest Induced Ancestors and Longest Common Substrings
- Finding Distinct Subpalindromes Online
- Parallel String Sample Sort
- Repetition-free longest common subsequence of random sequences
- Suffix Tree of Alignment: An Efficient Index for Similar Data
- Lightweight LCP Construction for Next-Generation Sequencing Datasets
2013/4
- Compact q-gram Profiling of Compressed Strings
- Efficient repeat finding via suffix arrays
- Detecting regularities on grammar-compressed strings
- Efficient Lyndon factorization of grammar compressed text
- Tree Compression with Top Trees
- Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
- Web graph compression with fast access
- Average Case and Distributional Analysis of Dual-Pivot Quicksort
- A Succinct Grammar Compression
2013/3
- Computing convolution on grammar-compressed text
- Order-Preserving Suffix Trees and Their Algorithmic Applications
- Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays
- Optimal Partitioning for Dual-Pivot Quicksort
- Ultra-fast Multiple Genome Sequence Matching Using GPU
- An Efficient Dynamic Programming Algorithm for the Generalized LCS Problem with Multiple Substring Exclusion Constrains
- Using cascading Bloom filters to improve the memory usage for de Brujin graphs
2013/2
- Lightweight Lempel-Ziv Parsing
- Alphabet-Dependent String Searching with Wexponential Search Trees
- Order Preserving Matching
- Full-fledged Real-Time Indexing for Constant Size Alphabets
- One-variable word equations in linear time
- Modulated String Searching
- Dynamic 2D Dictionary Matching in Small Space
- Parallel Suffix Array Construction by Accelerated Sampling
2013/1
- Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
- Single and multiple consecutive permutation motif search
- Various improvements to text fingerprinting
- A Dynamic Programming Solution to a Generalized LCS Problem
- Engineering Small Space Dictionary Matching
- Approximation of grammar-based compression via recompression
- A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
- Tree-based Arithmetic and Compressed Representations of Giant Numbers
- 2D Lyndon Words and Applications
2012
2012/12
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
- New Algorithms for Position Heaps
- Necklaces, Convolutions, and X+Y
2012/11
- Simpler and Faster Lempel Ziv Factorization
- Time-Space Trade-Offs for Longest Common Extensions
- Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching
- Faster Compact Top-k Document Retrieval
- The Rightmost Equal-Cost Position Problem
- Algorithms for discovering and proving theorems about permutation patterns
- A memory versus compression ratio trade-off in PPM via compressed context modeling
- Approximate pattern matching with k-mismatches in packed text
- Algorithms for Computing Abelian Periods of Words
- Note on the Greedy Parsing Optimality for Dictionary-Based Text Compression
2012/10
- Better Space Bounds for Parameterized Range Majority and Minority
- New algorithms for binary jumbled pattern matching
- In-place associative permutation sort
2012/9
- Predecessor search with distance-sensitive query time
- Sorting distinct integers using improved in-place associative sort
- Improved in-place associative integer sorting
- Sorting distinct integer keys using in-place associative sort
- A New Algorithm for Data Compression Optimization
- In-place associative integer sorting
- Fast Packed String Matching for Short Patterns
- Streaming Complexity of Checking Priority Queues
- Bouma2 - A Quasi-Stateless, Tunable Multiple String-Match Algorithm
- QuickHeapsort: Modifications and improved analysis
- Counting common substrings effectively
2012/8
- Space-Time Trade-offs for Stack-Based Algorithms
- Distance Measures for Sequences
- A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting
- A Note on Efficient Computation of All Abelian Periods in a String
- On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List
2012/7
- Efficient LZ78 factorization of grammar compressed text
- Sparse Suffix Tree Construction with Small Space
- Ranked Document Retrieval in (Almost) No Space
- Memory Efficient De Bruijn Graph Construction
- Refined Quicksort asymptotics
- On Optimal Top-K String Retrieval
- Efficient algorithms for highly compressed data: The Word Problem in Generalized Higman Groups is in P
2012/6
- Optimal Dynamic Sequence Representations
- Efficient Algorithms for Finding Tucker Patterns
- Some Novel Results From Analysis of Move To Front (MTF) List Accessing Algorithm
- Optimal compression of hash-origin prefix trees
- Quasi-Succinct Indices
- On the combinatorics of suffix arrays
- Comparison of Bucket Sort and RADIX Sort
- Binary Jumbled String Matching for Highly Run-Length Compressible Texts
- On the Complexity of Minimum Labeling Alignment of Two Genomes
2012/5
- Sequential-Access FM-Indexes
- Lyndon Words and Short Superstrings
- Improving Compressed Counting
- TH*:Scalable Distributed Trie Hashing
- Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
2012/4
- Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding
- On the Value of Multiple Read/Write Streams for Data Compression
- Sorted Range Reporting
- Adaptive Techniques to find Optimal Planar Boxes
- Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
- A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
- String Trees
- The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space
- Succinct Posets
2012/3
- Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
- On a New Method of Storing a Variable Size Array
- A Fast Algorithm Finding the Shortest Reset Words
- Sorting and preimages of pattern classes
- Simplified, stable parallel merging
2012/2
- Speeding-up $q$-gram mining on grammar-based compressed texts
- Linear-Space Substring Range Counting over Polylogarithmic Alphabets
- (Really) Tight bounds for dispatching binary methods
- Computing Lempel-Ziv Factorization Online
- Cross-Document Pattern Matching
- Pattern Matching in Multiple Streams
- On Approximating String Selection Problems with Outliers
2012/1
- Compact Binary Relation Representations with Rich Functionality
- SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
- An Entertaining Example for the Usage of Bitwise Operations in Programming
- A Bijective String Sorting Transform
- Lower bounding edit distances between permutations
- Deterministic Polynomial-Time Algorithms for Designing Short DNA Words
- Quasiperiodicities in Fibonacci strings
- BIN@ERN: Binary-Ternary Compressing Data Coding
2011
2011/12
- Self-Index based on LZ77 (thesis)
- Tight lower bounds for online labeling problem
- Uncommon Suffix Tries
- On the Complexity of Approximate Sum of Sorted List
- Computing on Binary Strings
2011/11
- A Compressed Self-Index for Genomic Databases
- Optimal Lower and Upper Bounds for Representing Sequences
- Practical Top-K Document Retrieval in Reduced Space
- Edit Distance to Monotonicity in Sliding Windows
- Faster fully compressed pattern matching by recompression
- De-amortizing Binary Search Trees
2011/10
- Improved Grammar-Based Compressed Indexes
- String Indexing for Patterns with Wildcards
- String Matching with Variable Length Gaps
- Mining Patterns in Networks using Homomorphism
- On Approximability of Block Sorting
- Computing a Longest Common Palindromic Subsequence
- Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection
2011/9
- A Faster Grammar-Based Self-Index
- Faster Approximate Pattern Matching in Compressed Repetitive Texts
- Tying up the loose ends in fully LZW-compressed pattern matching
- A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
- Approximating Edit Distance in Near-Linear Time
- A Regularity Measure for Context Free Grammars
- A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query
- Anomaly Sequences Detection from Logs Based on Compression
- Encoding 2-D Range Maximum Queries
- Lossless data compression on GPGPU architectures
- Pattern Matching under Polynomial Transformation
- Specific “scientific” data structures, and their processing
2011/8
- Towards Optimal Sorting of 16 Elements
- Substring Range Reporting
- On Compressing Permutations and Adaptive Sorting
- Succinct Representations of Permutations and Functions
- Linear Time Inference of Strings from Cover Arrays using a Binary Alphabet
- Optimal Indexes for Sparse Bit Vectors
- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
2011/7
- Restructuring Compressed Texts without Explicit Decompression
- Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts
- Computing q-gram Frequencies on Collage Systems
- External Memory Orthogonal Range Reporting with Fast Updates
- Sorting Algorithms with Restrictions
- K-sort: A new sorting algorithm that beats Heap sort for n <= 70 lakhs!
- Privacy-Enhanced Methods for Comparing Compressed DNA Sequences
- Genome Halving by Block Interchange
- Quadratic-time Algorithm for the String Constrained LCS Problem
2011/6
- Space-Efficient Data-Analysis Queries on Grids
- Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections
- Reference Sequence Construction for Relative Compression of Genomes
- Dynamic Range Selection in Linear Space
- Space Lower Bounds for Online Pattern Matching
- SparseAssembler: de novo Assembly with the Sparse de Bruijn Graph
2011/5
- The Cell Probe Complexity of Dynamic Range Counting
- An Improved Move-To-Front(IMTF) Off-line Algorithm for the List Accessing Problem
2011/4
- Fixed Block Compression Boosting in FM-Indexes
- Dynamic Range Majority Data Structures
- Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
- Random input helps searching predecessors
- Efficient Seeds Computation Revisited
- I/O-Efficient Data Structures for Colored Range and Prefix Reporting
- On-line construction of position heaps
2011/3
- Fast $q$-gram Mining on SLP Compressed Strings
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- On minimising automata with errors
- Linear pattern matching on sparse suffix trees
- Stratified B-trees and versioning dictionaries
- Orthogonal Range Searching on the RAM, Revisited
- An implementation of range trees with fractional cascading in C++
2011/2
- Upper Bounds for Maximally Greedy Binary Search Trees
- On Dynamic Optimality for Binary Search Trees
- Don’t Rush into a Union: Take Time to Find Your Roots
- Algorithms for Jumbled Pattern Matching in Strings
2011/1
- Self-Index Based on LZ77
- Compressed String Dictionaries
- Linear-Space Data Structures for Range Mode Query in Arrays
- Inducing the LCP-Array
- Succincter Text Indexing with Wildcards
2010
2010/12
- A Searchable Compressed Edit-Sensitive Parsing
- Lightweight LCP-Array Construction in Linear Time
2010/11
- New Algorithms on Wavelet Trees and Applications to Information Retrieval
- Counting Colours in Compressed Strings
- Worst case efficient single and multiple string matching in the Word-RAM model
- Pattern Kits
- CRAM: Compressed Random Access Memory
- Parallelization of Weighted Sequence Comparison by using EBWT
2010/9
- LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
- Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata
2010/8
- Succinct Data Structures for Assembling Large Genomes
- The universality of iterated hashing over variable-length strings
2010/7
- Tree structure compression with RePair
- Top-K Color Queries for Document Retrieval
- Fully Dynamic Data Structure for Top-k Queries on Uncertain Data
2010/6
- Dynamic Range Reporting in External Memory
- Optimal Trade-Off for Succinct String Indexes
- An Efficient Algorithm For Chinese Postman Walk on Bi-directed de Bruijn Graphs
- Should Static Search Trees Ever Be Unbalanced?
- Tight and simple Web graph compression
2010/5
- Succinct Representations of Dynamic Strings
- The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
- On Finding Frequent Patterns in Directed Acyclic Graphs
2010/4
- Unified Compression-Based Acceleration of Edit-Distance Computation
- Restricted Common Superstring and Restricted Common Supersequence
- Some long-period random number generators using shifts and xors
- Uses of randomness in computation
2010/3
- On the Border Length Minimization Problem (BLMP) on a Square Array
- Efficient Parallel and Out of Core Algorithms for Constructing Large Bi-directed de Bruijn Graphs
2010/2
- Range Reporting for Moving Points on a Grid
- Mergeable Dictionaries
2010/1
- Random Access to Grammar Compressed Strings
- Succinct Dictionary Matching With No Slowdown
- Document Clustering with K-tree
- Sampled Longest Common Prefix Array
- Random Indexing K-tree
- K-tree: Large Scale Document Clustering
2009
2009/12
- Grammar-Based Compression in a Streaming Model
- A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source
- Practical Algorithmic Techniques for Several String Processing Problems
- Time and Memory Efficient Lempel-Ziv Compression Using Suffix Arrays
- Renewal theory in analysis of tries and strings
2009/11
- Efficient Fully-Compressed Sequence Representations
- Re-Pair Compression of Inverted Lists
- Fast Arc-Annotated Subsequence Matching in Linear Space
- An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence
- A Minimal Periods Algorithm with Applications
2009/10
- Wee LCP
- Searching a bitstream in linear time for the longest substring of any given density
- b-Bit Minwise Hashing
- Estimating Entropy of Data Streams Using Compressed Counting
- Scalable Distributed-Memory External Sorting
2009/9
- Lightweight Data Indexing and Compression in External Memory
- Randomized Shellsort: A Simple Oblivious Sorting Algorithm
- Fast Set Intersection and Two Patterns Matching
- Range Non-Overlapping Indexing
- Generating All Partitions: A Comparison Of Two Encodings
2009/8
- On Bijective Variants of the Burrows-Wheeler Transform
2009/7
- Tight Bounds for Online Stable Sorting
- Fast In-Memory XPath Search over Compressed Text and Tree Indexes
- Fast Searching in Packed Strings
- Online Sorting via Searching and Selection
- A Lower Bound for Succinct Rank Queries
2009/6
- On optimally partitioning a text to improve its compression
- Data Structures for Approximate Range Counting
- Cell-Probe Lower Bounds for Prefix Sums
2009/5
- Fast and Compact Prefix Codes
- Fully-Functional Static and Dynamic Succinct Trees
2009/4
- Learning Character Strings via Mastermind Queries, with a Case Study Involving mtDNA
- On Smoothed Analysis of Quicksort and Hoare’s Find
2009/3
- Range Quantile Queries: Another Virtue of Wavelet Trees
- Heaps Simplified
- On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression
- Analysis of the Relationships among Longest Common Subsequences, Shortest Common Supersequences and Patterns and its application on Pattern Discovery in Biological Sequences
2009/2
- New Algorithms and Lower Bounds for Sequential-Access Data Compression
- Compressed Representations of Permutations, and Applications
- More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
- A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
2008
2008/12
- Worst-Case Optimal Adaptive Prefix Coding
- Minimax Trees in Linear Time
- The Violation Heap: A Relaxed Fibonacci-Like Heap
- Optimal Succinctness for Range Minimum Queries
2008/11
- Faster Approximate String Matching for Short Patterns
- Low-Memory Adaptive Prefix Coding
- How robust is quicksort average complexity?
- Binar Sort: A Linear Generalized Sorting Algorithm
- Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes
2008/10
- A New Algorithm for Building Alphabetic Minimax Trees
- Efficient Pattern Matching on Binary Strings
2008/9
- A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
2008/7
- Improved Algorithms for Approximate String Matching (Extended Abstract)
2008/6
- Biased Range Trees
- A Dynamic Programming Approach To Length-Limited Huffman Coding
- Space Efficient Multi-Dimensional Range Reporting
2008/5
- Succinct Geometric Indexes Supporting Point Location Queries
2008/4
- New Lower Bounds for the Maximum Number of Runs in a String
- Discovering More Accurate Frequent Web Usage Patterns
2008/3
- Succinct Data Structures for Retrieval and Approximate Membership
2008/2
- Bit-Optimal Lempel-Ziv compression
- Deriving Sorting Algorithms
- Understanding maximal repetitions in strings
- Parameterized Algorithms for Partial Cover Problems
- Approximating General Metric Distances Between a Pattern and a Text
2008/1
- String algorithms and data structures
2007
2007/12
- Compressed Text Indexes:From Theory to Practice!
2007/11
- Bounds for Compression in Streaming Models
2007/8
- Pattern Matching in Trees and Strings
- Empirical entropy in context
- A nearly tight memory-redundancy trade-off for one-pass compression
2007/6
- Radix Sorting With No Extra Space
- Sublinear Algorithms for Approximating String Compressibility
- Dualheap Sort Algorithm: An Inherently Parallel Generalization of Heapsort
2006
2006/11
- On the space complexity of one-pass compression
2006/9
- Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
- Practical Entropy-Compressed Rank/Select Dictionary
2006/8
- The Tree Inclusion Problem: In Linear Space and Faster
2006/6
- New Algorithms for Regular Expression Matching
2006/1
- An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
2005
2005/12
- Matching Subsequences in Trees
2005/9
- Fast and Compact Regular Expression Matching
2005/6
- Large Alphabets and Incompressibility
- Sorting a Low-Entropy Sequence
- Compressing Probability Distributions
2005/3
- Dynamic Shannon Coding
1996
1996/8
- Shellsort with three increments