StringologyTimes

ISAAC for Stringologist

ISAAC 2022

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

ISAAC 2021

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

ISAAC 2020

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

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.

ISAAC 2018

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

ISAAC 2017

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

ISAAC 2016

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

ISAAC 2015

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

ISAAC 2014

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

ISAAC 2013

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

ISAAC 2012

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

ISAAC 2011

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

ISAAC 2009

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

ISAAC 2008

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

ISAAC 2007

  1. Succinct Representation of Labeled Graphs.

ISAAC 2006

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

ISAAC 2005

  1. Space-Efficient Construction of LZ-Index.

ISAAC 2004

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

ISAAC 2003

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

ISAAC 2002

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

ISAAC 2000

  1. Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array.
This site is open source. Improve this page.