StringologyTimes

Papers for stringologist

Table of Contents

Contents

Inf. Process. Lett. 2026

  1. Finding the cyclic covers of a string.

Inf. Syst. 2026

  1. Extended parameterized Burrows-Wheeler transform.

ACNS (1) 2025

  1. Oblivious Suffix Sorting: A Multi-Party Computation Scheme for Secure and Efficient Suffix Sorting.

COCOON (2) 2025

  1. Revisit the Partial Coloring Method: Prefix Spencer and Sampling.

CPP 2025

  1. Formalized Burrows-Wheeler Transform.

ICIC (26) 2025

  1. Enough Consecutive Matches in k-Tuple Common Substrings.

IJTCS-FAW 2025

  1. Finding a Set of Long Common Substrings with Repeats from m Input Strings.
  2. k-Universality of Regular Languages Revisited.

RECOMB 2025

  1. Prokrustean Graph: A Substring Index for Rapid K-Mer Size Analysis.

STOC 2025

  1. On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM.

Acta Informatica 2025

  1. The Primitive Deficiency of two Primitive Strings.

Algorithms 2025

  1. Substring Counting with Insertions.

Algorithms Mol. Biol. 2025

  1. Faster computation of left-bounded shortest unique substrings.
  2. sc McDag: indexing maximal common subsequences for k strings.

CoRR 2025

  1. k-Universality of Regular Languages Revisited.
  2. 25 Additional Problems - Extension to the Book “125 Problems in Text Algorithms”.
  3. A Dynamic, Self-balancing k-d Tree.
  4. A Framework for Building Data Structures from Communication Protocols.
  5. A Space-Efficient Algorithm for Longest Common Almost Increasing Subsequence of Two Sequences.
  6. A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data.
  7. Adaptive Hybrid Sort: Dynamic Strategy Selection for Optimal Sorting Across Diverse Data Distributions.
  8. An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT.
  9. Approximate Cartesian Tree Matching with One Difference.
  10. Are Depth-2 Regular Expressions Hard to Intersect?
  11. BWT for string collections.
  12. Balanced Fibonacci word rectangles, and beyond.
  13. Better Indexing for Rectangular Pattern Matching.
  14. Binary Jumbled Indexing: Suffix tree histogram.
  15. Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds.
  16. Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms.
  17. Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism.
  18. Cartesian Forest Matching.
  19. Checking and producing word attractors.
  20. Cloitre’s Self-Generating Sequence.
  21. Combinatorics of Palindromes.
  22. Compact representation of maximal palindromes.
  23. Compact representations of pattern-avoiding permutations.
  24. Compressed Dictionary Matching on Run-Length Encoded Strings.
  25. Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations.
  26. Compressing Hypergraphs using Suffix Sorting.
  27. Compressing Suffix Trees by Path Decompositions.
  28. Computing k-mers in Graphs.
  29. Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric.
  30. Constant sensitivity on the CDAWGs.
  31. Contextual Pattern Mining and Counting.
  32. Counting Distinct Square Substrings in Sublinear Time.
  33. Counting distinct (non-)crossing substrings.
  34. Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform.
  35. Depth first representations of k2-trees.
  36. Deterministic Longest Common Subsequence Approximation in Near-Linear Time.
  37. Digital Convexity and Combinatorics on Words.
  38. Dorst-Smeulders Coding for Arbitrary Binary Words.
  39. Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance.
  40. Dynamic Indexing Through Learned Indices with Worst-case Guarantees.
  41. Dynamic Necklace Splitting.
  42. Dynamic Unit-Disk Range Reporting.
  43. Dynamic r-index: An Updatable Self-Index for Highly Repetitive Strings.
  44. Efficient Computation of Closed Substrings.
  45. Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets.
  46. Efficiently Finding All Minimal and Shortest Absent Subsequences in a String.
  47. Encoding Co-Lex Orders of Finite-State Automata in Linear Space.
  48. Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text.
  49. Engineering Select Support for Hybrid Bitvectors.
  50. Expected Length of the Longest Common Subsequence of Multiple Strings.
  51. Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries.
  52. Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares.
  53. Fast Pattern Matching with Epsilon Transitions.
  54. Fast and memory-efficient BWT construction of repetitive texts using Lyndon grammars.
  55. Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime.
  56. Faster ED-String Matching with k Mismatches.
  57. Fingerprint Filters Are Optimal.
  58. Fully Dynamic LZ77 in Sublinear Time.
  59. GPU Implementation of the Wavelet Tree.
  60. Generalization of Repetitiveness Measures for Two-Dimensional Strings.
  61. Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform.
  62. Generalized Orthogonal de Bruijn Sequences.
  63. IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data.
  64. Identifying Approximate Minimizers under Stochastic Uncertainty.
  65. Improved Circular Dictionary Matching.
  66. Improved Extended Regular Expression Matching.
  67. Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves.
  68. Improved Online Sorting.
  69. Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev’s Sorting Networks as Base Cases.
  70. Indexing Strings with Utilities.
  71. Indexing Tries within Entropy-Bounded Space.
  72. Inverting Parameterized Burrows-Wheeler Transform.
  73. Jumbled Scattered Factors.
  74. KeBaB: k-mer based breaking for finding super-maximal exact matches.
  75. LZD-style Compression Scheme with Truncation and Repetitions.
  76. LZSE: an LZ-style compressor supporting O(log n)-time random access.
  77. Lazy B-Trees.
  78. Learned Static Function Data Structures.
  79. Linear Time Subsequence and Supersequence Regex Matching.
  80. Linear-space LCS enumeration with quadratic-time delay for two strings.
  81. Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts.
  82. Longest Unbordered Factors on Run-Length Encoded Strings.
  83. Minimizers in Semi-Dynamic Strings.
  84. Modern Minimal Perfect Hashing: A Survey.
  85. Monochromatic arithmetic progressions in the Fibonacci word.
  86. MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing.
  87. Morphisms and BWT-run Sensitivity.
  88. Near-Optimal Property Testers for Pattern Matching.
  89. Nearly Tight Bounds for the Online Sorting Problem.
  90. Net Occurrences in Fibonacci and Thue-Morse Words.
  91. New simple and fastest quicksort algorithm for equal keys.
  92. Nyldon Factorization of Thue-Morse Words and Fibonacci Words.
  93. OSTRICH2: Solver for Complex String Constraints.
  94. Old and New Results on Alphabetic Codes.
  95. On Minimizers of Minimum Density.
  96. On a sequence of Kimberling and its relationship to the Tribonacci word.
  97. On the Complexity of Finding Approximate LCS of Multiple Strings.
  98. On the Hardness Hierarchy for the O(n √(log n)) Complexity in the Word RAM.
  99. On the Smallest Size of Internal Collage Systems.
  100. On the number of MUSs crossing a position.
  101. On the sensitivity of CDAWG-grammars.
  102. Online computation of normalized substring complexity.
  103. Optimal Non-Oblivious Open Addressing.
  104. Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings.
  105. Optimal Static Fully Indexable Dictionaries.
  106. Optimization of Base-n Radix Sort for Skewed Datasets.
  107. PHast - Perfect Hashing with fast evaluation.
  108. Pattern Matching under Weighted Edit Distance.
  109. Pcodec: Better Compression for Numerical Sequences.
  110. Permutation patterns in streams.
  111. Practical colinear chaining on sequences revisited.
  112. Prefix-free parsing for merging big BWTs.
  113. Quantum Pattern Matching with Wildcards.
  114. RLZ-r and LZ-End-r: Enhancing Move-r.
  115. Random generation of universal cycles and de Bruijn sequences.
  116. Resilient Pattern Mining.
  117. Review of Three Variants of the k-d Tree.
  118. Simple Quantum Algorithm for Approximate k-Mismatch Problem.
  119. Simple in-place yet comparison-optimal Mergesort.
  120. Smallest Suffixient Sets as a Repetitiveness Measure.
  121. Sorting with constraints.
  122. Space-Efficient k-Mismatch Text Indexes.
  123. Static Retrieval Revisited: To Optimality and Beyond.
  124. StrNim: a variant of Nim played on strings.
  125. Streaming periodicity with mismatches, wildcards, and edits.
  126. String Consensus Problems with Swaps and Substitutions.
  127. String Matching with a Dynamic Pattern.
  128. String Problems in the Congested Clique Model.
  129. Subtree Mode and Applications.
  130. Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck.
  131. Succinct Preferential Attachment Graphs.
  132. Symmetry of information for space-bounded online Kolmogorov complexity.
  133. Testing Quasiperiodicity.
  134. Testing Suffixient Sets.
  135. Text Indexing and Pattern Matching with Ephemeral Edits.
  136. The Complexity of Maximal Common Subsequence Enumeration.
  137. The Narayana Morphism and Related Words.
  138. The Structure of In-Place Space-Bounded Computation.
  139. The Trie Measure, Revisited.
  140. Theory Meets Practice for Bit Vectors Supporting Rank and Select.
  141. Tight Additive Sensitivity on LZ-style Compressors and String Attractors.
  142. Tight Lower Bounds for Central String Queries in Compressed Space.
  143. Towards universally optimal sorting algorithms.
  144. U-index: A Universal Indexing Framework for Matching Long Patterns.
  145. Unclustered BWTs of any Length over Non-Binary Alphabets.
  146. Universally Wheeler Languages.
  147. Verified Purely Functional Catenable Real-Time Deques.
  148. When is String Reconstruction using de Bruijn Graphs Hard?
  149. Word Break on SLP-Compressed Texts.
  150. Word Chain Generators for Prefix Normal Words.
  151. Words with factor somplexity 2n+1 and minimal critical exponent.
  152. Zip-Tries: Simple Dynamic Data Structures for Strings.
  153. jXBW: Fast Substructure Search in Large-Scale JSONL Datasets for Foundation Model Applications.
  154. persiansort : an alternative to mergesort inspired by persian rug.
  155. r*-indexing.

Comput. J. 2025

  1. Clustering-based compression for raster time series.

Eur. J. Comb. 2025

  1. The asymptotic repetition threshold of sequences rich in palindromes.

Geo spatial Inf. Sci. 2025

  1. Stronger compact representations of object trajectories.

Inf. Comput. 2025

  1. Hardness and approximability of bounded access Lempel Ziv coding.
  2. The generalized constrained longest common subsequence in the run-length encoded format.
  3. The longest subsequence-duplicated subsequence and related problems.

Inf. Process. Lett. 2025

  1. The longest common subsequence problem for small alphabets in the word RAM model.

Inf. Syst. 2025

  1. Substring compression variations and LZ78-Derivates.
  2. Two-level massive string dictionaries.

Int. J. Found. Comput. Sci. 2025

  1. Repetition Factorization of Automatic Sequences.

J. Autom. Reason. 2025

  1. Formally Verified Suffix Array Construction.

J. Heuristics 2025

  1. Heuristics for the run-length encoded Burrows-Wheeler transform alphabet ordering problem.

J. Syst. Softw. 2025

  1. On the compressibility of large-scale source code datasets.

Nat. Comput. 2025

  1. Palindromes in adjacent factor swap of a word.

Pattern Anal. Appl. 2025

  1. NEONATE: a bi-directional search strategy for non-overlapping pattern matching with gap constraint.

SoftwareX 2025

  1. SDSL-Mobile: Enabling space-efficient data structures for mobile applications.

Theor. Comput. Sci. 2025

  1. On the number of equal-letter runs of the bijective Burrows-Wheeler transform.
  2. Repetitiveness measures based on string morphisms.
  3. Subsequence covers of words.

VLDB J. 2025

  1. Text indexing for long patterns using locally consistent anchors.

ACIIDS (Companion 1) 2024

  1. The Merged Longest Common Increasing Subsequence Problem.

CALDAM 2024

  1. Consecutive Occurrences with Distance Constraints.

EvoStar 2024

  1. A Neural Network Based Guidance for a BRKGA: An Application to the Longest Common Square Subsequence Problem.

FUN 2024

  1. Baba Is Universal.
  2. Snake in Optimal Space and Time.
  3. The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples.

GASCom 2024

  1. A Symmetry Property of Christoffel Words.
  2. Perfectly Clustering Words and Iterated Palindromes over a Ternary Alphabet.

GandALF 2024

  1. Deterministic Suffix-reading Automata.

ICCS (5) 2024

  1. Efficient Search Algorithms for the Restricted Longest Common Subsequence Problem.

