StringologyTimes

ISAAC for Stringologist

ISAAC 2022

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

ISAAC 2021

  1. Streaming Pattern Matching (Invited Talk).
  2. Pattern Masking for Dictionary Matching.
  3. Repetition- and Linearity-Aware Rank/Select Dictionaries.
  4. Algorithms and Complexity on Indexing Elastic Founder Graphs.
  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. Enumerating Range Modes.
  2. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees.
  3. Update Query Time Trade-Off for Dynamic Suffix Arrays.
  4. Random Access in Persistent Strings.
  5. Efficient Labeling for Reachability in Directed Acyclic Graphs.
  6. A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem.
  7. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs.
  8. A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.

ISAAC 2019

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

ISAAC 2018

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

ISAAC 2017

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

ISAAC 2016

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

ISAAC 2015

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

ISAAC 2014

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

ISAAC 2013

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

ISAAC 2012

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

ISAAC 2011

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

ISAAC 2009

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

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. Succinct Data Structures for Searchable Partial Sums.
  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.