StringologyTimes

ESA for Stringologist

ESA 2022

  1. An Improved Algorithm for Finding the Shortest Synchronizing Words.
  2. Simple Worst-Case Optimal Adaptive Prefix-Free Coding.
  3. Lyndon Arrays Simplified.
  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. Approximate Circular Pattern Matching.
  8. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.

ESA 2021

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

ESA 2020

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

ESA 2019

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

ESA 2018

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

ESA 2017

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

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. Approximating LZ77 via Small-Space Multiple-Pattern Matching.
  3. Access, Rank, and Select in Grammar-compressed Strings.
  4. Dictionary Matching in a Stream.

ESA 2014

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

ESA 2013

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

ESA 2012

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

ESA 2011

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

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.