IJTCS-FAW 2024

  1. [Longest (k]-Tuple Common Substrings.](https://doi.org/10.1007/978-981-97-7752-5_8)

TAMC 2024

  1. Quantum Path Parallelism: A Circuit-Based Approach to Text Searching.

ACM Trans. Algorithms 2024

  1. Generic Non-recursive Suffix Array Construction.

Acta Informatica 2024

  1. Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm.
  2. The longest letter-duplicated subsequence and related problems.

Algorithmica 2024

  1. Pattern Masking for Dictionary Matching: Theory and Practice.

Algorithms 2024

  1. Computing RF Tree Distance over Succinct Representations.
  2. Text Indexing for Faster Gapped Pattern Matching.

Bioinform. 2024

  1. Sigmoni: classification of nanopore signal with a compressed pangenome index.

CoRR 2024

  1. A Connection Between Unbordered Partial Words and Sparse Rulers.
  2. A Family of LZ78-based Universal Sequential Probability Assignments.
  3. A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities.
  4. A Lock-free Binary Trie.
  5. A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation.
  6. A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs.
  7. A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm.
  8. A simpler data structure for dynamic strings.
  9. A visualization tool to explore alphabet orderings for the Burrows-Wheeler Transform.
  10. Adaptive Dynamic Bitvectors.
  11. Algorithms for Galois Words: Detection, Factorization, and Rotation.
  12. Algorithms for Parameterized String Matching with Mismatches.
  13. All-Pairs Suffix-Prefix on Dynamic Set of Strings.
  14. Almost Linear Size Edit Distance Sketch.
  15. An 11/6-Approximation Algorithm for Vertex Cover on String Graphs.
  16. An Algorithm for a Modification of the Shortest Common Superstring Problem.
  17. An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings.
  18. An Implementation and Experimental Comparison of Dynamic Ordered Sets.
  19. An Optimal Algorithm for Sorting Pattern-Avoiding Sequences.
  20. Approximate Circular Pattern Matching under Edit Distance.
  21. Avoiding abelian and additive powers in rich words.
  22. BAT-LZ Out of Hell.
  23. Better space-time-robustness trade-offs for set reconciliation.
  24. Bijective BWT based compression schemes.
  25. Bit catastrophes for the Burrows-Wheeler Transform.
  26. Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights.
  27. Characterization of Isometric Words based on Swap and Mismatch Distance.
  28. Characterizing and Transforming DAGs within the I-LCA Framework.
  29. Christoffel Matrices and Sturmian Determinants.
  30. Closed Repeats.
  31. Combinatorics on words and generating Dirichlet series of automatic sequences.
  32. Comparative genomics with succinct colored de Bruijn graphs.
  33. Compressed Game Solving.
  34. Compression with wildcards: All induced metric subgraphs.
  35. Computing Longest Common Subsequence under Cartesian-Tree Matching Model.
  36. Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space.
  37. Computing String Covers in Sublinear Time.
  38. Computing the LCP Array of a Labeled Graph.
  39. Computing the LZ-End parsing: Easy to implement and practically efficient.
  40. Computing the k-binomial complexity of generalized Thue-Morse words.
  41. Consecutive Power Occurrences in Sturmian Words.
  42. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications.
  43. Counting on General Run-Length Grammars.
  44. Counting overlapping pairs of strings.
  45. Differentially Private Substring and Document Counting.
  46. Dudeney’s Dissection is Optimal.
  47. Dynamic Range Minimum Queries on the Ultra-Wide Word RAM.
  48. Dynamic Suffix Array in Optimal Compressed Space.
  49. Edit and Alphabet-Ordering Sensitivity of Lex-parse.
  50. Efficient Construction of Long Orientable Sequences.
  51. Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences.
  52. Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing.
  53. Efficient top-down updates in AVL trees.
  54. Elastic-Degenerate String Comparison.
  55. Enhanced Graph Pattern Matching.
  56. Enumeration for MSO-Queries on Compressed Trees.
  57. Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG.
  58. Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs.
  59. Exploiting New Properties of String Net Frequency for Efficient Computation.
  60. Exploring Repetitiveness Measures for Two-Dimensional Strings.
  61. Exploring the Crochemore and Ziv-Lempel factorizations of some automatic sequences with the software Walnut.
  62. Exponent-Strings and Their Edit Distance.
  63. Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It.
  64. Fast and Lightweight Distributed Suffix Array Construction - First Results.
  65. Fast and Simple Sorting Using Partial Information.
  66. Fast and Small Subsampled R-indexes.
  67. Fast computation of the period and of the shortest cover of a string using its Character-Distance-Sampling representation.
  68. Faster and Simpler Online Computation of String Net Frequency.
  69. Faster and simpler online/sliding rightmost Lempel-Ziv factorizations.
  70. Faster two-dimensional pattern matching with k mismatches.
  71. Fault-Equivalent Lowest Common Ancestors.
  72. Finding Diverse Strings and Longest Common Subsequences in a Graph.
  73. From the Lyndon factorization to the Canonical Inverse Lyndon factorization: back and forth.
  74. Generalized Straight-Line Programs.
  75. Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings.
  76. Hairpin Completion Distance Lower Bound.
  77. Hardness Amplification for Dynamic Binary Search Trees.
  78. Hardness Results on Characteristics for Elastic-Degenerated Strings.
  79. Height-bounded Lempel-Ziv encodings.
  80. Heuristics for the Run-length Encoded Burrows-Wheeler Transform Alphabet Ordering Problem.
  81. How to Find Long Maximal Exact Matches and Ignore Short Ones.
  82. Implementation Of Dynamic De Bruijn Graphs Via Learned Index.
  83. Improved Lower Bounds on the Expected Length of Longest Common Subsequences.
  84. Incremental computation of the set of period sets.
  85. Indexing Finite-State Automata Using Forward-Stable Partitions.
  86. Internal Pattern Matching in Small Space and Applications.
  87. Iterated Straight-Line Programs.
  88. Kolmogorov complexity as a combinatorial tool.
  89. Lempel-Ziv (LZ77) Factorization in Sublinear Time.
  90. Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees.
  91. Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved.
  92. Lock-Free Augmented Trees.
  93. Longest Common Extensions with Wildcards: Trade-off and Applications.
  94. Lyndon pairs and the lexicographically greatest perfect necklace.
  95. MIOV: Reordering MOVI for even better locality.
  96. Many Flavors of Edit Distance.
  97. Maximal number of subword occurrences in a word.
  98. Minimizing the Minimizers via Alphabet Reordering.
  99. Movelet Trees.
  100. NP-Completeness for the Space-Optimality of Double-Array Tries.
  101. Near-Optimal Trace Reconstruction for Mildly Separated Strings.
  102. Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching.
  103. New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching.
  104. New Compressed Indices for Multijoins on Graph Databases.
  105. On Computing the Smallest Suffixient Set.
  106. On Differentially Private String Distances.
  107. On multidimensional generalization of binary search.
  108. On the Communication Complexity of Approximate Pattern Matching.
  109. On the Complexity of Computing the Co-lexicographic Width of a Regular Language.
  110. On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms.
  111. On the Number of Non-equivalent Parameterized Squares in a String.
  112. On the complexity and approximability of Bounded access Lempel Ziv coding.
  113. On the compressiveness of the Burrows-Wheeler transform.
  114. On the longest increasing subsequence and number of cycles of butterfly permutations.
  115. On the number of k-mers admitting a given lexicographical minimizer.
  116. On the piecewise complexity of words.
  117. Online Computation of String Net Frequency.
  118. Online String Attractors.
  119. Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees.
  120. Optimal Bounds for Distinct Quartics.
  121. Optimal Static Dictionary with Worst-Case Constant Query Time.
  122. Optimal prefix-suffix queries with applications.
  123. Packed Acyclic Deterministic Finite Automata.
  124. Palindromes Compression and Retrieval.
  125. Palindromic length of infinite aperiodic words.
  126. Pattern Matching with Mismatches and Wildcards.
  127. QR Sort: A Novel Non-Comparative Sorting Algorithm.
  128. Quantum Algorithm for the Multiple String Matching Problem.
  129. Quantum search in a dictionary based on fingerprinting-hashing.
  130. Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality.
  131. Recovery of cyclic words by their subwords.
  132. Regular Languages in the Sliding Window Model.
  133. Relating Left and Right Extensions of Maximal Repeats.
  134. Relative position in binary substitutions.
  135. Repetition Threshold for Binary Automatic Sequences.
  136. Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration.
  137. Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings.
  138. Rollercoasters with Plateaus.
  139. Runs in Paperfolding Sequences.
  140. SPIDER: Improved Succinct Rank and Select Performance.
  141. Scalable Distributed String Sorting.
  142. Scalable Order-Preserving Pattern Mining.
  143. ShiftDTW: adapting the DTW metric for cyclic time series clustering.
  144. Shortest cover after edit.
  145. Simple Linear-time Repetition Factorization.
  146. Simplified Tight Bounds for Monotone Minimal Perfect Hashing.
  147. Small Space Encoding and Recognition of k-Palindromic Prefixes.
  148. Some Remarks on Palindromic Periodicities.
  149. Sorted Consecutive Occurrence Queries in Substrings.
  150. Space-Efficient Indexes for Uncertain Strings.
  151. Space-Efficient Online Computation of String Net Occurrences.
  152. Space-efficient SLP Encoding for O(log N)-time Random Access.
  153. Stability properties for subgroups generated by return words.
  154. String 2-Covers with No Length Restrictions.
  155. String Partition for Building Big BWTs.
  156. String attractors and bi-infinite words.
  157. Subsequence Matching and Analysis Problems for Formal Languages.
  158. Subsequence Pattern Matching with Segment Number Constraint.
  159. Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds.
  160. Substring Compression Variations and LZ78-Derivates.
  161. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage.
  162. Succinct Data Structures for Segments.
  163. Tag arrays.
  164. Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests.
  165. Text Indexing for Long Patterns using Locally Consistent Anchors.
  166. The CDAWG Index and Pattern Matching on Grammar-Compressed Strings.
  167. The Quasi-probability Method and Applications for Trace Reconstruction.
  168. The Repetition Threshold for Rote Sequences.
  169. The Shortest Interesting Binary Words.
  170. The reflection complexity of sequences over finite alphabets.
  171. The repetition threshold for ternary rich words.
  172. Theoretical Analysis of Byte-Pair Encoding.
  173. Theoretical insights and an experimental comparison of tango trees and multi-splay trees.
  174. Tight Bounds for the Number of Absent Scattered Factors.
  175. Top-k Stabbing Interval Queries.
  176. Toward Greener Matrix Operations by Lossless Compressed Formats.
  177. Towards Optimal Grammars for RNA Structures.
  178. TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm.
  179. Unveiling the connection between the Lyndon factorization and the Canonical Inverse Lyndon factorization via a border property.
  180. Upper Bounds for Complexity of Asymptotically Optimal Learned Indexes.
  181. Upper bounds on the average edit distance between two random strings.
  182. Utilizing ChatGPT in a Data Structures and Algorithms Course: A Teaching Assistant’s Perspective.
  183. V-Words, Lyndon Words and Galois Words.
  184. Word equations, constraints, and formal languages.

Comput. J. 2024

  1. Dynamic compact data structure for temporal reachability with unsorted contact insertions.

Discret. Appl. Math. 2024

  1. On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms.
  2. Polynomial-time equivalences and refined algorithms for longest common subsequence variants.

Inf. Comput. 2024

  1. Constructing and indexing the bijective and extended Burrows-Wheeler transform.

Inf. Syst. 2024

  1. CoCo-trie: Data-aware compression and indexing of strings.

J. Comb. Theory, Ser. A 2024

  1. New string attractor-based complexities for infinite words.

J. Comput. Syst. Sci. 2024

  1. The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings.

J. Supercomput. 2024

  1. Palindromes in involutive Fibonacci arrays.

Knowl. Based Syst. 2024

  1. Dynamic-MLCS: Fast searching for dynamic multiple longest common subsequences in sequence stream data.

SIAM J. Comput. 2024

  1. Internal Pattern Matching Queries in a Text and Applications.

Theor. Comput. Sci. 2024

  1. Faster space-efficient STR-IC-LCS computation.

Theory Comput. Syst. 2024

  1. Elastic-Degenerate String Matching with 1 Error or Mismatch.
  2. String Attractors of Some Simple-Parry Automatic Sequences.

VLDB J. 2024

  1. Optimizing RPQs over a compact graph representation.

ALENEX 2023

  1. LZ77 via Prefix-Free Parsing.
  2. Lower Bounds for Sorting 16, 17, and 18 Elements.
  3. Multiway Powersort.
  4. PaCHash: Packed and Compressed Hash Tables.
  5. SicHash - Small Irregular Cuckoo Tables for Perfect Hashing.

COCOA (1) 2023

  1. V-Words, Lyndon Words and Substring circ-UMFFs.

COCOA (2) 2023

  1. On Problems Related to Absent Subsequences.

CPM 2023

  1. Approximation Algorithms for the Longest Run Subsequence Problem.
  2. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications.
  3. Compressed Indexing for Consecutive Occurrences.
  4. Computing MEMs on Repetitive Text Collections.
  5. Encoding Hard String Problems with Answer Set Programming.
  6. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor.
  7. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
  8. From Bit-Parallelism to Quantum String Matching for Labelled Graphs.
  9. Improving the Sensitivity of MinHash Through Hash-Value Analysis.
  10. L-Systems for Measuring Repetitiveness.
  11. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
  12. MONI Can Find k-MEMs.
  13. MUL-Tree Pruning for Consistency and Compatibility.
  14. Merging Sorted Lists of Similar Strings.
  15. On Distances Between Words with Parameters.
  16. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem.
  17. On the Impact of Morphisms on BWT-Runs.
  18. Optimal LZ-End Parsing Is Hard.
  19. Optimal Near-Linear Space Heaviest Induced Ancestors.
  20. Order-Preserving Squares in Strings.
  21. PalFM-Index: FM-Index for Palindrome Pattern Matching.
  22. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  23. Sliding Window String Indexing in Streams.
  24. String Factorization via Prefix Free Families.
  25. Suffix-Prefix Queries on a Dictionary.
  26. Trie-Compressed Adaptive Set Intersection.

DCC 2023

  1. Augmented Thresholds for MONI.
  2. Bit-Parallel (Compressed) Wavelet Tree Construction.
  3. Computing matching statistics on Wheeler DFAs.
  4. Computing the optimal BWT of very large string collections.
  5. Constructing the CDAWG CFG using LCP-Intervals.
  6. Contextual Pattern Matching in Less Space.
  7. FM-Directories: Extending the Burrows-Wheeler Transform for String Labeled Vertex Graphs of (Almost) Arbitrary Topology.
  8. JARVIS2: a data compressor for large genome sequences.
  9. LZ4r - A New Fast Compression Algorithm for High-Speed Data Storage Systems.
  10. Measuring the Similarity of Files by Data Compression.
  11. Model Compression for Data Compression: Neural Network Based Lossless Compressor Made Practical.
  12. Permutation coding using divide-and-conquer strategy.
  13. Practical Implementations of Compressed RAM.
  14. RNA secondary structures: from ab initio prediction to better compression, and back.
  15. Recursive Prefix-Free Parsing for Building Big BWTs.
  16. SnappyR: A New High-Speed Lossless Data Compression Algorithm.

DLT 2023

  1. Bit Catastrophes for the Burrows-Wheeler Transform.

ISBRA 2023

  1. CSA-MEM: Enhancing Circular DNA Multiple Alignment Through Text Indexing Algorithms.

ITCS 2023

  1. An Algorithmic Bridge Between Hamming and Levenshtein Distances.

SISAP 2023

  1. Runs of Side-Sharing Tandems in Rectangular Arrays.

SODA 2023

  1. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time.
  2. A Nearly-Tight Analysis of Multipass Pairing Heaps.
  3. A Tight Analysis of Slim Heaps and Smooth Heaps.
  4. Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.
  5. Optimal Square Detection Over General Alphabets.
  6. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching.
  7. Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
  8. Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures.
  9. Tight Bounds for Monotone Minimal Perfect Hashing.
  10. Tiny Pointers.

SOFSEM 2023

  1. Space-Efficient STR-IC-LCS Computation.
  2. The k-Centre Problem for Classes of Cyclic Words.

SOSA 2023

  1. An Optimal Lower Bound for Simplex Range Reporting.
  2. Optimal resizable arrays.
  3. Splay Top Trees.

STACS 2023

  1. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm.
  2. Dynamic Data Structures for Parameterized String Problems.
  3. Real Numbers Equally Compressible in Every Base.
  4. Reconstructing Words Using Queries on Subwords or Factors.

STOC 2023

  1. Approximating Binary Longest Common Subsequence in Almost-Linear Time.
  2. External Memory Fully Persistent Search Trees.
  3. Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
  4. Weighted Edit Distance Computation: Strings, Trees, and Dyck.

WALCOM 2023

  1. Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs.
  2. Energy Efficient Sorting, Selection and Searching.
  3. Finding the Cyclic Covers of a String.
  4. Inferring Strings from Position Heaps in Linear Time.
  5. Internal Longest Palindrome Queries in Optimal Time.
  6. Parity Permutation Pattern Matching.

WORDS 2023

  1. Smallest and Largest Block Palindrome Factorizations.
  2. String Attractors for Factors of the Thue-Morse Word.
  3. String Attractors of Fixed Points of k-Bonacci-Like Morphisms.

ACM Trans. Algorithms 2023

  1. On the Complexity of String Matching for Graphs.

Algorithmica 2023

  1. Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series.

Bioinform. 2023

  1. μ- PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data.

CoRR 2023

  1. (min, +) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences.
  2. A Compact DAG for Storing and Searching Maximal Common Subsequences.
  3. A Compact Representation for AVL Trees.
  4. A Huffman based short message service compression technique using adjacent distance array.
  5. A Myhill-Nerode Theorem for Generalized Automata.
  6. A Simple Data Structure for Maintaining a Discrete Probability Distribution.
  7. A symbolic-arithmetic for teaching double-black node removal in red-black trees.
  8. Acceleration of FM-index Queries Through Prefix-free Parsing.
  9. Adaptive Encoding Strategies for Erasing-Based Lossless Floating-Point Compression.
  10. Algorithms for Massive Data - Lecture Notes.
  11. An Algorithm for the Constrained Longest Common Subsequence and Substring Problem.
  12. An Algorithm for the Longest Common Subsequence and Substring Problem.
  13. An Efficient B-tree Implementation for Memory-Constrained Embedded Systems.
  14. Another virtue of wavelet forests?
  15. Approximate Cartesian Tree Matching: an Approach Using Swaps.
  16. Approximating Edit Distance in the Fully Dynamic Model.
  17. B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.
  18. Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching.
  19. CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions.
  20. Can You Solve Closest String Faster than Exhaustive Search?
  21. Chaining of Maximal Exact Matches in Graphs.
  22. Change a Bit to save Bytes: Compression for Floating Point Time-Series Data.
  23. Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space.
  24. Compressed Indexing for Consecutive Occurrences.
  25. Compressibility measures for two-dimensional data.
  26. Compressibility-Aware Quantum Algorithms on Strings.
  27. Computing SEQ-IC-LCS of Labeled Graphs.
  28. Computing all-vs-all MEMs in grammar-compressed text.
  29. Computing matching statistics on Wheeler DFAs.
  30. Counting occurrences of patterns in permutations.
  31. Critical exponent of binary words with few distinct palindromes.
  32. Deterministic 3SUM-Hardness.
  33. Dyck Words, Pattern Avoidance, and Automatic Sequences.
  34. Dynamic “Succincter”.
  35. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm.
  36. Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions.
  37. Dynamic Dictionary with Subconstant Wasted Bits per Key.
  38. Dynamic Dynamic Time Warping.
  39. Efficient Online String Matching through Linked Weak Factors.
  40. Efficient Parallel Output-Sensitive Edit Distance.
  41. Efficient Parameterized Pattern Matching in Sublinear Space.
  42. Efficient algorithms for enumerating maximal common subsequences of two strings.
  43. Engineering Rank/Select Data Structures for Big-Alphabet Strings.
  44. Enumerating all minimal hitting sets in polynomial total time.
  45. Erasing-based lossless compression method for streaming floating-point time series.
  46. Evaluating Regular Path Queries on Compressed Adjacency Matrices.
  47. Exact Shortest Paths with Rational Weights on the Word RAM.
  48. Fast and simple unrooted dynamic forests.
  49. Fast computation of approximate weak common intervals in multiple indeterminate strings.
  50. Faster Algorithms for Internal Dictionary Queries.
  51. Faster Algorithms for Text-to-Pattern Hamming Distances.
  52. Faster Compression of Deterministic Finite Automata.
  53. Faster Maximal Exact Matches with Lazy LCP Evaluation.
  54. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
  55. Faster Wavelet Trees with Quad Vectors.
  56. Finding Maximal Exact Matches in Graphs.
  57. Finding a reconfiguration sequence between longest increasing subsequences.
  58. Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data.
  59. Hierarchical Lowrank Arithmetic with Binary Compression.
  60. Learned Monotone Minimal Perfect Hashing.
  61. Linear Time Construction of Cover Suffix Tree and Applications.
  62. Linear Time Online Algorithms for Constructing Linear-size Suffix Trie.
  63. Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets.
  64. Linear-time computation of generalized minimal absent words for multiple strings.
  65. Locally consistent decomposition of strings with applications to edit distance sketching.
  66. Longest Common Prefix Arrays for Succinct k-Spectra.
  67. Longest Common Subsequence with Gap Constraints.
  68. Longest Common Substring and Longest Palindromic Substring in Õ(√n) Time.
  69. Lossy Compressor preserving variant calling through Extended BWT.
  70. Maintaining the cycle structure of dynamic permutations.
  71. Matching Patterns with Variables Under Simon’s Congruence.
  72. Matching Statistics speed up BWT construction.
  73. Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings.
  74. Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization.
  75. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
  76. On Sensitivity of Compact Directed Acyclic Word Graphs.
  77. On arch factorization and subword universality for words and compressed words.
  78. On the Maximal Independent Sets of k-mers with the Edit Distance.
  79. On the k-Hamming and k-Edit Distances.
  80. On the piecewise complexity of words and periodic words.
  81. Optimal Algorithms for Bounded Weighted Edit Distance.
  82. Optimal Heaviest Induced Ancestors.
  83. Optimal LZ-End Parsing is Hard.
  84. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.
  85. Optimal Square Detection Over General Alphabets.
  86. Optimal Wheeler Language Recognition.
  87. Optimal-Hash Exact String Matching Algorithms.
  88. Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph.
  89. Optimization with pattern-avoiding input.
  90. Order-Preserving Squares in Strings.
  91. Pairwise sequence alignment with block and character edit operations.
  92. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions.
  93. Pb-Hash: Partitioned b-bit Hashing.
  94. Phylogenetic tree distance computation over succinct representations.
  95. Prefix Sorting DFAs: a Recursive Algorithm.
  96. Prefix-free graphs and suffix array construction in sublinear space.
  97. Prefixes of the Fibonacci word.
  98. Quantum Circuits for Fixed Substring Matching Problems.
  99. Random Wheeler Automata.
  100. Range Entropy Queries and Partitioning.
  101. Rank and Select on Degenerate Strings.
  102. Ranking and Unranking k-subsequence universal words.
  103. Ranking and unranking bordered and unbordered words.
  104. Reconstructing words using queries on subwords or factors.
  105. Repetition factorization of automatic sequences.
  106. Rudin-Shapiro Sums Via Automata Theory and Logic.
  107. Searching 2D-Strings for Matching Frames.
  108. SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree.
  109. Selective Run-Length Encoding.
  110. Shorter and faster than Sort3AlphaDev.
  111. Size-constrained Weighted Ancestors with Applications.
  112. Sketching and Streaming for Dictionary Compression.
  113. Sliding Window String Indexing in Streams.
  114. Sliding suffix trees simplified.
  115. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares.
  116. Smallest and Largest Block Palindrome Factorizations.
  117. Some Fibonacci-Related Sequences.
  118. Sorting Finite Automata via Partition Refinement.
  119. Space-Efficient Data Structures for Polyominoes and Bar Graphs.
  120. Space-time Trade-offs for the LCP Array of Wheeler DFAs.
  121. Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast.
  122. Storing a Trie with Compact and Predictable Space.
  123. Streaming k-edit approximate pattern matching via string decomposition.
  124. String attractors of fixed points of k-bonacci-like morphisms.
  125. Structure and growth of R-bonacci words.
  126. Sturmian and infinitely desubstitutable words accepted by an ω-automaton.
  127. Subcubic algorithm for (Unweighted) Unrooted Tree Edit Distance.
  128. Succinct Data Structure for Graphs with d-Dimensional t-Representation.
  129. Succinct Planar Encoding with Minor Operations.
  130. Suffixient Sets.
  131. Sum-of-Local-Effects Data Structures for Separable Graphs.
  132. The 2-Attractor Problem is NP-Complete.
  133. The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing.
  134. The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold.
  135. The Longest Subsequence-Repeated Subsequence Problem.
  136. The Many Qualities of a New Directly Accessible Compression Scheme.
  137. The analogue of overlap-freeness for the Fibonacci morphism.
  138. The analogue of overlap-freeness for the period-doubling sequence.
  139. Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.
  140. Two-dimensional Dyck words.
  141. Weighted Edit Distance Computation: Strings, Trees and Dyck.
  142. Wheeler maps.

Comput. Sci. Rev. 2023

  1. Abelian combinatorics on words: A survey.

IEEE Trans. Commun. 2023

  1. Reconstruction of Sets of Strings From Prefix/Suffix Compositions.

IEEE Trans. Inf. Theory 2023

  1. Toward a Definitive Compressibility Measure for Repetitive Sequences.

IEEE Trans. Knowl. Data Eng. 2023

  1. Bidirectional String Anchors for Improved Text Indexing and Top-$K$ Similarity Search.

Inf. Comput. 2023

  1. Compact representations of spatial hierarchical structures with support for topological queries.
  2. Sensitivity of string compressors and repetitiveness measures.

Inf. Process. Lett. 2023

  1. Longest bordered and periodic subsequences.
  2. Order-preserving pattern matching with scaling.
  3. Space-efficient Huffman codes revisited.

Int. J. Comput. Geom. Appl. 2023

  1. Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries.

J. Comput. Biol. 2023

  1. Efficient Colored de Bruijn Graph for Indexing Reads.

Multim. Tools Appl. 2023

  1. Scalable thread based index construction using wavelet tree.

Proc. VLDB Endow. 2023

  1. Text Indexing for Long Patterns: Anchors are All you Need.

Theor. Comput. Sci. 2023

  1. Compact suffix automata representations for searching long patterns.
  2. Improved characters distance sampling for online and offline text searching.
  3. Linear-space S-table algorithms for the longest common subsequence problem.
  4. Maximal degenerate palindromes with gaps and mismatches.

CPM 2022

  1. Bi-Directional r-Indexes.
  2. Longest Palindromic Substring in Sublinear Time.
  3. The Dynamic k-Mismatch Problem.

DCC 2022

  1. A Benchmark of Entropy Coders for the Compression of Genome Sequencing Data.
  2. Burrows-Wheeler Transform on Purely Morphic Words.
  3. CSTs for Terabyte-Sized Data.
  4. Compressing the Tree of Canonical Huffman Coding.
  5. Computing Lexicographic Parsings.
  6. Computing Matching Statistics on Repetitive Texts.
  7. Converting RLBWT to LZ77 in smaller space.
  8. FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns.
  9. Fast Coding of Haar Wavelet Trees.
  10. Graphs can be succinctly indexed for pattern matching in $O(\vert E\vert ^{2}+\vert V\vert ^{5/2})$ time.
  11. HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances.
  12. Linear-time Minimization of Wheeler DFAs.
  13. Lower Bounds for Lexicographical DFS Data Structures.
  14. On Dynamic Bitvector Implementations.
  15. On different variants of the Burrows-Wheeler-Transform of string collections.
  16. RLBWT Tricks.
  17. Selective Weighted Adaptive Coding.
  18. Simple Worst-Case Optimal Adaptive Prefix-Free Coding.
  19. Succinct Data Structure for Path Graphs.
  20. x3: Lossless Data Compressor.

DLT 2022

  1. Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words.
  2. Prefix Palindromic Length of the Sierpinski Word.

ESA 2022

  1. An Improved Algorithm for Finding the Shortest Synchronizing Words.
  2. Approximate Circular Pattern Matching.
  3. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
  4. Computing NP-Hard Repetitiveness Measures via MAX-SAT.
  5. Distinct Elements in Streams: An Algorithm for the (Text) Book.
  6. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold.
  7. Lyndon Arrays Simplified.
  8. Simple Worst-Case Optimal Adaptive Prefix-Free Coding.

FOCS 2022

  1. Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
  2. Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices.
  3. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
  4. Online List Labeling: Breaking the log2n Barrier.
  5. Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract).
  6. Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.

HCVS/VPT@ETAPS 2022

  1. Reversible Programming: A Case Study of Two String-Matching Algorithms.

ICALP 2022

  1. An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space.
  2. Fully Functional Parameterized Suffix Trees in Compact Space.
  3. Galloping in Fast-Growth Natural Merge Sorts.
  4. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.
  5. Improved Sublinear-Time Edit Distance for Preprocessed Strings.
  6. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds.

ISAAC 2022

  1. Computing Palindromes on a Trie in Linear Time.
  2. External-Memory Dictionaries with Worst-Case Update Cost.
  3. On the Complexity of Tree Edit Distance with Variables.
  4. Simple Order-Isomorphic Matching Index with Expected Compact Space.
  5. Succinct List Indexing in Optimal Time.

ISBRA 2022

  1. Optimal Sequence Alignment to ED-Strings.

IWCIA 2022

  1. Lyndon Partial Words and Arrays with Applications.

IWOCA 2022

  1. Computing Longest (Common) Lyndon Subsequences.
  2. Linear Time Construction of Indexable Elastic Founder Graphs.
  3. Practical Space-Efficient Index for Structural Pattern Matching.
  4. Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings.
  5. Space-Efficient B Trees via Load-Balancing.

LATIN 2022

  1. Elastic-Degenerate String Matching with 1 Error.
  2. Near-Optimal Search Time in δ-Optimal Space.
  3. Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries.
  4. String Attractors and Infinite Words.

MFCS 2022

  1. On Uniformization in the Full Binary Tree.
  2. Streaming Word Problems.

NCMA 2022

  1. Combinatorial Algorithms for Subsequence Matching: A Survey.

SEA 2022

  1. Computing Maximal Unique Matches with the r-Index.
  2. RLBWT Tricks.

SODA 2022

  1. A Lower Bound for the n-queens Problem.
  2. An Improved Algorithm for The k-Dyck Edit Distance Problem.
  3. An Upper Bound and Linear-Space Queries on the LZ-End Parsing.
  4. Average Sensitivity of Dynamic Programming.
  5. Enumerating k-SAT functions.
  6. How Compression and Approximation Affect Efficiency in String Distance Measures.
  7. How many Clusters? - An algorithmic answer.
  8. Pattern Matching on Grammar-Compressed Strings in Linear Time.
  9. Selectable Heaps and Optimal Lazy Search Trees.
  10. Simulating a stack using queues.
  11. Splay trees on trees.
  12. Streaming Regular Expression Membership and Pattern Matching.

SOSA 2022

  1. Faster Exponential Algorithm for Permutation Pattern Matching.
  2. Simpler Adjacency Labeling for Planar Graphs with B-Trees.

SPIRE 2022

  1. KATKA: A KRAKEN-Like Tool with k Given at Query Time.
  2. Matching Patterns with Variables Under Edit Distance.
  3. Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions.

STACS 2022

  1. Existential Definability over the Subword Ordering.
  2. Probabilistic vs Deterministic Gamblers.

STOC 2022

  1. Almost-optimal sublinear-time edit distance in the low distance regime.
  2. Dynamic suffix array with polylogarithmic queries and updates.
  3. Explicit binary tree codes with sub-logarithmic size alphabet.
  4. Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios.
  5. On the optimal time/space tradeoff for hash tables.

SWAT 2022

  1. Predecessor on the Ultra-Wide Word RAM.
  2. Unit-Disk Range Searching and Applications.

WABI 2022

  1. Eulertigs: Minimum Plain Text Representation of k-mer Sets Without Repetitions in Linear Time.
  2. Fast Gapped k-mer Counting with Subdivided Multi-Way Bucketed Cuckoo Hash Tables.
  3. Haplotype Threading Using the Positional Burrows-Wheeler Transform.
  4. Locality-Sensitive Bucketing Functions for the Edit Distance.
  5. On Weighted k-mer Dictionaries.
  6. Prefix-Free Parsing for Building Large Tunnelled Wheeler Graphs.
  7. Suffix Sorting via Matching Statistics.
  8. Toward Optimal Fingerprint Indexing for Large Scale Genomics.
  9. phyBWT: Alignment-Free Phylogeny via eBWT Positional Clustering.

ACM Comput. Surv. 2022

  1. Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures.
  2. Indexing Highly Repetitive String Collections, Part II: Compressed Indexes.

ACM J. Exp. Algorithmics 2022

  1. Grammar Compression by Induced Suffix Sorting.

ACM Trans. Algorithms 2022

  1. A Simple Algorithm for Optimal Search Trees with Two-way Comparisons.

Algorithmica 2022

  1. A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.
  2. Adaptive Succinctness.
  3. Computing Minimal Unique Substrings for a Sliding Window.
  4. Efficient Computation of Sequence Mappability.
  5. Fast and Longest Rollercoasters.
  6. Space Efficient Merging of de Bruijn Graphs and Wheeler Graphs.
  7. Streaming Dictionary Matching with Mismatches.

Algorithms Mol. Biol. 2022

  1. Space-efficient representation of genomic k-mer count tables.

Appl. Soft Comput. 2022

  1. Graph search and variable neighborhood search for finding constrained longest common subsequences in artificial and real gene sequences.

Bioinform. 2022

  1. Fast and compact matching statistics analytics.

CoRR 2022

  1. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time.
  2. A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits.
  3. A New Class of String Transformations for Compressed Text Indexing.
  4. A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion.
  5. A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees.
  6. A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence.
  7. A fast and simple O(z log n)-space index for finding approximately longest common substrings.
  8. A nearly optimal randomized algorithm for explorable heap selection.
  9. Abelian Combinatorics on Words: a Survey.
  10. Algorithm to derive shortest edit script using Levenshtein distance algorithm.
  11. Almost optimal searching of maximal subrepetitions in a word.
  12. An Algorithmic Bridge Between Hamming and Levenshtein Distances.
  13. An Improved Algorithm for Finding the Shortest Synchronizing Words.
  14. An n Hk-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers.
  15. Antisquares and Critical Exponents.
  16. Approximate Circular Pattern Matching.
  17. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.
  18. Approximating binary longest common subsequence in near-linear time.
  19. Asymptotic bounds for the number of closed and privileged words.
  20. Augmented Thresholds for MONI.
  21. Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev.
  22. Balancing Run-Length Straight-Line Programs.
  23. Binary codes that do not preserve primitivity.
  24. Bounds and Estimates on the Average Edit Distance.
  25. CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams.
  26. Cache-Oblivious Representation of B-Tree Structures.
  27. Co-lexicographically ordering automata and regular languages. Part I.
  28. Comparing Two Counting Methods for Estimating the Probabilities of Strings.
  29. Complement Avoidance in Binary Words.
  30. Computing MEMs on Repetitive Text Collections.
  31. Computing Maximal Unique Matches with the r-index.
  32. Computing NP-hard Repetitiveness Measures via MAX-SAT.
  33. Computing all-vs-all MEMs in run-length encoded collections of HiFi reads.
  34. Computing maximal generalized palindromes.
  35. Computing palindromes on a trie in linear time.
  36. Computing the Parameterized Burrows-Wheeler Transform Online.
  37. Computing the optimal BWT of very large string collections.
  38. Concurrent Size.
  39. Constant-delay enumeration for SLP-compressed documents.
  40. Convergence of the number of period sets in strings.
  41. Cut-Down de Bruijn Sequences.
  42. Designing a parallel suffix sort.
  43. Double-Ended Palindromic Trees: A Linear-Time Data Structure and Its Applications.
  44. Dynamic data structures for parameterized string problems.
  45. Efficient Algorithms for Sorting in Trees.
  46. Efficient Construction of the BWT for Repetitive Text Using String Compression.
  47. Elastic-Degenerate String Matching with 1 Error.
  48. Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors.
  49. Engineering faster double-array Aho-Corasick automata.
  50. External-memory dictionaries with worst-case update cost.
  51. Fast Circular Pattern Matching.
  52. Fast Exact String to D-Texts Alignments.
  53. Fast detection of specific fragments against a set of sequences.
  54. Faster Min-Plus Product for Monotone Instances.
  55. Faster Pattern Matching under Edit Distance.
  56. Gapped String Indexing in Subquadratic Space and Sublinear Query Time.
  57. Hierarchical Relative Lempel-Ziv Compression.
  58. High Performance Construction of RecSplit Based Minimal Perfect Hash Functions.
  59. Hinted Dictionaries: Efficient Functional Ordered Sets and Maps.
  60. Implementing the Comparison-Based External Sort.
  61. Improved Sublinear-Time Edit Distance for Preprocessed Strings.
  62. Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices.
  63. Inferring strings from position heaps in linear time.
  64. Internal Longest Palindrome Queries in Optimal Time.
  65. KATKA: A KRAKEN-like tool with k given at query time.
  66. L-systems for Measuring Repetitiveness.
  67. Learning Augmented Binary Search Trees.
  68. Lie Complexity of Sturmian Words.
  69. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds.
  70. Locality-Preserving Minimal Perfect Hashing of k-mers.
  71. Longest Common Subsequence: Tabular vs. Closed-Form Equation Computation of Subsequence Probability.
  72. Lower Bounds for Sorting 16, 17, and 18 Elements.
  73. MARIA: Multiple-alignment r-index with aggregation.
  74. Matching Patterns with Variables Under Edit Distance.
  75. Maximal Closed Substrings.
  76. Merging Sorted Lists of Similar Strings.
  77. Multiway Powersort.
  78. Near-Optimal Search Time in δ-Optimal Space.
  79. New Parallel Order Maintenance Data Structure.
  80. Note on a Fibonacci Parity Sequence.
  81. On extended boundary sequences of morphic and Sturmian words.
  82. On the Optimisation of the GSACA Suffix Array Construction Algorithm.
  83. On the Power of Learning-Augmented BSTs.
  84. On the Practical Power of Automata in Pattern Matching.
  85. Onesweep: A Faster Least Significant Digit Radix Sort for GPUs.
  86. Online List Labeling: Breaking the log2n Barrier.
  87. Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions.
  88. Optimal resizable arrays.
  89. Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.
  90. PalFM-index: FM-index for Palindrome Pattern Matching.
  91. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  92. Pareto Optimal Compression of Genomic Dictionaries, with or without Random Access in Main Memory.
  93. Pattern matching algorithms in Blockchain for network fees reduction.
  94. Pattern matching under DTW distance.
  95. Polyominoes and graphs built from Fibonacci words.
  96. Practical KMP/BM Style Pattern-Matching on Indeterminate Strings.
  97. Prefix Filter: Practically and Theoretically Better Than Bloom.
  98. Prefix-free parsing for building large tunnelled Wheeler graphs.
  99. Properties of a Ternary Infinite Word.
  100. Pseudoperiodic Words and a Question of Shevelev.
  101. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching.
  102. Quantum jumbled pattern matching.
  103. Reduction ratio of the IS-algorithm: worst and random cases.
  104. Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings.
  105. SicHash - Small Irregular Cuckoo Tables for Perfect Hashing.
  106. Simple O(1) Query Algorithm for Level Ancestors.
  107. Simpler and Better Cardinality Estimators for HyperLogLog and PCSA.
  108. Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching.
  109. Some Results on Digital Segments and Balanced Words.
  110. Sorting Genomes by Prefix Double-Cut-and-Joins.
  111. Space-Efficient STR-IC-LCS Computation.
  112. Space-efficient RLZ-to-LZ77 conversion.
  113. Space-efficient conversions from SLPs.
  114. Space-efficient data structure for next/previous larger/smaller value queries.
  115. Speeding Hirschberg Algorithm for Sequence Alignment.
  116. Splay Top Trees.
  117. String Attractors and Infinite Words.
  118. String Covering: A Survey.
  119. String Rearrangement Inequalities and a Total Order Between Primitive Words.
  120. Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems.
  121. Subsequences in Bounded Ranges: Matching and Analysis Problems.
  122. Substring Complexities on Run-length Compressed Strings.
  123. Suffix sorting via matching statistics.
  124. Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems.
  125. Taming Large-Scale Genomic Analyses via Sparsified Genomics.
  126. Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform.
  127. The Complexity of the Co-Occurrence Problem.
  128. Theoretical analysis of edit distance algorithms: an applied perspective.
  129. Tight Bounds for Monotone Minimal Perfect Hashing.
  130. Transcoding Unicode Characters with AVX-512 Instructions.
  131. Trie-Compressed Intersectable Sets.
  132. Unbalancing Binary Trees.
  133. Walking on Words.
  134. Watson-Crick conjugates of words and languages.
  135. Which arithmetic operations can be performed in constant time in the RAM model with addition?
  136. Word Equations in Synergy with Regular Constraints (Technical Report).

