StringologyTimes

arXiv Papers

2024

2024/7

1. Words Avoiding Tangrams

2024/6

1. Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
2. Counting on General Run-Length Grammars
3. Space-efficient SLP Encoding for $O(\log N)$-time Random Access
4. Implementation Of Dynamic De Bruijn Graphs Via Learned Index
5. Almost Linear Size Edit Distance Sketch
6. String Partition for Building Big BWTs
7. The reflection complexity of sequences over finite alphabets
8. Repetition Threshold for Binary Automatic Sequences
9. Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
10. Indexing Finite-State Automata Using Forward-Stable Partitions
11. Maximal number of subword occurrences in a word
12. Word equations, constraints, and formal languages
13. A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs
14. A Symmetry Property of Christoffel Words
15. Evaluating $n$-Gram Novelty of Language Models Using Rusty-DAWG
16. The Repetition Threshold for Rote Sequences
17. Unveiling the connection between the Lyndon factorization and the Canonical Inverse Lyndon factorization via a border property
18. Perfectly Clustering Words and Iterated Palindromes over a Ternary Alphabet
19. Bijective BWT based compression schemes

2024/5

1. A Lock-free Binary Trie
2. Querying in Constant Time with Learned Indexes
3. Minimizing the Minimizers via Alphabet Reordering
4. SPIDER: Improved Succinct Rank and Select Performance
5. Finding Diverse Strings and Longest Common Subsequences in a Graph
6. De Bruijn Polyominoes
7. Theoretical insights and an experimental comparison of tango trees and multi-splay trees
8. Lyndon pairs and the lexicographically greatest perfect necklace
9. Adaptive Dynamic Bitvectors
10. String 2-Covers with No Length Restrictions
11. Lock-Free Augmented Trees
12. Kolmogorov complexity as a combinatorial tool
13. Counting overlapping pairs of strings

2024/4

1. Generalized Straight-Line Programs
2. Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
3. Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality
4. Fast and Simple Sorting Using Partial Information
5. Enumerating runs, valleys, and peaks in Catalan words
6. Characterization of Isometric Words based on Swap and Mismatch Distance
7. On multidimensional generalization of binary search
8. Computing the LCP Array of a Labeled Graph
9. Hairpin Completion Distance Lower Bound
10. Better space-time-robustness trade-offs for set reconciliation
11. Bit catastrophes for the Burrows-Wheeler Transform
12. Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
13. Dynamic Suffix Array in Optimal Compressed Space
14. Frogs, hats and common subsequences
15. Exploring Repetitiveness Measures for Two-Dimensional Strings
16. From the Lyndon factorization to the Canonical Inverse Lyndon factorization: back and forth
17. Internal Pattern Matching in Small Space and Applications
18. Scalable Distributed String Sorting
19. Exploiting New Properties of String Net Frequency for Efficient Computation

2024/3

1. How to Find Long Maximal Exact Matches and Ignore Short Ones
2. String attractors and bi-infinite words
3. A simpler data structure for dynamic strings
4. BAT-LZ Out of Hell
5. Height-bounded Lempel-Ziv encodings
6. Simplified Tight Bounds for Monotone Minimal Perfect Hashing
7. Optimal Bounds for Distinct Quartics
8. NP-Completeness for the Space-Optimality of Double-Array Tries
9. Enumeration for MSO-Queries on Compressed Trees
10. A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
11. Algorithms for Galois Words: Detection, Factorization, and Rotation
12. On the Communication Complexity of Approximate Pattern Matching
13. On the complexity and approximability of Bounded access Lempel Ziv coding
14. Exploring the Crochemore and Ziv-Lempel factorizations of some automatic sequences with the software Walnut
15. Space-Efficient Indexes for Uncertain Strings

2024/2

1. Consecutive Power Occurrences in Sturmian Words
2. Iterated Straight-Line Programs
3. Pattern Matching with Mismatches and Wildcards
4. Palindromic Periodicities
5. ShiftDTW: adapting the DTW metric for cyclic time series clustering
6. A visualization tool to explore alphabet orderings for the Burrows-Wheeler Transform
7. Computing Longest Common Subsequence under Cartesian-Tree Matching Model
8. Edit and Alphabet-Ordering Sensitivity of Lex-parse
9. Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
10. Shortest cover after edit
11. A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
12. Enhanced Graph Pattern Matching
13. Regular Languages in the Sliding Window Model
14. Approximate Circular Pattern Matching under Edit Distance
15. Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
16. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

2024/1

1. Combinatorics on words and generating Dirichlet series of automatic sequences
2. Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
3. Heuristics for the Run-length Encoded Burrows-Wheeler Transform Alphabet Ordering Problem
4. Towards Optimal Grammars for RNA Structures
5. Efficient Construction of Long Orientable Sequences

2023

2023/12

1. Range Entropy Queries and Partitioning
2. Selective Run-Length Encoding
3. Phylogenetic tree distance computation over succinct representations
4. A Huffman based short message service compression technique using adjacent distance array
5. Faster Algorithms for Internal Dictionary Queries
6. Some Fibonacci-Related Sequences
7. More characterizations of morphic words
8. Staircase graph words
9. A symbolic-arithmetic for teaching double-black node removal in red-black trees
10. r-indexing without backward searching

2023/11

1. Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
2. Dynamic Dictionary with Subconstant Wasted Bits per Key
3. On the piecewise complexity of words and periodic words
4. Enumeration and Succinct Encoding of AVL Trees
5. Repetition factorization of automatic sequences
6. The analogue of overlap-freeness for the Fibonacci morphism
7. Critical exponent of binary words with few distinct palindromes
8. Pairwise sequence alignment with block and character edit operations
9. Differentially Private Approximate Pattern Matching
10. Faster Maximal Exact Matches with Lazy LCP Evaluation
11. Exact Shortest Paths with Rational Weights on the Word RAM
12. Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
13. Space-Efficient Data Structures for Polyominoes and Bar Graphs
14. Size-constrained Weighted Ancestors with Applications

2023/10

1. Optimization with pattern-avoiding input
2. Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
3. The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold
4. Searching 2D-Strings for Matching Frames
5. Finding a reconfiguration sequence between longest increasing subsequences
6. Structure and growth of $\mathbb{R}$-bonacci words
7. Dynamic Dynamic Time Warping
8. Rank and Select on Degenerate Strings
9. Fast and simple unrooted dynamic forests
10. Sketching and Streaming for Dictionary Compression
11. Efficient Online String Matching through Linked Weak Factors
12. Faster Algorithms for Text-to-Pattern Hamming Distances
13. Deterministic 3SUM-Hardness

2023/9

1. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
2. The repetition threshold of episturmian sequences
3. $(\min,+)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
4. On Unique Factorization of Non-periodic Words
5. Dynamic “Succincter”
6. Correlations of minimal forbidden factors of the Fibonacci word
7. Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time

2023/8

1. Linear Time Construction of Cover Suffix Tree and Applications
2. An Algorithm for the Constrained Longest Common Subsequence and Substring Problem
3. Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
4. Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
5. String attractors of Rote sequences
6. An Algorithm for the Longest Common Subsequence and Substring Problem
7. Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions
8. Quantum Circuits for Fixed Substring Matching Problems
9. Adaptive Encoding Strategies for Erasing-Based Lossless Floating-Point Compression
10. Hierarchical Lowrank Arithmetic with Binary Compression
11. Wheeler maps
12. Matching Patterns with Variables Under Simon’s Congruence
13. Another virtue of wavelet forests?
14. Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
15. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

2023/7

1. Approximating Edit Distance in the Fully Dynamic Model
2. Computing SEQ-IC-LCS of Labeled Graphs
3. Random Wheeler Automata
4. Compressibility measures for two-dimensional data
5. Sliding suffix trees simplified
6. Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
7. Linear-time computation of generalized minimal absent words for multiple strings
8. Two-dimensional Dyck words
9. Evaluating Regular Path Queries on Compressed Adjacency Matrices
10. Shorter and faster than Sort3AlphaDev
11. A Compact DAG for Storing and Searching Maximal Common Subsequences
12. Efficient algorithms for enumerating maximal common subsequences of two strings
13. Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data

2023/6

1. Optimal Wheeler Language Recognition
2. Longest Common Prefix Arrays for Succinct k-Spectra
3. Maintaining the cycle structure of dynamic permutations
4. Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
5. Pb-Hash: Partitioned b-bit Hashing
6. Erasing-based lossless compression method for streaming floating-point time series
7. Approximate Cartesian Tree Matching: an Approach Using Swaps
8. Prefix-free graphs and suffix array construction in sublinear space
9. Faster Compression of Deterministic Finite Automata
10. Counting occurrences of patterns in permutations
11. Efficient Parameterized Pattern Matching in Sublinear Space
12. On the $k$-Hamming and $k$-Edit Distances
13. Subsequence frequency in binary words
14. Space-time Trade-offs for the LCP Array of Wheeler DFAs
15. Efficient Parallel Output-Sensitive Edit Distance
16. Computing all-vs-all MEMs in grammar-compressed text

2023/5

1. Optimal Algorithms for Bounded Weighted Edit Distance
2. Acceleration of FM-index Queries Through Prefix-free Parsing
3. Sorting Finite Automata via Partition Refinement
4. Sum-of-Local-Effects Data Structures for Separable Graphs
5. Ranking and unranking bordered and unbordered words
6. Prefix Sorting DFAs: a Recursive Algorithm
7. The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing
8. Streaming $k$-edit approximate pattern matching via string decomposition
9. CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
10. Can You Solve Closest String Faster than Exhaustive Search?
11. Affine Standard Lyndon words: A-type
12. Engineering Rank/Select Data Structures for Big-Alphabet Strings
13. Finding Maximal Exact Matches in Graphs
14. Matching Statistics speed up BWT construction

2023/4

1. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata
2. Subcubic algorithm for (Unweighted) Unrooted Tree Edit Distance
3. Lossy Compressor preserving variant calling through Extended BWT
4. The Longest Subsequence-Repeated Subsequence Problem
5. The 2-Attractor Problem is NP-Complete
6. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
7. Longest Common Subsequence with Gap Constraints
8. Ranking and Unranking k-subsequence universal words
9. Fast computation of approximate weak common intervals in multiple indeterminate strings
10. On arch factorization and subword universality for words and compressed words
11. Learned Monotone Minimal Perfect Hashing
12. Compressed Indexing for Consecutive Occurrences

2023/3

1. Enumerating all minimal hitting sets in polynomial total time
2. Optimal Square Detection Over General Alphabets
3. Optimal-Hash Exact String Matching Algorithms
4. B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load
5. Change a Bit to save Bytes: Compression for Floating Point Time-Series Data
6. On Sensitivity of Compact Directed Acyclic Word Graphs
7. The analogue of overlap-freeness for the period-doubling sequence
8. On the Maximal Independent Sets of $k$-mers with the Edit Distance
9. The Many Qualities of a New Directly Accessible Compression Scheme
10. Sturmian and infinitely desubstitutable words accepted by an ω-automaton

2023/2

1. Optimal Heaviest Induced Ancestors
2. Order-Preserving Squares in Strings
3. Faster Wavelet Trees with Quad Vectors
4. Compressibility-Aware Quantum Algorithms on Strings
5. A Simple Data Structure for Maintaining a Discrete Probability Distribution
6. Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
7. Prefixes of the Fibonacci word
8. Chaining of Maximal Exact Matches in Graphs
9. Locally consistent decomposition of strings with applications to edit distance sketching
10. Storing a Trie with Compact and Predictable Space
11. Weighted Edit Distance Computation: Strings, Trees and Dyck
12. Optimal LZ-End Parsing is Hard
13. Runs of Ones in Binary Strings
14. An Efficient B-tree Implementation for Memory-Constrained Embedded Systems
15. Smallest and Largest Block Palindrome Factorizations
16. String attractors of fixed points of k-bonacci-like morphisms
17. From Bit-Parallelism to Quantum String Matching for Labelled Graphs
18. Rudin-Shapiro Sums Via Automata Theory and Logic
19. A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression

2023/1

1. Algorithms for Massive Data – Lecture Notes
2. The Thue-Morse sequence in base 3/2
3. Succinct Planar Encoding with Minor Operations
4. Sliding Window String Indexing in Streams
5. Computing matching statistics on Wheeler DFAs
6. Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
7. SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree
8. Reconstructing words using queries on subwords or factors
9. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
10. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
11. Dyck Words, Pattern Avoidance, and Automatic Sequences

2022

2022/12

1. High Performance Construction of RecSplit Based Minimal Perfect Hash Functions
2. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
3. Transcoding Unicode Characters with AVX-512 Instructions
4. Pareto Optimal Compression of Genomic Dictionaries, with or without Random Access in Main Memory
5. Word Equations in Synergy with Regular Constraints (Technical Report)
6. Space-efficient conversions from SLPs
7. Trie-Compressed Intersectable Sets
8. Computing the optimal BWT of very large string collections

2022/11

