StringologyTimes

ESA for Stringologist

ESA 2022

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

ESA 2021

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

ESA 2020

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

ESA 2019

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

ESA 2018

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

ESA 2017

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

ESA 2016

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

ESA 2015

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

ESA 2014

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

ESA 2013

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

ESA 2012

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

ESA 2011

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

ESA 2009

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

ESA 2008

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

ESA 2006

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

ESA 2005

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

ESA 2004

  1. Dynamic Shannon Coding.

ESA 2002

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

ESA 2000

  1. On the Competitiveness of Linear Search.

ESA 1999

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

ESA 1995

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

ESA 1994

  1. Membership in Constant Time and Minimum Space.
This site is open source. Improve this page.