Commun. ACM 2022

  1. Resolution of the burrows-wheeler transform conjecture.
  2. The compression power of the BWT: technical perspective.

IEEE Access 2022

  1. Compressing and Querying Integer Dictionaries Under Linearities and Repetitions.

Inf. Comput. 2022

  1. A periodicity lemma for partial words.
  2. Efficient representation and counting of antipower factors in words.
  3. LZRR: LZ77 parsing with right reference.
  4. Order-preserving pattern matching indeterminate strings.
  5. c-trie++: A dynamic trie tailored for fast prefix searches.

Inf. Process. Lett. 2022

  1. All-pairs suffix/prefix in optimal time using Aho-Corasick space.
  2. Palindromic trees for a sliding window and its applications.

Inf. Retr. J. 2022

  1. Applying burst-tries for error-tolerant prefix search.

J. Comput. Biol. 2022

  1. Finding Maximal Exact Matches Using the r-Index.
  2. MONI: A Pangenomic Index for Finding Maximal Exact Matches.

J. Comput. Sci. 2022

  1. A sorting algorithm based on ordered block insertions.

SN Comput. Sci. 2022

  1. Combining Forward Compression with PPM.
  2. Correction to: Graph Compression for Adjacency-Matrix Multiplication.
  3. Graph Compression for Adjacency-Matrix Multiplication.

Theor. Comput. Sci. 2022

  1. A data structure for substring-substring LCS length queries.
  2. An efficient algorithm for the longest common palindromic subsequence problem.
  3. Combinatorics of minimal absent words for a sliding window.
  4. Efficient and compact representations of some non-canonical prefix-free codes.
  5. In-place initializable arrays.
  6. Internal shortest absent word queries in constant time and linear space.
  7. Parameterized DAWGs: Efficient constructions and bidirectional pattern searches.
  8. Partial sums on the ultra-wide word RAM.

Theory Comput. Syst. 2022

  1. Factorizing Strings into Repetitions.

ALENEX 2021

  1. A “Learned” Approach to Quicken and Compress Rank/Select Dictionaries.
  2. PFP Compressed Suffix Trees.

CIAA 2021

  1. Approximate Hashing for Bioinformatics.

CIAC 2021

  1. The Parameterized Suffix Tray.

COCOA 2021

  1. Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs.

CPM 2021

  1. A Compact Index for Cartesian Tree Matching.
  2. A Fast and Small Subsampled R-Index.
  3. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs.
  4. AWLCO: All-Window Length Co-Occurrence.
  5. An Invertible Transform for Efficient String Matching in Labeled Digraphs.
  6. Compressed Weighted de Bruijn Graphs.
  7. Computing Covers of 2D-Strings.
  8. Computing Edit Distance (Invited Talk).
  9. Constructing Strings Avoiding Forbidden Substrings.
  10. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time.
  11. Data Structures for Categorical Path Counting Queries.
  12. Disorders and Permutations.
  13. Efficient Algorithms for Counting Gapped Palindromes.
  14. Gapped Indexing for Consecutive Occurrences.
  15. Internal Shortest Absent Word Queries.
  16. On-Line Pattern Matching on D-Texts (Invited Talk).
  17. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance.
  18. Optimal Construction of Hierarchical Overlap Graphs.
  19. R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space.
  20. Ranking Bracelets in Polynomial Time.
  21. Repetitions in Strings: A “Constant” Problem (Invited Talk).
  22. String Sanitization Under Edit Distance: Improved and Generalized.
  23. The Longest Run Subsequence Problem: Further Complexity Results.
  24. The k-Mappability Problem Revisited.
  25. Weighted Ancestors in Suffix Trees Revisited.

DCC 2021

  1. A Disk-Based Index for Trajectories with an In-Memory Compressed Cache.
  2. A grammar compressor for collections of reads with applications to the construction of the BWT.
  3. Accelerating Knuth-Morris-Pratt String Matching over LZ77 Compressed Text.
  4. Approximate Hashing for Bioinformatics.
  5. Backward Weighted Coding.
  6. Compact Representation of Spatial Hierarchies and Topological Relationships.
  7. DZip: improved general-purpose loss less compression based on novel neural network modeling.
  8. Efficiently Merging r-indexes.
  9. End-to-End optimized image compression for machines, a study.
  10. Improved LZ77 Compression.
  11. Improving Run Length Encoding by Preprocessing.
  12. Neural Networks Optimally Compress the Sawbridge.
  13. On Elias-Fano for Rank Queries in FM-Indexes.
  14. On Random Editing in LZ-End.
  15. PHONI: Streamed Matching Statistics with Multi-Genome References.
  16. Parallel Processing of Grammar Compression.
  17. Smaller RLZ-Compressed Suffix Arrays.
  18. Succinct Data Structures for Small Clique-Width Graphs.
  19. Succinct representations of Intersection Graphs on a Circle.
  20. ndzip: A High-Throughput Parallel Lossless Compressor for Scientific Data.

DLT 2021

  1. Upper Bounds on Distinct Maximal (Sub-)Repetitions in Compressed Strings.
  2. Weighted Prefix Normal Words: Mind the Gap.

ESA 2021

  1. Bidirectional String Anchors: A New String Sampling Mechanism.
  2. Compression by Contracting Straight-Line Programs.
  3. Dynamic Colored Orthogonal Range Searching.
  4. Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing.
  5. Faster Algorithms for Longest Common Substring.
  6. Hypersuccinct Trees - New Universal Tree Source Codes for Optimal Compressed Tree Data Structures and Range Minima.
  7. Lyndon Words Accelerate Suffix Sorting.
  8. Minimum Common String Partition: Exact Algorithms.
  9. Space Efficient Two-Dimensional Orthogonal Colored Range Counting.

FOCS 2021

  1. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance.
  2. Small-space and streaming pattern matching with $k$ edits.

ICALP 2021

  1. A Linear-Time n0.4-Approximation for Longest Common Subsequence.
  2. An Almost Optimal Edit Distance Oracle.
  3. Analysis of Smooth Heaps and Slim Heaps.
  4. Faster Algorithms for Bounded Tree Edit Distance.
  5. Fine-Grained Hardness for Edit Distance to a Fixed Sequence.
  6. Improved Approximation for Longest Common Subsequence over Small Alphabets.
  7. LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching.
  8. Linear Time Runs Over General Ordered Alphabets.
  9. New Sublinear Algorithms and Lower Bounds for LIS Estimation.
  10. Optimal-Time Queries on BWT-Runs Compressed Indexes.
  11. Sorting Short Integers.
  12. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.

ISAAC 2021

  1. Algorithms and Complexity on Indexing Elastic Founder Graphs.
  2. Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space.
  3. Pattern Masking for Dictionary Matching.
  4. Repetition- and Linearity-Aware Rank/Select Dictionaries.
  5. Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees.
  6. Streaming Pattern Matching (Invited Talk).

IWOCA 2021

  1. The Tandem Duplication Distance Problem Is Hard over Bounded Alphabets.

LATA 2021

  1. Cadences in Grammar-Compressed Strings.
  2. Succinct Representations for (Non)Deterministic Finite Automata.

MFCS 2021

  1. Matching Patterns with Variables Under Hamming Distance.

RP 2021

  1. Absent Subsequences in Words.

SEA 2021

  1. Document Retrieval Hacks.
  2. Engineering Predecessor Data Structures for Dynamic Integer Sets.

SODA 2021

  1. A Lower Bound for Dynamic Fractional Cascading.
  2. Beating the probabilistic lower bound on perfect hashing.
  3. Competitive Data-Structure Dynamization.
  4. New Data Structures for Orthogonal Range Reporting and Range Minima Queries.
  5. On Indexing and Compressing Finite Automata.
  6. On Locating Paths in Compressed Tries.
  7. Optimal Oblivious Priority Queues.

SOFSEM 2021

  1. A Normal Sequence Compressed by PPM* But Not by Lempel-Ziv 78.
  2. Blocksequences of k-local Words.
  3. Novel Results on the Number of Runs of the Burrows-Wheeler-Transform.

SOSA 2021

  1. Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets.
  2. Soft Sequence Heaps.

SPIRE 2021

  1. A Separation of γ and b via Thue-Morse Words.
  2. All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent.
  3. An LMS-Based Grammar Self-index with Local Consistency Properties.
  4. Computing the Original eBWT Faster, Simpler, and with Less Memory.
  5. Exploiting Pseudo-locality of Interchange Distance.
  6. Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree.
  7. Grammar Index by Induced Suffix Sorting.
  8. Improved Topic Modeling in Twitter Through Community Pooling.
  9. Longest Common Rollercoasters.
  10. Lower Bounds for the Number of Repetitions in 2D Strings.
  11. Minimal Unique Palindromic Substrings After Single-Character Substitution.
  12. On Stricter Reachable Repetitiveness Measures.
  13. On the Approximation Ratio of LZ-End to LZ77.
  14. Permutation-Constrained Common String Partitions with Applications.
  15. Position Heaps for Cartesian-Tree Matching on Strings and Tries.
  16. String Covers of a Tree.
  17. TSXor: A Simple Time Series Compression Algorithm.
  18. Unicode at Gigabytes per Second.
  19. findere: Fast and Precise Approximate Membership Query.
  20. r-Indexing the eBWT.

STACS 2021

  1. Efficiently Testing Simon’s Congruence.
  2. Finding an Optimal Alphabet Ordering for Lyndon Factorization Is Hard.
  3. The Edit Distance to k-Subsequence Universality.

STOC 2021

  1. Fully dynamic approximation of LIS in polylogarithmic time.
  2. Improved dynamic algorithms for longest increasing subsequence.
  3. Subcubic algorithms for Gomory-Hu tree in unweighted graphs.

WABI 2021

  1. Compressing and Indexing Aligned Readsets.
  2. Space-Efficient Representation of Genomic k-Mer Count Tables.

ACM Comput. Surv. 2021

  1. Predecessor Search.

ACM J. Exp. Algorithmics 2021

  1. Engineering Practical Lempel-Ziv Tries.

ACM Trans. Algorithms 2021

  1. Optimal Substring Equality Queries with Applications to Sparse Text Indexing.
  2. Optimal-Time Dictionary-Compressed Indexes.

ACM Trans. Knowl. Discov. Data 2021

  1. Combinatorial Algorithms for String Sanitization.

Algorithmica 2021

  1. Internal Dictionary Matching.
  2. Range Majorities and Minorities in Arrays.
  3. Top Tree Compression of Tries.

Algorithms 2021

  1. Compressed Communication Complexity of Hamming Distance.
  2. Lempel-Ziv Parsing for Sequences of Blocks.
  3. Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees.
  4. Re-Pair in Small Space.
  5. Reversed Lempel-Ziv Factorization with Suffix Trees.
  6. Subpath Queries on Compressed Graphs: A Survey.

Bioinform. 2021

  1. Accurate spliced alignment of long RNA sequencing reads.

Comput. J. 2021

  1. Smaller Compressed Suffix Arrays†.

IEEE Trans. Inf. Theory 2021

  1. On the Approximation Ratio of Ordered Parsings.
  2. The Smallest Grammar Problem Revisited.

Inf. Comput. 2021

  1. Efficient pattern matching in elastic-degenerate strings.
  2. On the cost of unsuccessful searches in search trees with two-way comparisons.
  3. Wheeler languages.

Inf. Process. Lett. 2021

  1. Longest previous overlapping factor array.

Int. J. Geogr. Inf. Sci. 2021

  1. An index for moving objects with constant-time access to their compressed trajectories.

J. Comput. Syst. Sci. 2021

  1. Block trees.
  2. Circular pattern matching with k mismatches.
  3. Grammar-compressed indexes with logarithmic search time.

J. Inf. Process. 2021

  1. Towards a Complete Perspective on Labeled Tree Indexing: New Size Bounds, Efficient Constructions, and Beyond.

J. King Saud Univ. Comput. Inf. Sci. 2021

  1. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications.

Theor. Comput. Sci. 2021

  1. Adaptive learning of compressible strings.
  2. Computing longest palindromic substring after single-character or block-wise edits.
  3. Efficiently computing runs on a trie.
  4. Maximal unbordered factors of random strings.
  5. Space-efficient construction of compressed suffix trees.
  6. Tight upper and lower bounds on suffix tree breadth.
  7. When a dollar makes a BWT.

Theory Comput. Syst. 2021

  1. Constructing Antidictionaries of Long Texts in Output-Sensitive Space.

ALENEX 2020

  1. Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory.
  2. Engineering Top-Down Weight-Balanced Trees.
  3. RecSplit: Minimal Perfect Hashing via Recursive Splitting.
  4. Reverse-Safe Data Structures for Text Indexing.

APPROX-RANDOM 2020

  1. Improved Circular k-Mismatch Sketches.
  2. Lp Pattern Matching in a Stream.

BCB 2020

  1. SMART: SuperMaximal approximate repeats tool.

CPM 2020

  1. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk).
  2. Approximating Longest Common Substring with k mismatches: Theory and Practice.
  3. Approximating Text-To-Pattern Distance via Dimensionality Reduction.
  4. Chaining with Overlaps Revisited.
  5. Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP.
  6. Counting Distinct Patterns in Internal Dictionary Matching.
  7. DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.
  8. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.
  9. Double String Tandem Repeats.
  10. Dynamic String Alignment.
  11. Efficient Tree-Structured Categorical Retrieval.
  12. FM-Index Reveals the Reverse Suffix Array.
  13. Faster Binary Mean Computation Under Dynamic Time Warping.
  14. Finding the Anticover of a String.
  15. Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms.
  16. In-Place Bijective Burrows-Wheeler Transforms.
  17. Longest Common Subsequence on Weighted Sequences.
  18. On Extensions of Maximal Repeats in Compressed Strings.
  19. On Indeterminate Strings Matching.
  20. On Two Measures of Distance Between Fully-Labelled Trees.
  21. Parameterized Algorithms for Matrix Completion with Radius Constraints.
  22. String Factorizations Under Various Collision Constraints.
  23. String Sanitization Under Edit Distance.
  24. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions.
  25. Text Indexing and Searching in Sublinear Time.
  26. The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
  27. Time-Space Tradeoffs for Finding a Long Common Substring.
  28. Unary Words Have the Smallest Levenshtein k-Neighbourhoods.
  29. k-Approximate Quasiperiodicity under Hamming and Edit Distance.

CSR 2020

  1. Optimal Skeleton Huffman Trees Revisited.

CiE 2020

  1. Faster Online Computation of the Succinct Longest Previous Factor Array.

DCC 2020

  1. Approximating Optimal Bidirectional Macro Schemes.
  2. Bitvectors with Runs and the Successor/Predecessor Problem.
  3. Compact Representation of Graphs with Small Bandwidth and Treedepth.
  4. Compressing and Randomly Accessing Sequences (note).
  5. Decompressing Lempel-Ziv Compressed Text.
  6. Edge Minimization in de Bruijn Graphs.
  7. Grammar Compression with Probabilistic Context-Free Grammar.
  8. On Dynamic Succinct Graph Representations.
  9. Pattern Search in Grammar-Compressed Graphs.
  10. Practical Repetition-Aware Grammar Compression.
  11. Re-Pair in Small Space.
  12. Revisiting Compact RDF Stores Based on k2-Trees.
  13. Semantrix: A Compressed Semantic Matrix.
  14. Towards Better Compressed Representations.
  15. c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches.

DLT 2020

  1. Scattered Factor-Universality of Words.

ESA 2020

  1. Efficient Computation of 2-Covers of a String.
  2. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing.
  3. New Binary Search Tree Bounds via Geometric Inversions.
  4. On the Complexity of BWT-Runs Minimization via Alphabet Reordering.
  5. Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
  6. The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance.
  7. The Number of Repetitions in 2D-Strings.

Euro-Par 2020

  1. LCP-Aware Parallel String Sorting.

FOCS 2020

  1. Edit Distance in Near-Linear Time: it’s a Constant Factor.
  2. Faster Approximate Pattern Matching: A Unified Approach.
  3. Lazy Search Trees.
  4. On One-way Functions and Kolmogorov Complexity.
  5. Resolution of the Burrows-Wheeler Transform Conjecture.
  6. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.

FSTTCS 2020

  1. String Indexing for Top-k Close Consecutive Occurrences.

ICALP 2020

  1. Dynamic Longest Common Substring in Polylogarithmic Time.
  2. Space Efficient Construction of Lyndon Arrays in Linear Time.

ICDT 2020

  1. Optimal Joins Using Compact Data Structures.

ISAAC 2020

  1. A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  2. A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.
  3. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs.
  4. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees.
  5. Efficient Labeling for Reachability in Directed Acyclic Graphs.
  6. Enumerating Range Modes.
  7. Random Access in Persistent Strings.
  8. Update Query Time Trade-Off for Dynamic Suffix Arrays.

ITCS 2020

  1. Unexpected Power of Random Strings.

IWOCA 2020

  1. Optimal In-place Algorithms for Basic Graph Problems.

LATA 2020

  1. Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words.
  2. On Collapsing Prefix Normal Words.

LATIN 2020

  1. Batched Predecessor and Sorting with Size-Priced Information in External Memory.
  2. On the Collection of Fringe Subtrees in Random Binary Trees.
  3. Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries.
  4. Towards a Definitive Measure of Repetitiveness.

SEA 2020

  1. Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences.
  2. Fast and Simple Compact Hashing via Bucketing.
  3. Indexing Compressed Text: A Tale of Time and Space (Invited Talk).
  4. Pattern Discovery in Colored Strings.
  5. Zipping Segment Trees.

SODA 2020

  1. A Lower Bound for Jumbled Indexing.
  2. Better Data Structures for Colored Orthogonal Range Reporting.
  3. Combinatorial generation via permutation languages.
  4. Competitive Online Search Trees on Trees.
  5. Improved Algorithms for Edit Distance and LCS: Beyond Worst Case.
  6. Locally Consistent Parsing for Text Indexing in Small Space.
  7. Reducing approximate Longest Common Subsequence to approximate Edit Distance.
  8. Regular Languages meet Prefix Sorting.

SOFSEM 2020

  1. Fast Indexes for Gapped Pattern Matching.
  2. Faster STR-EC-LCS Computation.
  3. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window.
  4. Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching.

SOSA 2020

  1. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort.

SPIRE 2020

  1. A Comparison of Empirical Tree Entropies.
  2. Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction.
  3. An Efficient Elastic-Degenerate Text Index? Not Likely.
  4. Approximating the Anticover of a String.
  5. Computing Covers Under Substring Consistent Equivalence Relations.
  6. Contextual Pattern Matching.
  7. Efficient Construction of Hierarchical Overlap Graphs.
  8. Efficient Enumeration of Distinct Factors Using Package Representations.
  9. Internal Quasiperiod Queries.
  10. Longest Square Subsequence Problem Revisited.
  11. Lyndon Words, the Three Squares Lemma, and Primitive Squares.
  12. Measuring Controversy in Social Networks Through NLP.
  13. Multidimensional Period Recovery.
  14. Navigating Forest Straight-Line Programs in Constant Time.
  15. On Repetitiveness Measures of Thue-Morse Words.
  16. Practical Random Access to SLP-Compressed Texts.
  17. Pre-indexing Pruning Strategies.
  18. Relative Lempel-Ziv Compression of Suffix Arrays.
  19. Smaller Fully-Functional Bidirectional BWT Indexes.
  20. Tailoring r-index for Document Listing Towards Metagenomics Applications.
  21. Towards Efficient Interactive Computation of Dynamic Time Warping Distance.

STACS 2020

  1. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  2. Generalised Pattern Matching Revisited.
  3. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements.
  4. String Indexing with Compressed Patterns.
  5. Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before.

STOC 2020

  1. Approximating text-to-pattern Hamming distances.
  2. Constant factor approximations to edit distance on far input pairs in nearly linear time.
  3. Constant-factor approximation of near-linear edit distance in near-linear time.
  4. Lower bound for succinct range minimum query.
  5. Nearly optimal static Las Vegas succinct dictionary.

SWAT 2020

  1. Space-Efficient Data Structures for Lattices.

SoCG 2020

  1. Four-Dimensional Dominance Range Reporting in Linear Space.
  2. Further Results on Colored Range Searching.

TAMC 2020

  1. Partial Sums on the Ultra-Wide Word RAM.

WABI 2020

  1. Linear Time Construction of Indexable Founder Block Graphs.

WALCOM 2020

  1. Fast Multiple Pattern Cartesian Tree Matching.
  2. Faster Privacy-Preserving Computation of Edit Distance with Moves.
  3. Generalized Dictionary Matching Under Substring Consistent Equivalence Relations.
  4. Shortest Covers of All Cyclic Shifts of a String.

ACM J. Exp. Algorithmics 2020

  1. Dynamic Path-decomposed Tries.
  2. Property Suffix Array with Applications in Indexing Weighted Sequences.

ACM Trans. Algorithms 2020

  1. A Linear-Time Algorithm for Seeds Computation.
  2. Deterministic Sparse Suffix Sorting in the Restore Model.
  3. Linear-time String Indexing and Analysis in Small Space.
  4. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).

Algorithmica 2020

  1. Compressed Dynamic Range Majority and Minority Data Structures.
  2. Computational Aspects of Ordered Integer Partitions with Bounds.
  3. Dynamic and Internal Longest Common Substring.
  4. Fast Compressed Self-indexes with Deterministic Linear-Time Construction.
  5. Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts.
  6. Lempel-Ziv-Like Parsing in Small Space.

Algorithms 2020

  1. A New Lossless DNA Compression Algorithm Based on A Single-Block Encoding Scheme.
  2. Editorial: Special Issue on Data Compression Algorithms and Their Applications.
  3. Efficient Data Structures for Range Shortest Unique Substring Queries.
  4. More Time-Space Tradeoffs for Finding a Shortest Unique Substring.
  5. Practical Grammar Compression Based on Maximal Repeats.

Algorithms Mol. Biol. 2020

  1. Finding all maximal perfect haplotype blocks in linear time.
  2. gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections.

BMC Bioinform. 2020

  1. Variable-order reference-free variant discovery with the Burrows-Wheeler Transform.

Bioinform. 2020

  1. SMART: SuperMaximal approximate repeats tool.

Discret. Appl. Math. 2020

  1. Accelerated partial decoding in wavelet trees.
  2. Dynamic index and LZ factorization in compressed space.

Fundam. Informaticae 2020

  1. Comparing Degenerate Strings.

Inf. 2020

  1. On the Randomness of Compressed Data.

Inf. Comput. 2020

  1. A compressed dynamic self-index for highly repetitive text collections.
  2. Absent words in a sliding window with applications.
  3. Compact and succinct data structures for multidimensional orthogonal range searching.
  4. Computation over compressed data.
  5. Indexing weighted sequences: Neat and efficient.
  6. Online recognition of dictionary with one gap.
  7. Streaming k-mismatch with error correcting and applications.
  8. String periods in the order-preserving model.

Int. J. Found. Comput. Sci. 2020

  1. Efficient Identification of k-Closed Strings.

J. ACM 2020

  1. Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space.

J. Comput. Biol. 2020

  1. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.
  2. Matching Reads to Many Genomes with the r-Index.

J. Signal Process. Syst. 2020

  1. An Efficient High-Throughput LZ77-Based Decompressor in Reconfigurable Logic.

Proc. VLDB Endow. 2020

  1. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds.

Theor. Comput. Sci. 2020

  1. A linear-space data structure for range-LCP queries in poly-logarithmic time.
  2. Approximate pattern matching on elastic-degenerate text.
  3. Compressed range minimum queries.
  4. Efficient computation of longest single-arm-gapped palindromes in a string.
  5. Faster algorithms for 1-mappability of a sequence.
  6. Finding patterns and periods in Cartesian tree matching.
  7. Generating a Gray code for prefix normal words in amortized polylogarithmic time per word.
  8. Lightweight merging of compressed indices based on BWT variants.
  9. Longest property-preserved common factor: A new string-processing framework.
  10. Parallel computation of the Burrows Wheeler Transform in compact space.
  11. Refining the r-index.
  12. Space-efficient algorithms for computing minimal/shortest unique substrings.
  13. The Alternating BWT: An algorithmic perspective.
  14. Tree path majority data structures.
  15. Two-dimensional maximal repetitions.
  16. Universal reconstruction of a string.

Theory Comput. Syst. 2020

  1. Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings.

ALENEX 2019

  1. Lightweight Distributed Suffix Array Construction.

CIAC 2019

  1. The Parameterized Position Heap of a Trie.

CIKM 2019

  1. Improved Compressed String Dictionaries.