1. Polyominoes and graphs built from Fibonacci words
2. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
3. Computing palindromes on a trie in linear time
4. Comparing Two Counting Methods for Estimating the Probabilities of Strings
5. String attractors of episturmian sequences
6. An Algorithmic Bridge Between Hamming and Levenshtein Distances
7. String Covering: A Survey
8. Reversible Programming: A Case Study of Two String-Matching Algorithms
9. Optimal resizable arrays
10. Some Results on Digital Segments and Balanced Words
11. Genome-on-Diet: Taming Large-Scale Genomic Analyses via Sparsified Genomics
12. On the Power of Learning-Augmented BSTs
13. Augmented Thresholds for MONI
14. Bounds and Estimates on the Average Edit Distance
15. External-memory dictionaries with worst-case update cost
16. Gapped String Indexing in Subquadratic Space and Sublinear Query Time
17. Approximating binary longest common subsequence in almost-linear time
18. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
19. On fractal patterns in Ulam words
20. A fast and simple $O (z \log n)$-space index for finding approximately longest common substrings
21. Space-efficient RLZ-to-LZ77 conversion

2022/10

1. Computing MEMs on Repetitive Text Collections
2. Space-Efficient STR-IC-LCS Computation
3. SicHash - Small Irregular Cuckoo Tables for Perfect Hashing
4. A nearly optimal randomized algorithm for explorable heap selection
5. Internal Longest Palindrome Queries in Optimal Time
6. Computing maximal generalized palindromes
7. Double-Ended Palindromic Trees: A Linear-Time Data Structure and Its Applications
8. Designing a parallel suffix sort
9. Finding binary words with a given number of subsequences
10. The appearance function for paper-folding words
11. On word-representability of simplified de Bruijn graphs
12. Locality-Preserving Minimal Perfect Hashing of k-mers
13. A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees
14. Splay Top Trees

2022/9

1. Space-efficient data structure for next/previous larger/smaller value queries
2. Maximal Closed Substrings
3. Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching
4. Elastic-Degenerate String Matching with 1 Error
5. Inferring strings from position heaps in linear time
6. Complement Avoidance in Binary Words
7. Convergence of the number of period sets in strings
8. Antisquares and Critical Exponents
9. MARIA: Multiple-alignment $r$-index with aggregation
10. Cache-Oblivious Representation of B-Tree Structures
11. Concurrent Size
12. Multiway Powersort
13. $\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance
14. Constant-delay enumeration for SLP-compressed documents
15. A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits

2022/8

1. Merging Sorted Lists of Similar Strings
2. Walking on Words
3. Algorithm to derive shortest edit script using Levenshtein distance algorithm
4. Approximate Circular Pattern Matching
5. New Parallel Order Maintenance Data Structure
6. Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev
7. Co-lexicographically ordering automata and regular languages. Part I
8. Almost optimal searching of maximal subrepetitions in a word
9. Fast detection of specific fragments against a set of sequences
10. Watson-Crick conjugates of words and languages
11. Combinatorial Algorithms for Subsequence Matching: A Survey
12. Pattern matching under DTW distance
13. Computing all-vs-all MEMs in run-length encoded collections of HiFi reads
14. Sorting Genomes by Prefix Double-Cut-and-Joins
15. A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion
16. Hierarchical Relative Lempel-Ziv Compression
17. A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence
18. Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform
19. Unbalancing Binary Trees
20. Simpler and Better Cardinality Estimators for HyperLogLog and PCSA

2022/7

1. Enumerating and Locating the Subwords of the Two-dimensional Infinite Fibonacci Word
2. Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
3. Computing NP-hard Repetitiveness Measures via MAX-SAT
4. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
5. Suffix sorting via matching statistics
6. Pattern matching algorithms in Blockchain for network fees reduction
7. Engineering faster double-array Aho-Corasick automata
8. Simple O(1) Query Algorithm for Level Ancestors
9. Tight Bounds for Monotone Minimal Perfect Hashing
10. Pseudoperiodic Words and a Question of Shevelev
11. Abelian Combinatorics on Words: a Survey
12. Subsequences in Bounded Ranges: Matching and Analysis Problems
13. On the Practical Power of Automata in Pattern Matching
14. Matching Patterns with Variables Under Edit Distance
15. Implementing the Comparison-Based External Sort
16. An Improved Algorithm for Finding the Shortest Synchronizing Words

2022/6

1. Hinted Dictionaries: Efficient Functional Ordered Sets and Maps
2. Fast Exact String to D-Texts Alignments
3. Properties of a Ternary Infinite Word
4. L-systems for Measuring Repetitiveness*
5. On the Lie complexity of Sturmian words
6. Near-Optimal Search Time in $δ$-Optimal Space
7. Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
8. String Attractors and Infinite Words
9. Efficient Algorithms for Sorting in Trees
10. Asymptotic bounds for the number of closed and privileged words
11. Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
12. Learning Augmented Binary Search Trees
13. PalFM-index: FM-index for Palindrome Pattern Matching
14. Balancing Run-Length Straight-Line Programs*
15. On the Optimisation of the GSACA Suffix Array Construction Algorithm
16. Longest Common Subsequence: Tabular vs. Closed-Form Equation Computation of Subsequence Probability
17. The Complexity of the Co-Occurrence Problem
18. Lower Bounds for Sorting 16, 17, and 18 Elements
19. KATKA: A KRAKEN-like tool with $k$ given at query time
20. Which arithmetic operations can be performed in constant time in the RAM model with addition?
21. Prefix-free parsing for building large tunnelled Wheeler graphs
22. On extended boundary sequences of morphic and Sturmian words
23. Computing the Parameterized Burrows–Wheeler Transform Online
24. Onesweep: A Faster Least Significant Digit Radix Sort for GPUs

2022/5

1. Computing Maximal Unique Matches with the r-index
2. Dynamic data structures for parameterized string problems
3. Cut-Down de Bruijn Sequences
4. A New Class of String Transformations for Compressed Text Indexing
5. Substring Complexities on Run-length Compressed Strings
6. A note on the maximum number of $k$-powers in a finite word
7. On Lyndon-Word Representable Graphs

2022/4

1. Reduction ratio of the IS-algorithm: worst and random cases
2. Faster Min-Plus Product for Monotone Instances
3. Faster Pattern Matching under Edit Distance
4. Speeding Hirschberg Algorithm for Sequence Alignment
5. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
6. String Rearrangement Inequalities and a Total Order Between Primitive Words
7. Theoretical analysis of edit distance algorithms: an applied perspective
8. On the number of squares in a finite word
9. Fast Circular Pattern Matching
10. Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
11. An $n H_k$-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers
12. Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
13. Efficient Construction of the BWT for Repetitive Text Using String Compression
14. Two-dimensional Fibonacci Words: Tandem Repeats and Factor Complexity
15. Improved Sublinear-Time Edit Distance for Preprocessed Strings
16. Prefix Filter: Practically and Theoretically Better Than Bloom

2022/3

1. Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems
2. Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
3. Binary codes that do not preserve primitivity
4. Note on a Fibonacci Parity Sequence
5. Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches
6. Online List Labeling: Breaking the $\log^2n$ Barrier
7. Quantum jumbled pattern matching

2022/2

1. RePair Grammars are the Smallest Grammars for Fibonacci Words
2. Longest (Sub-)Periodic Subsequence
3. Memory Efficient Tries for Sequential Pattern Mining
4. MONI can find k-MEMs
5. Cartesian Tree Subsequence Matching
6. Logarithmic equal-letter runs for BWT of purely morphic words
7. An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
8. A theoretical and experimental analysis of BWT variants for string collections
9. Minimal Absent Words on Run-Length Encoded Strings
10. LCP-dropout: Compression-based Multiple Subword Segmentation for Neural Machine Translation
11. Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
12. OSM-tree: A Sortedness-Aware Index

2022/1

1. X3: Lossless Data Compressor
2. Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
3. What Does Dynamic Optimality Mean in External Memory?
4. Dynamic Suffix Array with Polylogarithmic Queries and Updates
5. Predecessor on the Ultra-Wide Word RAM
6. Safety and Completeness in Flow Decompositions for RNA Assembly
7. Computing Longest (Common) Lyndon Subsequences
8. Multiple Genome Analytics Framework: The Case of All SARS-CoV-2 Complete Variants
9. Linear Time Construction of Indexable Elastic Founder Graphs
10. The Efficiency of the ANS Entropy Encoding

2021

2021/12

1. String Sampling with Bidirectional String Anchors
2. Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
3. How Compression and Approximation Affect Efficiency in String Distance Measures
4. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
5. Beyond the Longest Letter-duplicated Subsequence Problem
6. Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
7. Estimating the Longest Increasing Subsequence in Nearly Optimal Time
8. RLBWT Tricks
9. Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time
10. Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model
11. Optimal Gap Sequences in Shellsort for $n\leq16$ Elements
12. Empirically Improved Tokuda Gap Sequence in Shellsort
13. Parallel Batch-Dynamic $k$d-Trees
14. SIMD-Optimized Search Over Sorted Data
15. Approximating Length-Restricted Means under Dynamic Time Warping
16. A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

2021/11

1. Pattern Matching on Grammar-Compressed Strings in Linear Time
2. Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
3. Succinct Data Structure for Path Graphs
4. Graphs can be succinctly indexed for pattern matching in $ O(│E│^2 + │V│^{5 / 2}) $ time
5. An Improved Algorithm for The $k$-Dyck Edit Distance Problem
6. Nearly Tight Lower Bounds for Succinct Range Minimum Query
7. HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
8. On the Optimal Time/Space Tradeoff for Hash Tables
9. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
10. Approximation Algorithms for LCS and LIS with Truly Improved Running Times
11. Prefixes of the Fibonacci word that end with a cube
12. Tiny Pointers
13. Linear-time Minimization of Wheeler DFAs
14. Stochastic and Worst-Case Generalized Sorting Revisited
15. Approximate Membership Query Filters with a False Positive Free Set

2021/10

1. Near-Optimal Quantum Algorithms for String Problems
2. Computing Matching Statistics on Repetitive Texts
3. Counting and Verifying Abelian Border Arrays of Binary Words
4. An $O(k \log{n})$ algorithm for prefix based ranked autocomplete
5. Approximating LCS and Alignment Distance over Multiple Sequences
6. Linear Approximate Pattern Matching Algorithm
7. On Solving the Minimum Common String Partition Problem by Decision Diagrams
8. Is this the simplest (and most surprising) sorting algorithm ever?
9. FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
10. Parallel Batched Interpolation Search Tree
11. Reconstruction of Sets of Strings from Prefix/Suffix Compositions
12. Friendly Cut Sparsifiers and Faster Gomory-Hu Trees

2021/9

1. Abelian Repetition Threshold Revisited
2. Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees
3. Simple Worst-Case Optimal Adaptive Prefix-Free Coding
4. Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report
5. Absent Subsequences in Words
6. Ruler Wrapping
7. Fast Succinct Retrieval and Approximate Membership using Ribbon

2021/8

1. Arbitrary-length analogs to de Bruijn sequences
2. Space-Efficient Huffman Codes Revisited
3. Practical evaluation of Lyndon factors via alphabet reordering
4. A Tight Analysis of Slim Heaps and Smooth Heaps
5. Faster Exponential Algorithm for Permutation Pattern Matching
6. Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs
7. Does Preprocessing help in Fast Sequence Comparisons?
8. A Conditional Lower Bound for Episode Matching
9. Hierarchical Bitmap Indexing for Range and Membership Queries on Multidimensional Arrays
10. On Specialization of a Program Model of Naive Pattern Matching in Strings (Extended Abstract)

2021/7

1. Compression by Contracting Straight-Line Programs
2. String Comparison on a Quantum Computer Using Hamming Distance
3. Optimal Space and Time for Streaming Pattern Matching
4. Analysis of Smooth Heaps and Slim Heaps
5. Defeating duplicates: A re-design of the LearnedSort algorithm
6. Burrows Wheeler Transform on a Large Scale: Algorithms Implemented in Apache Spark
7. On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
8. Space Efficient Two-Dimensional Orthogonal Colored Range Counting
9. A New Lossless Data Compression Algorithm Exploiting Positional Redundancy
10. Critical factorisation in square-free words
11. Learned Sorted Table Search and Static Indexes in Small Space: Methodological and Practical Insights via an Experimental Study
12. Hardness of Detecting Abelian and Additive Square Factors in Strings
13. Sensitivity of string compressors and repetitiveness measures
14. Fast direct access to variable length codes

2021/6

1. Pattern-defeating Quicksort
2. Closed Ziv-Lempel factorization of the $m$-bonacci words
3. Counting Lyndon Subsequences
4. On (co-lex) Ordering Automata
5. Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash
6. Position Heaps for Cartesian-tree Matching on Strings and Tries
7. Internal Shortest Absent Word Queries in Constant Time and Linear Space
8. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
9. On the approximation ratio of LZ-End to LZ77
10. Matching Patterns with Variables under Hamming Distance
11. A Bloom Filter Survey: Variants for Different Domain Applications
12. Breaking the $O(n)$-Barrier in the Construction of Compressed Suffix Arrays
13. Checking whether a word is Hamming-isometric in linear time
14. Computing the original eBWT faster, simpler, and with less memory
15. Small space and streaming pattern matching with k edits
16. ExtendedHyperLogLog: Analysis of a new Cardinality Estimator
17. An efficient way to manage ranges of data with Wise Red-Black Trees
18. The k-mappability problem revisited
19. Boosting the Search Performance of B+-tree for Non-volatile Memory with Sentinels
20. APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

2021/5

