StringologyTimes

ISAAC for Stringologist

ISAAC 2022

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

ISAAC 2021

  1. Algorithms and Complexity on Indexing Elastic Founder Graphs.
  2. Streaming Pattern Matching (Invited Talk).
  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. Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space.

ISAAC 2020

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

ISAAC 2019

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

ISAAC 2018

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

ISAAC 2017

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

ISAAC 2016

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

ISAAC 2015

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

ISAAC 2014

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

ISAAC 2013

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

ISAAC 2012

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

ISAAC 2011

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

ISAAC 2009

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

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. Succinct Data Structures for Searchable Partial Sums.
  2. New Ways to Construct Binary Search Trees.
  3. Constructing Compressed Suffix Arrays with Large Alphabets.

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.