CPM 2019

  1. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem.
  2. A New Class of Searchable and Provably Highly Compressible String Transformations.
  3. A Rearrangement Distance for Fully-Labelled Trees.
  4. Approximating Approximate Pattern Matching.
  5. Cartesian Tree Matching and Indexing.
  6. Compressed Multiple Pattern Matching.
  7. Computing Runs on a Trie.
  8. Computing the Antiperiod(s) of a String.
  9. Conversion from RLBWT to LZ77.
  10. Dichotomic Selection on Words: A Probabilistic Analysis.
  11. Entropy Lower Bounds for Dictionary Compression.
  12. Faster Queries for Longest Substring Palindrome After Block Edit.
  13. Finding a Small Number of Colourful Components.
  14. Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs.
  15. Hamming Distance Completeness.
  16. How to Exploit Periodicity (Invited Talk).
  17. Indexing the Bijective BWT.
  18. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding.
  19. On Maximal Repeats in Compressed Strings.
  20. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
  21. Online Algorithms for Constructing Linear-Size Suffix Trie.
  22. Optimal Rank and Select Queries on Dictionary-Compressed Text.
  23. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  24. Quasi-Periodicity in Streams.
  25. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
  26. Searching Long Repeats in Streams.
  27. Simulating the DNA Overlap Graph in Succinct Space.
  28. Some Variations on Lyndon Words (Invited Talk).
  29. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  30. Streaming Dictionary Matching with Mismatches.
  31. Stringology Combats Microbiological Threats (Invited Talk).
  32. Sufficient Conditions for Efficient Indexing Under Different Matchings.

DCC 2019

  1. A Compact Representation of Raster Time Series.
  2. A New Technique for Lossless Compression of Color Images Based on Hierarchical Prediction, Inversion and Context Adaptive Coding.
  3. BWT Tunnel Planning is Hard But Manageable.
  4. Better Than Optimal Huffman Coding?
  5. Constructing Antidictionaries in Output-Sensitive Space.
  6. Dv2v: A Dynamic Variable-to-Variable Compressor.
  7. Generalized Word Equations: A New Approach to Data Compresion.
  8. LZRR: LZ77 Parsing with Right Reference.
  9. Light Field Image Compression with Random Access.
  10. MR-RePair: Grammar Compression Based on Maximal Repeats.
  11. Multidimensional Compression with Pattern Matching.
  12. Numerical Pattern Mining Through Compression.
  13. On Lempel-Ziv Decompression in Small Space.
  14. On the Randomness of Compressed Data.
  15. Parameterized Text Indexing with One Wildcard.
  16. Practical Indexing of Repetitive Collections Using Relative Lempel-Ziv.
  17. RePair in Compressed Space and Time.
  18. Regular Expression Search on Compressed Text.
  19. Selective Dynamic Compression.
  20. Space-Efficient Computation of the Burrows-Wheeler Transform.
  21. Tunneling on Wheeler Graphs.
  22. Vectorizing Fast Compression.

DEXA (2) 2019

  1. Succinct BWT-Based Sequence Prediction.

DLT 2019

  1. Computing the k-binomial Complexity of the Thue-Morse Word.
  2. First Lower Bounds for Palindromic Length.
  3. On Palindromic Length of Sturmian Sequences.
  4. On the Length of Shortest Strings Accepted by Two-Way Finite Automata.
  5. Separating Many Words by Counting Occurrences of Factors.
  6. The Relative Edit-Distance Between Two Input-Driven Languages.
  7. k-Spectra of Weakly-c-Balanced Words.

ECML/PKDD (1) 2019

  1. String Sanitization: A Combinatorial Approach.

ESA 2019

  1. Bidirectional Text Compression in External Memory.
  2. Longest Common Substring Made Fully Dynamic.
  3. On the Hardness and Inapproximability of Recognizing Wheeler Graphs.
  4. Repetition Detection in a Dynamic String.

FCT 2019

  1. Circular Pattern Matching with k Mismatches.

FOCS 2019

  1. Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
  2. Balancing Straight-Line Programs.
  3. Optimal Document Exchange and New Codes for Insertions and Deletions.
  4. Sublinear Algorithms for Gap Edit Distance.
  5. Why are Proof Complexity Lower Bounds Hard?

ICALP 2019

  1. Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps.
  2. Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication.

INNSBDDL (Tutorials) 2019

  1. Learned Data Structures.

ISAAC 2019

  1. An Improved Data Structure for Left-Right Maximal Generic Words Problem.
  2. Internal Dictionary Matching.
  3. On Approximate Range Mode and Range Selection.
  4. Top Tree Compression of Tries.

ITCS 2019

  1. Testing Local Properties of Arrays.

IWOCA 2019

  1. Burrows-Wheeler Transform of Words Defined by Morphisms.
  2. Finding Periods in Cartesian Tree Matching.
  3. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings.

LATA 2019

  1. Automata over Infinite Sequences of Reals.
  2. Efficient Representation and Counting of Antipower Factors in Words.
  3. Generalized Register Context-Free Grammars.
  4. On the Maximum Number of Distinct Palindromic Sub-arrays.
  5. Palindromic Subsequences in Finite Words.
  6. Recurrence in Multidimensional Words.
  7. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables.

MFCS 2019

  1. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration.
  2. From Regular Expression Matching to Parsing.
  3. Indexing Graph Search Trees and Applications.
  4. RLE Edit Distance in Near Optimal Time.
  5. The Power Word Problem.
  6. Uniform Random Expressions Lack Expressivity.
  7. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations.

RECOMB 2019

  1. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.

SEA² 2019

  1. Searching for Best Karatsuba Recurrences.

SODA 2019

  1. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
  2. Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
  3. List Decoding with Double Samplers.
  4. Lower Bounds for Oblivious Data Structures.
  5. Lower bounds for text indexing with mismatches and differences.
  6. Optimal Construction of Compressed Indexes for Highly Repetitive Texts.
  7. Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.
  8. The streaming k-mismatch problem.

SOFSEM 2019

  1. On Infinite Prefix Normal Words.

SPIRE 2019

  1. A New Linear-Time Algorithm for Centroid Decomposition.
  2. A Practical Alphabet-Partitioning Rank/Select Data Structure.
  3. Adaptive Succinctness.
  4. An Index for Sequencing Reads Based on the Colored de Bruijn Graph.
  5. An Optimal Algorithm to Find Champions of Tournament Graphs.
  6. Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings.
  7. BM25 Beyond Query-Document Similarity.
  8. Bounds and Estimates on the Average Edit Distance.
  9. COBS: A Compact Bit-Sliced Signature Index.
  10. Compact Data Structures for Shortest Unique Substring Queries.
  11. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets.
  12. Fast Cartesian Tree Matching.
  13. Fast Identification of Heavy Hitters by Cached and Packed Group Testing.
  14. Fast, Small, and Simple Document Listing on Repetitive Text Collections.
  15. Faster Dynamic Compressed d-ary Relations.
  16. Faster Repetition-Aware Compressed Suffix Trees Based on Block Trees.
  17. Implementing the Topological Model Succinctly.
  18. Inducing the Lyndon Array.
  19. Linear Time Maximum Segmentation Problems in Column Stream Model.
  20. Lossless Image Compression Using List Update Algorithms.
  21. Minimal Absent Words in Rooted and Unrooted Trees.
  22. Network-Based Pooling for Topic Modeling on Microblog Content.
  23. On Longest Common Property Preserved Substring Queries.
  24. On the Computation of Longest Previous Non-overlapping Factors.
  25. Online Algorithms on Antipowers and Antiperiods.
  26. Parallel External Memory Wavelet Tree and Wavelet Matrix Construction.
  27. Polynomial-Delay Enumeration of Maximal Common Subsequences.
  28. Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search.
  29. Range Shortest Unique Substring Queries.
  30. Rpair: Rescaling RePair with Rsync.
  31. Run-Length Encoding in a Finite Universe.
  32. SACABench: Benchmarking Suffix Array Construction.
  33. Searching Runs in Streams.
  34. Space- and Time-Efficient Storage of LiDAR Point Clouds.
  35. Space-Efficient Merging of Succinct de Bruijn Graphs.
  36. Weighted Shortest Common Supersequence Problem Revisited.

STACS 2019

  1. Constant-Time Retrieval with O(log m) Extra Bits.
  2. Depth First Search in the Semi-streaming Model.
  3. Fast and Longest Rollercoasters.

STOC 2019

  1. Local decodability of the Burrows-Wheeler transform.
  2. Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
  3. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.

WABI 2019

  1. Finding All Maximal Perfect Haplotype Blocks in Linear Time.

WADS 2019

  1. Dynamic Dictionary Matching in the Online Model.
  2. Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.

WALCOM 2019

  1. Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index.

WORDS 2019

  1. Generalized Lyndon Factorizations of Infinite Words.
  2. Matching Patterns with Variables.
  3. Repetitions in Infinite Palindrome-Rich Words.

ACM J. Exp. Algorithmics 2019

  1. Better External Memory LCP Array Construction.

ACM Trans. Algorithms 2019

  1. Sparse Dynamic Programming on DAGs with Small Width.

ACM Trans. Inf. Syst. 2019

  1. Brotli: A General-Purpose Data Compressor.

Algorithmica 2019

  1. Can We Recover the Cover?
  2. Correction to: Longest Common Substring with Approximately k Mismatches.
  3. Fixed Block Compression Boosting in FM-Indexes: Theory and Practice.
  4. Longest Common Substring with Approximately k Mismatches.
  5. Mind the Gap! - Online Dictionary Matching with One Gap.
  6. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

Algorithms 2019

  1. Compaction of Church Numerals.
  2. Space-Efficient Fully Dynamic DFS in Undirected Graphs.

Algorithms Mol. Biol. 2019

  1. External memory BWT and LCP computation for sequence collections with applications.
  2. Linear time minimum segmentation enables scalable founder reconstruction.
  3. Prefix-free parsing for building big BWTs.
  4. SNPs detection by eBWT positional clustering.

Bioinform. 2019

  1. A framework for space-efficient variable-order Markov models.
  2. Compressed filesystem for managing large genome collections.
  3. Fully-sensitive seed finding in sequence graphs using a hybrid index.

Comput. J. 2019

  1. Context Sensitive Rewriting Codes for Flash Memory†.
  2. Edit Distance with Multiple Block Operations†.

Dagstuhl Reports 2019

  1. 25 Years of the Burrows-Wheeler Transform (Dagstuhl Seminar 19241).

IEEE Trans. Inf. Theory 2019

  1. RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy.

Inf. Comput. 2019

  1. Lempel-Ziv compressed structures for document retrieval.
  2. On-line weighted pattern matching.

Inf. Process. Lett. 2019

  1. Applying the Positional Burrows-Wheeler Transform to all-pairs Hamming distance.
  2. Comparison of LZ77-type parsings.

Inf. Sci. 2019

  1. GraCT: A Grammar-based Compressed Index for Trajectory Data.

Inf. Syst. 2019

  1. On the reproducibility of experiments of indexing repetitive document collections.

J. Comb. Optim. 2019

  1. Efficient enumeration of non-equivalent squares in partial words with few holes.

J. Comput. Syst. Sci. 2019

  1. Hide and seek with repetitions.

Rev. Socionetwork Strateg. 2019

  1. Storing Partitions of Integers in Sublinear Space.

SIAM J. Comput. 2019

  1. Bicriteria Data Compression.
  2. Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

SIAM J. Discret. Math. 2019

  1. Rollercoasters: Long Sequences without Short Runs.

Softw. Pract. Exp. 2019

  1. A compact index for order-preserving pattern matching.

Theor. Comput. Sci. 2019

  1. A substring-substring LCS data structure.
  2. Algorithms to compute the Burrows-Wheeler Similarity Distribution.
  3. Approximate cover of strings.
  4. Document listing on repetitive collections with guaranteed performance.
  5. Efficient dynamic dictionary matching with DAWGs and AC-automata.
  6. Improved upper bounds on all maximal α-gapped repeats and palindromes.
  7. Maximal common subsequence algorithms.
  8. On overabundant words and their application to biological sequence analysis.
  9. On the size of the smallest alphabet for Lyndon trees.
  10. Path queries on functions.
  11. Succinct data structure for dynamic trees with faster queries.
  12. Universal compressed text indexing.

Theory Comput. Syst. 2019

  1. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.

AIAI (Workshops) 2018

  1. How Much Different Are Two Words with Different Shortest Periods.

ALENEX 2018

  1. Adaptive Cuckoo Filters.
  2. Hybrid Indexing Revisited.
  3. Simple, Fast and Lightweight Parallel Wavelet Tree Construction.

COCOON 2018

  1. A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time.

CPM 2018

  1. Computing longest common square subsequences.
  2. Faster Online Elastic Degenerate String Matching.
  3. Linear-Time Algorithm for Long LCF with k Mismatches.
  4. Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
  5. Longest Lyndon Substring After Edit.
  6. Longest substring palindrome after edit.
  7. Lyndon Factorization of Grammar Compressed Texts Revisited.
  8. Maximal Common Subsequence Algorithms.
  9. On Undetected Redundancy in the Burrows-Wheeler Transform.
  10. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  11. Order-Preserving Pattern Matching Indeterminate Strings.
  12. Slowing Down Top Trees for Better Worst-Case Compression.

DCC 2018

  1. A Dynamic Compressed Self-Index for Highly Repetitive Text Collections.
  2. A Grammar Compression Algorithm Based on Induced Suffix Sorting.
  3. A Hybrid Approach for Wind Tunnel Data Compression.
  4. Compact Encoding for Galled-Trees and Its Applications.
  5. Compact Representations of Event Sequences.
  6. Compaction of Church Numerals for Higher-Order Compression.
  7. Compressed Hierarchical Clustering.
  8. Constant Delay Traversal of Compressed Graphs.
  9. Delta-Huffman Coding of Unbounded Integers.
  10. Efficient Processing of top-K Vector-Raster Queries Over Compressed Data.
  11. Engineering Compressed Static Functions.
  12. Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication.
  13. Fast and Efficient Compression of Next Generation Sequencing Data.
  14. Fibonacci Based Compressed Suffix Array.
  15. K-Means Algorithm Over Compressed Binary Data.
  16. LZ77 Like Lossy Transformation of Quality Scores.
  17. Lapped Transforms Based Image Recovery for Block Compressed Sensing.
  18. Optimal In-Place Suffix Sorting.
  19. Practical Succinct Text Indexes in External Memory.
  20. Run Compressed Rank/Select for Large Alphabets.
  21. The Bits Between Proteins.
  22. Two-Dimensional Block Trees.

DLT 2018

  1. Block Sorting-Based Transformations on Words: Beyond the Magic BWT.
  2. The Runs Theorem and Beyond.

ESA 2018

  1. Dynamic Trees with Almost-Optimal Access Cost.
  2. Edit Distance with Block Operations.
  3. Improved Time and Space Bounds for Dynamic Range Mode.
  4. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs.
  5. On the Decision Tree Complexity of String Matching.
  6. On the Worst-Case Complexity of TimSort.
  7. String Attractors: Verification and Optimization.
  8. Two-Dimensional Maximal Repetitions.

FOCS 2018

  1. Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.
  2. Bloom Filters, Adaptivity, and the Dictionary Problem.
  3. PanORAMa: Oblivious RAM with Logarithmic Overhead.

FSTTCS 2018

  1. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.

ICALP 2018

  1. Edit Distance between Unrooted Trees in Cubic Time.

IEEE BigData 2018

  1. Scalable Construction of Text Indexes with Thrill.

ISAAC 2018

  1. Encoding Two-Dimensional Range Top-k Queries Revisited.
  2. Longest Unbordered Factor in Quasilinear Time.
  3. Multi-Finger Binary Search Trees.
  4. Succinct Data Structures for Chordal Graphs.
  5. Tree Path Majority Data Structures.

ITCS 2018

  1. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.

IWOCA 2018

  1. An Efficient Representation of Partitions of Integers.
  2. LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression.
  3. On the Expected Number of Distinct Gapped Palindromic Factors.

KDD 2018

  1. Node Similarity with q -Grams for Real-World Labeled Networks.

LATA 2018

  1. Bubble-Flip - A New Generation Algorithm for Prefix Normal Words.
  2. On Periodicity Lemma for Partial Words.

LATIN 2018

  1. Compressed Indexing with Signature Grammars.
  2. On the Approximation Ratio of Lempel-Ziv Parsing.
  3. Property Suffix Array with Applications.

MFCS 2018

  1. Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
  2. Fast Entropy-Bounded String Dictionary Look-Up with Mismatches.

SEA 2018

  1. Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching VCF Files On-line.
  2. Fast matching statistics in small space.

SISAP 2018

  1. Privacy-Preserving String Edit Distance with Moves.

SODA 2018

  1. Improved bounds for testing Dyck languages.
  2. In-Place Sparse Suffix Sorting.
  3. Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
  4. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy.
  5. Multivariate Fine-Grained Complexity of Longest Common Subsequence.
  6. Optimal Dynamic Strings.
  7. Optimal-Time Text Indexing in BWT-runs Bounded Space.
  8. The Entropy of Backwards Analysis.
  9. Time and Space Efficient Representations of Distributive Lattices.
  10. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).

SOFSEM 2018

  1. Duel and Sweep Algorithm for Order-Preserving Pattern Matching.
  2. Longest Common Prefixes with k-Mismatches and Applications.
  3. New Variants of Pattern Matching with Constants and Variables.

SOSA 2018

  1. A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance.

SPIRE 2018

  1. Block Palindromes: A New Generalization of Palindromes.
  2. Compressed Communication Complexity of Longest Common Prefixes.
  3. Computing Burrows-Wheeler Similarity Distributions for String Collections.
  4. Efficient Computation of Sequence Mappability.
  5. Faster Recovery of Approximate Periods over Edit Distance.
  6. Longest Common Prefixes with k-Errors and Applications.
  7. Longest Property-Preserved Common Factor.
  8. Maximal Motif Discovery in a Sliding Window.
  9. On Extended Special Factors of a Word.
  10. Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.
  11. Searching for a Modified Pattern in a Changing Text.

STACS 2018

  1. An Improved Bound for Random Binary Search Trees with Concurrent Insertions.
  2. Computing the Longest Common Prefix of a Context-free Language in Polynomial Time.
  3. Improving the Upper Bound on the Length of the Shortest Reset Word.
  4. Relations Between Greedy and Bit-Optimal LZ77 Encodings.
  5. Space-Efficient Algorithms for Longest Increasing Subsequence.
  6. String Periods in the Order-Preserving Model.
  7. Succinct Oblivious RAM.
  8. Sums of Palindromes: an Approach via Automata.
  9. Upper and Lower Bounds for Dynamic Data Structures on Strings.

STOC 2018

  1. At the roots of dictionary compression: string attractors.
  2. Explicit binary tree codes with polylogarithmic size alphabet.
  3. Smooth heaps and a dual view of self-adjusting data structures.
  4. Synchronization strings: explicit constructions, local decoding, and applications.

SWAT 2018

  1. Succinct Dynamic One-Dimensional Point Reporting.

WABI 2018

  1. A Multi-labeled Tree Edit Distance for Comparing “Clonal Trees” of Tumor Progression.
  2. A Succinct Solution to Rmap Alignment.
  3. Degenerate String Comparison and Applications.
  4. Detecting Mutations by eBWT.
  5. External memory BWT and LCP computation for sequence collections with applications.
  6. Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time.
  7. PRINCE: Accurate Approximation of the Copy Number of Tandem Repeats.
  8. Prefix-Free Parsing for Building Big BWTs.

WALCOM 2018

  1. On Multiple Longest Common Subsequence and Common Motifs with Gaps (Extended Abstract).

Algorithmica 2018

  1. Crochemore’s Partitioning on Weighted Strings and Applications.
  2. Dynamic Path Queries in Linear Space.
  3. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.
  4. Guest Editorial: Special Issue on Compact Data Structures.
  5. LZ77 Computation Based on the Run-Length Encoded BWT.
  6. Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees.
  7. Lempel-Ziv-78 Compressed String Dictionaries.

Algorithms 2018

  1. DenseZDD: A Compact and Fast Index for Families of Sets.
  2. Sliding Suffix Tree.

BMC Bioinform. 2018

  1. STAble: a novel approach to de novo assembly of RNA-seq data and its application in a metabolic model network based metatranscriptomic workflow.

Bioinform. 2018

  1. CNEFinder: finding conserved non-coding elements in genomes.
  2. Practical dynamic de Bruijn graphs.

Comput. J. 2018

  1. Relative Suffix Trees.

Dagstuhl Reports 2018

  1. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281).

Fundam. Informaticae 2018

  1. On Abelian Longest Common Factor with and without RLE.

IEICE Trans. Inf. Syst. 2018

  1. Approximate Frequent Pattern Discovery in Compressed Space.

Inf. Comput. 2018

  1. Alignment-free sequence comparison using absent words.

Inf. Process. Lett. 2018

  1. A hardness result and new algorithm for the longest common palindromic subsequence problem.
  2. Algorithms for anti-powers in strings.

Int. J. Found. Comput. Sci. 2018

  1. Bidirectional Variable-Order de Bruijn Graphs.
  2. Diverse Palindromic Factorization is NP-Complete.
  3. Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions.
  4. Fast Average-Case Pattern Matching on Weighted Sequences.
  5. Palindromic Decompositions with Gaps and Errors.
  6. m-Bonsai: A Practical Compact Dynamic Trie.

J. Discrete Algorithms 2018

  1. A faster implementation of online RLBWT and its application to LZ77 parsing.
  2. A separation between RLSLPs and LZ77.
  3. Algorithms and combinatorial properties on shortest unique palindromic substrings.
  4. Lyndon array construction during Burrows-Wheeler inversion.

Theor. Comput. Sci. 2018

  1. Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos).
  2. Efficient algorithms for shortest partial seeds in words.
  3. Period recovery of strings over the Hamming and edit distances.
  4. The nearest colored node in a tree.
  5. Time-space trade-offs for Lempel-Ziv compressed indexing.

Theory Comput. Syst. 2018

  1. Finger Search in Grammar-Compressed Strings.
  2. Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.

ALENEX 2017

  1. CSA++: Fast Pattern Search for Large Alphabets.
  2. Compact Dynamic Rewritable (CDRW) Arrays.
  3. Elias-Fano meets Single-Term Top-k Document Retrieval.
  4. Engineering External Memory Induced Suffix Sorting.
  5. Engineering a Distributed Full-Text Index.

COCOA (2) 2017

  1. Faster Algorithms for 1-Mappability of a Sequence.

COCOON 2017

  1. Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes.

CPM 2017

  1. Approximate Cover of Strings.
  2. Can We Recover the Cover?.
  3. Communication and Streaming Complexity of Approximate Pattern Matching.
  4. Computing All Distinct Squares in Linear Time for Integer Alphabets.
  5. Deterministic Indexing for Packed Strings.
  6. Document Listing on Repetitive Collections with Guaranteed Performance.
  7. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
  8. Faster STR-IC-LCS Computation via RLE.
  9. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
  10. Lempel-Ziv Compression in a Sliding Window.
  11. Longest Common Extensions with Recompression.
  12. On-Line Pattern Matching on Similar Texts.
  13. Palindromic Length in Linear Time.
  14. Path Queries on Functions.
  15. Representing the Suffix Tree with the CDAWG.
  16. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
  17. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
  18. Wheeler Graphs: Variations on a Theme by Burrows and Wheeler.

CSR 2017

  1. Palindromic Decompositions with Gaps and Errors.

CiE 2017

  1. Flexible Indexing of Repetitive Collections.

DCC 2017

  1. A Compact Index for Order-Preserving Pattern Matching.
  2. A Succinct Data Structure for Multidimensional Orthogonal Range Searching.
  3. Complementary Contextual Models with FM-Index for DNA Compression.
  4. Compressed Dynamic Range Majority Data Structures.
  5. Content Adaptive Embedded Compression.
  6. Full Compressed Affix Tree Representations.
  7. Improved Parallel Construction of Wavelet Trees and Rank/Select Structures.
  8. Improvements on Re-Pair Grammar Compressor.
  9. LZ-End Parsing in Compressed Space.
  10. Making Compression Algorithms for Unicode Text.
  11. Marlin: A High Throughput Variable-to-Fixed Codec Using Plurally Parsable Dictionaries.
  12. Optimize Genomics Data Compression with Hardware Accelerator.
  13. Space-Efficient Re-Pair Compression.
  14. Stabbing Colors in One Dimension.
  15. Streaming K-Mismatch with Error Correcting and Applications.
  16. Symmetry-Compressible Graphs.

DLT 2017

  1. On the Number of Rich Words.

EANN 2017

  1. Efficient Computation of Palindromes in Sequences with Uncertainties.
  2. Efficient Identification of k-Closed Strings.

ESA 2017

  1. A Space-Optimal Grammar Compression.
  2. An Encoding for Order-Preserving Matching.
  3. Dynamic Space Efficient Hashing.
  4. Fast Dynamic Arrays.
  5. LZ-End Parsing in Linear Time.
  6. Real-Time Streaming Multi-Pattern Search for Constant Alphabet.

FCT 2017

  1. Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching.

FOCS 2017

  1. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.

ICALP 2017

  1. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier.
  2. String Inference from Longest-Common-Prefix Array.

ISAAC 2017

  1. Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings.
  2. Fast Compressed Self-Indexes with Deterministic Linear-Time Construction.
  3. On-the-Fly Array Initialization in Less Space.
  4. Structural Pattern Matching - Succinctly.
  5. Succinct Color Searching in One Dimension.

IWOCA 2017

  1. A Faster Implementation of Online Run-Length Burrows-Wheeler Transform.
  2. Computing Abelian String Regularities Based on RLE.
  3. How to Answer a Small Batch of RMQs or LCA Queries in Practice.
  4. Shortest Unique Palindromic Substring Queries in Optimal Time.

LATA 2017

  1. Efficient Pattern Matching in Elastic-Degenerate Texts.
  2. Integrated Encryption in Dynamic Arithmetic Compression.
  3. Two-Dimensional Palindromes and Their Properties.

MFCS 2017

  1. Binary Search in Graphs Revisited.
  2. Small-Space LCE Data Structure with Constant-Time Queries.
  3. The Hardness of Solving Simple Word Equations.

SEA 2017

  1. A Framework of Dynamic Data Structures for String Processing.
  2. Compression with the tudocomp Framework.
  3. Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet.
  4. Fast and Scalable Minimal Perfect Hashing for Massive Key Sets.
  5. Online Construction of Wavelet Trees.
  6. Practical Range Minimum Queries Revisited.
  7. The Quantile Index - Succinct Self-Index for Top-k Document Retrieval.

SISAP 2017

  1. Practical Space-Efficient Data Structures for High-Dimensional Orthogonal Range Searching.
  2. Scalable Similarity Search for Molecular Descriptors.
  3. Succinct Quadtrees for Road Data.