1. N-ary Huffman Encoding Using High-Degree Trees – A Performance Comparison
2. Weighted Burrows-Wheeler Compression
3. Combinatorics of minimal absent words for a sliding window
4. The Dynamic k-Mismatch Problem
5. Tree Edit Distance with Variables. Measuring the Similarity between Mathematical Formulas
6. Compact Euler Tours of Trees with Small Maximum Degree
7. Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
8. Improved Approximation for Longest Common Subsequence over Small Alphabets
9. Faster Algorithms for Longest Common Substring
10. Faster Algorithms for Bounded Tree Edit Distance
11. Lower Bounds for the Number of Repetitions in 2D Strings
12. A new distance based on minimal absent words and applications to biological sequences
13. On Stricter Reachable Repetitiveness Measures*
14. Grammar Index By Induced Suffix Sorting
15. Minimal unique palindromic substrings after single-character substitution
16. Support Optimality and Adaptive Cuckoo Filters
17. Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing

2021/4

1. Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures
2. HINT: A Hierarchical Index for Intervals in Main Memory
3. PTHash: Revisiting FCH Minimal Perfect Hashing
4. Engineering Predecessor Data Structures for Dynamic Integer Sets
5. A Separation of $γ$ and $b$ via Thue–Morse Words
6. Load-Balancing Succinct B Trees
7. Sorted Range Reporting
8. Scalable Hash Table for NUMA Systems
9. Memory-Optimal Non-Blocking Queues

2021/3

1. Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
2. On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons
3. A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons
4. Dynamic Range Mode Enumeration
5. Compressed Communication Complexity of Hamming Distance
6. An Almost Optimal Edit Distance Oracle
7. A Fast and Small Subsampled R-index

2021/2

1. Efficient construction of the extended BWT from grammar-compressed DNA sequencing reads
2. Gapped Indexing for Consecutive Occurrences
3. Weighted Ancestors in Suffix Trees Revisited
4. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
5. Algorithms and Complexity on Indexing Founder Graphs
6. Conditional Lower Bounds for Variants of Dynamic LIS
7. Range Minimum Queries in Minimal Space
8. Linear Time Runs over General Ordered Alphabets
9. Which Regular Languages can be Efficiently Indexed?
10. Sorting Short Integers
11. All instantiations of the greedy algorithm for the shortest superstring problem are equivalent
12. Optimal Sorting Circuits for Short Keys

2021/1

1. Improving Run Length Encoding by Preprocessing
2. Strictly In-Place Algorithms for Permuting and Inverting Permutations
3. Cantor Mapping Technique
4. SetSketch: Filling the Gap between MinHash and HyperLogLog
5. Chunk List: Concurrent Data Structures
6. Text Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations
7. Binary Dynamic Time Warping in Linear Time
8. $r$-indexing Wheeler graphs
9. Deriving monadic quicksort (Declarative Pearl)
10. Entropy of Mersenne-Twisters
11. Number Parsing at a Gigabyte per Second
12. Spanner Evaluation over SLP-Compressed Documents
13. Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
14. Solving one variable word equations in the free group in cubic time
15. Algorithms and Hardness for Multidimensional Range Updates and Queries

2020

2020/12

1. Sorting Lists with Equal Keys Using Mergesort in Linear Time
2. Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring
3. The Parameterized Suffix Tray
4. Quantum Algorithm for Lexicographically Minimal String Rotation
5. A New Approach to Regular & Indeterminate Strings
6. Counting ternary square-free words quickly
7. Galloping in natural merge sorts
8. Huskysort
9. Integer Division by Constants: Optimal Bounds
10. Arithmetic Binary Search Trees: Static Optimality in the Matching Model
11. String Attractors for Automatic Sequences
12. SARS-CoV-2 Coronavirus Data Compression Benchmark
13. Learning Halfspaces With Membership Queries
14. Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs

2020/11

1. Erdös-Szekeres Partitioning Problem
2. Selectable Heaps and Optimal Lazy Search Trees
3. Improved Dynamic Algorithms for Longest Increasing Subsequence
4. Fully Dynamic Approximation of LIS in Polylogarithmic Time
5. Subpath Queries on Compressed Graphs: a Survey
6. The Longest Run Subsequence Problem: Further Complexity Results
7. A grammar compressor for collections of reads with applications to the construction of the BWT
8. Substring Query Complexity of String Reconstruction
9. PHONI: Streamed Matching Statistics with Multi-Genome References
10. Scout Algorithm For Fast Substring Matching
11. Left Lyndon tree construction
12. Grammar Compression By Induced Suffix Sorting
13. Searching and Sorting with O(n^2) processors in O(1) time
14. Competitive Data-Structure Dynamization

2020/10

1. Lazy Search Trees
2. Solving Shisen-Sho boards
3. Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
4. Contextual Pattern Matching
5. New Sublinear Algorithms and Lower Bounds for LIS Estimation
6. Decode efficient prefix codes
7. A Tale of Two Trees: New Analysis for AVL Tree and Binary Heap
8. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
9. Splay trees on trees
10. Generalized Sorting with Predictions
11. Dynamic Boundary Time Warping for Sub-sequence Matching with Few Examples
12. An Improved Sketching Algorithm for Edit Distance
13. Sorting Short Keys in Circuits of Size o(n log n)
14. Impossibility Results for Grammar-Compressed Linear Algebra

2020/9

1. TADOC: Text Analytics Directly on Compression
2. Longest Common Subsequence in Sublinear Space
3. Pushdown and Lempel-Ziv Depth
4. A Normal Sequence Compressed by PPM$^*$ but not by Lempel-Ziv 78
5. A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
6. Space efficient merging of de Bruijn graphs and Wheeler graphs
7. On prefix palindromic length of automatic words
8. Access-Adaptive Priority Search Tree
9. Zuckerli: A New Compressed Representation for Graphs
10. A Case for Partitioned Bloom Filters
11. Dynamic Similarity Search on Integer Sketches
12. Space/time-efficient RDF stores based on circular suffix sorting
13. On One-way Functions and Kolmogorov Complexity

2020/8

1. Tight Bound for the Number of Distinct Palindromes in a Tree
2. Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
3. Fast and Simple Modular Subset Sum
4. Cadences in Grammar-Compressed Strings
5. Soft Sequence Heaps
6. Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
7. A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings
8. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
9. Blocksequences of k-local Words

2020/7

1. The Edit Distance to $k$-Subsequence Universality
2. Substring Complexity in Sublinear Space
3. The Simplest Binary Word with Only Three Squares
4. On Indexing and Compressing Finite Automata
5. Update Query Time Trade-off for dynamic Suffix Arrays
6. Local Editing in LZ-End Compressed Data
7. String Indexing for Top-$k$ Close Consecutive Occurrences
8. Near-Linear Time Edit Distance for Indel Channels
9. A New Upper Bound for Separating Words
10. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
11. Optimal construction of a layer-ordered heap
12. Beyond the Worst-Case Analysis of Algorithms (Introduction)
13. A Big Data Approach for Sequences Indexing on the Cloud via Burrows Wheeler Transform
14. String Sanitization Under Edit Distance: Improved and Generalized
15. New Data Structures for Orthogonal Range Reporting and Range Minima Queries
16. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
17. A Simple Sublinear Algorithm for Gap Edit Distance
18. Internal Quasiperiod Queries
19. A linear-time parameterized algorithm for computing the width of a DAG

2020/6

1. A Fast Algorithm for Online k-servers Problem on Trees
2. Efficient tree-structured categorical retrieval
3. Dynamic Longest Common Substring in Polylogarithmic Time
4. Computing Palindromic Trees for a Sliding Window and Its Applications
5. LCP-Aware Parallel String Sorting
6. Random Access in Persistent Strings
7. Lyndon Words, the Three Squares Lemma, and Primitive Squares
8. Small Longest Tandem Scattered Subsequences
9. PFP Data Structures
10. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
11. Extremal overlap-free and extremal $β$-free binary words
12. Sumsets of Wythoff Sequences, Fibonacci Representation, and Beyond
13. Optimal-Time Queries on BWT-runs Compressed Indexes
14. Tailoring r-index for metagenomics
15. Efficient Semi-External Depth-First Search
16. The Number of Repetitions in 2D-Strings
17. Pattern Masking for Dictionary Matching
18. Analysis of Compression Techniques for DNA Sequence Data
19. Improved Circular $k$-Mismatch Sketches

2020/5

1. Edit Distance in Near-Linear Time: it’s a Constant Factor
2. Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
3. Efficient and Effective Query Auto-Completion
4. k-Approximate Quasiperiodicity under Hamming and Edit Distance
5. Counting Distinct Patterns in Internal Dictionary Matching
6. Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings
7. Palindromic Length of Words with Many Periodic Palindromes
8. Incremental Multiple Longest Common Sub-Sequences
9. On Weighted Prefix Normal Words
10. Quantum string comparison method
11. A reduction of the dynamic time warping distance to the longest increasing subsequence length
12. Linear Time Construction of Indexable Founder Block Graphs
13. On repetitiveness measures of Thue-Morse words
14. Towards Efficient Interactive Computation of Dynamic Time Warping Distance
15. Classical and Quantum Algorithms for Constructing Text from Dictionary Problem
16. Longest Square Subsequence Problem Revisited
17. On the improvement of the in-place merge algorithm parallelization
18. An inequality for the number of periods in a word
19. Succinct Trit-array Trie for Scalable Trajectory Similarity Search
20. Still Simpler Static Level Ancestors
21. Primitive Sets of Words
22. New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
23. The K-Centre Problem for Necklaces
24. A Dynamic Space-Efficient Filter with Constant Time Operations
25. Efficiently Testing Simon’s Congruence

2020/4

1. SOPanG 2: online searching over a pan-genome without false positives
2. Zipping Segment Trees
3. Indexing Highly Repetitive String Collections
4. Enumeration of LCP values, LCP intervals and Maximal repeats in BWT-runs Bounded Space
5. Grammar-Compressed Indexes with Logarithmic Search Time
6. On Locating Paths in Compressed Cardinal Trees
7. No Repetition: Fast Streaming with Highly Concentrated Hashing
8. In-Place Bijective Burrows-Wheeler Transforms
9. Faster Approximate Pattern Matching: A Unified Approach
10. Black-White Array: A New Data Structure for Dynamic Data Sets
11. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring
12. Lower Bound for Succinct Range Minimum Query
13. Grammar-compressed Self-index with Lyndon Words
14. Two halves of a meaningful text are statistically different
15. Pattern Discovery in Colored Strings
16. A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm
17. Storing Set Families More Compactly with Top ZDDs
18. Approximating longest common substring with $k$ mismatches: Theory and practice
19. The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
20. Efficient Constrained Pattern Mining Using Dynamic Item Ordering for Explainable Classification
21. The n-dimensional k-vector and its application to orthogonal range searching

2020/3

1. Multiset Synchronization with Counting Cuckoo Filters
2. Adaptive Fibonacci and Pairing Heaps
3. Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
4. Approximating Optimal Bidirectional Macro Schemes
5. Time-Space Tradeoffs for Finding a Long Common Substring
6. Concurrent Disjoint Set Union
7. An Efficient Implementation of Manacher’s Algorithm
8. Grammar compression with probabilistic context-free grammar
9. Approximating LCS in Linear Time: Beating the $\sqrt{n}$ Barrier
10. Four-Dimensional Dominance Range Reporting in Linear Space
11. Shorter Labels for Routing in Trees
12. Scattered Factor-Universality of Words
13. A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
14. Further Results on Colored Range Searching
15. Succinct Dynamic Ordered Sets with Random Access
16. Hidden Words Statistics for Large Patterns
17. Notes on Randomized Algorithms

2020/2

1. Approximating Text-to-Pattern Distance via Dimensionality Reduction
2. On Extensions of Maximal Repeats in Compressed Strings
3. Computing Covers under Substring Consistent Equivalence Relations
4. DAWGs for parameterized matching: online construction and related indexing structures
5. Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
6. Engineering Faster Sorters for Small Sets of Items
7. On Two Measures of Distance between Fully-Labelled Trees
8. On Rearrangement of Items Stored in Stacks
9. Uniform Linked Lists Contraction
10. Palindromic k-Factorization in Pure Linear Time
11. The Bloom Tree
12. 2-Dimensional Palindromes with $k$ Mismatches
13. Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
14. Bitvectors with runs and the successor/predecessor problem
15. Wheeler Languages
16. Compression with wildcards: All spanning trees
17. Chronofold: a data structure for versioned text
18. Compressed Data Structures for Binary Relations in Practice
19. Space Efficient Deterministic Approximation of String Measures
20. Translating Between Wavelet Tree and Wavelet Matrix Construction
21. Fast and linear-time string matching algorithms based on the distances of $q$-gram occurrences
22. Learning Directly from Grammar Compressed Text
23. Fast Indexes for Gapped Pattern Matching
24. Semantrix: A Compressed Semantic Matrix
25. Revisiting compact RDF stores based on k2-trees
26. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
27. Faster Binary Mean Computation Under Dynamic Time Warping

2020/1

1. Optimal Skeleton Huffman Trees Revisited
2. Fast Generation of Big Random Binary Trees
3. Simulation computation in grammar-compressed graphs
4. Age-Partitioned Bloom Filters
5. Data Structure Primitives on Persistent Memory: An Evaluation
6. Computing the rearrangement distance of natural genomes
7. Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
8. A Hybrid Approach to Temporal Pattern Matching
9. Approximating Text-to-Pattern Hamming Distances
10. Lossless Compression of Deep Neural Networks
11. Reconstructing Words from Right-Bounded-Block Words
12. Lengths of extremal square-free ternary words
13. On the binomial equivalence classes of finite words
14. Communication-Efficient String Sorting
15. $O(\log \log n)$ Worst-Case Local Decoding and Update Efficiency for Data Compression
16. Chaining with overlaps revisited
17. Generalised Pattern Matching Revisited
18. Faster STR-EC-LCS Computation
19. Optimally selecting the top $k$ values from $X+Y$ with layer-ordered heaps
20. Optimal Entropy Compression and Purification in Quantum Bits
21. Analysis and Evaluation of Non-Blocking Interpolation Search Trees

