StringologyTimes

ESA for Stringologist

ESA 2022

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

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. Faster Algorithms for Longest Common Substring.
  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. Space Efficient Two-Dimensional Orthogonal Colored Range Counting.
  9. Lyndon Words Accelerate Suffix Sorting.

ESA 2020

  1. New Binary Search Tree Bounds via Geometric Inversions.
  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. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing.
  6. Efficient Computation of 2-Covers of a String.
  7. The Number of Repetitions in 2D-Strings.

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

ESA 2017

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

ESA 2016

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

ESA 2015

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

ESA 2014

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

ESA 2013

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

ESA 2012

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

ESA 2011

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

ESA 2009

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

ESA 2008

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

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. Engineering a Lightweight Suffix Array Construction Algorithm.
  2. Two Simplified Algorithms for Maintaining Order in a List.

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. The Binomial Transform and its Application to the Analysis of Skip Lists.
  2. Optimized Binary Search and Text Retrieval.

ESA 1994

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