SODA 2017

  1. File Maintenance: When in Doubt, Change the Layout!
  2. Hardness of Permutation Pattern Matching.
  3. Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time.
  4. Sparse Suffix Tree Construction in Optimal Time and Space.
  5. pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems.

SOFSEM 2017

  1. Computing Longest Single-arm-gapped Palindromes in a String.
  2. Edit-Distance Between Visibly Pushdown Languages.
  3. Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings.

SPIRE 2017

  1. A Self-index on Block Trees.
  2. Detecting One-Variable Patterns.
  3. Distinct Squares in Circular Words.
  4. Efficient Compression and Indexing of Trajectories.
  5. Fast Construction of Compressed Web Graphs.
  6. Fast Label Extraction in the CDAWG.
  7. LZ78 Compression in Low Main Memory Space.
  8. Lightweight BWT and LCP Merging via the Gap Algorithm.
  9. Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.
  10. Longest Common Factor After One Edit Operation.
  11. On Suffix Tree Breadth.
  12. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
  13. Optimal Skeleton Huffman Trees.
  14. Order Preserving Pattern Matching on Trees and DAGs.
  15. Pattern Matching on Elastic-Degenerate Text with Errors.
  16. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries.
  17. Succinct Partial Sums and Fenwick Trees.
  18. Tight Bounds for Top Tree Compression.

STACS 2017

  1. On Long Words Avoiding Zimin Patterns.
  2. On the Size of Lempel-Ziv and Lyndon Factorizations.

STOC 2017

  1. Synchronization strings: codes for insertions and deletions approaching the Singleton bound.

WABI 2017

  1. Optimal Computation of Overabundant Words.
  2. Rainbowfish: A Succinct Colored de Bruijn Graph Representation.

WADS 2017

  1. Optimal Query Time for Encoding Range Majority.

WALCOM 2017

  1. A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs.

WORDS 2017

  1. A de Bruijn Sequence Construction by Concatenating Cycles of the Complemented Cycling Register.
  2. Burrows-Wheeler Transform and Run-Length Enconding.
  3. Minimal Forbidden Factors of Circular Words.

ACM J. Exp. Algorithmics 2017

  1. Practical Compact Indexes for Top-k Document Retrieval.

Algorithmica 2017

  1. A Framework for Space-Efficient String Kernels.
  2. Compressed Subsequence Matching and Packed Tree Coloring.
  3. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
  4. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
  5. On the Succinct Representation of Equivalence Classes.
  6. String Powers in Trees.
  7. Top-k Term-Proximity in Succinct Space.

Algorithms Mol. Biol. 2017

  1. On avoided words, absent words, and their application to biological sequence analysis.

BMC Bioinform. 2017

  1. A framework for space-efficient read clustering in metagenomic samples.

Bioinform. 2017

  1. Succinct colored de Bruijn graphs.
  2. emMAW: computing minimal absent words in external memory.

IEEE ACM Trans. Comput. Biol. Bioinform. 2017

  1. Benchmark Dataset for Whole Genome Sequence Compression.

IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2017

  1. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.

Inf. Process. Lett. 2017

  1. Optimal suffix sorting and LCP array construction for constant alphabets.
  2. Tight lower bounds for the longest common extension problem.
  3. Two strings at Hamming distance 1 cannot be both quasiperiodic.

Inf. Retr. J. 2017

  1. Document retrieval on repetitive string collections.

Inf. Syst. 2017

  1. Compressed representation of dynamic binary relations with applications.

J. Comput. Syst. Sci. 2017

  1. Fast algorithms for Abelian periods in words and greatest common divisor queries.
  2. Fingerprints in compressed strings.

J. Discrete Algorithms 2017

  1. A space efficient direct access data structure.
  2. A succinct data structure for self-indexing ternary relations.
  3. Burrows-Wheeler transform and LCP array construction in constant space.
  4. Grammar compressed sequences with rank/select support.
  5. Preface - Compact Data Structures.
  6. Subsequence automata with default transitions.

Math. Comput. Sci. 2017

  1. Block Graphs in Practice.
  2. Compressed Spaced Suffix Arrays.
  3. Engineering a Lightweight External Memory Suffix Array Construction Algorithm.

Math. Struct. Comput. Sci. 2017

  1. Fast circular dictionary-matching algorithm.

Pattern Recognit. Lett. 2017

  1. A faster and more accurate heuristic for cyclic edit distance computation.

SIAM J. Comput. 2017

  1. The “Runs” Theorem.
  2. Time-Optimal Top-k Document Retrieval.

Theor. Comput. Sci. 2017

  1. Covering problems for partial words and for indeterminate strings.
  2. Inducing enhanced suffix arrays for string collections.
  3. Inferring strings from Lyndon factorization.
  4. String cadences.
  5. Wheeler graphs: A framework for BWT-based data structures.

ALENEX 2016

  1. A General Framework for Dynamic Succinct and Compressed Data Structures.

COCOA 2016

  1. On-Line Pattern Matching on Uncertain Sequences and Applications.

CPM 2016

  1. Boxed Permutation Pattern Matching.
  2. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
  3. Efficient Index for Weighted Sequences.
  4. Factorizing a String into Squares in Linear Time.
  5. Faster Longest Common Extension Queries in Strings over General Alphabets.
  6. Fully-online Construction of Suffix Trees for Multiple Texts.
  7. Longest Common Substring with Approximately k Mismatches.
  8. Minimal Suffix and Rotation of a Substring in Optimal Time.
  9. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
  10. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
  11. The Nearest Colored Node in a Tree.
  12. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

DCC 2016

  1. A Simple and Efficient Approach for Adaptive Entropy Coding over Large Alphabets.
  2. A Space Efficient Direct Access Data Structure.
  3. Analysis of a Rewriting Compression System for Flash Memory.
  4. Approximate String Matching for Self-Indexes.
  5. Burrows-Wheeler Transform for Terabases.
  6. CS2A: A Compressed Suffix Array-Based Method for Short Read Alignment.
  7. Compressing Combinatorial Objects.
  8. Computing LZ77 in Run-Compressed Space.
  9. Efficient Compression of Genomic Sequences.
  10. Efficient Environmental Temperature Monitoring Using Compressed Sensing.
  11. Faster, Minuter.
  12. Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios with LZ-Class Decompression Speed.
  13. Hardware Based Compression in Big Data.
  14. Improved Range Minimum Queries.
  15. Induced Suffix Sorting for String Collections.
  16. Lempel-Ziv Computation in Compressed Space (LZ-CICS).
  17. Linear Time Succinct Indexable Dictionary Construction with Applications.
  18. Lossy Compression of Unordered Rooted Trees.
  19. Online Grammar Transformation Based on Re-Pair Algorithm.
  20. Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction.
  21. Positional Inverted Self-index.
  22. Quick Access to Compressed Data in Storage Systems.
  23. Self-Indexing RDF Archives.
  24. Shortest DNA Cyclic Cover in Compressed Space.
  25. Small Polygon Compression.
  26. Timeliness in Lossless Block Coding.
  27. When Less is More - Using Restricted Repetition Search in Fast Compressors.

DLT 2016

  1. Ternary Square-Free Partial Words with Many Wildcards.

ESA 2016

  1. BlockQuicksort: Avoiding Branch Mispredictions in Quicksort.
  2. Faster External Memory LCP Array Construction.
  3. Streaming Pattern Matching with d Wildcards.

FOCS 2016

  1. Edit Distance: Sketching, Streaming, and Document Exchange.

FSTTCS 2016

  1. Finger Search in Grammar-Compressed Strings.
  2. LZ77 Factorisation of Trees.

ICALP 2016

  1. Approximate Hamming Distance in a Stream.
  2. Data Structure Lower Bounds for Document Indexing Problems.
  3. Towards Tight Lower Bounds for Range Reporting on the RAM.

ISAAC 2016

  1. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.
  2. Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap.
  3. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.
  4. Space-Time Trade-Offs for the Shortest Unique Substring Problem.

ITCS 2016

  1. Is There an Oblivious RAM Lower Bound?

IWOCA 2016

  1. Finding Gapped Palindromes Online.
  2. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.
  3. Partial Covering Arrays: Algorithms and Asymptotics.

KDD 2016

  1. Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices.

LATA 2016

  1. On Del-Robust Primitive Partial Words with One Hole.
  2. Optimal Bounds for Computing \alpha α -gapped Repeats.

LATIN 2016

  1. Bidirectional Variable-Order de Bruijn Graphs.
  2. Compressing Bounded Degree Graphs.
  3. Deterministic Sparse Suffix Sorting on Rewritable Texts.
  4. Linear-Time Sequence Comparison Using Minimal Absent Words & Applications.
  5. The Grandmama de Bruijn Sequence for Binary Strings.
  6. Tree Compression Using String Grammars.

MFCS 2016

  1. Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets.
  2. Dividing by Zero - How Bad Is It, Really?.
  3. Fully Dynamic Data Structure for LCE Queries in Compressed Space.
  4. Shortest Unique Substring Queries on Run-Length Encoded Strings.

SEA 2016

  1. CHICO: A Compressed Hybrid Index for Repetitive Collections.
  2. Fast Scalable Construction of (Minimal Perfect Hash) Functions.
  3. Lempel-Ziv Decoding in External Memory.
  4. Practical Dynamic Entropy-Compressed Bitvectors with Applications.
  5. Practical Variable Length Gap Pattern Matching.
  6. Worst-Case-Efficient Dynamic Arrays in Practice.

SIGIR 2016

  1. Fast and Compact Hamming Distance Index.
  2. Succinct Data Structures in Information Retrieval: Theory and Practice.

SODA 2016

  1. Range Predecessor and Lempel-Ziv Parsing.
  2. The k-mismatch problem revisited.
  3. Weighted dynamic finger in binary search trees.

SOFSEM 2016

  1. Compacting a Dynamic Edit Distance Table by RLE Compression.
  2. Subsequence Automata with Default Transitions.

SPIRE 2016

  1. A Linear-Space Algorithm for the Substring Constrained Alignment Problem.
  2. Analyzing Relative Lempel-Ziv Reference Construction.
  3. Bookmarks in Grammar-Compressed Strings.
  4. Dynamic and Approximate Pattern Matching in 2D.
  5. Efficient Representation of Multidimensional Data over Hierarchical Domains.
  6. Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes.
  7. Fully Dynamic de Bruijn Graphs.
  8. GraCT: A Grammar Based Compressed Representation of Trajectories.
  9. LCP Array Construction Using O(sort(n)) (or Less) I/Os.
  10. Longest Common Abelian Factors and Large Alphabets.
  11. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.
  12. Parallel Computation for the All-Pairs Suffix-Prefix Problem.
  13. RLZAP: Relative Lempel-Ziv with Adaptive Pointers.
  14. XBWT Tricks.

STACS 2016

  1. Efficiently Finding All Maximal alpha-gapped Repeats.
  2. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates.
  3. Periods and Borders of Random Words.

STOC 2016

  1. Streaming algorithms for embedding and computing edit distance in the low distance regime.

SWAT 2016

  1. A Framework for Dynamic Parameterized Dictionary Matching.
  2. A Simple Mergeable Dictionary.
  3. Cuckoo Filter: Simplification and Analysis.
  4. Lower Bounds for Approximation Schemes for Closest String.

WABI 2016

  1. A Graph Extension of the Positional Burrows-Wheeler Transform and Its Applications.
  2. A Natural Encoding of Genetic Variation in a Burrows-Wheeler Transform to Enable Mapping and Genome Inference.
  3. Optimal Computation of Avoided Words.

ACM J. Exp. Algorithmics 2016

  1. Faster Compressed Suffix Trees for Repetitive Collections.
  2. Inducing Suffix and LCP Arrays in External Memory.
  3. LCP Array Construction in External Memory.
  4. Lazy Lempel-Ziv Factorization Algorithms.

ACM Trans. Algorithms 2016

  1. Compressed Cache-Oblivious String B-Tree.
  2. Data Structures for Path Queries.
  3. Sparse Text Indexing in Small Space.

ACM Trans. Archit. Code Optim. 2016

  1. Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache.

Algorithmica 2016

  1. Compressed String Dictionary Search with Edit Distance One.
  2. Optimal Encodings for Range Majority Queries.

Algorithms 2016

  1. siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves.

Algorithms Mol. Biol. 2016

  1. Circular sequence comparison: algorithms and applications.
  2. Erratum to: Circular sequence comparison: algorithms and applications.

BMC Bioinform. 2016

  1. libFLASM: a software library for fixed-length approximate string matching.

Dagstuhl Reports 2016

  1. Computation over Compressed Structured Data (Dagstuhl Seminar 16431).

Discret. Appl. Math. 2016

  1. Closed factorization.
  2. Random access to Fibonacci encoded files.

IEEE ACM Trans. Comput. Biol. Bioinform. 2016

  1. Parallel and Space-Efficient Construction of Burrows-Wheeler Transform and Suffix Array for Big Genome Data.

IEEE Trans. Parallel Distributed Syst. 2016

  1. A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems.

Inf. 2016

  1. Lazy Management for Frequency Table on Hardware-Based Stream Lossless Data Compression.

Inf. Process. Lett. 2016

  1. Computing runs on a general alphabet.
  2. On the greedy algorithm for the Shortest Common Superstring problem with reversals.

Inf. Syst. 2016

  1. Aggregated 2D range queries on clustered points.
  2. New dynamic metric indices for secondary memory.
  3. Practical compressed string dictionaries.
  4. Universal indexes for highly repetitive document collections.

J. Discrete Algorithms 2016

  1. An improved algorithm for the all-pairs suffix-prefix problem.

SIAM J. Discret. Math. 2016

  1. Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence.

Softw. Pract. Exp. 2016

  1. Improving a lightweight LZ77 computation algorithm for running faster.

Theor. Comput. Sci. 2016

  1. A really simple approximation of smallest grammar.
  2. Computing minimal and maximal suffixes of a substring.
  3. Document retrieval with one wildcard.
  4. Dynamic range majority data structures.
  5. Fast computation of abelian runs.
  6. Fast construction of wavelet trees.
  7. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text.
  8. Finding the leftmost critical factorization on unordered alphabet.
  9. Generalized pattern matching and periodicity under substring consistent equivalence relations.
  10. Linear-time computation of prefix table for weighted strings & applications.
  11. Linear-time superbubble identification algorithm for genome assembly.
  12. Longest common extensions in trees.
  13. Maximum number of distinct and nonequivalent nonstandard squares in a word.
  14. Order-preserving indexing.
  15. Order-preserving pattern matching with k mismatches.
  16. Permuted scaled matching.
  17. Reporting consecutive substring occurrences under bounded gap constraints.
  18. Simple and efficient fully-functional succinct trees.
  19. Tighter bounds for the sum of irreducible LCP values.

ALENEX 2015

  1. A Data-Aware FM-index.
  2. Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions.
  3. Improved Single-Term Top-k Document Retrieval.

BCB 2015

  1. Fast and efficient compression of high-throughput sequencing reads.

BPOE 2015

  1. Stream-Based Lossless Data Compression Hardware Using Adaptive Frequency Table Management.

CIAC 2015

  1. An Opportunistic Text Indexing Structure Based on Run Length Encoding.

CPM 2015

  1. A Framework for Space-Efficient String Kernels.
  2. Alphabet-Dependent String Searching with Wexponential Search Trees.
  3. Compact Indexes for Flexible Top- k k Retrieval.
  4. Composite Repetition-Aware Data Structures.
  5. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.
  6. Lempel Ziv Computation in Small Space (LZ-CISS).
  7. Longest Common Extensions in Sublinear Space.
  8. Longest Common Extensions in Trees.
  9. On Maximal Unbordered Factors.
  10. Online Detection of Repetitions with Backtracking.
  11. Parallel External Memory Suffix Sorting.
  12. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  13. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  14. Tighter Bounds for the Sum of Irreducible LCP Values.

DCC 2015

  1. Bi-Directional Context Modeling with Combinatorial Structuring for Genome Sequence Compression.
  2. Compressing Yahoo Mail.
  3. Compression for Similarity Identification: Computing the Error Exponent.
  4. Compression of Next Generation Sequencing Data.
  5. Compression-Aware Algorithms for Massive Datasets.
  6. Data Compression Cost Optimization.
  7. Document Counting in Compressed Space.
  8. Efficient Set Operations over k2-Trees.
  9. Enhanced Direct Access to Huffman Encoded Files.
  10. Faster Compressed Quadtrees.
  11. Geometric Compression of Orientation Signals for Fast Gesture Analysis.
  12. Improving PPM with Dynamic Parameter Updates.
  13. Incremental Locality and Clustering-Based Compression.
  14. On Probability Estimation via Relative Frequencies and Discount.
  15. OnlineRePair: A Recompressor for XML Structures.
  16. Parallel Wavelet Tree Construction.
  17. Queries on LZ-Bounded Encodings.
  18. Range Selection Queries in Data Aware Space and Time.
  19. Serializing RDF in Compressed Space.
  20. Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+.
  21. Universal Compression of Memoryless Sources over Large Alphabets via Independent Component Analysis.
  22. Variable-Order de Bruijn Graphs.

DEXA Workshops 2015

  1. Longest Previous Non-overlapping Factors Computation.

DLT 2015

  1. Diverse Palindromic Factorization Is NP-complete.
  2. Grammar-Based Tree Compression.
  3. Squareable Words.
  4. State Complexity of Neighbourhoods and Approximate Pattern Matching.
  5. Transfinite Lyndon Words.
  6. Unary Patterns with Permutations.

ESA 2015

  1. Access, Rank, and Select in Grammar-compressed Strings.
  2. Approximating LZ77 via Small-Space Multiple-Pattern Matching.
  3. Compressed Data Structures for Dynamic Sequences.
  4. Dictionary Matching in a Stream.

FCT 2015

  1. Longest α-Gapped Repeat and Palindrome.

FOCS 2015

  1. Pattern-Avoiding Access in Binary Search Trees.
  2. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
  3. Tight Hardness Results for LCS and Other Sequence Similarity Measures.

ICALP (1) 2015

  1. Hollow Heaps.
  2. Optimal Encodings for Range Top- k k , Selection, and Min-Max.
  3. Replacing Mark Bits with Randomness in Fibonacci Heaps.

ISAAC 2015

  1. An In-place Framework for Exact and Approximate Shortest Unique Substring Queries.
  2. Inferring Strings from Full Abelian Periods.
  3. Multidimensional Range Selection.
  4. On the Succinct Representation of Unlabeled Permutations.
  5. Optimal Search Trees with 2-Way Comparisons.

IWOCA 2015

  1. Computing the BWT and the LCP Array in Constant Space.
  2. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.
  3. Longest Common Extensions in Partial Words.

LATA 2015

  1. Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform.
  2. Average-Case Optimal Approximate Circular String Matching.
  3. Backward Linearised Tree Pattern Matching.
  4. Compressed Data Structures for Range Searching.
  5. Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree.
  6. Coverability in Two Dimensions.
  7. Equation x^iy^jx^k=u^iv^ju^k in Words.
  8. On the Language of Primitive Partial Words.
  9. On the Number of Closed Factors in a Word.
  10. Online Computation of Abelian Runs.
  11. Square-Free Words over Partially Commutative Alphabets.

MFCS (1) 2015

  1. Longest Gapped Repeats and Palindromes.
  2. Strong Inapproximability of the Shortest Reset Word.

MFCS (2) 2015

  1. Faster Lightweight Lempel-Ziv Parsing.

PPAM (2) 2015

  1. Parallelising the Computation of Minimal Absent Words.

SEA 2015

  1. A Bulk-Parallel Priority Queue in External Memory with STXXL.
  2. Huffman Codes versus Augmented Non-Prefix-Free Codes.
  3. Parallel Construction of Succinct Trees.
  4. Tree Compression with Top Trees Revisited.

SODA 2015

  1. A new characterization of maximal repetitions by Lyndon trees.
  2. Approximate Range Emptiness in Constant Time and Optimal Space.
  3. Cell-probe bounds for online edit distance and other pattern matching problems.
  4. Internal Pattern Matching Queries in a Text and Applications.
  5. The amortized cost of finding the minimum.
  6. Wavelet Trees Meet Suffix Trees.

SPIRE 2015

  1. A Compact RDF Store Using Suffix Arrays.
  2. A Faster Algorithm for Computing Maximal \alpha -gapped Repeats in a String.
  3. Beyond the Runs Theorem.
  4. Computing the Longest Unbordered Substring.
  5. Efficient Algorithms for Longest Closed Factor Array.
  6. Fast Online Lempel-Ziv Factorization in Compressed Space.
  7. Longest Common Prefix with Mismatches.
  8. Online Self-Indexed Grammar Compression.
  9. Range LCP Queries Revisited.
  10. Relative Select.
  11. Space-Efficient Detection of Unusual Words.
  12. Tight Bound for the Number of Distinct Palindromes in a Tree.

STACS 2015

  1. Lempel-Ziv Factorization May Be Harder Than Computing All Runs.
  2. Pattern Matching with Variables: Fast Algorithms and New Hardness Results.
  3. Space-efficient Basic Graph Algorithms.

STOC 2015

  1. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).

WABI 2015

  1. Bloom Filter Trie - A Data Structure for Pan-Genome Storage.
  2. Circular Sequence Comparison with q-grams.
  3. Optimizing Read Reversals for Sequence Compression - (Extended Abstract).

WADS 2015

  1. Universal Reconstruction of a String.

WALCOM 2015

  1. A Practical Succinct Data Structure for Tree-Like Graphs.
  2. Non-repetitive Strings over Alphabet Lists.

WORDS 2015

  1. Arithmetics on Suffix Arrays of Fibonacci Words.
  2. Linear-Time Computation of Prefix Table for Weighted Strings.

WWW 2015

  1. Compressed Indexes for String Searching in Labeled Graphs.

ACM Trans. Algorithms 2015

  1. Optimal Lower and Upper Bounds for Representing Sequences.

Algorithmica 2015

  1. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures.
  2. Fast Algorithm for Partial Covers in Words.
  3. Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error.
  4. Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space.
  5. Space-Time Trade-offs for Stack-Based Algorithms.

BMC Bioinform. 2015

  1. Fast randomized approximate string matching with succinct hash data structures.

Bioinform. 2015

  1. MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph.
  2. Ultrafast SNP analysis using the Burrows-Wheeler transform of short-read data.

IEEE Trans. Inf. Theory 2015

  1. Efficient and Compact Representations of Prefix Codes.

Inf. Comput. 2015

  1. Approximate periodicity.
  2. Detecting regularities on grammar-compressed strings.
  3. Tree compression with top trees.

Inf. Process. Lett. 2015

  1. Constructing LZ78 tries and position heaps in linear time for large alphabets.

Inf. Syst. 2015

  1. The wavelet matrix: An efficient wavelet tree for large alphabets.

J. Discrete Algorithms 2015

  1. A suffix tree or not a suffix tree?
  2. An efficient Variable-to-Fixed length encoding using multiplexed parse trees.
  3. Approximate pattern matching in LZ77-compressed texts.
  4. Bottom-k document retrieval.
  5. Computing the Burrows-Wheeler transform in place and in small space.
  6. Dynamic edit distance table under a general weighted cost function.
  7. Improved and extended locating functionality on compressed suffix arrays.

Knowl. Inf. Syst. 2015

  1. Compressed vertical partitioning for efficient RDF management.

SIAM J. Comput. 2015

  1. Random Access to Grammar-Compressed Strings and Trees.

SIAM J. Discret. Math. 2015

  1. String Reconstruction from Substring Compositions.

Softw. Pract. Exp. 2015

  1. Fast in-memory XPath search using compressed indexes.

Theor. Comput. Sci. 2015

  1. Compressed automata for dictionary matching.
  2. Dictionary matching with a few gaps.
  3. Global and local sequence alignment with a bounded number of gaps.
  4. On hardness of several string indexing problems.

ALENEX 2014

  1. Multi-Pivot Quicksort: Theory and Experiments.
  2. Top-k Substring Matching for Auto-Completion.

CPM 2014

  1. A really Simple Approximation of Smallest Grammar.
  2. Approximate On-line Palindrome Recognition, and Applications.
  3. Compressed Subsequence Matching and Packed Tree Coloring.
  4. Computing Minimal and Maximal Suffixes of a Substring Revisited.
  5. Computing Palindromic Factorizations and Palindromic Covers On-line.
  6. Dictionary Matching with One Gap.
  7. Efficient Algorithms for Shortest Partial Seeds in Words.
  8. Encodings for Range Majority Queries.
  9. Indexed Geometric Jumbled Pattern Matching.
  10. Most Recent Match Queries in On-Line Suffix Trees.
  11. Order-Preserving Pattern Matching with k Mismatches.
  12. Permuted Scaled Matching.
  13. String Range Matching.

DCC 2014

  1. A Practical Implementation of Compressed Suffix Arrays with Applications to Self-Indexing.
  2. Adaptive Dictionary Sharing Method for Re-Pair Algorithm.
  3. Alignment Free Sequence Similarity with Bounded Hamming Distance.
  4. Better Compression through Better List Update Algorithms.
  5. Boosting the Compression of Rewriting on Flash Memory.
  6. Combining Deduplication and Delta Compression to Achieve Low-Overhead Data Reduction on Backup Datasets.
  7. Compressing Sets and Multisets of Sequences.
  8. Compressing Similar Biological Sequences Using FM-Index.
  9. Compression Schemes for Similarity Queries.
  10. Direct Access to Variable-to-Fixed Length Codes with a Succinct Index.
  11. Entropy Reduction Using Context Transformations.
  12. Fast Fully-Compressed Suffix Trees.
  13. Fully Online Grammar Compression in Constant Space.
  14. Hybrid Compression of Bitvectors for the FM-Index.
  15. Information Profiles for DNA Pattern Discovery.
  16. Interleaved K2-Tree: Indexing and Navigating Ternary Relations.
  17. LZ-Compressed String Dictionaries.
  18. Lempel-Ziv Parsing in External Memory.
  19. Relative Lempel-Ziv with Constant-Time Random Access.
  20. Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets.
  21. Towards Markup-Aware Text Compression.
  22. Universal Text Preprocessing and Postprocessing for PPM Using Alphabet Adjustment.

Developments in Language Theory 2014

  1. On k-Abelian Palindromic Rich and Poor Words.
  2. k-Abelian Pattern Matching.