2019

2019/12

1. String factorisations with maximum or minimum dimension
2. Circ-Tree: A B+-Tree Variant with Circular Design for Persistent Memory
3. Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
4. New Bounds on Antipowers in Binary Words
5. Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
6. Gardens of Eden in the Game of Life
7. On the Reproducibility of Experiments of Indexing Repetitive Document Collections
8. Efficient processing of raster and vector data
9. The Weak Circular Repetition Threshold Over Large Alphabets
10. Flat combined Red Black Trees
11. Learning Multi-dimensional Indexes

2019/11

1. Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
2. An Efficient Word Lookup System by using Improved Trie Algorithm
3. Fast Multiple Pattern Cartesian Tree Matching
4. Counting Small Permutation Patterns
5. Nearly Optimal Static Las Vegas Succinct Dictionary
6. Optimal Adaptive Detection of Monotone Patterns
7. Edge minimization in de Bruijn graphs
8. In Search of the Fastest Concurrent Union-Find Algorithm
9. Enumerative Data Compression with Non-Uniquely Decodable Codes
10. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses
11. Space Efficient Construction of Lyndon Arrays in Linear Time
12. Dv2v: A Dynamic Variable-to-Variable Compressor
13. GraCT: A Grammar-based Compressed Index for Trajectory Data
14. Lock-Free Hopscotch Hashing
15. Towards Better Compressed Representations
16. On the Complexity of BWT-runs Minimization via Alphabet Reordering
17. On dynamic succinct graph representations
18. Listing Conflicting Triples in Optimal Time
19. Implementing the Topological Model Succinctly
20. Energy consumption in compact integer vectors: A study case
21. Faster Dynamic Compressed d-ary Relations
22. Grammar Compressed Sequences with Rank/Select Support
23. Extending General Compact Querieable Representations to GIS Applications
24. Improved Compressed String Dictionaries
25. Faster Integer Multiplication Using Preprocessing
26. Constructing the Bijective BWT
27. Words With Few Palindromes, Revisited
28. Words Avoiding Reversed Factors, Revisited
29. Fast Fibonacci heaps with worst case extensions
30. Faster Privacy-Preserving Computation of Edit Distance with Moves
31. SOSD: A Benchmark for Learned Indexes

2019/10

1. The PGM-index: a multicriteria, compressed and learned approach to data indexing
2. E2FM: an encrypted and compressed full-text index for collections of genomic sequences
3. LISA: Towards Learned DNA Sequence Search
4. Stack Sorting with Increasing and Decreasing Stacks
5. RAMBO: Repeated And Merged Bloom Filter for Multiple Set Membership Testing (MSMT) in Sub-linear time
6. Practical Random Access to Large SLP-Compressed Texts
7. It is high time we let go of the Mersenne Twister
8. Apply Sorting Algorithms to FAST Problem
9. RecSplit: Minimal Perfect Hashing via Recursive Splitting
10. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
11. Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms
12. Resolution of the Burrows-Wheeler Transform Conjecture
13. EvoZip: Efficient Compression of Large Collections of Evolutionary Trees
14. Engineering Top-Down Weight-Balanced Trees
15. Practical Repetition-Aware Grammar Compression
16. Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps
17. ALLSAT compressed with wildcards: Frequent Set Mining
18. Towards a Definitive Measure of Repetitiveness
19. ER-index: a referential index for encrypted genomic databases
20. Sublinear Algorithms for Gap Edit Distance
21. Approximating the Geometric Edit Distance
22. Superset Technique for Approximate Recovery in One-Bit Compressed Sensing
23. Finding monotone patterns in sublinear time

2019/9

1. Run-Length Encoding in a Finite Universe
2. Local Decode and Update for Big Data Compression
3. Generalized Dictionary Matching under Substring Consistent Equivalence Relations
4. Leyenda: An Adaptive, Hybrid Sorting Algorithm for Large Scale Data with Limited Memory
5. Weighted Shortest Common Supersequence Problem Revisited
6. Internal Dictionary Matching
7. String Indexing with Compressed Patterns
8. RECIPE : Converting Concurrent DRAM Indexes to Persistent-Memory Indexes
9. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
10. A New Deterministic Algorithm for Dynamic Set Cover
11. A Simple Reduction for Full-Permuted Pattern Matching Problems on Multi-Track Strings
12. An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping

2019/8

1. Engineering Faster Sorters for Small Sets of Items
2. Revisiting Consistent Hashing with Bounded Loads
3. When a Dollar Makes a BWT
4. Partial Sums on the Ultra-Wide Word RAM
5. Bloom filter variants for multiple sets: a comparative assessment
6. An Incompressibility Theorem for Automatic Complexity
7. Compacted binary trees admit a stretched exponential
8. Techniques for Inverted Index Compression
9. Parallel Finger Search Structures
10. The repetition threshold for binary rich words
11. Space-Efficient Construction of Compressed Suffix Trees
12. Beyond the Inverted Index
13. Fast Cartesian Tree Matching
14. Re-Pair In Small Space
15. On Occupancy Moments and Bloom Filter Efficiency
16. New Results on Nyldon Words Derived Using an Algorithm from Hall Set Theory
17. Efficient Online String Matching Based on Characters Distance Text Sampling
18. The smallest grammar problem revisited
19. Competitive Online Search Trees on Trees
20. Dynamic Optimality Refuted – For Tournament Heaps
21. On the cyclic regularities of strings
22. Matching reads to many genomes with the $r$-index
23. An Index for Sequencing Reads Based on The Colored de Bruijn Graph
24. Optimal Joins using Compact Data Structures

2019/7

1. Quantum Computing: Lecture Notes
2. Enumerating Range Modes
3. How to Store a Random Walk
4. Exhaustive Exact String Matching: The Analysis of the Full Human Genome
5. Minimal Absent Words in Rooted and Unrooted Trees
6. On Approximate Range Mode and Range Selection
7. Data Structures Meet Cryptography: 3SUM with Preprocessing
8. Finding First and Most-Beautiful Queens by Integer Programming
9. Succinct Representation for (Non)Deterministic Finite Automata
10. Optimal In-place Algorithms for Basic Graph Problems
11. Constant Delay Traversal of Grammar-Compressed Graphs with Bounded Rank
12. The Strong 3SUM-INDEXING Conjecture is False
13. Abelian-square factors and binary words
14. New Paths from Splay to Dynamic Optimality
15. Splaying Preorders and Postorders
16. Stack sorting with restricted stacks
17. Efficient computation of the Jacobi symbol
18. Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
19. Cache-Friendly Search Trees; or, In Which Everything Beats std::set
20. Circular Pattern Matching with $k$ Mismatches
21. The Alternating BWT: an algorithmic perspective
22. Bidirectional Text Compression in External Memory
23. Sparse Regular Expression Matching
24. String Attractors and Combinatorics on Words
25. $L_p$ Pattern Matching in a Stream
26. DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks
27. Improved local search for graph edit distance
28. On Slicing Sorted Integer Sequences

2019/6

1. Recurrence along directions in multidimensional words
2. Vector Programming Using Generative Recursion
3. On Longest Common Property Preserved Substring Queries
4. Loop Programming Practices that Simplify Quicksort Implementations
5. Dynamic Path-Decomposed Tries
6. Matching Patterns with Variables
7. Space Efficient Algorithms for Breadth-Depth Search
8. Indexing Graph Search Trees and Applications
9. Dynamic Palindrome Detection
10. Pseudo-solutions of word equations
11. Combinatorial Algorithms for String Sanitization
12. Survey of Information Encoding Techniques for DNA
13. Rpair: Rescaling RePair with Rsync
14. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
15. Characteristic Parameters and Special Trapezoidal Words
16. Every nonnegative real number is an abelian critical exponent
17. Borders, Palindrome Prefixes, and Square Prefixes
18. Sorted Top-k in Rounds
19. The Tandem Duplication Distance is NP-hard

2019/5

1. Separating many words by counting occurrences of factors
2. Prefix Block-Interchanges on Binary and Ternary Strings
3. Speeding up the Karatsuba algorithm
4. Memory lower bounds for deterministic self-stabilization
5. Cartesian Tree Matching and Indexing
6. A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets
7. On the Average Case of MergeInsertion
8. Inducing the Lyndon Array
9. Compact Data Structures for Shortest Unique Substring Queries
10. The Bloom Clock
11. Parallel decompression of gzip-compressed files and random access to DNA sequences
12. Fast hashing with Strong Concentration Bounds
13. Separate Chaining Meets Compact Hashing
14. Using Non-Linear Difference Equations to Study Quicksort Algorithms
15. RLE edit distance in near optimal time
16. Palindromic Ziv-Lempel and Crochemore Factorizations of $m$-Bonacci Infinite Words
17. Order-Preserving Pattern Matching Indeterminate Strings
18. Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
19. Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
20. Abelian periods of factors of Sturmian words
21. Constrained Orthogonal Segment Stabbing
22. Don’t Persist All : Efficient Persistent Data Structures
23. An invertible transform for efficient string matching in labeled digraphs

2019/4

1. Compact Fenwick trees for dynamic ranking and selection
2. The power word problem
3. About Fibonacci trees. I
4. Constant factor approximations to edit distance on far input pairs in nearly linear time
5. Constant-factor approximation of near-linear edit distance in near-linear time
6. What Storage Access Privacy is Achievable with Small Overhead?
7. Dynamic Packed Compact Tries Revisited
8. Compressed Indexes for Fast Search of Semantic Data
9. Repetitions in infinite palindrome-rich words
10. New results on pseudosquare avoidance
11. k-Spectra of weakly-c-Balanced Words
12. Proving tree algorithms for succinct data structures
13. String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
14. Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries
15. Heuristic algorithms for the Longest Filled Common Subsequence Problem
16. Reducing approximate Longest Common Subsequence to approximate Edit Distance
17. Convex Graph Invariant Relaxations For Graph Edit Distance

2019/3

1. Matching strings in encoded sequences
2. Data structures to represent sets of k-long DNA sequences
3. Multiplication method for factoring natural numbers
4. Shed More Light on Bloom Filter’s Variants
5. Determining satisfiability of 3-SAT in polynomial time
6. Algorithms to compute the Burrows-Wheeler Similarity Distribution
7. A New Lower Bound for Semigroup Orthogonal Range Searching
8. QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations
9. Belga B-trees
10. How far away must forced letters be so that squares are still avoidable?
11. The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time
12. Maximal State Complexity and Generalized de Bruijn Words
13. scaleBF: A High Scalable Membership Filter using 3D Bloom Filter
14. Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
15. The Parameterized Position Heap of a Trie
16. A Simple Solution to the Level-Ancestor Problem
17. Lempel-Ziv-like Parsing in Small Space
18. Lightweight merging of compressed indices based on BWT variants
19. Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
20. Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
21. Encoding 3SUM
22. The One-Way Communication Complexity of Dynamic Time Warping Distance

2019/2

1. On the Hardness and Inapproximability of Recognizing Wheeler Graphs
2. Faster and simpler algorithms for finding large patterns in permutations
3. Succinct Data Structures for Families of Interval Graphs
4. Padovan heaps
5. Fast Concurrent Data Sketches
6. Constructing Antidictionaries in Output-Sensitive Space
7. Conversion from RLBWT to LZ77
8. Space-Efficient Data Structures for Lattices
9. A New Class of Searchable and Provably Highly Compressible String Transformations
10. On long words avoiding Zimin patterns
11. Finite test sets for morphisms which are square-free on some of Thue’s square-free ternary words
12. A sub-quadratic algorithm for the longest common increasing subsequence problem
13. Fast, Small, and Simple Document Listing on Repetitive Text Collections
14. In oder Aus
15. On Greedy Algorithms for Binary de Bruijn Sequences
16. Regular Languages meet Prefix Sorting
17. Top Tree Compression of Tries
18. A fast algorithm for constructing balanced binary search trees
19. Space-efficient merging of succinct de Bruijn graphs
20. Faster Repetition-Aware Compressed Suffix Trees based on Block Trees
21. Balancing Straight-Line Programs
22. Set Cover in Sub-linear Time
23. On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching
24. Fast Sequence Segmentation using Log-Linear Models
25. Compressed Range Minimum Queries
26. An efficient sorting algorithm - Ultimate Heapsort(UHS)
27. An Extension of Linear-size Suffix Tries for Parameterized Strings

2019/1

1. Simulating the DNA String Graph in Succinct Space
2. Fully-functional bidirectional Burrows-Wheeler indexes
3. Online Algorithms for Constructing Linear-size Suffix Trie
4. A study for Image compression using Re-Pair algorithm
5. Faster queries for longest substring palindrome after block edit
6. Computing runs on a trie
7. Quasi-Linear-Time Algorithm for Longest Common Circular Factor
8. Longest Common Subsequence on Weighted Sequences
9. On Huang and Wong’s Algorithm for Generalized Binary Split Trees
10. Quotient Hash Tables - Efficiently Detecting Duplicates in Streaming Data
11. Unconstrained Church-Turing thesis cannot possibly be true
12. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
13. On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree
14. Dynamic Partition Bloom Filters: A Bounded False Positive Solution For Dynamic Set Membership (Extended Abstract)
15. Palindromic Subsequences in Finite Words
16. A randomized strategy in the mirror game
17. Learning Space Partitions for Nearest Neighbor Search
18. Mergeable Dictionaries With Shifts
19. Communication cost of consensus for nodes with limited memory
20. Multiple Set Matching and Pre-Filtering with Bloom Multifilters
21. An in-place, subquadratic algorithm for permutation inversion
22. A Compact Representation of Raster Time Series
23. Entropy Bounds for Grammar-Based Tree Compressors
24. Depth First Search in the Semi-streaming Model