ESA 2014

  1. Amortized Bounds for Dynamic Orthogonal Range Reporting.
  2. Bicriteria Data Compression: Efficient and Usable.
  3. Document Retrieval on Repetitive Collections.
  4. Equivalence between Priority Queues and Sorting in External Memory.
  5. Sublinear Space Algorithms for the Longest Common Substring Problem.
  6. The Batched Predecessor Problem in External Memory.
  7. Weighted Ancestors in Suffix Trees.

FOCS 2014

  1. Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
  2. The Dyck Language Edit Distance Problem in Near-Linear Time.

FSTTCS 2014

  1. Asymptotically Optimal Encodings for Range Selection.

HPCA 2014

  1. MemZip: Exploring unconventional benefits from memory compression.

ICALP (1) 2014

  1. Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM.
  2. On Hardness of Jumbled Indexing.

ISAAC 2014

  1. Depth-First Search Using O(n) Bits.
  2. Hashing and Indexing: Succinct DataStructures and Smoothed Analysis.
  3. The Power and Limitations of Static Binary Search Trees with Lazy Finger.
  4. Top- k Term-Proximity in Succinct Space.

IWOCA 2014

  1. A Suffix Tree Or Not a Suffix Tree?
  2. Computing Primitively-Rooted Squares and Runs in Partial Words.
  3. Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance.

JSAI-isAI Workshops 2014

  1. Finding Ambiguous Patterns on Grammar Compressed String.

LATIN 2014

  1. Biased Predecessor Search.
  2. LZ77-Based Self-indexing with Faster Pattern Matching.
  3. Multiply Balanced k -Partitioning.
  4. Quad-K-d Trees.

Language, Culture, Computation (1) 2014

  1. Hypertext Searching - A Survey.

MFCS (1) 2014

  1. Universal Lyndon Words.

MFCS (2) 2014

  1. Document Retrieval with One Wildcard.
  2. Inferring Strings from Lyndon Factorization.

SEA 2014

  1. Approximate Online Matching of Circular Strings.
  2. DenseZDD: A Compact and Fast Index for Families of Sets.
  3. Efficient Representation for Online Suffix Tree Construction.
  4. Efficient Wavelet Tree Construction and Querying for Multicore Architectures.
  5. Faster Compressed Suffix Trees for Repetitive Text Collections.
  6. From Theory to Practice: Plug and Play with Succinct Data Structures.
  7. Improved ESP-index: A Practical Self-index for Highly Repetitive Texts.
  8. Improved and Extended Locating Functionality on Compressed Suffix Arrays.
  9. LCP Array Construction in External Memory.
  10. Order-Preserving Matching with Filtration.
  11. Retrieval and Perfect Hashing Using Fingerprinting.

SISAP 2014

  1. Dynamic List of Clusters in Secondary Memory.

SODA 2014

  1. Bicriteria data compression.
  2. Concurrent Range Reporting in Two-Dimensional Space.
  3. Finding small patterns in permutations in linear time.
  4. Near-optimal labeling schemes for nearest common ancestors.
  5. Selection and Sorting in the “Restore” Model.

SOFSEM 2014

  1. Shortest Unique Substrings Queries in Optimal Time.

SPIRE 2014

  1. Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings.
  2. Efficient Compressed Indexing for Approximate Top-k String Retrieval.
  3. Efficient Indexing and Representation of Web Access Logs.
  4. Fast Construction of Wavelet Trees.
  5. Grammar Compressed Sequences with Rank/Select Support.
  6. Indexed Matching Statistics and Shortest Unique Substrings.
  7. K 2-Treaps: Range Top-k Queries in Compact Space.
  8. Online Pattern Matching for String Edit Distance with Moves.
  9. Relative FM-Indexes.
  10. Relative Lempel-Ziv with Constant-Time Random Access.
  11. Simple and Efficient String Algorithms for Query Suggestion Metrics Computation.
  12. Strategic Pattern Search in Factor-Compressed Text.

STACS 2014

  1. Data-Oblivious Data Structures.
  2. Faster Compact On-Line Lempel-Ziv Factorization.
  3. Faster Sparse Suffix Sorting.
  4. Space-Efficient String Indexing for Wildcard Pattern Matching.
  5. Testing Generalised Freeness of Words.
  6. Weighted Coloring in Trees.

STOC 2014

  1. Linear time construction of compressed text indices in compact space.
  2. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time.

SWAT 2014

  1. B-slack Trees: Space Efficient B-Trees.
  2. Colored Range Searching in Linear Space.
  3. Expected Linear Time Sorting for Word Size Ω(log2 n loglogn).
  4. Ranked Document Selection.

WABI 2014

  1. Constructing String Graphs in External Memory.
  2. Manifold de Bruijn Graphs.

WALCOM 2014

  1. Alignment with Non-overlapping Inversions on Two Strings.

ACM J. Exp. Algorithmics 2014

  1. General Document Retrieval in Compact Space.
  2. Locally Compressed Suffix Arrays.

ACM Trans. Algorithms 2014

  1. Alphabet-Independent Compressed Text Indexing.
  2. Fully Functional Static and Dynamic Succinct Trees.

ACM Trans. Inf. Syst. 2014

  1. XXS: Efficient XPath Evaluation on Compressed XML Documents.

Algorithmica 2014

  1. A Framework for Succinct Labeled Ordinal Trees over Large Alphabets.
  2. Efficient Fully-Compressed Sequence Representations.
  3. Substring Range Reporting.

Algorithms 2014

  1. High-Order Entropy Compressed Bit Vectors with Rank/Select.

Algorithms Mol. Biol. 2014

  1. Fast algorithms for approximate circular string matching.
  2. Optimal computation of all tandem repeats in a weighted sequence.

BMC Bioinform. 2014

  1. Linear-time computation of minimal absent words using suffix array.

Comput. Geom. 2014

  1. Space efficient data structures for dynamic orthogonal range counting.

Discret. Appl. Math. 2014

  1. Inferring strings from suffix trees and links on a binary alphabet.

IEEE Trans. Knowl. Data Eng. 2014

  1. Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays.

J. Comput. Syst. Sci. 2014

  1. Range LCP.

J. Discrete Algorithms 2014

  1. A subquadratic algorithm for minimum palindromic factorization.
  2. Cross-document pattern matching.
  3. Multi-pattern matching with bidirectional indexes.
  4. Simple and efficient LZW-compressed multiple pattern matching.
  5. Simple, compact and robust approximate string dictionary.
  6. Time-space trade-offs for longest common extensions.
  7. Wavelet trees for all.

Knowl. Inf. Syst. 2014

  1. Compressed representations for web and social graphs.

Parallel Comput. 2014

  1. Distributed text search using suffix arrays.

SIAM J. Comput. 2014

  1. Optimal Dynamic Sequence Representations.

Softw. Pract. Exp. 2014

  1. Optimized succinct data structures for massive data.

Theor. Comput. Sci. 2014

  1. Closest periodic vectors in Lp spaces.
  2. Compact q-gram profiling of compressed strings.
  3. Detecting approximate periodic patterns.
  4. Extending alignments with k-mismatches and ℓ-gaps.
  5. Fast relative Lempel-Ziv self-index for similar sequences.
  6. Less space: Indexing for queries with wildcards.
  7. New space/time tradeoffs for top-k document retrieval on sequences.
  8. Order-preserving matching.
  9. Towards optimal packed string matching.

Theory Comput. Syst. 2014

  1. String Indexing for Patterns with Wildcards.
  2. Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

ALENEX 2013

  1. Fast Packed String Matching for Short Patterns.
  2. Inducing Suffix and Lcp Arrays in External Memory.
  3. Lempel-Ziv factorization: Simple, fast, practical.

CIAA 2013

  1. Compressed Automata for Dictionary Matching.

CIAC 2013

  1. Average Optimal String Matching in Packed Strings.

CPM 2013

  1. A Succinct Grammar Compression.
  2. Compact q-Gram Profiling of Compressed Strings.
  3. Converting SLP to LZ78 in almost Linear Time.
  4. Document Listing on Repetitive Collections.
  5. Efficient Lyndon Factorization of Grammar Compressed Text.
  6. Fast Algorithm for Partial Covers in Words.
  7. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
  8. New Algorithms for Position Heaps.
  9. On Minimal and Maximal Suffixes of a Substring.
  10. Time-Space Trade-Offs for the Longest Common Substring Problem.

CSR 2013

  1. Alphabetic Minimax Trees in Linear Time.

CiE 2013

  1. Discovering Hidden Repetitions in Words.

DCC 2013

  1. A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
  2. Algorithms for Compressed Inputs.
  3. An Adaptive Difference Distribution-Based Coding with Hierarchical Tree Structure for DNA Sequence Compression.
  4. Compressed Parameterized Pattern Matching.
  5. Compressing Huffman Models on Large Alphabets.
  6. Computing Convolution on Grammar-Compressed Text.
  7. Effective Variable-Length-to-Fixed-Length Coding via a Re-Pair Algorithm.
  8. Faster Compact Top-k Document Retrieval.
  9. Faster Compressed Top-k Document Retrieval.
  10. From Run Length Encoding to LZ78 and Back Again.
  11. Partition Tree Weighting.
  12. Practical Parallel Lempel-Ziv Factorization.
  13. Quadratic Similarity Queries on Compressed Data.
  14. Random Extraction from Compressed Data - A Practical Study.
  15. Simpler and Faster Lempel Ziv Factorization.
  16. Space-Efficient Construction Algorithm for the Circular Suffix Tree.
  17. Texture Compression.
  18. The Rightmost Equal-Cost Position Problem.
  19. Variable-to-Fixed-Length Encoding for Large Texts Using Re-Pair Algorithm with Shared Dictionaries.

Developments in Language Theory 2013

  1. Abelian Repetitions in Sturmian Words.
  2. On the Number of Abelian Bordered Words.
  3. Repetition Avoidance in Circular Factors.
  4. Suffixes, Conjugates and Lyndon Words.

ESA 2013

  1. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures.
  2. Compressed Cache-Oblivious String B-tree.
  3. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
  4. Encodings for Range Selection and Top-k Queries.
  5. Optimal Color Range Reporting in One Dimension.
  6. Parallel String Sample Sort.
  7. The Encoding Complexity of Two Dimensional Range Minimum Data Structures.
  8. Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform.

ICALP (1) 2013

  1. Combining Binary Search Trees.
  2. Dynamic Compressed Strings with Random Access.
  3. Sparse Suffix Tree Construction in Small Space.
  4. Tree Compression with Top Trees.

ICCS 2013

  1. n-step FM-Index for Faster Pattern Matching.

IEEE BigData 2013

  1. A reconfigurable stream compression hardware based on static symbol-lookup table.

ISAAC 2013

  1. Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching.
  2. Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers.
  3. Less Space: Indexing for Queries with Wildcards.
  4. Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms.
  5. RAM-Efficient External Memory Sorting.
  6. Single and Multiple Consecutive Permutation Motif Search.
  7. Sliding Bloom Filters.
  8. Succinct Data Structures for Representing Equivalence Classes.
  9. Top-k Document Retrieval in Compact Space and Near-Optimal Time.

IWOCA 2013

  1. An Optimal Algorithm for Computing All Subtree Repeats in Trees.
  2. Deciding Representability of Sets of Words of Equal Length in Polynomial Time.
  3. Motif Matching Using Gapped Patterns.
  4. Prefix Table Construction and Conversion.
  5. Suffix Tree of Alignment: An Efficient Index for Similar Data.

Information Theory, Combinatorics, and Search Theory 2013

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

LATA 2013

  1. Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing.
  2. On the Number of Unbordered Factors.

MFCS 2013

  1. Detecting Regularities on Grammar-Compressed Strings.

MICRO 2013

  1. Decoupled compressed cache: exploiting spatial locality for energy-optimized compressed caching.
  2. Linearly compressed pages: a low-complexity, low-latency main memory compression framework.

PPAM (2) 2013

  1. Accelerating String Matching on MIC Architecture for Motif Extraction.

SEA 2013

  1. Lightweight Lempel-Ziv Parsing.
  2. Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences.

SIGIR 2013

  1. Faster and smaller inverted indices with treaps.

SODA 2013

  1. Adaptive and Approximate Orthogonal Range Counting.
  2. Compressed static functions with applications.
  3. Lyndon Words and Short Superstrings.
  4. Near-Optimal Range Reporting Structures for Categorical Data.
  5. Optimal Dynamic Sequence Representations.
  6. The Space Complexity of 2-Dimensional Approximate Range Counting.
  7. Twisted Tabulation Hashing.

SOFSEM 2013

  1. Permuted Pattern Matching on Multi-track Strings.

SPIRE 2013

  1. A Lempel-Ziv Compressed Structure for Document Listing.
  2. Adding Compression and Blended Search to a Compact Two-Level Suffix Array.
  3. Compact Querieable Representations of Raster Data.
  4. Document Listing on Versioned Documents.
  5. Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text.
  6. Faster Top-k Document Retrieval in Optimal Space.
  7. Fully-Online Grammar Compression.
  8. Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs.
  9. Minimal Discriminating Words Problem Revisited.
  10. Order-Preserving Incomplete Suffix Trees and Order-Preserving Indexes.
  11. Space-Efficient Construction of the Burrows-Wheeler Transform.

STACS 2013

  1. Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries.
  2. Finding Pseudo-repetitions.
  3. Parameterized Matching in the Streaming Model.
  4. Recompression: a simple and powerful technique for word equations.

WABI 2013

  1. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications.
  2. Probabilistic Approaches to Alignment with Tandem Repeats.
  3. Using Cascading Bloom Filters to Improve the Memory Usage for de Brujin Graphs.

WADS 2013

  1. Better Space Bounds for Parameterized Range Majority and Minority.
  2. Compressed Persistent Index for Efficient Rank/Select Queries.
  3. Fingerprints in Compressed Strings.
  4. On (Dynamic) Range Minimum Queries in External Memory.

ACM Comput. Surv. 2013

  1. Spaces, Trees, and Colors: The algorithmic landscape of document retrieval on sequences.

ACM J. Exp. Algorithmics 2013

  1. Compressed suffix trees: Efficient computation and storage of LCP-values.

ACM Trans. Algorithms 2013

  1. Optimal Pattern Matching in LZW Compressed Strings.

Algorithmica 2013

  1. Distribution-Aware Compressed Full-Text Indexes.
  2. Sublinear Algorithms for Approximating String Compressibility.

Algorithms 2013

  1. Practical Compressed Suffix Trees.

Algorithms Mol. Biol. 2013

  1. Data compression for sequencing data.

BMC Bioinform. 2013

  1. libgapmis: extending short-read alignments.

Eur. J. Comb. 2013

  1. Computing the Longest Previous Factor.
  2. Minimax trees in linear time with applications.

IEICE Trans. Inf. Syst. 2013

  1. Scalable Detection of Frequent Substrings by Grammar-Based Compression.

Inf. Comput. 2013

  1. Compact binary relation representations with rich functionality.
  2. Range majority in constant time and linear space.

Inf. Process. Manag. 2013

  1. DACs: Bringing direct access to variable-length codes.

Inf. Syst. 2013

  1. Space-efficient representations of rectangle datasets supporting orthogonal range querying.
  2. Succinct nearest neighbor search.

Int. J. Comput. Biol. Drug Des. 2013

  1. Querying highly similar sequences.

Int. J. Comput. Geom. Appl. 2013

  1. External Memory orthogonal Range Reporting with Fast Updates.

J. Discrete Algorithms 2013

  1. Computing the longest common prefix array based on the Burrows-Wheeler transform.
  2. ESP-index: A compressed index based on edit-sensitive parsing.
  3. Fast q-gram mining on SLP compressed strings.
  4. Improved compressed indexes for full-text document retrieval.
  5. Various improvements to text fingerprinting.

SIAM J. Comput. 2013

  1. On the Bit-Complexity of Lempel-Ziv Compression.

Theor. Comput. Sci. 2013

  1. Colored range queries and document retrieval.
  2. Enhanced string covering.
  3. On compressing and indexing repetitive sequences.
  4. On compressing permutations and adaptive sorting.
  5. On the weak prefix-search problem.
  6. Palindrome pattern matching.
  7. Space-efficient data-analysis queries on grids.
  8. Succinct encoding of arbitrary graphs.

AIAI (2) 2012

  1. GapMis-OMP: Pairwise Short-Read Alignment on Multi-core Architectures.

ALENEX 2012

  1. Computing a Consensus of Multilabeled Trees.
  2. Fast Compressed Tries through Path Decompositions.
  3. Solving the Minimum String Cover Problem.
  4. The Complexity of Partial Orders.

ANALCO 2012

  1. The Complexity of Partial Orders.

BCB 2012

  1. ERNE-BS5: aligning BS-treated sequences by multiple hits on a 5-letters alphabet.

BIBM Workshops 2012

  1. Libgapmis: An ultrafast library for short-read single-gap alignment.

COCOON 2012

  1. Multi-pattern Matching with Bidirectional Indexes.

CPM 2012

  1. Compressed String Dictionary Look-Up with Edit Distance One.
  2. Constant-Time Word-Size String Matching.
  3. Cross-Document Pattern Matching.
  4. Simple and Efficient LZW-Compressed Multiple Pattern Matching.
  5. Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.
  6. Time-Space Trade-Offs for Longest Common Extensions.
  7. Wavelet Trees for All.

DCC 2012

  1. A Cuckoo Hashing Variant with Improved Memory Utilization and Insertion Time.
  2. Adaptive Context Tree Weighting.
  3. Compressed Dynamic Binary Relations.
  4. Differentially Encoded Search Trees.
  5. Fast Construction of Nearly-Optimal Prefix Codes without Probability Sorting.
  6. Fast Insertion and Deletion in Compressed Texts.
  7. Gipfeli - High Speed Compression Algorithm.
  8. Mixing Strategies in Data Compression.
  9. Slashing the Time for BWT Inversion.

Developments in Language Theory 2012

  1. Fine and Wilf’s Theorem for k-Abelian Periods.
  2. Pseudoperiodic Words.
  3. Squares in Binary Partial Words.

ECML/PKDD (2) 2012

  1. General Algorithms for Mining Closed Flexible Patterns under Various Equivalence Relations.

ESA 2012

  1. Efficient Communication Protocols for Deciding Edit Distance.
  2. New Lower and Upper Bounds for Representing Sequences.
  3. Succinct Data Structures for Path Queries.
  4. Succinct Posets.

FAW-AAIM 2012

  1. Fast Relative Lempel-Ziv Self-index for Similar Sequences.

FOCS 2012

  1. On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List.

ICALP (1) 2012

  1. CRAM: Compressed Random Access Memory.
  2. De-amortizing Binary Search Trees.
  3. Faster Fully Compressed Pattern Matching by Recompression.
  4. Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima.

ISAAC 2012

  1. A Framework for Succinct Labeled Ordinal Trees over Large Alphabets.
  2. A General Method for Improving Insertion-Based Adaptive Sorting.
  3. An Improved Algorithm for Static 3D Dominance Reporting in the Pointer Machine.
  4. Computing the Longest Common Subsequence of Two Run-Length Encoded Strings.
  5. Efficient Counting of Square Substrings in a Tree.
  6. Finger Search in the Implicit Model.

IWOCA 2012

  1. A Sequential Recursive Implementation of Dead-Zone Single Keyword Pattern Matching.
  2. Border Array for Structural Strings.
  3. Computing a Longest Common Palindromic Subsequence.
  4. Indexing Highly Repetitive Collections.
  5. Range Extremum Queries.

LATA 2012

  1. A Faster Grammar-Based Self-index.
  2. Longest Common Extensions via Fingerprinting.

LATIN 2012

  1. Forbidden Patterns.
  2. Indexed Multi-pattern Matching.

MFCS 2012

  1. Abelian Pattern Avoidance in Partial Words.
  2. Computing Lempel-Ziv Factorization Online.
  3. Fine and Wilf’s Theorem and Pseudo-repetitions.
  4. How to Reconstruct a Genome.

SEA 2012

  1. Branch Mispredictions Don’t Affect Mergesort.
  2. Dynamizing Succinct Tree Representations.
  3. Fast, Small, Simple Rank/Select on Bitmaps.
  4. Space Efficient Modifications to Structator - A Fast Index-Based Search Tool for RNA Sequence-Structure Patterns.
  5. Space-Efficient Top-k Document Retrieval.

SODA 2012

  1. A linear time algorithm for seeds computation.
  2. Fully persistent B-trees.
  3. I/O-efficient data structures for colored range and prefix reporting.
  4. Top-k document retrieval in optimal time and linear space.
  5. Using hashing to solve the dictionary problem.

SOFSEM 2012

  1. Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts.

SPIRE 2012

  1. Compressed Suffix Trees for Repetitive Texts.
  2. Computing Discriminating and Generic Words.
  3. Dual-Sorted Inverted Lists in Practice.
  4. Efficient LZ78 Factorization of Grammar Compressed Text.
  5. Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings.
  6. Grammar Precompression Speeds Up Burrows-Wheeler Compression.
  7. Improved Grammar-Based Compressed Indexes.
  8. Ranked Document Retrieval in (Almost) No Space.
  9. Smaller Self-indexes for Natural Language.
  10. The Position Heap of a Trie.
  11. The Wavelet Matrix.
  12. Variable-Length Codes for Space-Efficient Grammar-Based Compression.

STACS 2012

  1. Linear-Space Data Structures for Range Mode Query in Arrays.
  2. Tying up the loose ends in fully LZW-compressed pattern matching.

STOC 2012

  1. Strict fibonacci heaps.
  2. Tight lower bounds for the online labeling problem.

SWAT 2012

  1. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs.
  2. Linear-Space Data Structures for Range Minority Query in Arrays.
  3. Sorted Range Reporting.
  4. String Indexing for Patterns with Wildcards.

WABI 2012

  1. Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes.
  2. Distributed String Mining for High-Throughput Sequencing Data.
  3. Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom Filter.
  4. Succinct de Bruijn Graphs.

WALCOM 2012

  1. Linear Time Inference of Strings from Cover Arrays Using a Binary Alphabet - (Extended Abstract).

ACM Comput. Surv. 2012

  1. A comparison of index-based lempel-Ziv LZ77 factorization algorithms.

ACM Trans. Algorithms 2012

  1. Succinct ordinal trees based on tree covering.

ACM Trans. Inf. Syst. 2012

  1. Word-based self-indexes for natural language text.

Algorithmica 2012

  1. Fast Arc-Annotated Subsequence Matching in Linear Space.
  2. Lightweight Data Indexing and Compression in External Memory.
  3. Stronger Lempel-Ziv Based Compressed Text Indexing.
  4. Succinct Representation of Labeled Graphs.

Algorithms 2012

  1. A Note on Sequence Prediction over Large Alphabets.
  2. An Online Algorithm for Lightweight Grammar-Based Compression.

Comput. J. 2012

  1. Boosting Text Compression with Word-Based Statistical Encoding.
  2. The String-to-Dictionary Matching Problem.

IEEE ACM Trans. Comput. Biol. Bioinform. 2012

  1. An Efficient Alignment Algorithm for Searching Simple Pseudoknots over Long Genomic Sequence.

IEEE Trans. Knowl. Data Eng. 2012

  1. Practical Efficient String Mining.

IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2012

  1. A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet.

Inf. Comput. 2012

  1. Bidirectional search in a string with wavelet trees and bidirectional matching statistics.

Inf. Process. Lett. 2012

  1. An efficient algorithm to test square-freeness of strings compressed by straight-line programs.
  2. Computing all subtree repeats in ordered trees.

Inf. Process. Manag. 2012

  1. Bidirectional delta files.

Inf. Retr. 2012

  1. Implicit indexing of natural language text by reorganizing bytecodes.

Int. J. Found. Comput. Sci. 2012

  1. Finding Characteristic Substrings from Compressed Texts.
  2. Parallel Algorithms for Mapping Short degenerate and Weighted DNA Sequences to a Reference genome.

J. Comput. Syst. Sci. 2012

  1. Ultra-succinct representation of ordered trees with applications.

J. Discrete Algorithms 2012

  1. An algorithm for mapping short reads to a dynamically changing genomic sequence.
  2. Dictionary-symbolwise flexible parsing.
  3. On left and right seeds of a string.
  4. String matching with alphabet sampling.
  5. Tree template matching in ranked ordered trees by pushdown automata.
  6. Worst-case efficient single and multiple string matching on packed texts in the word-RAM model.

SIAM J. Comput. 2012

  1. An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries.

Softw. Pract. Exp. 2012

  1. Revisiting bounded context block-sorting transformations.

Theor. Comput. Sci. 2012

  1. LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations.
  2. New algorithms on wavelet trees and applications to information retrieval.
  3. String matching with variable length gaps.
  4. Succinct representations of permutations and functions.

Theory Comput. Syst. 2012

  1. Faster Approximate String Matching for Short Patterns.

ALENEX 2011

  1. A Closer Look at the Closest String and Closest Substring Problem.
  2. A Simple Parallel Cartesian Tree Algorithm and its Application to Suffix Tree Construction.
  3. Exact Pattern Matching with Feed-Forward Bloom Filters.
  4. Fast and Lightweight LCP-Array Construction Algorithms.

BCB 2011

  1. Approximate string-matching with a single gap for sequence alignment.
  2. DynMap: mapping short reads to multiple related genomes.

CCP 2011

  1. A Method to Ensure the Confidentiality of the Compressed Data.
  2. An Online Algorithm for Lightweight Grammar-Based Compression.
  3. Asymptotic Optimal Lossless Compression via the CSE Technique.
  4. Backwards Search in Context Bound Text Transformations.
  5. Cache Friendly Burrows-Wheeler Inversion.
  6. Combining Non-stationary Prediction, Optimization and Mixing for Data Compression.
  7. Generalized Witness Sets.
  8. Lempel-Ziv Data Compression on Parallel and Distributed Systems.
  9. Lossless Compression of Hyperspectral Imagery.
  10. Natural Language Compression per Blocks.
  11. Pattern Matching on Sparse Suffix Trees.
  12. Quick Estimation of Data Compression and De-duplication for Large Storage Systems.
  13. Straight-Line Programs: A Practical Test.
  14. Wavelet Trees: From Theory to Practice.

CIAA 2011

  1. Chrobak Normal Form Revisited, with Applications.
  2. Tree Template Matching in Ranked Ordered Trees by Pushdown Automata.

CIKM 2011

  1. Indexes for highly repetitive document collections.

COCOON 2011

  1. On the Right-Seed Array of a String.