2018

2018/12

1. Computing the $k$-binomial complexity of the Thue–Morse word
2. Lower bounds for text indexing with mismatches and differences
3. A Grammar-based Compressed Representation of 3D Trajectories
4. Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs
5. A Compact Representation for Trips over Networks built on self-indexes
6. ALLSAT compressed with wildcards: Partitionings and face-numbers of simplicial complexes
7. LZRR: LZ77 Parsing with Right Reference
8. Optimal Algorithm for Profiling Dynamic Arrays with Finite Values
9. Simple Concurrent Labeling Algorithms for Connected Components
10. Minuet: A method to solve Sudoku puzzles by hand
11. A Fast Combination of AES Encryption and LZ4 Compression Algorithms
12. Efficient Representation and Counting of Antipower Factors in Words
13. A Simple Algorithm for Computing the Document Array
14. Fast Breadth-First Search in Still Less Space
15. Locally Consistent Parsing for Text Indexing in Small Space
16. Improving Similarity Search with High-dimensional Locality-sensitive Hashing

2018/11

1. On Infinite Prefix Normal Words
2. DeepZip: Lossless Data Compression using Recurrent Neural Networks
3. Tunneling on Wheeler Graphs
4. The entropy of lies: playing twenty questions with a liar
5. Static Data Structure Lower Bounds Imply Rigidity
6. MR-RePair: Grammar Compression based on Maximal Repeats
7. Efficiently Approximating Edit Distance Between Pseudorandom Strings
8. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment
9. An optimized Parallel Failure-less Aho-Corasick algorithm for DNA sequence matching
10. Optimal-Time Dictionary-Compressed Indexes
11. Worst-Case Efficient Sorting with QuickMergesort
12. RePair in Compressed Space and Time
13. QuickXsort - A Fast Sorting Scheme in Theory and Practice
14. Compressed Multiple Pattern Matching
15. Multidimensional segment trees can do range queries and updates in logarithmic time
16. Optimal Rank and Select Queries on Dictionary-Compressed Text
17. Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
18. Vectorized Character Counting for Faster Pattern Matching

2018/10

1. MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
2. Distinct Sampling on Streaming Data with Near-Duplicates
3. Non-Empty Bins with Simple Tabulation Hashing
4. Fast and Longest Rollercoasters
5. Parallelism in Randomized Incremental Algorithms
6. Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity
7. Relative compression of trajectories
8. Nearly Optimal Space Efficient Algorithm for Depth First Search
9. Lower Bounds for Oblivious Data Structures
10. Sub-O(log n) Out-of-Order Sliding-Window Aggregation
11. Some comments on the structure of the best known networks sorting 16 elements
12. Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
13. Simple and Fast BlockQuicksort using Lomuto’s Partitioning Scheme
14. Sesquickselect: One and a half pivots for cache-efficient selection
15. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
16. Approximating Approximate Pattern Matching
17. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient
18. Weighted dynamic finger in binary search trees
19. Compound Binary Search Tree and Algorithms
20. Longest Property-Preserved Common Factor
21. Randen - fast backtracking-resistant random generator with AES+Feistel+Reverie
22. Approximate Online Pattern Matching in Sub-linear Time
23. On the discrepancy of random low degree set systems
24. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

2018/9

1. Streaming dictionary matching with mismatches
2. Multi-finger binary search trees
3. Massively Parallel Dynamic Programming on Trees
4. Approximate Query Processing over Static Sets and Sliding Windows
5. Calculation of extended gcd by normalization
6. Encoding two-dimensional range top-k queries revisited
7. Relaxing Wheeler Graphs for Indexing Reads
8. Small Uncolored and Colored Choice Dictionaries
9. Adaptive Shivers Sort: An Alternative Sorting Algorithm
10. Collapsing Superstring Conjecture
11. Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra
12. Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space

2018/8

1. List Decoding with Double Samplers
2. Finding a Small Number of Colourful Components
3. Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms
4. Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools
5. Right-to-left online construction of parameterized position heaps
6. Dynamic all scores matrices for LCS score
7. Longest Increasing Subsequence under Persistent Comparison Errors
8. Local Decodability of the Burrows-Wheeler Transform
9. The effective entropy of next/previous larger/smaller value queries
10. Cardinality Estimators do not Preserve Privacy
11. On the tails of the limiting QuickSort density

2018/7

1. Enumerating Cryptarithms Using Deterministic Finite Automata
2. Improved Time and Space Bounds for Dynamic Range Mode
3. Push-Down Trees: Optimal Self-Adjusting Complete Trees
4. Know When to Fold ‘Em: Self-Assembly of Shapes by Folding in Oritatami
5. A Simple and Space Efficient Segment Tree Implementation
6. Using statistical encoding to achieve tree succinctness never seen before
7. The colored longest common prefix array computed via sequential scans
8. Two Algorithms to Find Primes in Patterns
9. Faster Recovery of Approximate Periods over Edit Distance
10. Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model
11. Optimal Ball Recycling
12. Efficient Computation of Sequence Mappability

2018/6

1. Enhanced string factoring from alphabet orderings
2. Zip Trees
3. A Faster External Memory Priority Queue with DecreaseKeys
4. Improved bounds for multipass pairing heaps and path-balanced binary search trees
5. Fast entropy-bounded string dictionary look-up with mismatches
6. Dynamic Trees with Almost-Optimal Access Cost
7. BDDs Naturally Represent Boolean Functions, and ZDDs Naturally Represent Sets of Sets
8. Practical Access to Dynamic Programming on Tree Decompositions
9. Approximate Nearest Neighbors in Limited Space
10. Efficient Genomic Interval Queries Using Augmented Range Trees
11. Fast Locality Sensitive Hashing for Beam Search on GPU
12. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
13. Tree Path Majority Data Structures
14. Another Proof of Cuckoo hashing with New Variants
15. Alignment-free sequence comparison using absent words
16. Compressed Communication Complexity of Longest Common Prefixes
17. CuCoTrack: Cuckoo Filter Based Connection Tracking
18. Indexed Dynamic Programming to boost Edit Distance and LCSS Computation
19. $O(n \log n)$-time text compression by LZ-style longest first substitution
20. Block Palindromes: A New Generalization of Palindromes

2018/5

1. On the Worst-Case Complexity of TimSort
2. Orthogonal Point Location and Rectangle Stabbing Queries in 3-d
3. copMEM: Finding maximal exact matches via sampling both genomes
4. Optimal Hashing in External Memory
5. Strong link between BWT and XBW via Aho-Corasick automaton and applications to Run-Length Encoding
6. Algorithms for Anti-Powers in Strings
7. Longest Unbordered Factor in Quasilinear Time
8. Succinct data structure for dynamic trees with faster queries
9. Space-Efficient DFS and Applications: Simpler, Leaner, Faster
10. Haplotype-aware graph indexes
11. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
12. An $O(N)$ Sorting Algorithm: Machine Learning Sort
13. Beating Fredman-Komlós for perfect $k$-hashing
14. Assembling Omnitigs using Hidden-Order de Bruijn Graphs
15. Parallel Working-Set Search Structures
16. Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
17. On Computing Average Common Substring Over Run Length Encoded Sequences
18. External memory BWT and LCP computation for sequence collections with applications
19. Revisiting the tree edit distance and its backtracing: A tutorial
20. On improving the approximation ratio of the r-shortest common superstring problem
21. Detecting Mutations by eBWT
22. Wormhole: A Fast Ordered Index for In-memory Data Management
23. Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables
24. Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time

2018/4

1. Longest Common Substring Made Fully Dynamic
2. Succinct Oblivious RAM
3. Entropy bounds for grammar compression
4. Edit Distance between Unrooted Trees in Cubic Time
5. QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
6. On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
7. Graph Pattern Matching Preserving Label-Repetition Constraints
8. Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
9. Fast Prefix Search in Little Space, with Applications
10. Optimizing Bloom Filter: Challenges, Solutions, and Comparisons
11. Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
12. A Weighted Generalization of the Graham-Diaconis Inequality for Ranked List Similarity
13. Design and Implementation of Dynamic Memory Management in a Reversible Object-Oriented Programming Language
14. k-Maximum Subarrays for Small k: Divide-and-Conquer made simpler
15. On Abelian Longest Common Factor with and without RLE
16. Optimal Sorting with Persistent Comparison Errors
17. On Undetected Redundancy in the Burrows-Wheeler Transform
18. Optimal streaming and tracking distinct elements with high probability
19. Red-Black Trees with Constant Update Time
20. From Regular Expression Matching to Parsing
21. Optimal Document Exchange and New Codes for Insertions and Deletions
22. Restructuring expression dags for efficient parallelization
23. Dualities in Tree Representations
24. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018/3

1. Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
2. Prefix-Free Parsing for Building Big BWTs
3. On the Diameter of Tree Associahedra
4. Optimal Substring-Equality Queries with Applications to Sparse Text Indexing
5. String Attractors: Verification and Optimization
6. Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
7. Parallel Range, Segment and Rectangle Queries with Augmented Maps
8. On the Approximation Ratio of Ordered Parsings
9. Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
10. Universal Compressed Text Indexing
11. Linear-Time In-Place DFS and BFS on the Word RAM
12. Average Cost of QuickXsort with Pivot Sampling
13. Twelve Simple Algorithms to Compute Fibonacci Numbers
14. Two-Dimensional Block Trees
15. Compact Representations of Event Sequences
16. Flexible and Efficient Algorithms for Abelian Matching in Strings
17. Multivariate Fine-Grained Complexity of Longest Common Subsequence
18. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve

2018/2

1. Decompressing Lempel-Ziv Compressed Text
2. Refining the $r$-index
3. Improved Upper Bounds on all Maximal $α$-gapped Repeats and Palindromes
4. Linear-Time Algorithm for Long LCF with $k$ Mismatches
5. Upper and lower bounds for dynamic data structures on strings
6. Periodicity in Data Streams with Wildcards
7. Smooth heaps and a dual view of self-adjusting data structures
8. Grammar-based Compression of Unranked Trees
9. Synchronization Strings: List Decoding for Insertions and Deletions

2018/1

1. String Periods in the Order-Preserving Model
2. On Periodicity Lemma for Partial Words
3. Longest Common Prefixes with $k$-Errors and Applications
4. Sliding Suffix Tree using LCA
5. Generalized Leapfrogging Samplesort: A Class of $O(n \log^2 n)$ Worst-Case Complexity and $O(n \log n)$ Average-Case Complexity Sorting Algorithms
6. Faster Approximate(d) Text-to-Pattern L1 Distance
7. Strategies for Stable Merge Sorting

2017

2017/12

1. Optimal Construction of Compressed Indexes for Highly Repetitive Texts
2. Text Indexing and Searching in Sublinear Time
3. Longest common substring with approximately $k$ mismatches
4. Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space
5. Cartesian trees and Lyndon trees
6. Bubble-Flip—A New Generation Algorithm for Prefix Normal Words
7. Optimal top dag compression
8. B-slack trees: Highly Space Efficient B-trees
9. The Case for Learned Index Structures
10. On the Decision Tree Complexity of String Matching
11. Space-Efficient Algorithms for Longest Increasing Subsequence

2017/11

1. Compressed Indexing with Signature Grammars
2. A Separation Between Run-Length SLPs and LZ77
3. A compressed dynamic self-index for highly repetitive text collections
4. Fast Dynamic Arrays
5. Run Compressed Rank/Select for Large Alphabets
6. Faster range minimum queries
7. The Hidden Binary Search Tree:A Balanced Rotation-Free Search Tree in the AVL RAM Model
8. A Grammar Compression Algorithm based on Induced Suffix Sorting
9. Bloom Filters, Adaptivity, and the Dictionary Problem
10. Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index

2017/10

1. At the Roots of Dictionary Compression: String Attractors
2. Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
3. Dismantling DivSufSort
4. Lyndon Array Construction during Burrows-Wheeler Inversion
5. Efficient Compression and Indexing of Trajectories
6. Improved Bounds for Testing Forbidden Order Patterns
7. Exact Mean Computation in Dynamic Time Warping Spaces
8. HyperMinHash: MinHash in LogLog space
9. Twin Sort Technique
10. Probabilistic Analysis of the Dual-Pivot Quicksort “Count”
11. Ordered Dags: HypercubeSort
12. Orthogonal Vectors Indexing

2017/9

1. String Attractors
2. In-Place Initializable Arrays
3. On-the-Fly Array Initialization in Less Space
4. Fast Computation of Graph Edit Distance
5. Whole Genome Phylogenetic Tree Reconstruction Using Colored de Bruijn Graphs

2017/8

1. Distinct Squares in Circular Words
2. The streaming $k$-mismatch problem
3. Comparison of LZ77-type Parsings
4. Exploiting Computation-Friendly Graph Compression Methods
5. Streaming Periodicity with Mismatches
6. Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform

2017/7

1. Document Listing on Repetitive Collections with Guaranteed Performance
2. Relations Between Greedy and Bit-Optimal LZ77 Encodings
3. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy
4. A succinct data structure for self-indexing ternary relations
5. Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
6. Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
7. Improved bounds for testing Dyck languages
8. Fast Label Extraction in the CDAWG
9. Persistent Cache-oblivious Streaming Indexes
10. Greedy Shortest Common Superstring Approximation in Compact Space
11. The Compressed Overlap Index
12. Compressed Representation of Dynamic Binary Relations with Applications
13. Biased Predecessor Search
14. Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product

2017/6

1. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
2. Order preserving pattern matching on trees and DAGs
3. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
4. Compaction of Church Numerals for Higher-Order Compression
5. The complexity of the Multiple Pattern Matching Problem for random strings
6. On-line Assembling Mitochondrial DNA from de novo transcriptome
7. New Cardinality Estimation Methods for HyperLogLog Sketches
8. Faster batched range minimum queries

2017/5

1. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
2. Optimal-Time Text Indexing in BWT-runs Bounded Space
3. Linear-size CDAWG: new repetition-aware indexing and grammar compression
4. Near-optimal linear decision trees for k-SUM and related problems
5. Succinct Partial Sums and Fenwick Trees
6. How to answer a small batch of RMQs or LCA queries in practice
7. Faster algorithms for 1-mappability of a sequence
8. Optimal Computation of Overabundant Words
9. Representing the suffix tree with the CDAWG
10. Inverse Lyndon words and Inverse Lyndon factorizations of words
11. Multiresolution Priority Queues
12. New Variants of Pattern Matching with Constants and Variables
13. Duel and sweep algorithm for order-preserving pattern matching
14. Assembling sequences of DNA using an on-line algorithm based on DeBruijn graphs
15. Improved Average Complexity for Comparison-Based Sorting

2017/4

1. Practical and Effective Re-Pair Compression
2. A Faster Implementation of Online Run-Length Burrows-Wheeler Transform
3. Optimal trade-offs for pattern matching with $k$ mismatches
4. m-Bonsai: a Practical Compact Dynamic Trie
5. Indexing Weighted Sequences: Neat and Efficient
6. Grammar-Based Graph Compression
7. FMtree: A fast locating algorithm of FM-indexes for genomic data
8. Maximal Unbordered Factors of Random Strings
9. Hybridizing Non-dominated Sorting Algorithms: Divide-and-Conquer Meets Best Order Sort
10. Streaming Pattern Matching with d Wildcards
11. Succinct Approximate Rank Queries
12. Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching

2017/3

1. Faster STR-IC-LCS computation via RLE
2. Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets
3. Palindromic Decompositions with Gaps and Errors
4. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
5. Near-Optimal Compression for the Planar Graph Metric
6. Reoptimization of the Closest Substring Problem under Pattern Length Modification
7. Approximation ratio of RePair
8. Space-efficient K-MER algorithm for generalized suffix tree
9. Faster truncated integer multiplication
10. Even faster sorting of (not only) integers

2017/2

1. Compression with the tudocomp Framework
2. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back
3. Small-space encoding LCE data structure with constant-time queries
4. Simple, Fast and Lightweight Parallel Wavelet Tree Construction
5. Fast and Simple Jumbled Indexing for Binary RLE Strings
6. Trie Compression for GPU Accelerated Multi-Pattern Matching
7. A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem
8. Position Heaps for Parameterized Strings
9. A local search 2.917-approximation algorithm for duo-preservation string mapping
10. New cardinality estimation algorithms for HyperLogLog sketches

2017/1

1. Computing Abelian regularities on RLE strings
2. A Framework of Dynamic Data Structures for String Processing

2016

2016/12

1. A hardness result and new algorithm for the longest common palindromic subsequence problem
2. Deterministic Indexing for Packed Strings
3. Efficient Representation of Multidimensional Data over Hierarchical Domains
4. GraCT: A Grammar based Compressed representation of Trajectories
5. Monte Carlo Sort for unreliable human comparisons
6. Oblivious Sorting and Queues

2016/11

1. Space-Efficient Re-Pair Compression
2. LZ-End Parsing in Compressed Space
3. Burrows-Wheeler transform and LCP array construction in constant space
4. Compressed Dynamic Range Majority and Minority Data Structures
5. On the Size of Lempel-Ziv and Lyndon Factorizations
6. Longest Common Extensions with Recompression
7. Tight Lower Bounds for the Longest Common Extension Problem
8. Twenty (simple) questions
9. A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs
10. Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
11. Optimizing run-length algorithm using octonary repetition tree

2016/10

1. Computing All Distinct Squares in Linear Time for Integer Alphabets
2. Engineering a Distributed Full-Text Index
3. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
4. Efficient Pattern Matching in Elastic-Degenerate Strings
5. String Cadences
6. An Encoding for Order-Preserving Matching
7. Sort well with energy-constrained comparisons
8. Optimal In-Place Suffix Sorting
9. Scalable Construction of Text Indexes
10. Comments on Dumitrescu’s “A Selectable Sloppy Heap”

2016/9

1. Practical Data Compression for Modern Memory Hierarchies
2. Tight bounds on the maximum number of shortest unique substrings
3. Longest Common Subsequence in at Least $k$ Length Order-Isomorphic Substrings
4. Efficient computation of longest single-arm-gapped palindromes in a string
5. From H&M to Gap for Lightweight BWT Merging
6. Linear-time string indexing and analysis in small space
7. Sort Race
8. Succinct data-structure for nearest colored node in a tree
9. The Generalized Smallest Grammar Problem

2016/8

1. Shortest unique palindromic substring queries in optimal time
2. In-Place Sparse Suffix Sorting
3. Sparse Suffix Tree Construction in Optimal Time and Space
4. Hardness of Permutation Pattern Matching
5. A family of fast exact pattern matching algorithms
6. Quicksort Is Optimal For Many Equal Keys
7. Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

2016/7

1. Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
2. Fast Longest Common Extensions in Small Space
3. Online Grammar Compression for Frequent Pattern Discovery
4. Streaming k-mismatch with error correcting and applications
5. Fully Dynamic de Bruijn Graphs
6. Edit Distance: Sketching, Streaming and Document Exchange
7. A New Lightweight Algorithm to compute the BWT and the LCP array of a Set of Strings
8. Suffix arrays with a twist
9. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
10. Multi-view pattern matching
11. Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
12. An Optimal Algorithm for Range Search on Multidimensional Points
13. Representing Pattern Matching Algorithms by Polynomial-Size Automata

2016/6

1. A Self-Index on Block Trees
2. Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices
3. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
4. String Inference from the LCP Array
5. A Compact Index for Order-Preserving Pattern Matching
6. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
7. Range Majorities and Minorities in Arrays
8. Improved Space efficient linear time algorithms for BFS, DFS and applications
9. Randomized Ternary Search Tries
10. Two-stage algorithms for covering array construction
11. A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

2016/5

1. Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes
2. Dynamic index and LZ factorization in compressed space
3. Fully dynamic data structure for LCE queries in compressed space
4. Document Retrieval on Repetitive String Collections
5. RLZAP: Relative Lempel-Ziv with Adaptive Pointers
6. Rank and select: Another lesson learned
7. Algorithms to Compute the Lyndon Array
8. Energy-Efficient Algorithms
9. CSA++: Fast Pattern Search for Large Alphabets
10. Games from Basic Data Structures
11. Variance of the Internal Profile in Suffix Trees
12. Lightweight LCP Construction for Very Large Collections of Strings
13. Average Size of a Suffix Tree for Markov Sources
14. Asymmetric Rényi Problem and PATRICIA Tries

2016/4

1. Universal Indexes for Highly Repetitive Document Collections
2. Practical combinations of repetition-aware data structures
3. Detecting One-variable Patterns
4. Optimal Computation of Avoided Words
5. Designing optimal- and fast-on-average pattern matching algorithms
6. Data Structure Lower Bounds for Document Indexing Problems
7. Succinct Choice Dictionaries
8. Efficient Index Maintenance Under Dynamic Genome Modification
9. Computing Longest Increasing Subsequence Over Sequential Data Streams
10. GateKeeper: A New Hardware Architecture for Accelerating Pre-Alignment in DNA Short Read Mapping
11. New Error Tolerant Method to Search Long Repeats in Symbol Sequences
12. An Estimation of the Size of Non-Compact Suffix Trees

2016/3

1. Aggregated 2D Range Queries on Clustered Points
2. Parameterized Pattern Matching – Succinctly
3. The landscape of bounds for binary search trees
4. Encoding Arguments

2016/2

1. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
2. Efficient Index for Weighted Sequences
3. Faster Longest Common Extension Queries in Strings over General Alphabets
4. Approximate Hamming distance in a stream
5. siEDM: an efficient string index and search algorithm for edit distance with moves
6. Lempel-Ziv Decoding in External Memory
7. Compressing Graphs and Indexes with Recursive Graph Bisection
8. Access Time Tradeoffs in Archive Compression
9. A loopless and branchless $O(1)$ algorithm to generate the next Dyck word
10. Distortion-Resistant Hashing for rapid search of similar DNA subsequence
11. TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes
12. On the circuit complexity of the standard and the Karatsuba methods of multiplying integers
13. On pattern matching with k mismatches and few don’t cares

2016/1

1. Pachinko
2. Deterministic sub-linear space LCE data structures with efficient construction
3. Simple and Efficient Fully-Functional Succinct Trees
4. Optimal Prefix Free Codes With Partial Sorting
5. Minimal Suffix and Rotation of a Substring in Optimal Time
6. Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array
7. The complexity of bit retrieval

2015

2015/12

1. Fast Average-Case Pattern Matching on Weighted Sequences
2. A Quadratic Assignment Formulation of the Graph Edit Distance
3. A Fast Heuristic for Exact String Matching

2015/11

1. Burrows-Wheeler transform for terabases
2. Longest Gapped Repeats and Palindromes
3. Optimal Dynamic Strings
4. Efficient Deterministic Single Round Document Exchange for Edit Distance
5. Word Existence Algorithm
6. On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
7. A Study on Splay Trees
8. Traversing Grammar-Compressed Trees with Constant Delay

2015/10

1. Computing LZ77 in Run-Compressed Space
2. Efficiently Finding All Maximal $α$-gapped Repeats
3. Lempel-Ziv Computation In Compressed Space (LZ-CICS)
4. Subsequence Automata with Default Transitions
5. How Good is Multi-Pivot Quicksort?
6. Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
7. Layered Heaps Beating Standard and Fibonacci Heaps in Practice
8. A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
9. Fast Algorithms for Exact String Matching
10. Permutations sortable by two stacks in series
11. Multiple sequence alignment for short sequences
12. The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

2015/9

1. Deterministic Sparse Suffix Sorting in the Restore Model
2. Finding the Leftmost Critical Factorization on Unordered Alphabet
3. Testing k-binomial equivalence
4. Communication Complexity (for Algorithm Designers)
5. Parallel Query in the Suffix Tree
6. Lower bounds for approximation schemes for Closest String
7. Probabilistic Threshold Indexing for Uncertain Strings
8. Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations
9. External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates
10. Practical Concurrent Priority Queues
11. Dynamic concurrent van Emde Boas array

2015/8

1. Relative Suffix Trees
2. Space-efficient detection of unusual words
3. The k-mismatch problem revisited
4. Full-text and Keyword Indexes for String Searching
5. A Practical O(R\log\log n+n) time Algorithm for Computing the Longest Common Subsequence

2015/7

1. Range Predecessor and Lempel-Ziv Parsing
2. Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
3. Finger Search in Grammar-Compressed Strings
4. Compressed Data Structures for Dynamic Sequences
5. Computing Runs on a General Alphabet
6. Online Self-Indexed Grammar Compression
7. A numerical analysis of Quicksort: How many cases are bad cases?
8. A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays
9. Pattern-avoiding access in binary search trees
10. A Bloom filter based semi-index on $q$-grams

2015/6

1. Relative Select
2. Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
3. Fast Computation of Abelian Runs
4. Linear Algorithms for Computing the Lyndon Border Array and the Lyndon Suffix Array
5. Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables
6. FM-index for dummies
7. Linear Algorithm for Conservative Degenerate Pattern Matching
8. Error Tree: A Tree Structure for Hamming & Edit Distances & Wildcards Matching
9. Tree Compression with Top Trees Revisited
10. Amortized Rotation Cost in AVL Trees
11. Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers

2015/5

1. Optimal Search Trees with 2-Way Comparisons
2. Linear-Time Superbubble Identification Algorithm for Genome Assembly
3. Triple State QuickSort, A replacement for the C/C++ library qsort
4. Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
5. Read Mapping on de Bruijn graph
6. An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints
7. An Efficient Dynamic Programming Algorithm for STR-IC-SEQ-EC-LCS Problem
8. Fast and Powerful Hashing using Tabulation
9. Implementation of BT-trees

2015/4

1. Faster Lightweight Lempel-Ziv Parsing
2. Approximating LZ77 via Small-Space Multiple-Pattern Matching
3. Dynamic index, LZ factorization, and LCE queries in compressed space
4. Lempel Ziv Computation In Small Space (LZ-CISS)
5. Longest Common Extensions in Sublinear Space
6. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
7. On Maximal Unbordered Factors
8. Dictionary matching in a stream
9. Tree compression using string grammars
10. The complexity of computation in bit streams

2015/3