CPM 2011

  1. Counting Colours in Compressed Strings.
  2. Efficient Seeds Computation Revisited.
  3. Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts.
  4. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  5. Lempel-Ziv Factorization Revisited.
  6. On the Weak Prefix-Search Problem.
  7. Palindrome Pattern Matching.
  8. Self-indexing Based on LZ77.
  9. Substring Range Reporting.

DCC 2011

  1. Coding of Sets of Words.
  2. Color Image Compression Using a Learned Dictionary of Pairs of Orthonormal Bases.
  3. Compressed Context Modeling for Text Compression.
  4. Compressed Index for Property Matching.
  5. Compressed Property Suffix Trees.
  6. Deplump for Streaming Data.
  7. Error Recovery Method for PPM Compressed Data.
  8. Improving PPM Algorithm Using Dictionaries.
  9. Lossless Data Compression Testbed: ExCom and Prague Corpus.
  10. Mixing Deduplication and Compression on Active Data Sets.
  11. On Performance of Compressed Pattern Matching on VF Codes.
  12. Search and Modification in Compressed Texts.
  13. Sequence Similarity by Gapped LZW.
  14. Sliding Window Update Using Suffix Arrays.
  15. The String-to-Dictionary Matching Problem.
  16. Tree Structure Compression with RePair.

Developments in Language Theory 2011

  1. Abelian Primitive Words.
  2. Avoiding Abelian Powers in Partial Words.
  3. On Highly Repetitive and Power Free Words.
  4. On Prefix Normal Words.

Discovery Science 2011

  1. Scalable Detection of Frequent Substrings by Grammar-Based Compression.

ESA 2011

  1. Alphabet-Independent Compressed Text Indexing.
  2. Distribution-Aware Compressed Full-Text Indexes.
  3. Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic.

FSTTCS 2011

  1. Optimal Packed String Matching.

ICALP (1) 2011

  1. Range Majority in Constant Time and Linear Space.

ISAAC 2011

  1. A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time.
  2. A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria.
  3. Compact Representation of Posets.
  4. Dynamic Range Majority Data Structures.
  5. Dynamic Range Selection in Linear Space.
  6. Encoding 2D Range Maximum Queries.
  7. External Memory Orthogonal Range Reporting with Fast Updates.
  8. Faster Approximate Pattern Matching in Compressed Repetitive Texts.
  9. Path Queries in Weighted Trees.
  10. Range LCP.
  11. Space-Efficient Data-Analysis Queries on Grids.
  12. Succinct Indexes for Circular Patterns.

IWOCA 2011

  1. A Unifying Property for Distribution-Sensitive Priority Queues.
  2. Parameterized Longest Previous Factor.
  3. Periods in Partial Words: An Algorithm.
  4. Two Constant-Factor-Optimal Realizations of Adaptive Heapsort.
  5. p-Suffix Sorting as Arithmetic Coding.

LATA 2011

  1. Improved Alignment Based Algorithm for Multilingual Text Compression.
  2. Unary Pattern Avoidance in Partial Words Dense with Holes.

MFCS 2011

  1. Compressed Word Problems for Inverse Monoids.
  2. On Minimising Automata with Errors.
  3. Periodicity Algorithms for Partial Words.
  4. The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity.

SEA 2011

  1. An Empirical Evaluation of Extendible Arrays.
  2. Compressed String Dictionaries.
  3. Online Dictionary Matching with Variable-Length Gaps.
  4. Practical Compressed Document Retrieval.

SIGIR 2011

  1. Sample selection for dictionary-based corpus compression.

SISAP 2011

  1. Succinct nearest neighbor search.

SODA 2011

  1. Improved Space Bounds for Cache-Oblivious Range Reporting.
  2. Optimal pattern matching in LZW compressed strings.
  3. Ordered and Unordered Top-K Range Reporting in Large Data Sets.
  4. Persistent Predecessor Search and Orthogonal point Location on the Word RAM.
  5. Random Access to grammar-Compressed Strings.
  6. Top-K Color Queries for Document Retrieval.

SOFSEM 2011

  1. An Improved B+ Tree for Flash File Systems.
  2. In-Place Sorting.

SPIRE 2011

  1. Approximate Regular Expression Matching with Multi-strings.
  2. COCA Filters: Co-occurrence Aware Bloom Filters.
  3. Computing All Subtree Repeats in Ordered Ranked Trees.
  4. Computing the Longest Common Prefix Array Based on the Burrows-Wheeler Transform.
  5. ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing.
  6. Fast q-gram Mining on SLP Compressed Strings.
  7. Finding Frequent Elements in Compressed 2D Arrays and Strings.
  8. Fixed Block Compression Boosting in FM-Indexes.
  9. Improved Compressed Indexes for Full-Text Document Retrieval.
  10. Reference Sequence Construction for Relative Compression of Genomes.

STACS 2011

  1. On Minimal Sturmian Partial Words.

STOC 2011

  1. The power of simple tabulation hashing.

WADS 2011

  1. Space Efficient Data Structures for Dynamic Orthogonal Range Counting.

WALCOM 2011

  1. De Bruijn Sequences for the Binary Strings with Maximum Density.
  2. Efficient Top-k Queries for Orthogonal Ranges.

ACM J. Exp. Algorithmics 2011

  1. Theory and practice of monotone minimal perfect hashing.

ACM Trans. Algorithms 2011

  1. Fully compressed suffix trees.
  2. Succinct indexes for strings, binary relations and multilabeled trees.
  3. The tree inclusion problem: In linear space and faster.

Algorithmica 2011

  1. On Optimally Partitioning a Text to Improve Its Compression.

Algorithms 2011

  1. Compressed Matching in Dictionaries.
  2. Edit Distance with Block Deletions.

Bioinform. 2011

  1. Compression of DNA sequence reads in FASTQ format.

Fundam. Informaticae 2011

  1. Self-Indexed Grammar-Based Compression.

Inf. Comput. 2011

  1. Space-efficient construction of Lempel-Ziv compressed text indexes.

Inf. Process. Lett. 2011

  1. Computing Longest Previous non-overlapping Factors.

Inf. Process. Manag. 2011

  1. Improving semistatic compression via phrase-based modeling.

Inf. Syst. 2011

  1. Fully dynamic metric access methods based on hyperplane partitioning.

Int. J. Found. Comput. Sci. 2011

  1. Stronger Quickheaps.

J. Discrete Algorithms 2011

  1. Fast searching in packed strings.
  2. Missing pattern discovery.
  3. Tight bounds for online stable sorting.

Probl. Inf. Transm. 2011

  1. Computing the longest common substring with one mismatch.

Proc. VLDB Endow. 2011

  1. Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections.

Theor. Comput. Sci. 2011

  1. Approximate string matching with stuck address bits.
  2. On-line approximate string matching with bounded errors.
  3. Succinct data structures for Searchable Partial Sums with optimal worst-case performance.
  4. Succinct representation of dynamic trees.
  5. Verifying and enumerating parameterized border arrays.

ALENEX 2010

  1. Succinct Trees in Practice.

Algorithms and Applications 2010

  1. A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches.
  2. Extended Compact Web Graph Representations.
  3. Unified View of Backward Backtracking in Short Read Mapping.

BIBE 2010

  1. Compressed q-Gram Indexing for Highly Repetitive Biological Sequences.

BIBM 2010

  1. An algorithm for mapping short reads to a dynamically changing genomic sequence.

CPM 2010

  1. Approximate All-Pairs Suffix/Prefix Overlaps.
  2. Bidirectional Search in a String with Wavelet Trees.
  3. Parallel and Distributed Compressed Indexes.
  4. Succinct Dictionary Matching with No Slowdown.
  5. Verifying a Parameterized Border Array in O(n1.5) Time.

CSR 2010

  1. Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

DASFAA Workshops 2010

  1. An Improved Algorithm for Extracting Research Communities from Bibliographic Data.

DCC 2010

  1. A New Searchable Variable-to-Variable Compressor.
  2. A Pseudo-Random Number Generator Based on LZSS.
  3. A Similarity Measure Using Smallest Context-Free Grammars.
  4. Advantages of Shared Data Structures for Sequences of Balanced Parentheses.
  5. Bidirectional Delta Files.
  6. Efficient Algorithms for Constructing Optimal Bi-directional Context Sets.
  7. File-Size Preserving LZ Encoding for Reversible Data Embedding.
  8. I/O-Efficient Compressed Text Indexes: From Theory to Practice.
  9. LZ77-Like Compression with Fast Random Access.
  10. Local Modeling for WebGraph Compression.
  11. Lossless Compression of Maps, Charts, and Graphs via Color Separation.
  12. Lossless Data Compression via Substring Enumeration.
  13. Modelling Parallel Texts for Boosting Compression.
  14. Neural Markovian Predictive Compression: An Algorithm for Online Lossless Data Compression.
  15. On Computation of Performance Bounds of Optimal Index Assignment.
  16. Optimum String Match Choices in LZSS.
  17. Xampling: Analog Data Compression.
  18. gFPC: A Self-Tuning Compression Algorithm.

Discovery Science 2010

  1. Sparse Substring Pattern Set Discovery Using Linear Programming Boosting.

ER Workshops 2010

  1. Range Queries over a Compact Representation of Minimum Bounding Rectangles.

ESA (1) 2010

  1. A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings.
  2. Fast Prefix Search in Little Space, with Applications.
  3. Medium-Space Algorithms for Inverse BWT.
  4. On the Huffman and Alphabetic Tree Problem with General Cost Functions.

ESA (2) 2010

  1. Data Structures: Time, I/Os, Entropy, Joules!
  2. On Space Efficient Two Dimensional Range Minimum Data Structures.
  3. Top-k Ranked Document Search in General Text Databases.

FOCS 2010

  1. A Lower Bound for Dynamic Approximate Membership Data Structures.

FUN 2010

  1. A Fun Application of Compact Data Structures to Indexing Geographic Data.

ICALP (1) 2010

  1. Interval Sorting.
  2. Mergeable Dictionaries.
  3. Optimal Trade-Offs for Succinct String Indexes.

ICDE 2010

  1. Fast in-memory XPath search using compressed indexes.

ISAAC (1) 2010

  1. Priority Range Trees.
  2. Should Static Search Trees Ever Be Unbalanced?

ISAAC (2) 2010

  1. Alphabet Partitioning for Compressed Rank/Select and Applications.
  2. Dynamic Range Reporting in External Memory.
  3. Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets.
  4. Entropy-Bounded Representation of Point Grids.
  5. Identifying Approximate Palindromes in Run-Length Encoded Strings.

IWOCA 2010

  1. Dictionary-Symbolwise Flexible Parsing.
  2. Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three.
  3. On the Maximal Sum of Exponents of Runsin a String.
  4. Skip Lift: A Probabilistic Alternative to Red-Black Trees.
  5. Worst Case Efficient Single and Multiple String Matching in the RAM Model.

LATA 2010

  1. A Fast Longest Common Subsequence Algorithm for Similar Strings.
  2. Abelian Square-Free Partial Words.
  3. Avoidable Binary Patterns in Partial Words.
  4. Choosing Word Occurrences for the Smallest Grammar Problem.
  5. Extending Stochastic Context-Free Grammars for an Application in Bioinformatics.
  6. Grammar-Based Compression in a Streaming Model.
  7. Hard Counting Problems for Partial Words.

LATIN 2010

  1. Compact Rich-Functional Binary Relation Representations.
  2. Fast Set Intersection and Two-Patterns Matching.
  3. Lightweight Data Indexing and Compression in External Memory.
  4. Optimal Succinctness for Range Minimum Queries.
  5. Sharp Separation and Applications to Exact and Parameterized Algorithms.

MFCS 2010

  1. Counting Dependent and Independent Strings.

SEA 2010

  1. Bit-Parallel Search Algorithms for Long Patterns.
  2. Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure.
  3. Practical Compressed Suffix Trees.

SODA 2010

  1. Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs.
  2. Cell-Probe Lower Bounds for Succinct Partial Sums.
  3. Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.
  4. Data Structures for Range Minimum Queries in Multidimensional Arrays.
  5. Data-Specific Analysis of String Sorting.
  6. Deletion Without Rebalancing in Balanced Binary Trees.
  7. Fully-Functional Succinct Trees.
  8. Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities.
  9. On the Cell Probe Complexity of Dynamic Membership.
  10. Randomized Shellsort: A Simple Oblivious Sorting Algorithm.
  11. Regular Expression Matching with Multi-Strings and Intervals.

SOFSEM 2010

  1. Dynamic Edit Distance Table under a General Weighted Cost Function.
  2. Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays.
  3. Fast Arc-Annotated Subsequence Matching in Linear Space.
  4. Fast and Compact Prefix Codes.

SPIRE 2010

  1. CST++.
  2. Colored Range Queries and Document Retrieval.
  3. Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes.
  4. Counting and Verifying Maximal Palindromes.
  5. Dual-Sorted Inverted Lists.
  6. Dynamic Z-Fast Tries.
  7. Range Queries over Untangled Chains.
  8. Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval.
  9. String Matching with Variable Length Gaps.
  10. Succinct Representations of Dynamic Strings.

STACS 2010

  1. On Equations over Sets of Integers.

SWAT 2010

  1. An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times.

WABI 2010

  1. Swiftly Computing Center Strings.

WSDM 2010

  1. On compressing the textual web.

ACM J. Exp. Algorithmics 2010

  1. Practical approaches to reduce the space requirement of lempel-ziv-based compressed text indices.

ACM Trans. Algorithms 2010

  1. The compressed permuterm index.

ACM Trans. Embed. Comput. Syst. 2010

  1. Online memory compression for embedded systems.

ACM Trans. Inf. Syst. 2010

  1. Dynamic lightweight text compression.

ACM Trans. Web 2010

  1. Fast and Compact Web Graph Representations.

Algorithmica 2010

  1. On Sorting, Heaps, and Minimum Spanning Trees.

Algorithms Mol. Biol. 2010

  1. Linear-time protein 3-D structure searching with insertions and deletions.

Bioinform. 2010

  1. Efficient construction of an assembly string graph using the FM-index.

Discret. Appl. Math. 2010

  1. Sorting with networks of data structures.

IEICE Trans. Inf. Syst. 2010

  1. Context-Sensitive Grammar Transform: Compression and Pattern Matching.

Inf. Process. Lett. 2010

  1. Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem.

J. Comput. Biol. 2010

  1. Storage and Retrieval of Highly Repetitive Sequence Collections.

J. Discrete Algorithms 2010

  1. The longest common extension problem revisited and applications to approximate string searching.

Math. Comput. Sci. 2010

  1. Fast, Practical Algorithms for Computing All the Repeats in a String.

Theor. Comput. Sci. 2010

  1. Move-to-Front, Distance Coding, and Inversion Frequencies revisited.
  2. On compact representations of All-Pairs-Shortest-Path-Distance matrices.

ACISP 2009

  1. Testing Stream Ciphers by Finding the Longest Substring of a Given Density.

ALENEX 2009

  1. Theory and Practise of Monotone Minimal Perfect Hashing.

CIAA 2009

  1. Implementation and Application of Automata in String Processing.

CPM 2009

  1. Fast Searching in Packed Strings.
  2. Faster and Space-Optimal Edit Distance “1” Dictionary.
  3. On the Value of Multiple Read/Write Streams for Data Compression.
  4. Permuted Longest-Common-Prefix Array.

DASFAA 2009

  1. Reducing Space Requirements for Disk Resident Suffix Arrays.

DCC 2009

  1. Low-Memory Adaptive Prefix Coding.
  2. Suffix Tree Based VF-Coding for Compressed Pattern Matching.

ECDL 2009

  1. A Compressed Self-indexed Representation of XML Documents.

ER Workshops 2009

  1. A New Point Access Method Based on Wavelet Trees.

ESA 2009

  1. On Optimally Partitioning a Text to Improve Its Compression.

Efficient Algorithms 2009

  1. Reflections on Optimal and Nearly Optimal Binary Search Trees.

ICALP (1) 2009

  1. Dynamic Succinct Ordered Trees.
  2. Faster Regular Expression Matching.

IJCBS 2009

  1. Practical and Efficient Algorithms for Degenerate and Weighted Sequences Derived from High Throughput Sequencing Technologies.

ISAAC 2009

  1. Data Structures for Approximate Orthogonal Range Counting.
  2. Deletion without Rebalancing in Multiway Search Trees.
  3. Finding All Approximate Gapped Palindromes.
  4. Interval Stabbing Problems in Small Integer Ranges.
  5. Online Sorted Range Reporting.
  6. Range Non-overlapping Indexing.
  7. Succinct Index for Dynamic Dictionary Matching.

ITW 2009

  1. Constructing optimal whole-bit recycling codes.

IWOCA 2009

  1. LPF Computation Revisited.
  2. Lightweight Parameterized Suffix Array Construction.
  3. Minimax Trees in Linear Time with Applications.
  4. Succinct Representations of Trees.

LATA 2009

  1. A Series of Run-Rich Strings.
  2. Counting Parameterized Border Arrays for a Binary Alphabet.

MFCS 2009

  1. Self-indexed Text Compression Using Straight-Line Programs.

PARCO 2009

  1. A Parallel Algorithm for the Fixed-length Approximate String Matching Problem for High Throughput Sequencing Technologies.

RECOMB 2009

  1. Storage and Retrieval of Individual Genomes.

SEA 2009

  1. An Application of Self-organizing Data Structures to Compression.
  2. Broadword Computing and Fibonacci Code Speed Up Compressed Suffix Arrays.

SISAP 2009

  1. Analyzing Metric Space Indexes: What For?
  2. Dynamic Spatial Approximation Trees for Massive Data.

SODA 2009

  1. Monotone minimal perfect hashing: searching a sorted table with O(1) accesses.

SPIRE 2009

  1. A Compressed Enhanced Suffix Array Supporting Fast String Matching.
  2. A Linear-Time Burrows-Wheeler Transform Using Induced Sorting.
  3. Directly Addressable Variable-Length Codes.
  4. Indexing Variable Length Substrings for Exact and Approximate Matching.
  5. Range Quantile Queries: Another Virtue of Wavelet Trees.
  6. k2-Trees for Compact Web Graph Representation.

STACS 2009

  1. Compressed Representations of Permutations, and Applications.

WABI 2009

  1. Linear-Time Protein 3-D Structure Searching with Insertions and Deletions.

WADS 2009

  1. Worst-Case Optimal Adaptive Prefix Coding.

ACM J. Exp. Algorithmics 2009

  1. Engineering a compressed suffix tree implementation.
  2. Speeding up spatial approximation search in metric spaces.

ACM Trans. Algorithms 2009

  1. Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts.

Algorithms 2009

  1. Approximate String Matching with Compressed Indexes.
  2. Linear-Time Text Compression by Longest-First Substitution.

Bioinform. 2009

  1. A fast hybrid short read fragment assembly algorithm.
  2. SHREC: a short-read error correction method.
  3. Textual data compression in computational biology: a synopsis.

Fundam. Informaticae 2009

  1. A New Algorithm for Building Alphabetic Minimax Trees.

IEICE Trans. Inf. Syst. 2009

  1. A Space-Saving Approximation Algorithm for Grammar-Based Compression.

Inf. Comput. 2009

  1. The myriad virtues of Wavelet Trees.

Inf. Process. Lett. 2009

  1. Parameterized matching on non-linear structures.

Int. J. Comput. Biol. Drug Des. 2009

  1. Algorithms for mapping short degenerate and weighted sequences to a reference genome.

J. ACM 2009

  1. Compressing and indexing labeled trees, with applications.

J. Discrete Algorithms 2009

  1. Matching subsequences in trees.

SIAM J. Comput. 2009

  1. Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.

Theor. Comput. Sci. 2009

  1. Compressed depth sequences.
  2. Efficient algorithms to compute compressed longest common substrings and compressed palindromes.
  3. Efficient construction of maximal and minimal representations of motifs of a string.
  4. Faster entropy-bounded compressed suffix trees.
  5. Rank/select on dynamic compressed sequences and applications.

CPM 2008

  1. An(other) Entropy-Bounded Compressed Suffix Tree.
  2. Dynamic Fully-Compressed Suffix Trees.
  3. Lower Bounds for Succinct Data Structures.
  4. On-Line Approximate String Matching with Bounded Errors.

CSR 2008

  1. Computing Longest Common Substrings Via Suffix Arrays.

DCC 2008

  1. All-Match LZ77 Bit Recycling.
  2. List Update Algorithms for Data Compression.
  3. On Self-Indexing Images - Image Compression with Added Value.
  4. Re-pair Achieves High-Order Entropy.
  5. Word-Based Statistical Compressors as Natural Language Compression Boosters.

DNA 2008

  1. Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints.

Discovery Science 2008

  1. String Kernels Based on Variable-Length-Don’t-Care Patterns.

ESA 2008

  1. An Online Algorithm for Finding the Longest Previous Factors.
  2. Succinct Representations of Arbitrary Graphs.

ISAAC 2008

  1. Space-Time Tradeoffs for Longest-Common-Prefix Array Computation.

LATA 2008

  1. 2-Synchronizing Words.

LATIN 2008

  1. Fully-Compressed Suffix Trees.
  2. Improved Dynamic Rank-Select Entropy-Bound Structures.

SIGIR 2008

  1. Reorganizing compressed text.

SIGMOD Conference 2008

  1. Improving suffix array locality for fast pattern matching on disk.

SOFSEM 2008

  1. Computing Longest Common Substring and All Palindromes from Compressed Strings.

SPIRE 2008

  1. Context-Sensitive Grammar Transform: Compression and Pattern Matching.
  2. Improved Variable-to-Fixed Length Codes.
  3. Indexed Hierarchical Approximate String Matching.
  4. Practical Rank/Select Queries over Arbitrary Sequences.
  5. Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections.
  6. Self-indexing Natural Language.
  7. Speeding Up Pattern Matching by Text Sampling.

SWAT 2008

  1. A Uniform Approach Towards Succinct Representation of Trees.

ACM J. Exp. Algorithmics 2008

  1. Compressed text indexes: From theory to practice.
  2. Implementing the LZ-index: Theory versus practice.

ACM Trans. Algorithms 2008

  1. Dynamic entropy-compressed sequences and full-text indexes.

BMC Bioinform. 2008

  1. RNACompress: Grammar-based compression and informational complexity measurement of RNA secondary structure.

Bioinform. 2008

  1. GENESIS: genome evolution scenarios.

Inf. Process. Lett. 2008

  1. Computing Longest Previous Factor in linear time and applications.
  2. Sorting streamed multisets.

Inf. Retr. 2008

  1. A compressed self-index using a Ziv-Lempel dictionary.

Int. J. Found. Comput. Sci. 2008

  1. Reachability on Suffix Tree Graphs.

Math. Comput. Sci. 2008

  1. Lempel-Ziv Factorization Using Less Time & Space.

Softw. Pract. Exp. 2008

  1. New adaptive compressors for natural language text.

Theor. Comput. Sci. 2008

  1. Fast and compact regular expression matching.
  2. How many runs can a string contain?

ALENEX 2007

  1. Practical Entropy-Compressed Rank/Select Dictionary.

CPM 2007

  1. A Lempel-Ziv Text Index on Secondary Storage.
  2. Compressed Text Indexes with Fast Locate.
  3. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
  4. Fast and Practical Algorithms for Computing All the Runs in a String.
  5. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.
  6. Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.
  7. Space-Efficient Algorithms for Document Retrieval.
  8. Suffix Arrays on Words.

DCC 2007

  1. Bit Recycling with Prefix Codes.
  2. Compressed Delta Encoding for LZSS Encoded Files.
  3. Simple Linear-Time Off-Line Text Compression by Longest-First Substitution.

DNA 2007

  1. Dynamic Neighborhood Searches for Thermodynamically Designing DNA Sequence.

FSTTCS 2007

  1. Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space.

ICALP 2007

  1. Succinct Ordinal Trees Based on Tree Covering.

ICESS 2007

  1. A Unified Compressed Cache Hierarchy Using Simple Frequent Pattern Compression and Partial Cache Line Prefetching.

ISAAC 2007

  1. Succinct Representation of Labeled Graphs.

MDAI 2007

  1. Algorithms for String Pattern Discovery.

MFCS 2007

  1. Space-Conscious Compression.

SIGIR 2007

  1. Compressed permuterm index.

SPIRE 2007

  1. A Fast and Compact Web Graph Representation.
  2. Approximate String Matching with Lempel-Ziv Compressed Indexes.
  3. Implicit Compression Boosting with Applications to Self-indexing.

WEA 2007

  1. Engineering a Compressed Suffix Tree Implementation.

ACM Comput. Surv. 2007

  1. A taxonomy of suffix array construction algorithms.
  2. Compressed full-text indexes.

ACM J. Exp. Algorithmics 2007

  1. An efficient, versatile approach to suffix sorting.

ACM Trans. Algorithms 2007

  1. A data structure for a sequence of string accesses in external memory.
  2. Compressed indexes for dynamic text collections.
  3. Compressed representations of sequences and full-text indexes.

Algorithmica 2007

  1. A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays.

BMC Bioinform. 2007

  1. Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment.

Bioinform. 2007

  1. Compressed suffix tree - a basis for genome-scale sequence analysis.

Inf. Comput. 2007

  1. Rotation and lighting invariant template matching.

Inf. Process. Lett. 2007

  1. Dynamic Shannon coding.

Inf. Process. Manag. 2007

  1. Using structural contexts to compress semistructured text collections.

Inf. Retr. 2007

  1. Lightweight natural language text compression.

J. Assoc. Inf. Sci. Technol. 2007

  1. Lempel-Ziv compression of highly structured documents.

J. Discrete Algorithms 2007

  1. Edit distance with move operations.
  2. Succinct data structures for flexible text retrieval systems.

Theor. Comput. Sci. 2007

  1. A simple storage scheme for strings achieving entropy bounds.
  2. Adaptive searching in succinctly encoded binary relations and tree-structured documents.
  3. Compressed data structures: Dictionaries and data-aware measures.
  4. Fast BWT in small space by blockwise suffix sorting.
  5. Faster suffix sorting.
  6. Rank and select revisited and extended.

Theory Comput. Syst. 2007

  1. Compressed Suffix Trees with Full Functionality.

ALENEX 2006

  1. Optimal Incremental Sorting.

CIAC 2006

  1. Matching Subsequences in Trees.