1. Approximating LZ77 in Small Space
2. Diverse Palindromic Factorization is NP-Complete
3. Mind the Gap
4. Dynamic Data Structures for Document Collections and Graphs
5. Binary Coding in Stream
6. A note on the longest common Abelian factor problem
7. Dual pivot Quicksort

2015/2

1. Composite repetition-aware data structures
2. A Compressed-Gap Data-Aware Measure
3. A framework for space-efficient string kernels
4. Algorithms for Longest Common Abelian Factors
5. Compressed Tree Canonization
6. Adaptive Search over Sorted Sets
7. Parameterized Complexity of Superstring Problems
8. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

2015/1

1. Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets
2. On Longest Repeat Queries
3. Mespotine-RLE-basic v0.9 - An overhead-reduced and improved Run-Length-Encoding Method
4. Efficient Algorithms for the Order Preserving Pattern Matching Problem
5. Online Computation of Abelian Runs
6. A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms
7. Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
8. On The Average-Case Complexity of Shellsort

2014

2014/12

1. Queries on LZ-Bounded Encodings
2. Longest Common Extensions in Trees
3. Searching and Indexing Genomic Databases via Kernelization
4. Online Detection of Repetitions with Backtracking
5. Run-Length Encoded Nondeterministic KMP and Suffix Automata
6. Covering Problems for Partial Words and for Indeterminate Strings
7. Computing Covers Using Prefix Tables
8. Simple Balanced Binary Search Trees
9. Compression of high throughput sequencing data with probabilistic de Bruijn graph
10. Fewer runs than word length
11. Pattern Matching and Local Alignment for RNA Structures

2014/11

1. Variable-Order de Bruijn Graphs
2. Faster Compressed Quadtrees
3. Online Square Detection
4. Optimal Encodings for Range Top-k, Selection, and Min-Max
5. PivotCompress: Compression by Sorting
6. Analysis of Branch Misses in Quicksort
7. Towards Tight Lower Bounds for Range Reporting on the RAM
8. Fusion Tree Sorting
9. Analysis of Pivot Sampling in Dual-Pivot Quicksort
10. Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems
11. Algorithms in the Ultra-Wide Word Model

2014/10

1. Efficient and Compact Representations of Prefix Codes
2. Encodings of Range Maximum-Sum Segment Queries and Applications
3. A massively parallel algorithm for constructing the BWT of large string sets
4. Practical Massively Parallel Sorting
5. Tight tradeoffs for approximating palindromes in streams
6. Building a Balanced k-d Tree in O(kn log n) Time
7. Optimal Time Random Access to Grammar-Compressed Strings in Small Space
8. Faster Sorting Networks for $17$, $19$ and $20$ Inputs

2014/9

1. Document Counting in Practice
2. Lempel-Ziv Factorization May Be Harder Than Computing All Runs
3. Approximating solution structure of the Weighted Sentence Alignment problem
4. Path algebra algorithm for finding longest increasing subsequence
5. A Parameterized Study of Maximum Generalized Pattern Matching Problems
6. Longest common substrings with k mismatches

2014/8

1. Wavelet Trees Meet Suffix Trees
2. Strong inapproximability of the shortest reset word
3. Rank, select and access in grammar-compressed strings
4. Online Pattern Matching for String Edit Distance with Moves
5. Dictionary Matching with One Gap
6. Analysis of String Sorting using Heapsort
7. Quantum pattern matching fast on average

2014/7

1. Suffix Arrays for Spaced-SNP Databases
2. Sublinear Space Algorithms for the Longest Common Substring Problem
3. Fibonacci Heaps Revisited
4. Constructing small tree grammars and small circuits for formulas
5. $LCSk$++: Practical similarity metric for long strings
6. On the Average-case Complexity of Pattern Matching with Wildcards
7. Parallel Wavelet Tree Construction
8. A note on multipivot Quicksort
9. GCD Computation of n Integers

2014/6

1. The “Runs” Theorem
2. Weighted ancestors in suffix trees
3. Linear-time Computation of Minimal Absent Words Using Suffix Array
4. Average-Case Optimal Approximate Circular String Matching
5. How inefficient can a sort algorithm be?
6. Fast construction of FM-index for long sequence reads
7. Compact Indexes for Flexible Top-k Retrieval
8. A note on the largest number of red nodes in red-black trees
9. Multilevel polynomial partitions and simplified range searching
10. Sampling the suffix array with minimizers
11. ARC Sort: Enhanced and Time Efficient Sorting Algorithm
12. Kernelization lower bound for Permutation Pattern Matching

2014/5

1. Efficient Compressed Wavelet Trees over Large Alphabets
2. On Hardness of Jumbled Indexing
3. Alternative Algorithms for Lyndon Factorization
4. Introduction to Dynamic Unary Encoding
5. An External-Memory Algorithm for String Graph Construction
6. Disk-based genome sequencing data compression
7. Two simple full-text indexes based on the suffix array
8. Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
9. Compressive Mining: Fast and Optimal Data Mining in the Compressed Domain
10. Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
11. The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm
12. Multiple pattern matching revisited

2014/4

1. Reusing an FM-index
2. Optimal Encodings for Range Majority Queries
3. Document Retrieval on Repetitive Collections
4. Improved ESP-index: a practical self-index for highly repetitive texts
5. Combining pattern-based CRFs and weighted context-free grammars
6. Normal, Abby Normal, Prefix Normal

2014/3

1. A really simple approximation of smallest grammar
2. Compressed Subsequence Matching and Packed Tree Coloring
3. A Subquadratic Algorithm for Minimum Palindromic Factorization
4. A Suffix Tree Or Not A Suffix Tree?
5. Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time
6. String Reconstruction from Substring Compositions
7. Engineering Parallel String Sorting
8. Efficient Representation for Online Suffix Tree Construction
9. Most Recent Match Queries in On-Line Suffix Trees (with appendix)

2014/2

1. Longest Common Subsequence in k-length substrings
2. Static Level Ancestors in Practice
3. Dynamic Partial Sorting
4. Data Compaction - Compression without Decompression
5. How Fast Can We Multiply Large Integers on an Actual Computer?
6. Integer Set Compression and Statistical Modeling

2014/1

1. Linear time construction of compressed text indices in compact space
2. Fast Algorithm for Partial Covers in Words
3. Space-Efficient String Indexing for Wildcard Pattern Matching
4. Fully Online Grammar Compression in Constant Space
5. Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
6. A Comparative Study on String Matching Algorithm of Biological Sequences
7. GPU-Accelerated BWT Construction for Large Collection of Short Reads
8. A Fast String Matching Algorithm Based on Lowlight Characters in the Pattern
9. On Combinatorial Generation of Prefix Normal Words
10. On the representation of de Bruijn graphs

2013

2013/12

1. Compressed Spaced Suffix Arrays
2. Simple, compact and robust approximate string dictionary
3. Succinct representation of labeled trees
4. A Functional Approach to Standard Binary Heaps
5. Near-optimal labeling schemes for nearest common ancestors
6. Shortest Unique Substring Query Revisited
7. A Note on the Longest Common Compatible Prefix Problem for Partial Words
8. RAM-Efficient External Memory Sorting

2013/11

1. Encoding Range Minimum Queries
2. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays
3. Efficient algorithms for the longest common subsequence in $k$-length substrings
4. Efficiently Computing Edit Distance to Dyck Language
5. Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
6. From Theory to Practice: Plug and Play with Succinct Data Structures
7. Internal Pattern Matching Queries in a Text and Applications

2013/10

1. Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets
2. Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression
3. Approximate String Matching using a Bidirectional Index
4. Dynamic Gomory-Hu Tree Construction – fast and simple

2013/9

1. Order-preserving pattern matching with k mismatches
2. Substring Suffix Selection
3. The Swap Matching Problem Revisited
4. TRANS outperforms MTF for two special types of request sequences without locality of reference
5. O-notation in algorithm analysis
6. The Dynamic Longest Increasing Subsequence Problem
7. XML Compression via DAGs
8. Approximation of smallest linear tree grammar

2013/8

1. Beating O(nm) in approximate LZW-compressed pattern matching
2. ELB-Trees, An Efficient and Lock-free B-tree Derivative
3. Sublinear Matching With Finite Automata Using Reverse Suffix Scanning
4. Sorted Range Reporting Revisited
5. Estimating the longest increasing sequence in polylogarithmic time
6. Data Structures in Classical and Quantum Computing

2013/7

1. Lempel-Ziv Parsing in External Memory
2. AliBI: An Alignment-Based Index for Genomic Datasets
3. Optimal Top-k Document Retrieval
4. Bicriteria data compression
5. First-Come-First-Served for Online Slot Allocation and Huffman Coding
6. Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead
7. Finding small patterns in permutations in linear time
8. QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average
9. The technique of in-place associative sorting
10. Complexity of the FIFO Stack-Up Problem
11. Compressed Pattern-Matching with Ranked Variables in Zimin Words
12. An Elegant Algorithm for the Construction of Suffix Arrays
13. On string matching with k mismatches
14. Domain Specific Hierarchical Huffman Encoding
15. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications

2013/6

1. Hybrid Indexes for Repetitive Datasets
2. Succinct data structures for representing equivalence classes
3. Optimal Color Range Reporting in One Dimension
4. On a compact encoding of the swap automaton
5. Parallel Algorithm for Longest Common Subsequence in a String
6. Minimal Indices for Successor Search
7. Set-Difference Range Queries
8. Motif matching using gapped patterns
9. Sorting suffixes of a text via its Lyndon Factorization
10. Orthogonal Range Searching for Text Indexing

2013/5

1. Faster Compact On-Line Lempel-Ziv Factorization
2. LZ-Compressed String Dictionaries
3. Fingerprints in Compressed Strings
4. Heaviest Induced Ancestors and Longest Common Substrings
5. Finding Distinct Subpalindromes Online
6. Parallel String Sample Sort
7. Repetition-free longest common subsequence of random sequences
8. Suffix Tree of Alignment: An Efficient Index for Similar Data
9. Lightweight LCP Construction for Next-Generation Sequencing Datasets

2013/4

1. Compact q-gram Profiling of Compressed Strings
2. Efficient repeat finding via suffix arrays
3. Detecting regularities on grammar-compressed strings
4. Efficient Lyndon factorization of grammar compressed text
5. Tree Compression with Top Trees
6. Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
7. Web graph compression with fast access
8. Average Case and Distributional Analysis of Dual-Pivot Quicksort
9. A Succinct Grammar Compression

2013/3

1. Computing convolution on grammar-compressed text
2. Order-Preserving Suffix Trees and Their Algorithmic Applications
3. Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays
4. Optimal Partitioning for Dual-Pivot Quicksort
5. Ultra-fast Multiple Genome Sequence Matching Using GPU
6. An Efficient Dynamic Programming Algorithm for the Generalized LCS Problem with Multiple Substring Exclusion Constrains
7. Using cascading Bloom filters to improve the memory usage for de Brujin graphs

2013/2

1. Lightweight Lempel-Ziv Parsing
2. Alphabet-Dependent String Searching with Wexponential Search Trees
3. Order Preserving Matching
4. Full-fledged Real-Time Indexing for Constant Size Alphabets
5. One-variable word equations in linear time
6. Modulated String Searching
7. Dynamic 2D Dictionary Matching in Small Space
8. Parallel Suffix Array Construction by Accelerated Sampling

2013/1

1. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
2. Single and multiple consecutive permutation motif search
3. Various improvements to text fingerprinting
4. A Dynamic Programming Solution to a Generalized LCS Problem
5. Engineering Small Space Dictionary Matching
6. Approximation of grammar-based compression via recompression
7. A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
8. Tree-based Arithmetic and Compressed Representations of Giant Numbers
9. 2D Lyndon Words and Applications

2012

2012/12

1. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
2. New Algorithms for Position Heaps
3. Necklaces, Convolutions, and X+Y

2012/11

1. Simpler and Faster Lempel Ziv Factorization
2. Time-Space Trade-Offs for Longest Common Extensions
3. Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching
4. Faster Compact Top-k Document Retrieval
5. The Rightmost Equal-Cost Position Problem
6. Algorithms for discovering and proving theorems about permutation patterns
7. A memory versus compression ratio trade-off in PPM via compressed context modeling
8. Approximate pattern matching with k-mismatches in packed text
9. Algorithms for Computing Abelian Periods of Words
10. Note on the Greedy Parsing Optimality for Dictionary-Based Text Compression

2012/10

1. Better Space Bounds for Parameterized Range Majority and Minority
2. New algorithms for binary jumbled pattern matching
3. In-place associative permutation sort

2012/9

1. Predecessor search with distance-sensitive query time
2. Sorting distinct integers using improved in-place associative sort
3. Improved in-place associative integer sorting
4. Sorting distinct integer keys using in-place associative sort
5. A New Algorithm for Data Compression Optimization
6. In-place associative integer sorting
7. Fast Packed String Matching for Short Patterns
8. Streaming Complexity of Checking Priority Queues
9. Bouma2 - A Quasi-Stateless, Tunable Multiple String-Match Algorithm
10. QuickHeapsort: Modifications and improved analysis
11. Counting common substrings effectively

2012/8

1. Space-Time Trade-offs for Stack-Based Algorithms
2. Distance Measures for Sequences
3. A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting
4. A Note on Efficient Computation of All Abelian Periods in a String
5. On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List

2012/7

1. Efficient LZ78 factorization of grammar compressed text
2. Sparse Suffix Tree Construction with Small Space
3. Ranked Document Retrieval in (Almost) No Space
4. Memory Efficient De Bruijn Graph Construction
5. Refined Quicksort asymptotics
6. On Optimal Top-K String Retrieval
7. Efficient algorithms for highly compressed data: The Word Problem in Generalized Higman Groups is in P

2012/6

1. Optimal Dynamic Sequence Representations
2. Efficient Algorithms for Finding Tucker Patterns
3. Some Novel Results From Analysis of Move To Front (MTF) List Accessing Algorithm
4. Optimal compression of hash-origin prefix trees
5. Quasi-Succinct Indices
6. On the combinatorics of suffix arrays
7. Comparison of Bucket Sort and RADIX Sort
8. Binary Jumbled String Matching for Highly Run-Length Compressible Texts
9. On the Complexity of Minimum Labeling Alignment of Two Genomes

2012/5

1. Sequential-Access FM-Indexes
2. Lyndon Words and Short Superstrings
3. Improving Compressed Counting
4. TH*:Scalable Distributed Trie Hashing
5. Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform

2012/4

1. Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding
2. On the Value of Multiple Read/Write Streams for Data Compression
3. Sorted Range Reporting
4. Adaptive Techniques to find Optimal Planar Boxes
5. Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
6. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
7. String Trees
8. The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space
9. Succinct Posets

2012/3

1. Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
2. On a New Method of Storing a Variable Size Array
3. A Fast Algorithm Finding the Shortest Reset Words
4. Sorting and preimages of pattern classes
5. Simplified, stable parallel merging

2012/2

1. Speeding-up $q$-gram mining on grammar-based compressed texts
2. Linear-Space Substring Range Counting over Polylogarithmic Alphabets
3. (Really) Tight bounds for dispatching binary methods
4. Computing Lempel-Ziv Factorization Online
5. Cross-Document Pattern Matching
6. Pattern Matching in Multiple Streams
7. On Approximating String Selection Problems with Outliers

2012/1

1. Compact Binary Relation Representations with Rich Functionality
2. SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
3. An Entertaining Example for the Usage of Bitwise Operations in Programming
4. A Bijective String Sorting Transform
5. Lower bounding edit distances between permutations
6. Deterministic Polynomial-Time Algorithms for Designing Short DNA Words
7. Quasiperiodicities in Fibonacci strings
8. BIN@ERN: Binary-Ternary Compressing Data Coding

2011

2011/12

1. Self-Index based on LZ77 (thesis)
2. Tight lower bounds for online labeling problem
3. Uncommon Suffix Tries
4. On the Complexity of Approximate Sum of Sorted List
5. Computing on Binary Strings

2011/11

1. A Compressed Self-Index for Genomic Databases
2. Optimal Lower and Upper Bounds for Representing Sequences
3. Practical Top-K Document Retrieval in Reduced Space
4. Edit Distance to Monotonicity in Sliding Windows
5. Faster fully compressed pattern matching by recompression
6. De-amortizing Binary Search Trees

2011/10

1. Improved Grammar-Based Compressed Indexes
2. String Indexing for Patterns with Wildcards
3. String Matching with Variable Length Gaps
4. Mining Patterns in Networks using Homomorphism
5. On Approximability of Block Sorting
6. Computing a Longest Common Palindromic Subsequence
7. Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection

2011/9

1. A Faster Grammar-Based Self-Index
2. Faster Approximate Pattern Matching in Compressed Repetitive Texts
3. Tying up the loose ends in fully LZW-compressed pattern matching
4. A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
5. Approximating Edit Distance in Near-Linear Time
6. A Regularity Measure for Context Free Grammars
7. A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query
8. Anomaly Sequences Detection from Logs Based on Compression
9. Encoding 2-D Range Maximum Queries
10. Lossless data compression on GPGPU architectures
11. Pattern Matching under Polynomial Transformation
12. Specific “scientific” data structures, and their processing

2011/8

1. Towards Optimal Sorting of 16 Elements
2. Substring Range Reporting
3. On Compressing Permutations and Adaptive Sorting
4. Succinct Representations of Permutations and Functions
5. Linear Time Inference of Strings from Cover Arrays using a Binary Alphabet
6. Optimal Indexes for Sparse Bit Vectors
7. Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval

2011/7

1. Restructuring Compressed Texts without Explicit Decompression
2. Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts
3. Computing q-gram Frequencies on Collage Systems
4. External Memory Orthogonal Range Reporting with Fast Updates
5. Sorting Algorithms with Restrictions
6. K-sort: A new sorting algorithm that beats Heap sort for n <= 70 lakhs!
7. Privacy-Enhanced Methods for Comparing Compressed DNA Sequences
8. Genome Halving by Block Interchange
9. Quadratic-time Algorithm for the String Constrained LCS Problem

2011/6

1. Space-Efficient Data-Analysis Queries on Grids
2. Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections
3. Reference Sequence Construction for Relative Compression of Genomes
4. Dynamic Range Selection in Linear Space
5. Space Lower Bounds for Online Pattern Matching
6. SparseAssembler: de novo Assembly with the Sparse de Bruijn Graph

2011/5

1. The Cell Probe Complexity of Dynamic Range Counting
2. An Improved Move-To-Front(IMTF) Off-line Algorithm for the List Accessing Problem

2011/4

1. Fixed Block Compression Boosting in FM-Indexes
2. Dynamic Range Majority Data Structures
3. Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
4. Random input helps searching predecessors
5. Efficient Seeds Computation Revisited
6. I/O-Efficient Data Structures for Colored Range and Prefix Reporting
7. On-line construction of position heaps

2011/3

1. Fast $q$-gram Mining on SLP Compressed Strings
2. Improved space-time tradeoffs for approximate full-text indexing with one edit error
3. On minimising automata with errors
4. Linear pattern matching on sparse suffix trees
5. Stratified B-trees and versioning dictionaries
6. Orthogonal Range Searching on the RAM, Revisited
7. An implementation of range trees with fractional cascading in C++

2011/2

1. Upper Bounds for Maximally Greedy Binary Search Trees
2. On Dynamic Optimality for Binary Search Trees
3. Don’t Rush into a Union: Take Time to Find Your Roots
4. Algorithms for Jumbled Pattern Matching in Strings

2011/1

1. Self-Index Based on LZ77
2. Compressed String Dictionaries
3. Linear-Space Data Structures for Range Mode Query in Arrays
4. Inducing the LCP-Array
5. Succincter Text Indexing with Wildcards

2010

2010/12

1. A Searchable Compressed Edit-Sensitive Parsing
2. Lightweight LCP-Array Construction in Linear Time

2010/11

1. New Algorithms on Wavelet Trees and Applications to Information Retrieval
2. Counting Colours in Compressed Strings
3. Worst case efficient single and multiple string matching in the Word-RAM model
4. Pattern Kits
5. CRAM: Compressed Random Access Memory
6. Parallelization of Weighted Sequence Comparison by using EBWT

2010/9

1. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
2. Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata

2010/8

1. Succinct Data Structures for Assembling Large Genomes
2. The universality of iterated hashing over variable-length strings

2010/7

1. Tree structure compression with RePair
2. Top-K Color Queries for Document Retrieval
3. Fully Dynamic Data Structure for Top-k Queries on Uncertain Data

2010/6

1. Dynamic Range Reporting in External Memory
2. Optimal Trade-Off for Succinct String Indexes
3. An Efficient Algorithm For Chinese Postman Walk on Bi-directed de Bruijn Graphs
4. Should Static Search Trees Ever Be Unbalanced?
5. Tight and simple Web graph compression

2010/5

1. Succinct Representations of Dynamic Strings
2. The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
3. On Finding Frequent Patterns in Directed Acyclic Graphs

2010/4

1. Unified Compression-Based Acceleration of Edit-Distance Computation
2. Restricted Common Superstring and Restricted Common Supersequence
3. Some long-period random number generators using shifts and xors
4. Uses of randomness in computation

2010/3

1. On the Border Length Minimization Problem (BLMP) on a Square Array
2. Efficient Parallel and Out of Core Algorithms for Constructing Large Bi-directed de Bruijn Graphs

2010/2

1. Range Reporting for Moving Points on a Grid
2. Mergeable Dictionaries

2010/1

1. Random Access to Grammar Compressed Strings
2. Succinct Dictionary Matching With No Slowdown
3. Document Clustering with K-tree
4. Sampled Longest Common Prefix Array
5. Random Indexing K-tree
6. K-tree: Large Scale Document Clustering

2009

2009/12

1. Grammar-Based Compression in a Streaming Model
2. A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source
3. Practical Algorithmic Techniques for Several String Processing Problems
4. Time and Memory Efficient Lempel-Ziv Compression Using Suffix Arrays
5. Renewal theory in analysis of tries and strings

2009/11

1. Efficient Fully-Compressed Sequence Representations
2. Re-Pair Compression of Inverted Lists
3. Fast Arc-Annotated Subsequence Matching in Linear Space
4. An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence
5. A Minimal Periods Algorithm with Applications

2009/10

1. Wee LCP
2. Searching a bitstream in linear time for the longest substring of any given density
3. b-Bit Minwise Hashing
4. Estimating Entropy of Data Streams Using Compressed Counting
5. Scalable Distributed-Memory External Sorting

2009/9

1. Lightweight Data Indexing and Compression in External Memory
2. Randomized Shellsort: A Simple Oblivious Sorting Algorithm
3. Fast Set Intersection and Two Patterns Matching
4. Range Non-Overlapping Indexing
5. Generating All Partitions: A Comparison Of Two Encodings

2009/8

1. On Bijective Variants of the Burrows-Wheeler Transform

2009/7

1. Tight Bounds for Online Stable Sorting
2. Fast In-Memory XPath Search over Compressed Text and Tree Indexes
3. Fast Searching in Packed Strings
4. Online Sorting via Searching and Selection
5. A Lower Bound for Succinct Rank Queries

2009/6

1. On optimally partitioning a text to improve its compression
2. Data Structures for Approximate Range Counting
3. Cell-Probe Lower Bounds for Prefix Sums

2009/5

1. Fast and Compact Prefix Codes
2. Fully-Functional Static and Dynamic Succinct Trees

2009/4

1. Learning Character Strings via Mastermind Queries, with a Case Study Involving mtDNA
2. On Smoothed Analysis of Quicksort and Hoare’s Find

2009/3

1. Range Quantile Queries: Another Virtue of Wavelet Trees
2. Heaps Simplified
3. On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression
4. Analysis of the Relationships among Longest Common Subsequences, Shortest Common Supersequences and Patterns and its application on Pattern Discovery in Biological Sequences

2009/2

1. New Algorithms and Lower Bounds for Sequential-Access Data Compression
2. Compressed Representations of Permutations, and Applications
3. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
4. A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression

2008

2008/12

1. Worst-Case Optimal Adaptive Prefix Coding
2. Minimax Trees in Linear Time
3. The Violation Heap: A Relaxed Fibonacci-Like Heap
4. Optimal Succinctness for Range Minimum Queries

2008/11

1. Faster Approximate String Matching for Short Patterns
2. Low-Memory Adaptive Prefix Coding
3. How robust is quicksort average complexity?
4. Binar Sort: A Linear Generalized Sorting Algorithm
5. Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes

2008/10

1. A New Algorithm for Building Alphabetic Minimax Trees
2. Efficient Pattern Matching on Binary Strings

2008/9

1. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding

2008/7

1. Improved Algorithms for Approximate String Matching (Extended Abstract)

2008/6

1. Biased Range Trees
2. A Dynamic Programming Approach To Length-Limited Huffman Coding
3. Space Efficient Multi-Dimensional Range Reporting

2008/5

1. Succinct Geometric Indexes Supporting Point Location Queries

2008/4

1. New Lower Bounds for the Maximum Number of Runs in a String
2. Discovering More Accurate Frequent Web Usage Patterns

2008/3

1. Succinct Data Structures for Retrieval and Approximate Membership

2008/2

1. Bit-Optimal Lempel-Ziv compression
2. Deriving Sorting Algorithms
3. Understanding maximal repetitions in strings
4. Parameterized Algorithms for Partial Cover Problems
5. Approximating General Metric Distances Between a Pattern and a Text

2008/1

1. String algorithms and data structures

2007

2007/12

1. Compressed Text Indexes:From Theory to Practice!

2007/11

1. Bounds for Compression in Streaming Models

2007/8

1. Pattern Matching in Trees and Strings
2. Empirical entropy in context
3. A nearly tight memory-redundancy trade-off for one-pass compression

2007/6

1. Radix Sorting With No Extra Space
2. Sublinear Algorithms for Approximating String Compressibility
3. Dualheap Sort Algorithm: An Inherently Parallel Generalization of Heapsort

2006

2006/11

1. On the space complexity of one-pass compression

2006/9

1. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
2. Practical Entropy-Compressed Rank/Select Dictionary

2006/8

1. The Tree Inclusion Problem: In Linear Space and Faster

2006/6

1. New Algorithms for Regular Expression Matching

2006/1

1. An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture

2005

2005/12

1. Matching Subsequences in Trees

2005/9

1. Fast and Compact Regular Expression Matching

2005/6

1. Large Alphabets and Incompressibility
2. Sorting a Low-Entropy Sequence
3. Compressing Probability Distributions

2005/3

1. Dynamic Shannon Coding

1996

1996/8

1. Shellsort with three increments

This site is open source. Improve this page.