CPM 2006

  1. Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents.
  2. Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
  3. On-Line Linear-Time Construction of Word Suffix Trees.
  4. Reducing the Space Requirement of LZ-Index.
  5. Statistical Encoding of Succinct Data Structures.

DCC 2006

  1. Compressed Data Structures: Dictionaries and Data-Aware Measures.
  2. Modeling Delta Encoding of Compressed Files.

ESA 2006

  1. The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression.

Ershov Memorial Conference 2006

  1. Improving Semistatic Compression Via Pair-Based Coding.

ICALP (1) 2006

  1. New Algorithms for Regular Expression Matching.
  2. The Myriad Virtues of Wavelet Trees.

IFIP TCS 2006

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

ISAAC 2006

  1. Improving Time and Space Complexity for Compressed Pattern Matching.

ISSAC 2006

  1. Succinct representation of finite abelian groups.

International Conference on Computational Science (1) 2006

  1. An Index Data Structure for Searching in Metric Space Databases.

LATIN 2006

  1. Position-Restricted Substring Searching.

MFCS 2006

  1. A Combinatorial Approach to Collapsing Words.

PODS 2006

  1. Cache-oblivious string B-trees.

SPIRE 2006

  1. A Compressed Self-index Using a Ziv-Lempel Dictionary.
  2. Inverted Files Versus Suffix Arrays for Locating Patterns in Primary Memory.
  3. Sparse Directed Acyclic Word Graphs.

WWW 2006

  1. Compressing and searching XML data via two zips.

Inf. Process. Lett. 2006

  1. Compressing probability distributions.
  2. Large alphabets and incompressibility.

Inf. Process. Manag. 2006

  1. Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts.

Int. J. Found. Comput. Sci. 2006

  1. A Simple Alphabet-independent Fm-index.
  2. Compressed Pattern Matching in Jpeg Images.
  3. Flexible Music Retrieval in Sublinear Time.

SIAM J. Discret. Math. 2006

  1. A New Periodicity Lemma.

Theor. Comput. Sci. 2006

  1. A metric index for approximate string matching.
  2. The binomial transform and the analysis of skip lists.

Theory Comput. Syst. 2006

  1. Insertion Sort is O(n log n).

AMT 2005

  1. A simple extension of queriable compression for XML data.

CONIELECOMP 2005

  1. Approximate Searching on Compressed Text.

CPM 2005

  1. DNA Compression Challenge Revisited: A Dynamic Programming Approach.
  2. Succinct Suffix Arrays Based on Run-Length Encoding.

DCC 2005

  1. Compressed Pattern Matching in JPEG Images.
  2. Real-Time Traversal in Grammar-Based Compressed Files.
  3. The Performance of Linear Time Suffix Sorting Algorithms.

Discovery Science 2005

  1. Practical Algorithms for Pattern Based Linear Regression.

ECDL 2005

  1. Compressing Dynamic Text Collections via Phrase-Based Coding.

ENC 2005

  1. Combining Structural and Textual Contexts for Compressing Semistructured Databases.

ESA 2005

  1. Space Efficient Algorithms for the Burrows-Wheeler Backtransformation.

FCT 2005

  1. Fully Incremental LCS Computation.

FOCS 2005

  1. Structuring labeled trees for optimal succinctness, and beyond.

Federation over the Web 2005

  1. Faster Pattern Matching Algorithm for Arc-Annotated Sequences.

ICALP 2005

  1. The Tree Inclusion Problem: In Optimal Space and Faster.
  2. Towards Optimal Multiple Selection.

ISAAC 2005

  1. Space-Efficient Construction of LZ-Index.

SIGIR 2005

  1. Efficiently decodable and searchable natural language adaptive compression.

SPIRE 2005

  1. Composite Pattern Discovery for PCR Application.

ACM J. Exp. Algorithmics 2005

  1. Increased bit-parallelism for approximate and multiple string matching.

Algorithmica 2005

  1. Bit-Parallel Witnesses and Their Applications to Approximate String Matching.
  2. New Techniques for Regular Expression Searching.

Comput. J. 2005

  1. In Place Differential File Compression.

Discret. Appl. Math. 2005

  1. On-line construction of compact directed acyclic word graphs.

Inf. Process. Lett. 2005

  1. New bounds on D-ary optimal codes.
  2. Restructuring binary search trees revisited.

Inf. Process. Manag. 2005

  1. Pattern matching in Huffman encoded texts.

Int. J. Found. Comput. Sci. 2005

  1. A fully compressed pattern matching algorithm for simple collage systems.

J. ACM 2005

  1. Boosting textual compression in optimal linear time.
  2. Indexing compressed text.

J. Algorithms 2005

  1. Lowest common ancestors in trees and directed acyclic graphs.
  2. Transposition invariant string matching.

J. Discrete Algorithms 2005

  1. A fully linear-time approximation algorithm for grammar-based compression.
  2. Bit-parallel (delta, gamma)-matching and suffix automata.
  3. Indexing text with approximate q-grams.
  4. On minimizing pattern splitting in multi-track string matching.
  5. Practical algorithms for transposition-invariant string-matching.

J. Syst. Softw. 2005

  1. Worst case constant time priority queue.

Pattern Recognit. Lett. 2005

  1. A compact space decomposition for effective metric indexing.

SIAM J. Comput. 2005

  1. Cache-Oblivious B-Trees.
  2. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching.

SIAM J. Discret. Math. 2005

  1. Labeling Schemes for Small Distances in Trees.

Softw. Pract. Exp. 2005

  1. LZgrep: a Boyer-Moore string matching tool for Ziv-Lempel compressed text.

Theor. Comput. Sci. 2005

  1. A survey on tree edit distance and related problems.
  2. Sequential and indexed two-dimensional combinatorial template matching allowing rotations.

CATS 2004

  1. Succinct Data Structures.

CPM 2004

  1. Compressed Compact Suffix Arrays.
  2. Improved Single and Multiple Approximate String Matching.
  3. Real-Time String Matching in Sublinear Space.

Data Compression Conference 2004

  1. Adapting the Knuth-Morris-Pratt Algorithm for Pattern Matching in Huffman Encoded Texts.
  2. Compressed Index for Dynamic Text.
  3. Dynamic Shannon Coding.
  4. Lempel-Ziv Compression of Structured Text.
  5. Merging Prediction by Partial Matching with Structural Contexts Model.

Developments in Language Theory 2004

  1. An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars.

ECCV (2) 2004

  1. From a 2D Shape to a String Structure Using the Symmetry Set.

ESA 2004

  1. Dynamic Shannon Coding.

ICALP 2004

  1. Succinct Representations of Functions.

ISAAC 2004

  1. Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.

LATIN 2004

  1. Rooted Maximum Agreement Supertrees.
  2. Rotation and Lighting Invariant Template Matching.

PVM/MPI 2004

  1. Neighborhood Composition: A Parallelization of Local Search Algorithms.

SPIRE 2004

  1. A Space-Saving Linear-Time Algorithm for Grammar-Based Compression.
  2. An Alphabet-Friendly FM-Index.
  3. First Huffman, Then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index.
  4. Simple, Fast, and Efficient Natural Language Adaptive Compression..

Theory Is Forever 2004

  1. On NFA Reductions.

WABI 2004

  1. Finding Missing Patterns.
  2. Finding Optimal Pairs of Patterns.

WEA 2004

  1. Increased Bit-Parallelism for Approximate String Matching.

WMPI 2004

  1. A compressed memory hierarchy using an indirect index cache.

ACM J. Exp. Algorithmics 2004

  1. Average-optimal single and multiple approximate string matching.

Algorithmica 2004

  1. Engineering a Lightweight Suffix Array Construction Algorithm.

Discret. Appl. Math. 2004

  1. Fun-Sort–or the chaos of unordered binary search.

J. Comput. Syst. Sci. 2004

  1. Implicit B-trees: a new data structure for the dictionary problem.

J. Discrete Algorithms 2004

  1. Compact directed acyclic word graphs for a sliding window.
  2. Indexing text using the Ziv-Lempel trie.
  3. Practical and flexible pattern matching over Ziv-Lempel compressed text.

Softw. Pract. Exp. 2004

  1. A simple and fast DNA compressor.

Theor. Comput. Sci. 2004

  1. Average complexity of exact and approximate multiple string matching.
  2. Ternary directed acyclic word graphs.
  3. The Level Ancestor Problem simplified.

CIAA 2003

  1. Ternary Directed Acyclic Word Graphs.

CPM 2003

  1. A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression.
  2. Average-Optimal Multiple Approximate String Matching.
  3. On Minimizing Pattern Splitting in Multi-track String Matching.

DCC 2003

  1. In-Place Differential File Compression.

ECIR 2003

  1. An Efficient Compression Code for Text Databases.
  2. Compressing Semistructured Text Databases.

ENC 2003

  1. Current Challenges in Textual Databases.

Euro-Par 2003

  1. Compression in Data Caches with Compressible Field Isolation for Recursive Data Structures.
  2. Suffix Arrays in Parallel.

FOCS 2003

  1. Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.

ICALP 2003

  1. Succinct Representations of Permutations.

ISAAC 2003

  1. Constructing Compressed Suffix Arrays with Large Alphabets.
  2. New Ways to Construct Binary Search Trees.
  3. Succinct Data Structures for Searchable Partial Sums.

ISLPED 2003

  1. Non redundant data cache.

MFCS 2003

  1. Inferring Strings from Graphs and Arrays.

SPIRE 2003

  1. (S, C)-Dense Coding: An Optimized Compression Code for Natural Language Text Databases.
  2. A Bit-Parallel Suffix Automation Approach for (delta, gamma)-Matching in Music Retrieval.
  3. A Practical Index for Genome Searching.
  4. Distributed Query Processing Using Suffix Arrays.
  5. Flexible and Efficient Bit-Parallel Techniques for Transposition Invariant Approximate Matching in Music Retrieval.
  6. Large Edit Distance with Multiple Block Operations.
  7. Linear-Time Off-Line Text Compression by Longest-First Substitution.
  8. Memory-Adaptive Dynamic Spatial Approximation Trees.
  9. SCM: Structural Contexts Model for Improving Compression in Semistructured Text Databases.

STACS 2003

  1. Algorithms for Transposition Invariant String Matching.

Algorithmica 2003

  1. Approximate Matching of Run-Length Compressed Strings.

IEEE Trans. Inf. Theory 2003

  1. Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models.

J. Algorithms 2003

  1. New text indexing functionalities of the compressed suffix arrays.

J. Comput. Biol. 2003

  1. Fast and Simple Character Classes and Bounded Gaps Pattern Matching, with Applications to Protein Searching.

J. Comput. Syst. Sci. 2003

  1. Two-dimensional substring indexing.

J. Discrete Algorithms 2003

  1. Approximate string matching on Ziv-Lempel compressed text.
  2. Regular expression searching on compressed text.

Theor. Comput. Sci. 2003

  1. Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
  2. Collage system: a unifying framework for compressed pattern matching.
  3. Optimal binary search trees with costs depending on the access paths.

CC 2002

  1. Data Compression Transformations for Dynamically Allocated Data Structures.

COCOON 2002

  1. A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays.

CPM 2002

  1. Edit Distance with Move Operations.
  2. Faster Bit-Parallel Approximate String Matching.
  3. Local Similarity Based Point-Pattern Matching.
  4. Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations.
  5. Space-Economical Algorithms for Finding Maximal Unique Matches.
  6. The Minimum DAWG for All Suffixes of a String and Its Applications.

DCC 2002

  1. Searching in Compressed Dictionaries.

Discovery Science 2002

  1. Discovering Best Variable-Length-Don’t-Care Patterns.

ESA 2002

  1. Engineering a Lightweight Suffix Array Construction Algorithm.
  2. Two Simplified Algorithms for Maintaining Order in a List.

FOCS 2002

  1. Implicit B-Trees: New Results for the Dictionary Problem.
  2. Static Optimality Theorem for External Memory String Access.

ISAAC 2002

  1. Space-Efficient Data Structures for Flexible Text Retrieval Systems.

LATIN 2002

  1. A Metric Index for Approximate String Matching.
  2. The Level Ancestor Problem Simplified.

MFCS 2002

  1. Space-Economical Construction of Index Structures for All Suffixes of a String.

Progress in Discovery Science 2002

  1. Data Compression Method Combining Properties of PPM and CTW.
  2. Efficient Data Mining from Large Text Databases.
  3. Finding Best Patterns Practically.

SCCC 2002

  1. Improved Antidictionary Based Compression.

SPIRE 2002

  1. Compact Directed Acyclic Word Graphs for a Sliding Window.
  2. Fully Dynamic Spatial Approximation Trees.
  3. Indexing Text Using the Ziv-Lempel Trie.
  4. Probabilistic Proximity Searching Algorithms Based on Compact Partitions.
  5. Processing Text Files as Is: Pattern Matching over Compressed Texts, Multi-byte Character Texts, and Semi-structured Texts.
  6. t-Spanners as a Data Structure for Metric Space Searching.

Algorithmica 2002

  1. A Theoretical and Experimental Study on the Construction of Suffix Arrays in External Memory.

Bioinform. 2002

  1. DNACompress: fast and effective DNA sequence compression.

Random Struct. Algorithms 2002

  1. New and faster filters for multiple approximate string matching.

ALENEX 2001

  1. Experiments on Adaptive Set Intersections for Text Retrieval Systems.
  2. Trade Off Between Compression and Search Times in Compact Suffix Array.

CPM 2001

  1. Approximate Matching of Run-Length Compressed Strings.
  2. Efficient Discovery of Proximity Patterns with Suffix Arrays.
  3. Multiple Pattern Matching Algorithms on Collage System.
  4. On-Line Construction of Compact Directed Acyclic Word Graphs.
  5. Regular Expression Searching over Ziv-Lempel Compressed Text.

Data Compression Conference 2001

  1. Faster Approximate String Matching over Compressed Text.
  2. Pattern Matching in Huffman Encoded Texts.
  3. Space-Time Tradeoffs in the Inverse B-W Transform.

Discovery Science 2001

  1. A Practical Algorithm to Find the Best Episode Patterns.

PODS 2001

  1. Two-dimensional Substring Indexing.

RECOMB 2001

  1. Fast and simple character classes and bounded gaps pattern matching, with application to protein searching.

SPIRE 2001

  1. On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs.
  2. Using Edit Distance in Point-Pattern Matching.

ACM Comput. Surv. 2001

  1. A guided tour to approximate string matching.
  2. Searching in metric spaces.

Algorithmica 2001

  1. Improving an Algorithm for Approximate Pattern Matching.

Inf. Sci. 2001

  1. An experimental study of a compressed index.

J. ACM 2001

  1. An analysis of the Burrows-Wheeler transform.

J. Algorithms 2001

  1. Space Efficient Suffix Trees.

SIAM J. Comput. 2001

  1. Succinct Representation of Balanced Parentheses and Static Trees.

Softw. Pract. Exp. 2001

  1. NR-grep: a fast and flexible pattern-matching tool.

CIAC 2000

  1. Speeding Up Pattern Matching by Text Compression.

CPM 2000

  1. A Boyer-Moore Type Algorithm for Compressed Pattern Matching.
  2. Approximate String Matching over Ziv-Lempel Compressed Text.
  3. Boyer-Moore String Matching over Ziv-Lempel Compressed Text.
  4. Compact Suffix Array.
  5. Indexing Text with Approximate q-Grams.

Data Compression Conference 2000

  1. A New Compression Method for Compressed Matching.
  2. Implementing the Context Tree Weighting Method for Text Compression.

Discovery Science 2000

  1. A Practical Algorithm to Find the Best Subsequence Patterns.

ESA 2000

  1. On the Competitiveness of Linear Search.

FOCS 2000

  1. Cache-Oblivious B-Trees.
  2. Opportunistic Data Structures with Applications.

IFIP TCS 2000

  1. An Index for Two Dimensional String Matching Allowing Rotations.

ISAAC 2000

  1. Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array.

LATIN 2000

  1. The LCA Problem Revisited.

RECOMB 2000

  1. A compression algorithm for DNA sequences and its applications in genome comparison.

Recent Advances in Intrusion Detection 2000

  1. A Pattern Matching Based Filter for Audit Reduction and Fast Detection of Potential Intrusions.

SPIRE 2000

  1. Bit-Parallel Approach to Approximate String Matching in Compressed Texts.
  2. Fast Multipattern Search Algorithms for Intrusion Detection.
  3. Fully Compressed Pattern Matching Algorithm for Balanced Straight-Line Programs.
  4. Online Construction of Subsequence Automata for Multiple Texts.

ACM J. Exp. Algorithmics 2000

  1. An Experimental Study of Priority Queues in External Memory.
  2. Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata.

ACM Trans. Inf. Syst. 2000

  1. Fast and flexible word searching on compressed text.

Algorithmica 2000

  1. Binary Searching with Nonuniform Costs and Its Application to Text Retrieval.

Computer 2000

  1. Compression: A Key for Next-Generation Text Retrieval Systems.

Inf. Retr. 2000

  1. Adding Compression to Block Addressing Inverted Indexes.

J. ACM 2000

  1. On the sorting-complexity of suffix tree construction.

Proc. IEEE 2000

  1. Off-line compression by greedy textual substitution.
  2. Off-line dictionary-based compression.

Theor. Comput. Sci. 2000

  1. Improved approximate pattern matching on hypertext.

CPM 1999

  1. A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text.
  2. A New Indexing Method for Approximate String Matching.
  3. Fast Multi-dimensional Approximate Pattern Matching.
  4. Shift-And Approach to Pattern Matching in LZW Compressed Text.

Data Compression Conference 1999

  1. A Modified Burrows-Wheeler Transformation for Case-Insensitive Search with Application to Suffix Array Compression.
  2. Offline Dictionary-Based Compression.

ESA 1999

  1. Efficient Algorithms foe On-Line Symbol Ranking Compression.
  2. On Constructing Suffix Arrays in External Memory.

MFCS 1999

  1. Invited Lecture: The Burrows-Wheeler Transform: Theory and Practice.

RECOMB 1999

  1. q-gram based database searching using a suffix array (QUASAR).

SPIRE/CRIWG 1999

  1. A Fast Distributed Suffix Array Generation Algorithm.
  2. A Unifying Framework for Compressed Pattern Matching.

STOC 1999

  1. Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.

WADS 1999

  1. Representing Trees of Higer Degree.
  2. Resizable Arrays in Optimal Time and Space.

WAE 1999

  1. An Experimental Study of Priority Queues in External Memory.
  2. Fast Regular Expression Search.

Algorithmica 1999

  1. Faster Approximate String Matching.
  2. String Search in Coarse-Grained Parallel Computers.
  3. Suffix Trees on Words.

Inf. Process. Lett. 1999

  1. Very Fast and Simple Approximate String Matching.

J. ACM 1999

  1. The String B-tree: A New Data Structure for String Search in External Memory and Its Applications.

J. Algorithms 1999

  1. Improved Dynamic Text Indexing.

Parallel Process. Lett. 1999

  1. An EREW PRAM Algorithm for Updating Minimum Spanning Trees.

SIAM J. Comput. 1999

  1. Compression of Low Entropy Strings with Lempel-Ziv Algorithms.
  2. Membership in Constant Time and Almost-Minimum Space.

Theory Comput. Syst. 1999

  1. Bounding the Expected Length of Longest Common Subsequences and Forests.

CPM 1998

  1. A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching.

Data Compression Conference 1998

  1. A Fast Algorithms for Making Suffix Arrays and for Burrows-Wheeler Transformation.
  2. Multiple Pattern Matching in LZW Compressed Text.
  3. On Optimality of Varients of the Block Sorting Compression.
  4. Some Theory and Practice of Greedy Off-Line Textual Substitution.
  5. The Context Trees of Block Sorting Compression.

FOCS 1998

  1. Overcoming the Memory Bottleneck in Suffix Tree Construction.

FSTTCS 1998

  1. Space Efficient Suffix Trees.

LATIN 1998

  1. Fast Two-Dimensional Approximate Pattern Matching
  2. Improved Approximate Pattern Matching on Hypertext.

SIGIR 1998

  1. Fast Searching on Compressed Text Allowing Errors.

SPIRE 1998

  1. A Model and a Visual Query Language for Structured Text.
  2. Direct Pattern Matching on Compressed Text.
  3. Fast Approximate String Matching in a Dictionary.

CLEI Electron. J. 1998

  1. A Practical q -Gram Index for Text Retrieval Allowing Errors.

Inf. Comput. 1998

  1. Dynamic Dictionary Matching in External Memory.

SIAM J. Comput. 1998

  1. Optimal On-Line Search and Sublinear Time Update in String Matching.

Theor. Comput. Sci. 1998

  1. On Updating Suffix Tree Labels.

CIAC 1997

  1. A Note on Updating Suffix Tree Labels.

CIKM 1997

  1. Block Addressing Indices for Approximate Text Retrieval.

CPM 1997

  1. Distributed Generation of Suffix Arrays.

FOCS 1997

  1. Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs.

SEQUENCES 1997

  1. Compression of low entropy strings with Lempel-Ziv algorithms.
  2. Multi-string search in BSP.
  3. Sequence sorting in secondary storage.
  4. Text compression using recency rank with context and relation to context sorting, block sorting and PPM*.

STOC 1997

  1. On Sorting Strings in External Memory (Extended Abstract).

WADS 1997

  1. Multiple Approximate String Matching.
  2. Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds.

ACM Trans. Inf. Syst. 1997

  1. Proximal Nodes: A Model to Query Document Databases by Content and Structure.

IEEE Trans. Inf. Theory 1997

  1. On the average redundancy rate of the Lempel-Ziv code.

IEEE Trans. Knowl. Data Eng. 1997

  1. Text Compression for Dynamic Document Databases.

J. Algorithms 1997

  1. Dynamic Text Indexing under String Updates.

CPM 1996

  1. A Faster Algorithm for Approximate String Matching.
  2. Suffix Trees on Words.

Data Compression Conference 1996

  1. Extended Application of Suffix Trees to Data Compression.

Algorithmica 1996

  1. Fast Stable In-Place Sorting with O (n) Data Moves.

SIGMOD Rec. 1996

  1. Integrating Contents and Structure in Text Retrieval.

Theor. Comput. Sci. 1996

  1. Selection from Read-Only Memory and Sorting with Minimum Data Movement.

ESA 1995

  1. Optimized Binary Search and Text Retrieval.
  2. The Binomial Transform and its Application to the Analysis of Skip Lists.

IWMM 1995

  1. Dynamic Storage Allocation: A Survey and Critical Review

SIGIR 1995

  1. A Language for Queries on Structure and Contents of Textual.

SIAM J. Comput. 1995

  1. Permuting in Place.

ESA 1994

  1. Membership in Constant Time and Minimum Space.

Inf. Process. Manag. 1994

  1. A New Challenge for Compression Algorithms: Genetic Sequences.

Proc. IEEE 1994

  1. The sliding-window Lempel-Ziv algorithm is asymptotically optimal.

FSTTCS 1992

  1. Selection from Read-Only Memory and Sorting with Optimum Data Movement.

BIT 1992

  1. Average Search and Update Costs in Skip Lists.

J. Algorithms 1992

  1. Sorting with Minimum Data Movement.

FSTTCS 1991

  1. Fast Sorting In-Place Sorting with O(n) Data.

WADS 1991

  1. A Case Study in Comparison Based Complexity: Finding the Nearest Value(s).
  2. Sorting Multisets and Vectors In-Place.

Inf. Comput. 1991

  1. Fringe Analysis for Extquick: An in Situ Distributive External Sorting Algorithm

J. Comput. Syst. Sci. 1991

  1. An Implicit Data Structure for Searching a Multikey Table in Logarithmic Time.

FOCS 1990

  1. Permuting

SWAT 1990

  1. Analysis of the Expected Search Cost in Skip Lists.

Algorithmica 1990

  1. Analysis of the Standard Deletion Algorithms in Exact Fit Domain Binary Search Trees.

BIT 1990

  1. Stable in Situ Sorting and Minimum Data Movement.

Comput. J. 1989

  1. Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations.

SWAT 1988

  1. An Implicit Binomial Queue with Constant Insertion Time.

SIAM J. Comput. 1988

  1. A Functional Approach to Data Structures and Its Use in Multidimensional Searching.

STOC 1987

  1. Searching a Two Key Table Under a Single Key

BIT 1987

  1. Searchability in Merging and Implicit Data Structures.

MFCS 1986

  1. Developing Implicit Data Structures.

SCG 1986

  1. Linear Data Structures for Two Types of Range Search.

Algorithmica 1986

  1. Fractional Cascading: I. A Data Structuring Technique.
  2. Fractional Cascading: II. Applications.

J. Comput. Syst. Sci. 1986

  1. An Implicit Data Structure Supporting Insertion, Deletion, and Search in O(log² n) Time.

SIAM J. Comput. 1986

  1. Filtering Search: A New Approach to Query-Answering.
  2. Heaps on Heaps.

FOCS 1985

  1. Robin Hood Hashing (Preliminary Report)

J. Algorithms 1985

  1. The Analysis of a Fringe Heuristic for Binary Search Trees.

PODS 1983

  1. A Discipline for Robustness or Storage Reduction in Binary Search Trees.

Comput. Vis. Graph. Image Process. 1983

  1. Direct dynamic structures for some line segment problems.

ICALP 1982

  1. Heaps on Heaps.

J. ACM 1982

  1. Data compression via textual substitution.

STOC 1981

  1. A Linear Probing Sort and its Analysis (Preliminary Draft)

SIAM J. Comput. 1981

  1. Exegesis of Self-Organizing Linear Search.

J. Comput. Syst. Sci. 1980

  1. Implicit Data Structures for Fast Search and Update.

FOCS 1979

  1. Toward Self-Organizing Linear Search (Preliminary Draught)

STOC 1979

  1. Implicit Data Structures (Preliminary Draft)

SIAM J. Comput. 1979

  1. Efficient Ordering of Hash Tables.

FOCS 1978

  1. Selection and Sorting with Limited Storage

J. ACM 1978

  1. Self-Organizing Binary Search Trees.

STOC 1977

  1. The Analysis of an Improved Hashing Technique

FOCS 1976

  1. Self-Organizing Binary Search Trees

SIAM J. Comput. 1976

  1. Sorting and Searching in Multisets.
This site is open source. Improve this page.